Efficient and flexible incremental parsing
Authors:
Open Access
- 1 September 1998
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 20 (5) , 980-1013
Abstract
Previously published algorithms for LR ( k ) incremental parsing are inefficient, unnecessarily restrictive, and in some cases incorrect. We present a simple algorithm based on parsing LR( k ) sentential forms that can incrementally parse an arbitrary number of textual and/or structural modifications in optimal time and with no storage overhead. The central role of balanced sequences in achieving truly incremental behavior from analysis algorithms is described, along with automated methods to support balancing during parse table generation and parsing. Our approach extends the theory of sentential-form parsing to allow for ambiguity in the grammar, exploiting it for notational convenience, to denote sequences, and to construct compact (“abstract”) syntax trees directly. Combined, these techniques make the use of automatically generated incremental parsers in interactive software development environments both practical and effective. In addition, we address information preservation in these environments: Optimal node reuse is defined; previous definitions are shown to be insufficient; and a method for detecting node reuse is provided that is both simpler and faster than existing techniques. A program representation based on self-versioning documents is used to detect changes in the program, generate efficient change reports for subsequent analyses, and allow the parsing transformation itself to be treated as a reversible modification in the edit log.Keywords
This publication has 20 references indexed in Scilit:
- Precedences in specifications and implementations of programming languagesTheoretical Computer Science, 1995
- Controlled grammatic ambiguityACM Transactions on Programming Languages and Systems, 1994
- Incremental LL(1) parsing in language-based editorsIEEE Transactions on Software Engineering, 1993
- Incremental scanning and parsing with galaxyIEEE Transactions on Software Engineering, 1991
- Incremental recursive descent parsingComputer Languages, 1990
- Automatic construction of incremental LR(1)—parsersACM SIGPLAN Notices, 1988
- A practical method for LR and LL syntactic error diagnosis and recoveryACM Transactions on Programming Languages and Systems, 1987
- Augmenting Parsers to Support IncrementalityJournal of the ACM, 1980
- Regular right part grammars and their parsersCommunications of the ACM, 1977
- Deterministic parsing of ambiguous grammarsCommunications of the ACM, 1975