Home

Download

Support

Developers

Page

Web

Wiki

Stratego/XT Grammar Engineering Tools

Stratego -- Strategies for Program Transformation

Introduction

The Stratego/XT Grammar Engineering Tools is a collection of tools for the recovery, development, testing, and maintenance of grammars. Currently, the package mainly provides tools to support the recovery and comparison of precedence rules from YACC and SDF grammars. Also, the package could be used as the basis of other tools that analyze YACC generated parsers.

Documentation

Research Papers

  • Eric Bouwers, Martin Bravenboer, and Eelco Visser. Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking. In Proceedings of LDTA'07, Seventh Workshop on Language Descriptions, Tools and Applications at ETAPS'07, Braga, Portugal, March 2007. (pdf, slides)

Blogs

Samples

Examples of how to use the tools are available in the samples directory. The samples are currently not distributed in the tarball, so you need to check them out from their location in Subversion.

The samples/expr directory provides a series of examples based on a variety of simple expression grammars. The samples/c and samples/php grammars are used for larger examples of how to apply the tools to a series of C and PHP grammars.

Every sample directory has a script maak (Dutch for make) that you can invoke to run the tools on the sample.

Simple Examples

The following example illustrate how to invoke the various tools.

Precedence rules of a YACC grammar: 

$ bison expr.y -o expr.c --report=all
$ yacc-precedence -i expr.output -s E
<E -> <E -> E '+' E> '*' E>
<E -> E '*' <E -> E '*' E>>
<E -> E '*' <E -> E '+' E>>
<E -> E '+' <E -> E '+' E>>

Precedence rules of an SDF grammar: 

$ sdf2table -i expr.sdf
$ sglr-precedence -i expr.tbl -s E
<E -> E "+" <E -> E "+" E>>
<E -> <E -> E "+" E> "*" E>
<E -> E "*" <E -> E "+" E>>
<E -> E "*" <E -> E "*" E>>

Comparing two precedence rule sets (example of unequal grammars) : 

$ sglr-precedence -i expr.tbl -s E --common -o expr.sglrprec
$ yacc-precedence -i expr.output -s E --common -o expr.yaccprec
$ common-precedence-equality -i expr.sglrprec expr.yaccprec
Some precedence rules of first are not defined in second:
  <E -> <E -> E "+" E> "-" E>
  <E -> E "-" <E -> E "+" E>>
  <E -> E "-" <E -> E "-" E>>
  <E -> <E -> E "-" E> "*" E>
  <E -> E "*" <E -> E "-" E>>
Some precedence rules of second are not defined in first:
  <E -> E "*" <E -> E "*" E>>

Or using bash process subtitution: 

$ common-precedence-equality -i \
  <(sglr-precedence -i expr.tbl -s E --common) \
  <(yacc-precedence -i expr.output -s E --common)

Example of two equal grammars: 

$ common-precedence-equality -i expr.sglrprec expr.yaccprec
All precedence rules of first are defined in second.
All precedence rules of second are defined in first.

Before comparing precedence rules it is useful to compare productions first. 

$ common-precedence-production-equality -i expr.sglrprec expr.yaccprec
Some productions of first are not defined in second:
  E -> E "-" E
All productions of second are defined in first.

Extract productions used in YACC precedence rules: 

$ yacc-precedence -i expr.output --common -s E  | common-precedence-productions
E -> E "*" E
E -> E "+" E

Extract productions used in SDF/SGLR precedence rules: 

$ sglr-precedence -i expr.tbl --common -s E  | common-precedence-productions
E -> E "+" E
E -> E "*" E

Download

Latest Developments

Distributions (tarball, rpm, srpm) of the head revision are created continuously:

The distributions contain the latest of the latest developments, but if you really want to, the latest sources can be checked out using: 

  svn checkout https://svn.strategoxt.org/repos/StrategoXT/grammar-engineering-tools/trunk
Before you can configure the package as described above you have to run the ./bootstrap script.

Installation

Install the package with the usual sequence of commands: 

$ ./configure
$ make
$ make install

You might need to set your PKG_CONFIG_PATH if you did not install the dependencies in a standard location. Configure will tell you to do this if it cannot find aterm, sdf or strategoxt.

Success Stories

Until now, the precedence tools have reported precedence issues for every single grammar that is a derivative from some standard (try your grammar and see if you can make this statement invalid ;) )

  • The precedence tools have reported a bug in the C-Transformers grammar for C99, which has now been fixed (revision 1613).

  • The precedence tools have reported several problems in the open source PHP Compiler, which was reported by us and fixed soon after by the developers. These problems have been found by comparing the precedence rules of the PHP Compiler to the official PHP implementation.

  • The precedence tools have reported several problems in the ANSI C grammar of the SDF Library, which have been reported to the maintainers as issues 669, 670, and 671.

  • In an ongoing effort to define the precise syntax of PHP in SDF (see PHP-front), the precedence tools are used to recover the precedence rules from the YACC grammar that is part of the official PHP implementation. These precedence rules are now being used to derive the appropriate SDF priority definitions.

Project Info

Contact and Mailing List

Please send questions to the stratego@cs.uu.nl mailing list. Also, the developers are usually available on IRC at irc.freenode.net/stratego. Feel free to drop by!

Source Repository

The sources are available from Subversion.

Team

Contributors:

Feedback and bug reports:

License

Stratego/XT Grammar Engineering Tools are GPL (GNU General Public License) software.

Related Projects and Tools

  • Meta-Environment, in particular its instantiations the ASF+SDF Meta-Environment and the SDF Meta-Environment.