Parse::RecDescent : Parsing nested arithmetic expression?

Question

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 ) )

Answer 1

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.

Answer 2

Add a rule to combine a bracketed expression with another expression using an infix operator:

| '(' expr ')' op expr

Btw, the original grammar does not suffer wrt nested expressions but infix expressions that start with a term in parentheses.

In general, the solution by user hobbs is the standard approach to tackle expressions with infix operators of different preference. It has the additional advantage that the correct subexpression evaluation order is taken care of by the grammar proper and need not be handled by extra code.

Stay with my solution only if you do not need a full-fledged expression evaluator (You will most certainly find that you need one ...).