Accession Number : ADA192449

Title :   Automatic Error Recovery in a Fast Parser,

Corporate Author : COLORADO UNIV AT BOULDER DEPT OF COMPUTER SCIENCE

Personal Author(s) : Gray, Robert W

PDF Url : ADA192449

Report Date : Jan 1987

Pagination or Media Count : 10

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.

Descriptors :   *PARSERS, *MACHINE TRANSLATION, AUTOMATIC, COSTS, ERRORS, GENERATORS, GRAMMARS, GUARANTEES, LANGUAGE, RECOGNITION, RECOVERY, SEMANTICS, COMPUTER APPLICATIONS

Subject Categories : Voice Communications
      Linguistics

Distribution Statement : APPROVED FOR PUBLIC RELEASE