3

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 ) )
sten
  • 7,028
  • 9
  • 41
  • 63
  • http://cpansearch.perl.org/src/SMUELLER/Math-Symbolic-0.612/lib/Math/Symbolic/Parser.pm – choroba Feb 14 '16 at 20:24
  • Please [edit] your question to show the input that doesn't work. Ideally, create a runnable testcase that would pass when your problem is solved. See also: [How to create a Minimal, Complete, and Verifiable example](https://stackoverflow.com/help/mcve). – amon Feb 14 '16 at 20:35

2 Answers2

4

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.

hobbs
  • 223,387
  • 19
  • 210
  • 288
  • seem to work except on the following expression : # got: 'z / 13 + 22' # expected: 'z / 13 + 22 * abc + 16' any idea ? – sten Feb 15 '16 at 01:05
  • @user1019129 sorry, been a while since I've done this, I forgot to allow for associativity. Edited, try again? – hobbs Feb 15 '16 at 01:15
  • @user1019129 cool. Look at the docs for `leftop` (and `rightop`) to see how to simplify it further — what I gave you is the canonical version, but it's not the best that P::RD can do :) – hobbs Feb 15 '16 at 01:40
  • I've been trying to solve a left-recursive problem for a few nights now, and this was the single clearest breakdown of the problem I've seen anywhere! Very easily transferable, too. – kevlarr Apr 02 '19 at 01:24
  • @kevlarr glad to have helped :) – hobbs Apr 02 '19 at 01:54
3

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

collapsar
  • 17,010
  • 4
  • 35
  • 61