6.5 Eliminating Parser Class Loops

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  6.   Transforming a Grammar


6.5 Eliminating Parser Class Loops

You can write the code for the Midimath parser by creating a method for each grammar definition. This approach helps organize the code, but it introduces the prospect of looping during the construction of the parsers. Translating a grammar to a parser class creates a definition loop if the grammar contains a cycle. For example, you might extend Midimath to allow parentheses:

 expression = term ('+' term)*;  term       = factor ('*' factor)*; factor     = '(' expression ')'  Num; 

This grammar allows an expression such as "(7 + 13) * 5" to use parentheses to control precedence. Using this grammar to build a parser creates a cycle: Building expression requires building term , which requires building factor , which requires building expression . The way to avoid this looping is to create a variable for at least one subparser that is involved in each cycle of the grammar. In this example, you can declare expression as an instance variable and then lazy-initialize it. This means the code leaves the instance variable null until its first use, as follows :

 public Parser expression() {      if (expression == null) {         expression = new Sequence();         Sequence plusTerm = new Sequence();         plusTerm.add(new Symbol('+').discard());         plusTerm.add(term());         plusTerm.setAssembler(new PlusAssembler());         expression.add(term());         expression.add(new Repetition(plusTerm));     }     return expression; } 

It is still the case that expression() calls term() , which calls factor() , which calls expression() . However, the first time expression() runs, the instance variable expression is null. The code in expression() immediately changes this, giving expression the value of an empty Sequence . When the method refers to term() , it results in a call to factor() and a call back to expression() . On this call, the instance variable expression is no longer empty; rather, it is a partially constructed Sequence . So expression() returns with no problem, term() and factor() return, and the first call to expression() returns.

If a grammar has more than one cycle, each cycle must have at least one subparser that breaks the looping of the definitions. One way to ensure that your parser class does not encounter loops as it builds its subparsers is to create an instance variable for each subparser and lazy-initialize each of these variables , as in expression() earlier. On the other hand, you may want to create a minimal number of variables and just test that your class does not loop. The difference in these approaches is primarily esthetic.


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