Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

Eliminating the common prefix from a Parse::RecDescent rule

by ikegami (Pope)
on Aug 13, 2006 at 21:18 UTC ( #567116=note: print w/replies, xml ) Need Help??

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

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"; }

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

    Thank you


      You must check that nothing follows what sum matches.
      evaluate : sum /\Z/ { $item[1] } ->evaluate($expr)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://567116]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (6)
As of 2021-05-11 11:19 GMT
Find Nodes?
    Voting Booth?
    Perl 7 will be out ...

    Results (116 votes). Check out past polls.