[SOLVED] Parse::RecDescent : Parsing nested arithmetic expression?

Parse::RecDescent : Parsing nested arithmetic expression?

Currently I use this to parse Arithmetic expressions :

expr  : '(' expr ')' 
      | number op expr 
      | variable op expr 
      | number
      | variable
      | <error>

It works for simple expressions, but can't handle nested bracketed-expressions. Any idea how to extend/modify it so it can handle nested expressions.

For example this works :

5 + 12
33 - $var
13 + 2 * $v
( 44 + 98 )

but this does not work :

( 44 + 98 ) / 2
( 44 + 98 ) / ( 5 + $var2 )
( 11 + 5 ) * ( 3 + ( $v * 2 ) )

Solution

Your precedence chain has a problem. 1 + (2 + 3) can parse as number op expr, with the expr on the right being '(' expr ')', but (1 + 2) + 3 can't, because expr can't appear to the left of op. Of course you can't add it there directly because left-recursion is forbidden. What you need to do is break it down like:

expr: term '+' expr
    | term '-' expr
    | term

term: factor '*' term
      | factor '/' term
      | factor

factor: '(' expr ')'
    | number
    | variable
    | <error>

yes, parentheses are all the way down there at the end of the chain, which might seem weird, but what it says is that a parenthesized expression can appear anywhere a factor can, and will be evaluated before it bubbles up. Now it's easy to see that since everything refers to factor, a parenthesized expression can appear anywhere it needs to.