Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Generate counter-examples for conflicts in LALR parsing #1449

Open
BenzoX opened this issue Aug 16, 2024 · 3 comments
Open

Generate counter-examples for conflicts in LALR parsing #1449

BenzoX opened this issue Aug 16, 2024 · 3 comments

Comments

@BenzoX
Copy link

BenzoX commented Aug 16, 2024

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
Copy link
Member

erezsh commented Aug 16, 2024

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
Copy link
Member

MegaIng commented Aug 16, 2024

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
Copy link
Author

BenzoX commented Aug 16, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants