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), 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), ACM, 2009. (abstract) (pdf) (bib)
Downloads
The test set (input files and grammars), permissive grammar derivation
tool, and stand-alone recovery tool can be found at:
https://svn.strategoxt.org/repos/StrategoXT/sglr-recovery/trunk
The implementation of
JSGLR has been adapted to include the error recovery algorithm:
https://svn.strategoxt.org/repos/StrategoXT/spoofax/trunk
The components above are applied in the
Spoofax/IMP editor trunk
series at:
https://svn.strategoxt.org/repos/StrategoXT/spoofax-imp/trunk
Grammars and Test Sets
We generated a number of grammars for languages including Java, Stratego, and Stratego-Java. These grammars can be downloaded from this page:
The Java test set can also be found here:
Contact and Mailing List
Please send questions or feedback to the
users@strategoxt.org mailing list or directly to the authors (listed above). We'd be interested in any form of feedback or discussing ideas of applying these techniques in a different context. Also, the developers are usually available on IRC at
#spoofax on freenode.net (
web version). Feel free to drop by!