Added support for counterexamples

bugengine commented 2 years ago

This change adds support for showing counterexamples when finding a Shift/Reduce or a Reduce/Reduce conflict. The feature does not change the algorithm used to construct the table, but stores additional information during the construction of the table which enables SLY to backtrack to one (at least) pair of LR0 items from which the conflict originated, keeping track of the expansion along the way.

4 examples are provided:

the full C 2x grammar (not disambiguated) shows a few conflicts hwith counterexamples
a grammar showing the dangling else conflict
a grammar implementing a subset of C that shows a conflict between a cast expression and a declaration
a copy of the CALC example where the precedence rules have been commented out, which causes many conflicts (and counterexamples) to appear.

I am very happy with the feature itself, I could use the output to clearly analyze conflicts in complicated grammar and the cost at table construction is not excessive (provided the conflict count is reasonable, i.e. below 100). There is no overhead at parse time since the debug information is discarded after the table is constructed. I am not completely satisfied with the implementation though and I will gladly ask for reviews and corrections.

jpsnyder commented 2 years ago

This looks cool. It would be helpful to have this for debugging complex grammars. I've found myself needing to manually add print statements into sly to help figure out conflicts, so this would be a welcome addition.

dabeaz commented 2 years ago

Just a quick note that I haven't forgotten about this and will be looking at it. I just don't have time to work on SLY all of the time with kids, pandemic, teaching, etc. Also, I had been thinking about a few SLY organizational changes as well so I want to see how it might interface with that.

bugengine commented 2 years ago

If you want to see it in action, I have used this tool to list and document all ambiguities of the C++ grammar as specified in the C++ standard. The documentation I produced is at https://motor-engine.readthedocs.io/en/latest/guides/build/tools/cxx.html

The counterexample I implemented for my own parser generator (still in progress) is almost identical to the one I posted here. I used counterexamples to document as well as I could the origin of the conflicts of the C++ grammar (expand the code examples by clicking on the "show" button to show the counterexamples)

bugengine commented 2 years ago

@dabeaz I have a daytime job and 3 kids, one of them has corona since today, I have no problem waiting :) I am available when you're ready and I will merge any conflict if necessary. I've used Sly/Ply for quite a few years now and it's my pleasure to help back if I can. As long as there's no divergence between our repos, it shouldn't be a problem for people to try this out.

dabeaz / sly

Added support for counterexamples #89