The Permissive Grammars Project
Stratego -- Strategies for Program Transformation
This page reports on the permissive grammars project. This project is aimed at adding practical error recovery to the Java implementation of SGLR, for interactive parsing of stand-alone and composite programming languages using SDF.
The base idea of the permissive grammars project is simple: given an SDF grammar, we derive a permissive grammar [1] that also accepts programs with minor errors (missing brackets, etc.). These grammars are normal SDF grammars and can be tweaked by the language engineer. Using a specialized version of the SGLR algorithm, both syntactically correct and incorrect programs can be efficiently parsed using these grammars [1]. As a refinement of these techniques, we also use indentation to constrain the search space of error recovery suggestions and to provide better error recovery suggestions [2].
Implementation
Automatic generation of permissive grammars and use of error recovery in Eclipse has been integrated to and is automatically supported in the Spoofax language workbench.Presentations
The slides of our OOPSLA 2009 presentation, explaining the core recovery mechanism, are available here: Providing Rapid Feedback in Generated Modular Language Environments. The presentation of our followup work at SLE 2009 can be downloaded here: Natural and Flexible Error Recovery for Generated Parsers.Publications
- [2]
- Maartje de Jonge, Emma Nilsson-Nyman, Lennart C. L. Kats, Eelco Visser. Natural and Flexible Error Recovery for Generated Parsers. In Mark van den Brand, Jeff Gray, editors, Proceedings of Software Language Engineering (SLE 2009), pages 204-223, Lecture Notes in Computer Science, Springer, 2009. (abstract) (pdf) (bib)
- [1]
- Lennart C. L. Kats, Maartje de Jonge, Emma Nilsson-Nyman, Eelco Visser. Providing Rapid Feedback in Generated Modular Language Environments. Adding Error Recovery to Scannerless Generalized-LR Parsing. In Gary T. Leavens, editor, Proceedings of the 24th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2009), pages 445-464, ACM, 2009. (abstract) (pdf) (bib)