Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking
Stratego -- Strategies for Program Transformation
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,
implementation)
Abstract
A wide range of parser generators are used to generate parsers
for programming languages. The grammar formalisms that come
with parser generators provide different approaches for
defining operator precedence. Some generators (e.g. YACC)
support precedence declarations, others require the grammar to
be unambiguous, thus encoding the precedence rules. Even if
the grammar formalism provides precedence rules, a particular
grammar might not use it.
The result is grammar variants implementing the same
language. For the C language, the GNU Compiler uses YACC with
precedence rules, the C-Transformers uses
SDF without
priorities, while the
SDF library does use priorities. For
PHP, Zend uses YACC with precedence rules, whereas PHP-front
uses
SDF with priority and associativity declarations.
The variance between grammars raises the question if the
precedence rules of one grammar are compatible with those of
another. This is usually not obvious, since some languages
have complex precedence rules. Also, for some parser
generators the semantics of precedence rules is defined
operationally, which makes it hard to reason about their
effect on the defined language.
We present a method and tool for comparing the precedence
rules of different grammars and parser generators. Although it
is undecidable whether two grammars define the same language,
this tool provides support for comparing and recovering
precedence rules, which is especially useful for reliable
migration of a grammar from one grammar formalism to
another. We evaluate our method by the application to
non-trivial mainstream programming languages, such as PHP and
C.