Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking

Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking

Bouwers, E.
Bravenboer, M.
Visser, E.

Electrical Engineering, Mathematics and Computer Science

Software Technology

2007-03-25

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. Presented at LDTA 2007 Seventh Workshop on Language Descriptions, Tools and Applications, 25-3-2007, Braga, Portugal

precedence
precedence rules
disambiguation
priorities, associativity
grammar engineering
grammar recovery
parsing
YACC
SDF

http://resolver.tudelft.nl/uuid:ceeb5582-4e0d-4102-a2e3-846f7312e16a

Delft University of Technology, Software Engineering Research Group

1872-5392

Technical Report Series TUD-SERG-2007-004

Institutional Repository

report

(c) 2007 The authors. Software Engineering Research Group, Department of Software Technology, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology.