7.4 An Arithmetic Grammar Parser


 
Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  7.   Parsing Arithmetic

    Content

You can create an arithmetic parser by translating the arithmetic grammar into a parser class and plugging in the assemblers. Section 3.6, "Translating a Grammar to Code," gives a set of rules for creating a parser from a grammar. The only remaining problem is to prevent looping in the subparser definitions.

Section 6.5, "Eliminating Parser Class Loops," explains how to address loops in a grammar. The arithmetic grammar has two cycles.

 expression    = term (plusTerm  minusTerm)*;  term          = factor (timesFactor  divideFactor)*; plusTerm      = '+' term; minusTerm     = '-' term; factor        = phrase expFactor  phrase; timesFactor   = '*' factor; divideFactor  = '/' factor; expFactor     = '^' factor; phrase        = '(' expression ')'  Num; 

One cycle is in factor . This definition depends on expFactor , which depends on factor . The other cycle in the grammar begins with expression . The expression rule depends on term , which depends on factor , which depends on phrase , which depends on expression . To avoid loops in the code, use instance variables to hold the expression and factor parsers. Figure 7.3 shows the ArithmeticParser class.

Figure 7.3. The ArithmeticParser class. This class holds a collection of methods that can be composed into a parser for arithmetic.

graphics/07fig03.gif

To use this class, you can apply the parser ArithmeticParser.start() to match a token assembly. Alternatively, you can use this class's value() method, which takes a String and returns a double value. The following class shows this approach:

 package sjm.examples.arithmetic;  /**  * Show how to use the <code>ArithmeticParser</code> class.  */ public class ShowArithmeticParser { /*  * Help out the main() method.  */ private static void eval(String s, double d)     throws ArithmeticExpressionException {     System.out.println(         "Given: "    + s +         " Expected: " + d +         "\tFound: "  + ArithmeticParser.value(s)); } /**  * Show a few examples of arithmetic.  */ public static void main(String args[])     throws ArithmeticExpressionException {     eval("9^2 - 81       ",   0); // exponentiation     eval("7 - 3 - 1      ",   3); // minus associativity     eval("2 ^ 1 ^ 4      ",   2); // exp associativity     eval("100 - 25*3     ",  25); // precedence     eval("100 - 5^2*3    ",  25); // precedence     eval("(100 - 5^2) * 3", 225); // parentheses } } 

Running this class prints the following:

 Given: 9^2 - 81         Expected: 0.0    Found: 0.0  Given: 7 - 3 - 1        Expected: 3.0    Found: 3.0 Given: 2 ^ 1 ^ 4        Expected: 2.0    Found: 2.0 Given: 100 - 25*3       Expected: 25.0   Found: 25.0 Given: 100 - 5^2*3      Expected: 25.0   Found: 25.0 Given: (100 - 5^2) * 3  Expected: 225.0  Found: 225.0 

The display shows various expected results that demonstrate associativity, precedence, and the use of parentheses.


   
Top


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