Finding counterexamples from parsing conflicts
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 03, 2015
- Source ID
- 10.1145/2813885.2737961
Entities
People
- Andrew C. Myers
- Chinawat Isradisaikul
Organizations
- Cornell University
- National Science Foundation
- Office of Naval Research