search

lark-parser / lark

Lark is a parsing toolkit for Python, built with a focus on ergonomics, performance and modularity.
MIT License
4.92k stars 417 forks source link

Generate counter-examples for conflicts in LALR parsing #1449

Open BenzoX opened 3 months ago

BenzoX commented 3 months ago

Suggestion Recent versions of Bison are able to generate counter-examples witnessing shift/reduce and reduce/reduce conflicts, which helps fine-tuning the grammar so that it belongs to LR(1). Would it be feasible to add such a feature to Lark?

Describe alternatives you've considered The output of Lark is already quite informative, since it mentions the conflicting terminal and rules. Being able to generate counter-examples would make it one step further, and doesn't seem out of reach since Lark has already most of the information.

Additional context I am a teaching assistant for a compiling course at an undergraduate level. We are for now teaching the course with Lex/Yacc but I am experimenting with Lark to have a more modern tool for parsing, and to allow the students to use Python instead of C, which would considerably ease the code generation part: for now, they spend a lot of time struggling with the data structure for the symbol table; this is relevant from the algorithms and data structure point of view but comes in the way of understanding the big picture. SLR/LR/LALR grammars are a key aspect of the course as it is now, because it is also an occasion to study formal languages and pushdown automata, so I'd rather have an LALR parser, even if I for my personal use I am very happy with the Earley one. I am also very happy with Lark in general, congratulations for the tremendous work!

erezsh commented 3 months ago

I'm glad to hear you find Lark to be useful, and especially as a teaching device!

Producing counter-examples for shift/reduce conflicts would be a great feature in Lark. But I must say it's not obvious to me, what is the best way to do so. Perhaps you could shed some light on this?

MegaIng commented 3 months ago

The docs for bison link to this paper:

[Isradisaikul 2015] Chinawat Isradisaikul, Andrew Myers, Finding Counterexamples from Parsing Conflicts, in Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’15), ACM, pp. 555–564. https://www.cs.cornell.edu/andru/papers/cupex/cupex.pdf

BenzoX commented 3 months ago

Thanks MegaIng, you made me realise I forgot to include the link to the docs in my initial comment. I also saw this paper, I'd start there! The paper comes with a Java implementation for CUP: https://github.com/polyglot-compiler/polyglot/tree/master/tools/java_cup.