- Author:
- Philippe Charles
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 the wide-range of applications.
A practical framework for LR(k) parsing is introduced. An efficient algorithm incrementally constructs an LALR(k) parser with varying-length lookahead strings, whose symbols are consulted during parsing only when necessary. Currently, effective LR error recovery systems require some user intervention. An effective and fully automated syntactic error recovery method for LR(k) parsers is presented. A generally effective method for compressing LR(k) parsing tables is also presented.
These innovations have been incorporated into a parser generator system which automatically produces a production-quality parser with error diagnostics and recovery.
Cited By
- Omar C, Voysey I, Chugh R and Hammer M (2019). Live functional programming with typed holes, Proceedings of the ACM on Programming Languages, 3:POPL, (1-32), Online publication date: 2-Jan-2019.
- Parr T, Harwell S and Fisher K Adaptive LL(*) parsing Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, (579-598)
- Parr T, Harwell S and Fisher K (2014). Adaptive LL(*) parsing, ACM SIGPLAN Notices, 49:10, (579-598), Online publication date: 31-Dec-2015.
- de Jonge M, Kats L, Visser E and Söderberg E (2012). Natural and Flexible Error Recovery for Generated Modular Language Environments, ACM Transactions on Programming Languages and Systems (TOPLAS), 34:4, (1-50), Online publication date: 1-Dec-2012.
- Parr T and Fisher K (2019). LL(*), ACM SIGPLAN Notices, 46:6, (425-436), Online publication date: 4-Jun-2011.
- Parr T and Fisher K LL(*) Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, (425-436)
- Kats L, Visser E and Wachsmuth G Pure and declarative syntax definition Proceedings of the ACM international conference on Object oriented programming systems languages and applications, (918-932)
- Kats L, Visser E and Wachsmuth G (2010). Pure and declarative syntax definition, ACM SIGPLAN Notices, 45:10, (918-932), Online publication date: 17-Oct-2010.
- Schmitz S Noncanonical LALR(1) parsing Proceedings of the 10th international conference on Developments in Language Theory, (95-107)
Index Terms
- A practical method for constructing efficient LALR(K) parsers with automatic error recovery
Recommendations
Towards automatic error recovery in parsing expression grammars
SBLP '18: Proceedings of the XXII Brazilian Symposium on Programming LanguagesError recovery is an essential feature for a parser that should be plugged in Integrated Development Environments (IDEs), which must build Abstract Syntax Trees (ASTs) even for syntactically invalid programs in order to offer features such as automated ...
Error repair in shift-reduce parsers
Local error repair of strings during CFG parsing requires the insertion and deletion of symbols in the region of a syntax error to produce a string that is error free. Rather than precalculating tables at parser generation time to assist in finding such ...
Automatic syntax error reporting and recovery in parsing expression grammars
AbstractError recovery is an essential feature for a parser that should be plugged in Integrated Development Environments (IDEs), which must build Abstract Syntax Trees (ASTs) even for syntactically invalid programs in order to offer features ...
Highlights- We discuss two approaches, Standard and Unique, to build PEG-based error recovering parsers in a more automatic way.