Incremental Scannerless Generalized LR Parsing

Incremental Scannerless Generalized LR Parsing

Sijm, Maarten P. (TU Delft Electrical Engineering, Mathematics and Computer Science)

Denkers, J. (mentor)
Visser, Eelco (mentor)
Poulsen, C.B. (graduation committee)
van der Storm, T. (graduation committee)
Mosses, P.D. (graduation committee)

Delft University of Technology

Computer Science

2021-07-14

The Scannerless Generalized LR (SGLR) parsing algorithm supports the development of composed languages seamlessly but does not support incremental parsing. The Incremental Generalized LR (IGLR) parsing algorithm, on the other hand, does not support the seamless composition of languages. This thesis presents the Incremental Scannerless Generalized LR (ISGLR) parsing algorithm and investigates the effects of combining the SGLR and IGLR parsing algorithms. While the algorithmic differences are orthogonal, the fact that scannerless parsing relies on non-deterministic parsing for disambiguation has a negative impact on incrementality. Nonetheless, we show that the ISGLR parsing algorithm performs better than the batch SGLR parsing algorithm in typical scenarios. On average, the ISGLR parser can reuse 99% of a previous parse result. When parsing from scratch, the ISGLR parser has a 24% run time overhead compared to the SGLR parser, but when parsing incrementally for changes that are smaller than 1% of the input size on average, it has a 9× speedup.

incremental
scannerless
parsing
GLR
IGLR
SGLR
ISGLR
imploding
syntax
Spoofax

http://resolver.tudelft.nl/uuid:6ddf9fbd-c39e-4aae-b6ce-13389def6a9f

Successor of https://doi.org/10.1145/3359061.3361085

Student theses

master thesis

© 2021 Maarten P. Sijm