Incremental scannerless generalized LR parsing
2019pp. 54–56
Citations Over Time
Abstract
We present the Incremental Scannerless Generalized LR (ISGLR) parsing algorithm, which combines the benefits of Incremental Generalized LR (IGLR) parsing and Scannerless Generalized LR (SGLR) parsing. The parser preprocesses the input by modifying the previously saved parse forest. This allows the input to the parser to be a stream of parse nodes, instead of a stream of characters. Scannerless parsing relies heavily on non-determinism during parsing, negatively impacting the incrementality of ISGLR parsing. We evaluated the ISGLR parsing algorithm using file histories from Git, achieving a speedup of up to 25 times over non-incremental SGLR.
Related Papers
- → Recursive ascent parsing: from Earley to Marcus(1992)16 cited
- An efficient augmented-context-free parsing algorithm(1987)
- → LR parsers for natural languages(1984)30 cited
- An abstract view of generalized LR parsing(2003)
- → A Kind of Syntax Parsing Algorithm Based on The Predictive Parsing Table(2022)