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
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.
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.