http://qs1969.pair.com?node_id=567116


in reply to Operator Associativity and Eliminating Left-Recursion in Parse::RecDescent

I made some rather major changes to the parent node. I'm creating this new node so people interested in the topic notice the change.

Most of the changes were made to improve clarity. Despite the scope of the changes, the node is very similar to it's previous incarnation. (That's why I didn't create a new node.)

The most important change is the new section discussing the elimination of the very inefficient duplication in rules such as 

pow : NUM '**' pow
    | NUM

[download]

In the spirit of the node in which it is contained, I refered to this as the "improving right-recursion", but the concepts can be applied to any rule with productions with a common prefix.

Replies are listed 'Best First'.
Re: Eliminating the common prefix from a Parse::RecDescent rule
by Dirk80 (Pilgrim) on Sep 02, 2010 at 22:27 UTC

    Thank you for this great tutorial. This was a very helpful introduction.

    I tried to play a bit with your example. In the following code I do not get the Error "Bad Expression" for my second expression although it is not valid.

    use strict;
use warnings;


use Parse::RecDescent ();

my $grammar = <<'__END_OF_GRAMMAR__';

   {
      use strict;
      use warnings;
   }


{
    sub eval_sum {
        my $acc = shift(@_);
        while (@_) {
            my $op = shift(@_);
            if    ($op eq '+') { $acc += shift(@_); }
            elsif ($op eq '-') { $acc -= shift(@_); }
        }
        return $acc;
    }
}

sum :  NUM sum_         { eval_sum( ($item[1], @{$item[2]}) ) }
sum_:  /[+-]/ NUM sum_  { $return = [$item[1], $item[2], @{$item[3]}] 
+}
      |                 { $return = [] }
NUM : /\d+/             { $return = $item[1] }

__END_OF_GRAMMAR__


my $parser = Parse::RecDescent->new($grammar)
   or die("Bad grammar\n");

foreach my $expr ('4-5+6-2','4*5')
{
    my $sum = $parser->sum($expr) or die "Bad expression";
    print "$sum" . "\n";
}

    [download]

    Why do I not get the "Bad expression" error for my second expression?

    Thank you

    Dirk

[reply]
[d/l]
      You must check that nothing follows what sum matches. 
      evaluate : sum /\Z/ { $item[1] }

->evaluate($expr)

      [download]
[reply]
[d/l]
[select]

In Section Tutorials