CODEWITHSUNDEEP
antlr
KIC
KIC

Reputation: 6121

simple math expression parser

I have a simple math expression parser and I want to build the AST by myself (means no ast parser). But every node can just hold two operands. So a 2+3+4 will result in a tree like this:

        +
       / \
      2   +
         / \
        3   4

The problem is, that I am not able to get my grammer doing the recursion, here ist just the "add" part:

add returns [Expression e]
  : op1=multiply { $e = $op1.e; Print.ln($op1.text); } 
    ( '+' op2=multiply   { $e = new AddOperator($op1.e, $op2.e); Print.ln($op1.e.getClass(), $op1.text, "+", $op2.e.getClass(), $op2.text); }
    | '-' op2=multiply   { $e = null; } // new MinusOperator    
    )*
  ;

But at the end of the day this will produce a single tree like:

     +
    / \
   2   4

I know where the problem is, it is because a "add" can occour never or infinitly (*) but I do not know how to solve this. I thought of something like:

"add" part:

add returns [Expression e]
  : op1=multiply { $e = $op1.e; Print.ln($op1.text); } 
    ( '+' op2=(multiply|add)   { $e = new AddOperator($op1.e, $op2.e); Print.ln($op1.e.getClass(), $op1.text, "+", $op2.e.getClass(), $op2.text); }
    | '-' op2=multiply   { $e = null; } // new MinusOperator    
    )?
  ;

But this will give me a recoursion error. Any ideas?

Upvotes: 0

Views: 635

Answers (1)

user1201210
user1201210

Reputation: 3809

I don't have the full grammar to test this solution, but consider replacing this (from the first add rule in the question):

$e = new AddOperator($op1.e, $op2.e);

With this:

$e = new AddOperator($e, $op2.e);  //$e instead of $op1.e

This way each iteration over ('+' multiply)* extends e rather than replaces it.

It may require a little playing around to get it right, or you may need a temporary Expression in the rule to keep things managed. Just make sure that the last expression created by the loop is somewhere on the right-hand side of the = operator, as in $e = new XYZ($e, $rhs.e);.

Upvotes: 1

Related Questions