Writing a parser remains remarkably painful. Automatic parser generators offer a powerful and systematic way to parse complex grammars, but debugging conflicts in grammars can be time-consuming even for experienced language designers. Better tools for diagnosing parsing conflicts will alleviate this difficulty. This paper proposes a practical algorithm that generates compact, helpful counterexamples for LALR grammars. For each parsing conflict in a grammar, a counterexample demonstrating the conflict is constructed. When the grammar in question is ambiguous, the algorithm usually generates a compact counterexample illustrating the ambiguity. This algorithm has been implemented as an extension to the CUP parser generator. The results from applying this implementation to a diverse collection of faulty grammars show that the algorithm is practical, effective, and suitable for inclusion in other LALR parser generators.
Wed 17 JunDisplayed time zone: Tijuana, Baja California change
16:00 - 17:40 | |||
16:00 25mTalk | Zero-Overhead Metaprogramming: Reflection and Metaobject Protocols Fast and without Compromises Research Papers Stefan Marr Inria, France, Chris Seaton Oracle Labs / University of Manchester, Stéphane Ducasse INRIA Lille Media Attached | ||
16:25 25mTalk | Finding Counterexamples from Parsing Conflicts Research Papers Media Attached | ||
16:50 25mTalk | Interactive Parser Synthesis by Example Research Papers Alan Leung University of California, San Diego, John Sarracino University of California, San Diego, Sorin Lerner University of California, San Diego Media Attached | ||
17:15 25mTalk | A Simpler, Safer Programming and Execution Model for Intermittent Systems Research Papers Media Attached |