aud.example.expr.ExpressionParser Class Reference

Simple expression parser. More...

Inheritance diagram for aud.example.expr.ExpressionParser:

Collaboration diagram for aud.example.expr.ExpressionParser:

Public Member Functions
ExpressionTree	parse (String input)
	parse input More...
void	setVerbose (boolean b)
	set verbose mode (report state to System.err) More...

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

Protected Member Functions
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...

Detailed Description

Simple expression parser.

Build ExpressionTree from (infix) string representation of a term.

Implements a top-down recusive descent parser based on the following rules in BNF form (w/o <> to ease HTML formatting of this page)

expression ::= sum

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

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

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

<number> and <symbol> are identified during the lexcical analysis. They correspond to AtomicExpression instances, which are used to build the tree. The same applies to operators '+',...

Notes

• The left-hand-sides of the BNF rules are "mapped" to (recursive) method calls, e.g. expression.

• The level argument is provided only for formatting verbose output.

• The parser uses a Tokenizer for lexcical scanning.

• The current token is used for "looking ahead" (lookahead): it is advanced (by nextToken only if this token is "consumed" by part of a BNF rule.

• The given grammar defines expressions right-associative, which is not quite correct: a+b+c should equal (a+b)+c (left associative) rather than a+(b+c)!
  A simple change of the grammar however leads to an infinite recursion (due to left recursion in the new grammar.
  This can be fixed easily by a transformation of the grammar. Also, the practical implementation is easy (use an iteration). However, both is boyond the scope of the lecture at this point. For a correct implementation see ExpressionParser2

See also

ExpressionTree

Tokenizer

AtomicExpression

Definition at line 69 of file ExpressionParser.java.

Member Function Documentation

errorNear()

String aud.example.expr.ExpressionParser.errorNear ( )

protected

helper: generate a simple error message

Definition at line 93 of file ExpressionParser.java.

                               {
    return "near '"+scanner_.matchedText()+
      "'\nbefore '"+scanner_.remainder()+"'";
  }

Referenced by aud.example.expr.ExpressionParser.factor().

Here is the caller graph for this function:

expect()

void aud.example.expr.ExpressionParser.expect ( int  tokenid, String  text  )

protected

helper: check token (without calling nextToken!)

Exceptions

SyntaxError

if token does not match

Definition at line 120 of file ExpressionParser.java.

                                                 {
    if (lookahead()!=tokenid)
      throw new SyntaxError("expected '"+text+"' got '"+
                            scanner_.matchedText()+"'\nbefore '"+
                            scanner_.remainder());
  }

References aud.example.expr.ExpressionParser.lookahead().

Referenced by aud.example.expr.ExpressionParser.factor().

Here is the call graph for this function:

Here is the caller graph for this function:

expression()

ExpressionTree aud.example.expr.ExpressionParser.expression ( int  level )

protected

parse expression

expression ::= sum

Definition at line 142 of file ExpressionParser.java.

                                                 {
    verbose(level,"<expression>");
    return sum(level+1);
  }

References aud.example.expr.ExpressionParser.sum(), and aud.example.expr.ExpressionParser.verbose().

Referenced by aud.example.expr.ExpressionParser.factor().

Here is the call graph for this function:

Here is the caller graph for this function:

factor()

ExpressionTree aud.example.expr.ExpressionParser.factor ( int  level )

protected

parse factor

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

The last part of the rule correspong to unary plus and minus operators +x and -x. The implementation ignores unary plus, i.e., +x -> x.

Definition at line 207 of file ExpressionParser.java.

                                             {
    verbose(level,"<factor>");
 
    ExpressionTree tree=null;
 
    if (lookahead()==Tokenizer.NUMBER) {
      tree=new ExpressionTree
                (new Number(Double.parseDouble(matchedText())));
    }
    else if (lookahead()==Tokenizer.IDENTIFIER) {
      tree=new ExpressionTree(new Symbol(matchedText()));
    }
    else if (lookahead()==Tokenizer.LEFT_PAREN) {
      nextToken();
      tree=expression(level+1);
      expect(Tokenizer.RIGHT_PAREN,"closing parenthesis )");
    }
    else if (lookahead()==Tokenizer.PLUS) { // unary plus
      nextToken();
      return factor(level+1); // ignore: +x == x
     }
    else if (lookahead()==Tokenizer.MINUS) { // unary minus
      nextToken();
      return new ExpressionTree(new UnaryMinus(),factor(level+1),null);
    }
    else
      throw new SyntaxError(errorNear());
 
    nextToken();
    assert(tree!=null);
 
    return tree;
  }

References aud.example.expr.ExpressionParser.errorNear(), aud.example.expr.ExpressionParser.expect(), aud.example.expr.ExpressionParser.expression(), aud.example.expr.ExpressionParser.factor(), aud.example.expr.Tokenizer.IDENTIFIER, aud.example.expr.Tokenizer.LEFT_PAREN, aud.example.expr.ExpressionParser.lookahead(), aud.example.expr.ExpressionParser.matchedText(), aud.example.expr.Tokenizer.MINUS, aud.example.expr.ExpressionParser.nextToken(), aud.example.expr.Tokenizer.NUMBER, aud.example.expr.Tokenizer.PLUS, aud.example.expr.Tokenizer.RIGHT_PAREN, and aud.example.expr.ExpressionParser.verbose().

Referenced by aud.example.expr.ExpressionParser.factor(), aud.example.expr.ExpressionParser.product(), and aud.example.expr.ExpressionParser2.product().

Here is the call graph for this function:

Here is the caller graph for this function:

lookahead()

int aud.example.expr.ExpressionParser.lookahead ( )

protected

helper: "lookahead" is the usual phrasing

Definition at line 99 of file ExpressionParser.java.

                            {
    return scanner_.matchedTokenId();
  }

Referenced by aud.example.expr.ExpressionParser.expect(), aud.example.expr.ExpressionParser.factor(), aud.example.expr.ExpressionParser.product(), aud.example.expr.ExpressionParser2.product(), aud.example.expr.ExpressionParser.sum(), and aud.example.expr.ExpressionParser2.sum().

Here is the caller graph for this function:

main()

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

static

test and example for usage

Reimplemented in aud.example.expr.ExpressionParser2.

Definition at line 245 of file ExpressionParser.java.

                                         {
 
    String input=(args.length>0) ? args[0] : "1+2*(3+4)";
 
    System.out.println("input = '"+input+"'");
 
    ExpressionParser p=new ExpressionParser();
    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:

matchedText()

String aud.example.expr.ExpressionParser.matchedText ( )

protected

helper: get match corresponding to lookahead

Returns

Tokenizer#matchedText

Definition at line 113 of file ExpressionParser.java.

                                 {
    return scanner_.matchedText();
  }

Referenced by aud.example.expr.ExpressionParser.factor().

Here is the caller graph for this function:

nextToken()

void aud.example.expr.ExpressionParser.nextToken ( )

protected

helper: consume current token and advance to next token

Definition at line 104 of file ExpressionParser.java.

                             {
    if (scanner_.next()==Tokenizer.NO_MATCH)
      throw new SyntaxError("unknown token: lexcial analysis failed at '"+
                            scanner_.remainder()+"'");
  }

Referenced by aud.example.expr.ExpressionParser.factor(), aud.example.expr.ExpressionParser.product(), aud.example.expr.ExpressionParser2.product(), aud.example.expr.ExpressionParser.sum(), and aud.example.expr.ExpressionParser2.sum().

Here is the caller graph for this function:

parse()

ExpressionTree aud.example.expr.ExpressionParser.parse

(

String

input

)

parse input

Parameters

input

term

Exceptions

SyntaxError

on syntax error

Returns

extression tree that represents input term

Definition at line 79 of file ExpressionParser.java.

                                            {
    scanner_ = new Tokenizer(input);
    scanner_.next(); // use as "lookahead"
    ExpressionTree tree=expression(0);
    expect(Tokenizer.END_OF_INPUT,"<end of input>");
    return tree;
  }

Referenced by aud.example.expr.ExpressionParser.main(), aud.example.expr.ExpressionParser2.main(), and aud.example.expr.ExpressionTreeTraversal.main().

Here is the caller graph for this function:

product()

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

protected

parse product

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

Reimplemented in aud.example.expr.ExpressionParser2.

Definition at line 178 of file ExpressionParser.java.

                                              {
    verbose(level,"<product>");
 
    ExpressionTree left=factor(level+1);
 
    if (lookahead()==Tokenizer.TIMES) {
      nextToken();
      ExpressionTree right=product(level+1);
      return new ExpressionTree(new Times(),left,right);
    }
    else if (lookahead()==Tokenizer.DIVIDE) {
      nextToken();
      ExpressionTree right=product(level+1);
      return new ExpressionTree(new Divide(),left,right);
    }
 
    return left;
  }

References aud.example.expr.Tokenizer.DIVIDE, aud.example.expr.ExpressionParser.factor(), aud.example.expr.ExpressionParser.lookahead(), aud.example.expr.ExpressionParser.nextToken(), aud.example.expr.ExpressionParser.product(), aud.example.expr.Tokenizer.TIMES, and aud.example.expr.ExpressionParser.verbose().

Referenced by aud.example.expr.ExpressionParser.product(), and aud.example.expr.ExpressionParser.sum().

Here is the call graph for this function:

Here is the caller graph for this function:

setVerbose()

void aud.example.expr.ExpressionParser.setVerbose

(

boolean

b

)

set verbose mode (report state to System.err)

Definition at line 88 of file ExpressionParser.java.

                                    {
    verbose_=b;
  }

Referenced by aud.example.expr.ExpressionParser.main(), and aud.example.expr.ExpressionParser2.main().

Here is the caller graph for this function:

sum()

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

protected

parse sum

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

Reimplemented in aud.example.expr.ExpressionParser2.

Definition at line 153 of file ExpressionParser.java.

                                          {
    verbose(level,"<sum>");
 
    ExpressionTree left=product(level+1);
 
    if (lookahead()==Tokenizer.PLUS) {
      nextToken();
      ExpressionTree right=sum(level+1);
      return new ExpressionTree(new Plus(),left,right);
    }
    else if (lookahead()==Tokenizer.MINUS) {
      nextToken();
      ExpressionTree right=sum(level+1);
      return new ExpressionTree(new Minus(),left,right);
    }
 
    return left;
  }

References aud.example.expr.ExpressionParser.lookahead(), aud.example.expr.Tokenizer.MINUS, aud.example.expr.ExpressionParser.nextToken(), aud.example.expr.Tokenizer.PLUS, aud.example.expr.ExpressionParser.product(), aud.example.expr.ExpressionParser.sum(), and aud.example.expr.ExpressionParser.verbose().

Referenced by aud.example.expr.ExpressionParser.expression(), and aud.example.expr.ExpressionParser.sum().

Here is the call graph for this function:

Here is the caller graph for this function:

verbose()

void aud.example.expr.ExpressionParser.verbose ( int  level, String  message  )

protected

helper: print out information

Definition at line 128 of file ExpressionParser.java.

                                                   {
    if (verbose_) {
      System.err.println(Sys.indent(level)+message+
                         " ['"+scanner_.matchedText()+"','"+
                         scanner_.remainder()+"']");
    }
  }

Referenced by aud.example.expr.ExpressionParser.expression(), aud.example.expr.ExpressionParser.factor(), aud.example.expr.ExpressionParser.product(), aud.example.expr.ExpressionParser2.product(), aud.example.expr.ExpressionParser.sum(), and aud.example.expr.ExpressionParser2.sum().

Here is the caller graph for this function:

---

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

• ExpressionParser.java