Incremental Scannerless Generalized-LR Parsing
Master Project of Maarten Sijm


Project description

Extend the Scannerless Generalized-LR (SGLR) Parsing algorithm to incremental parsing. The work of Tim Wagner is a good starting point.

This project involves the following steps:

  • Combine the SGLR and IGLR algorithms

  • Integrate in the JSGLR2 implementation

  • Develop a test suite for testing the correct (incremtal) behavior

  • Benchmark the algorithm

  • Integrate in the Spoofax language workbench

[1] Tim A. Wagner, Susan L. Graham. Efficient and Flexible Incremental Parsing. ACM Transactions on Programming Languages and Systems, 20(5):980-1013, 1998.

[2] Tim A. Wagner, Susan L. Graham. Integrating Incremental Analysis with Version Management. In Wilhelm Schäfer, Pere Botella, editors, 5th European Software Engineering Conference, Sitges, Spain, September 25-28, 1995, Proceedings. Volume 989 of Lecture Notes in Computer Science, pages 205-218, Springer, 1995.

[3] Tim A. Wagner, Susan L. Graham. Incremental Analysis of real Programming Languages. In PLDI. pages 31-43, 1997.

[4] Tree Sitter project. http://tree-sitter.github.io/tree-sitter/ and https://github.com/tree-sitter/tree-sitter


Incremental Scannerless Generalized-LR Parsing

Student: Maarten Sijm
Supervisor(s): Eelco Visser, Jasper Denkers