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)

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!