Incremental parsers
An incremental parser is a device which is able to perform syntax analysis in an incremental way, avoiding complete reparsing of a program after each modification. The incremental parser presented extends the conventional LR parsing algorithm and its performance is compared with that of a conventional parser. Suggestions for an implementation and possible extensions to other parsing methods are also discussed.
— Carlo Ghezzi and Dino Mandrioli. 1979. Incremental Parsing. ACM Trans. Program. Lang. Syst. 1, 1 (July 1979), 58–70. https://doi.org/10.1145/357062.357066
GLR
Code:
- Lezer is an LR(1) (more precisely pseudo-LALR,with opt-in GLR).
Papers:
- Incremental Analysis of Real Programming Languages, 2010
- SPLASH: G: Incremental Scannerless Generalized LR Parsing, Maarten P. Sijm, 2020
PEG
- Patrick Dubroy and Alessandro Warth. 2017. Incremental packrat parsing. In Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017). Association for Computing Machinery, New York, NY, USA, 14–25. https://doi.org/10.1145/3136014.3136022
- talk: YouTube video
- code: https://ohmjs.org/
- Zachary Yedidia and Stephen Chong. 2021. Fast incremental PEG parsing. In Proceedings of the 14th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2021). Association for Computing Machinery, New York, NY, USA, 99–112. https://doi.org/10.1145/3486608.3486900
- talk: YouTube video
- code: https://github.com/zyedidia/gpeg