in reply to Re: Order of Precedence in Parse::RecDescent grammar
in thread Order of Precedence in Parse::RecDescent grammar

So... away I went... and that seems to work, BUT!

where when I parsed 4+1*2 before I got 

$VAR1 = [
          '4',
          '+',
          [
            '1',
            '*',
            '2'
          ]
        ];

[download]
Now I get 
$VAR1 = [
          [
            [
              [
                '4'
              ]
            ],
            '+',
            [
              [
                '1'
              ],
              '*',
              [
                '2'
              ]
            ]
          ]
        ];

[download]
Ick... any good way to clean that up? It gets really nasty with more complex statements.
Here is the new grammar. 
  startrule: comparison_expr

  comparison_expr: additive_expr
               (comparison_op additive_expr { [ @item[1..2] ] })(s?)
               { [  $item[1], map { @ $_ } @{$item[2]} ] }
  comparison_op: />=?|<=?|!=|==?|le|ge|eq|ne|lt|gt/

  additive_expr: multiplicative_expr
               (additive_op multiplicative_expr { [ @item[1..2] ] })(s
+?)
               { [  $item[1], map { @ $_ } @{$item[2]} ] }
  additive_op: /[+-]/

  multiplicative_expr: modulus_expr
               (multiplicative_op modulus_expr { [ @item[1..2] ] })(s?
+)
               { [  $item[1], map { @ $_ } @{$item[2]} ] }
  multiplicative_op: /[*\/]/

  modulus_expr: paren_expr
               ('%' paren_expr { [ @item[1..2] ] })(s?)
               { [  $item[1], map { @ $_ } @{$item[2]} ] }


  paren_expr: '(' comparison_expr ')' { $item[2] }
            | number

  number: /[+-]?\d+/ { $item[1] }

[download]

                - Ant
                - Some of my best work - (1 2 3)

Replies are listed 'Best First'.
Re^3: Order of Precedence in Parse::RecDescent grammar
by blokhead (Monsignor) on Jun 01, 2005 at 18:21 UTC
    That's another reason why it's simpler to have just binary operations at each level (instead of a longer sequence of same-precedence operations). ;)

    Consider the generic outline: 

    lower_prec_expr : higher_prec_expr lower_prec_op lower_prec_expr
                | higher_prec expr

    [download]
    The problem is that you want your parse to give different semantic values for the different branches. If you take the 2nd branch, it's just a "pass-through" of the semantic value and you don't want to construct a new arrayref around it. If you take the first branch where there is actually an operation, you need to construct an arrayref with the appropriate things.

    You've combined both of these branches into one production in the grammar like this: 

    lower_prec_expr : higher_prec_expr (lower_prec_op lower_prec_expr)(s?)
                      { [ "put stuff in arrayref" ] }

    [download]
    So now you're putting things inside an arrayref even in the "pass-through" case, where there is no operator at this point in the parse.

    To fix this, put a conditional in your semantic rule to distinguish these cases, i.e: 

    lower_prec_expr : higher_prec_expr (lower_prec_op lower_prec_expr)(s?)
                      { @{$item[2]} ? [ ... ] : $item[1] }

    [download]
    That's kinda nasty. Alternatively, have two different productions explicitly in the grammar: 
    lower_prec_expr : higher_prec_expr (lower_prec_op lower_prec_expr)(s)
                      { [ ... ] }
                | higher_prec_expr

    [download]
    I.e, if there *are* operators here (no question mark on the (s) quantifier), we build an arrayref for the semantic value with the first branch. Otherwise, the second branch has no semantic rule, so it's just a "pass-through" of the semantic value and does not add layers of arrayref.

    The latter is probably the best choice. Just change the (s?)'s to (s)'s and add the other alternation to the grammar.

    blokhead

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom