A Practical Method for Constructing Efficient LALR(k) Parsers with Automatic Error Recovery
Candidate: Philippe Charles
Advisor: Edmond Schonberg
10:00 a.m., Monday, March 4, 1991
715 Broadway, 7th floor conference room


LR parsing is used for a wide range of applications, including compiler construction, automatic code generation, language-specific editors and natural language processing. Currently, however, solutions have not been developed for practical multiple-lookahead parsing, fully-automatic error recovery, and space and time-efficient LR parsing across this wide-range of applications.

We present a practical framework for LR(k) parsing, for k > 1. We give an efficient algorithm that incrementally constructs an LALR(k) parser with varying- length lookahead strings, and whose symbols are consulted during parsing only when necessary.

Currently, effective LR error recovery systems require some user intervention. We describe an effective and fully automated syntactic error recovery method for LR(k) parsers. Finally, we present a generally effective method for compressing LR(k) parsing tables.

We have incorporated these innovations into a parser generator system that automatically constructs a production-quality parser with built-in error diagnostics and recovery. We will show examples of its performance on several programming languages.