Automatic Error Recovery in a Fast Parser,
Abstract
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. For any input, the error recovery technique guarantees that a syntactically correct parse tree will be delivered after parsing has completed. This improves robustness because the remaining compilation phases, such as semantic analysis, will not have to deal with infinitely many special cases of incorrect parse trees. The high speed of the parser is a result of making the code directly executable and paying careful attention to implementation details. Measurements show that the generated parser runs faster than any other parser examined, including handwritten recursive descent parsers. The cost of this fast parser with error recovery is a slight increase in space. Although this particular generator requires LL grammars, the ideas can be applied to generators taking LALR grammars. Furthermore, we give the transformations that allow one to transform may LALR grammars into equivalent LL grammars.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1987
- Accession Number
- ADA192449
Entities
People
- Robert W. Gray
Organizations
- University of Colorado Boulder