Generating Fast, Error Recovering Parsers
Abstract
A parser is the part of a compiler that recognizes the structure of the input language. It should be time and space efficient and user friendly that is, present clear and concise diagnostics for syntax errors. A parser should also be maintainable; that is, a small change or fix should only require a small amount of effort. Although parser generators have provided significant power for language recognition tasks, many of them are deficient in error recovery. Of the ones that do provide error recovery, many of these produce unacceptably slow parsers. I have designed and implemented a parser generator that produces fast, error recovering parsers. The high speed of the parser is a result of making the code directly executable, and paying careful attention to implementation details. The error recovery technique guarantees that a syntactically correct parse tree will be delivered after parsing has completed no matter what the input. This is important so that remaining compilation phases will not have to deal with infinitely many special cases of incorrect parse trees. Measurements show that the generated parser runs faster than any other parser examined, including hand-written recursive descent parsers. The cost of this fast parser is a slight increase in space requirements. Although this particular generator requires LL grammars, the ideas can be applied to generators taking LAR grammars. Furthermore, there is evidence that most LALR grammars for programming languages can be automatically converted to equivalent LL grammars.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1987
- Accession Number
- ADA196581
Entities
People
- Robert W. Gray
Organizations
- University of Colorado Boulder