aud.example.expr.ExpressionParser2 Class Reference

Same as ExpressionParser but using modified grammar to provide the usual left-associative expressions. More...

Inheritance diagram for aud.example.expr.ExpressionParser2:

Collaboration diagram for aud.example.expr.ExpressionParser2:

Static Public Member Functions
static void	main (String[] args)
	test and example for usage More...
static void	main (String[] args)
	test and example for usage More...

Protected Member Functions
ExpressionTree	sum (int level)
	parse sum More...
ExpressionTree	product (int level)
	parse product More...
Protected Member Functions inherited from aud.example.expr.ExpressionParser
String	errorNear ()
	helper: generate a simple error message More...
int	lookahead ()
	helper: "lookahead" is the usual phrasing More...
void	nextToken ()
	helper: consume current token and advance to next token More...
String	matchedText ()
	helper: get match corresponding to lookahead More...
void	expect (int tokenid, String text)
	helper: check token (without calling nextToken!) More...
void	verbose (int level, String message)
	helper: print out information More...
ExpressionTree	expression (int level)
	parse expression More...
ExpressionTree	sum (int level)
	parse sum More...
ExpressionTree	product (int level)
	parse product More...
ExpressionTree	factor (int level)
	parse factor More...

Additional Inherited Members
Public Member Functions inherited from aud.example.expr.ExpressionParser
ExpressionTree	parse (String input)
	parse input More...
void	setVerbose (boolean b)
	set verbose mode (report state to System.err) More...

Detailed Description

Same as ExpressionParser but using modified grammar to provide the usual left-associative expressions.

Here is the "correct" grammar, that implements left-associative expressions, i.e., a+b+c=(a+b)+c and a*b*c=(a*b)*c.

expression ::= sum

sum        ::= product |
               sum '+' product | sum '-' product

product    ::= factor |
               product '*' factor | product '/' factor

factor     ::= number | symbol | '(' expression ')' |
               '+' factor | '-' factor

Important note: We cannot implement this directly with a recursive descent parser as this would result in an infinite recursion! (This type of recursion is generally referred to as left recursion and requires a transformation of the grammar.)

I don't go into details but provide a simple solution right ahead: model part of the recursion (the left recursion) using an iterative implementation. (Can you see how the transformed grammar would look like?)

See also

ExpressionParser

Definition at line 36 of file ExpressionParser2.java.

Member Function Documentation

main()

static void aud.example.expr.ExpressionParser2.main ( String[]  args )

static

test and example for usage

Reimplemented from aud.example.expr.ExpressionParser.

Definition at line 110 of file ExpressionParser2.java.

                                         {
 
    String input=(args.length>0) ? args[0] : "a*b*c";
 
    System.out.println("input = '"+input+"'");
 
    ExpressionParser2 p=new ExpressionParser2();
    p.setVerbose(true);
    ExpressionTree tree=p.parse(input);
 
    System.out.println("output = '"+tree+"'");
 
    System.out.println(tree.postorder().toString());
 
    System.out.println(tree.toTikZ());
  }

References aud.example.expr.ExpressionParser.parse(), aud.BinaryTree< T >.postorder(), aud.example.expr.ExpressionParser.setVerbose(), aud.BinaryTreeTraversal< T >.Traversal.toString(), and aud.BinaryTree< T >.toTikZ().

Here is the call graph for this function:

product()

ExpressionTree aud.example.expr.ExpressionParser2.product ( int  level )

protected

parse product

product ::= factor |
            product '*' factor | product '/' factor

Reimplemented from aud.example.expr.ExpressionParser.

Definition at line 82 of file ExpressionParser2.java.

                                              {
    verbose(level,"<product>");
 
    // temporary storage
    Queue<ExpressionTree> expr = new Queue<ExpressionTree>();
    Queue<Integer>        op   = new Queue<Integer>();
 
    ExpressionTree tree=factor(level+1);
 
    // parse iteratively
    while (lookahead()==Tokenizer.TIMES || lookahead()==Tokenizer.DIVIDE) {
      op.enqueue(lookahead());
      nextToken();
      expr.enqueue(factor(level+1));
    }
 
    // setup tree
    while (!op.is_empty()) {
      if (op.dequeue()==Tokenizer.TIMES)
        tree=new ExpressionTree(new Times(),tree,expr.dequeue());
      else
        tree=new ExpressionTree(new Divide(),tree,expr.dequeue());
    }
    return tree;
  }

References aud.Queue< T >.dequeue(), aud.example.expr.Tokenizer.DIVIDE, aud.Queue< T >.enqueue(), aud.example.expr.ExpressionParser.factor(), aud.Queue< T >.is_empty(), aud.example.expr.ExpressionParser.lookahead(), aud.example.expr.ExpressionParser.nextToken(), aud.example.expr.Tokenizer.TIMES, and aud.example.expr.ExpressionParser.verbose().

Referenced by aud.example.expr.ExpressionParser2.sum().

Here is the call graph for this function:

Here is the caller graph for this function:

sum()

ExpressionTree aud.example.expr.ExpressionParser2.sum ( int  level )

protected

parse sum

sum ::= product |
        sum  '+' product | sum '-' product

Reimplemented from aud.example.expr.ExpressionParser.

Definition at line 50 of file ExpressionParser2.java.

                                                    {
    verbose(level,"<sum>");
 
    // temporary storage
    Queue<ExpressionTree> expr = new Queue<ExpressionTree>();
    Queue<Integer>        op   = new Queue<Integer>();
 
    ExpressionTree tree=product(level+1);
 
    // parse iteratively
    while (lookahead()==Tokenizer.PLUS || lookahead()==Tokenizer.MINUS) {
      op.enqueue(lookahead());
      nextToken();
      expr.enqueue(product(level+1));
    }
 
    // setup tree
    while (!op.is_empty()) {
      if (op.dequeue()==Tokenizer.PLUS)
        tree=new ExpressionTree(new Plus(),tree,expr.dequeue());
      else
        tree=new ExpressionTree(new Minus(),tree,expr.dequeue());
    }
    return tree;
  }

References aud.Queue< T >.dequeue(), aud.Queue< T >.enqueue(), aud.Queue< T >.is_empty(), aud.example.expr.ExpressionParser.lookahead(), aud.example.expr.Tokenizer.MINUS, aud.example.expr.ExpressionParser.nextToken(), aud.example.expr.Tokenizer.PLUS, aud.example.expr.ExpressionParser2.product(), and aud.example.expr.ExpressionParser.verbose().

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• ExpressionParser2.java