Package aud.example.expr

Class ExpressionParser

java.lang.Object
aud.example.expr.ExpressionParser
Direct Known Subclasses:
ExpressionParser2
public class ExpressionParser extends Object
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(int).
  • The level argument is provided only for formatting verbose(int, java.lang.String) 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:

  • Constructor Details

    • ExpressionParser

      public ExpressionParser()

  • Method Details

    • parse

      public ExpressionTree parse(String input)
      parse input
      Parameters:
      input - term
      Returns:
      extression tree that represents input term
      Throws:
      SyntaxError - on syntax error

    • setVerbose

      public void setVerbose(boolean b)
      set verbose mode (report state to System.err)

    • errorNear

      protected String errorNear()
      helper: generate a simple error message

    • lookahead

      protected int lookahead()
      helper: "lookahead" is the usual phrasing

    • nextToken

      protected void nextToken()
      helper: consume current token and advance to next token

    • matchedText

      protected String matchedText()
      helper: get match corresponding to lookahead()
      Returns:
      LexicalScanner.matchedText()

    • expect

      protected void expect(int tokenid, String text)
      helper: check token (without calling nextToken()!)
      Throws:
      SyntaxError - if token does not match

    • verbose

      protected void verbose(int level, String message)
      helper: print out information

    • expression

      protected ExpressionTree expression(int level)
      parse expression 
      expression ::= sum

    • sum

      protected ExpressionTree sum(int level)
      parse sum

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

    • product

      protected ExpressionTree product(int level)
      parse product

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

    • factor

      protected ExpressionTree factor(int level)
      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.

    • main

      public static void main(String[] args)
      test and example for usage