6.1 The Role of Grammar Transformation

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  6.   Transforming a Grammar


Many simple languages, including most data languages, avoid the subtleties of grammar design by not introducing operators. Operators such as " + " and " - " bring up the question of whether

 11 + 5 * 2 

should equal 32 or 21 . Different languages, notably Smalltalk and Java, have different answers to this question, depending on the precedence of operators. Another question that arithmetic encounters is whether

 25  16 - 9 

equals or 18 . Here the answer depends on the associativity of the " - " operator, which determines whether the rightmost or leftmost operator applies first. The grammar for your language determines the associativity and precedence of operators in your language.

In addition to establishing operator precedence and associativity, a grammar can contain loops . There is nothing wrong with a grammar that has loops, but translating such a grammar to code can result in code that contains infinite loops. In particular, a grammar rule that refers to itself with its leftmost element will cause a loop when you translate the grammar to code. In addition, if a grammar contains cyclic definitions, implementing the grammar as a parser class can cause looping in the code.

This chapter shows how to transform a grammar to attain the following objectives:

  1. Ensure correct associativity.

  2. Eliminate left recursion.

  3. Ensure correct precedence.

  4. Eliminate parser class loops.


Building Parsers with Java
Building Parsers With Javaв„ў
ISBN: 0201719622
EAN: 2147483647
Year: 2000
Pages: 169

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net