| Subject: | Improvements to left recursion detection |
Attached is a patch against 1.965001 that significantly improves left
recursion detection.
Given the grammar:
<autostub>
direct: direct
second: a(s?) second
third : b(s?) c(?) third
fourth: <leftop: a /,/ b>(s?) fourth
fifth : <leftop: fifth /,/ b>
# mutually recursive
recurse1 : b(?) recurse2
recurse2 : a(?) recurse1
# these better not be tagged
okay1 : a okay1
okay2 : <leftop: a /,/ okay2>(s?) b okay2
okay3 : a(..5) okay3
__END_GRAMMAR__
Output is:
ERROR: Rule "direct" is left-recursive.
(Hint: Set $::RD_HINT (or -RD_HINT if you're using "perl -s")
for hints on fixing these problems.)
ERROR: Rule "second" is left-recursive.
(Hint: Set $::RD_HINT (or -RD_HINT if you're using "perl -s")
for hints on fixing these problems.)
ERROR: Rule "fifth" is left-recursive.
(Hint: Set $::RD_HINT (or -RD_HINT if you're using "perl -s")
for hints on fixing these problems.)
ERROR: Rule "third" is left-recursive.
ERROR: Rule "recurse2" is left-recursive.
ERROR: Rule "recurse1" is left-recursive.
ERROR: Rule "fourth" is left-recursive.
(Hint: Set $::RD_HINT (or -RD_HINT if you're using "perl -s")
for hints on fixing these problems.)
| Subject: | left_recursion_detection.patch |
*** RecDescent.pm.orig 2010-11-10 19:09:38.817613072 -0500
--- RecDescent.pm 2010-11-10 19:10:35.075602785 -0500
*************** sub Precompile
*** 82,87 ****
--- 82,88 ----
print OUT "my ";
require Data::Dumper;
+ local $Data::Dumper::Indent = 1;
print OUT Data::Dumper->Dump([$self], [qw(self)]);
print OUT "}";
*************** sub leftmostsubrule($)
*** 542,554 ****
{
my $self = shift;
! if ( $#{$self->{"items"}} >= 0 )
! {
! my $subrule = $self->{"items"}[0]->issubrule();
! return $subrule if defined $subrule;
}
! return ();
}
sub checkleftmost($)
--- 543,558 ----
{
my $self = shift;
! my @ret_subrules;
! my $item;
! foreach $item (@{$self->{'items'}}) {
! my $subrule = (ref($item) =~ /\AParse::RecDescent::Operator/) ?
! $item->{'leftarg'}->issubrule() : $item->issubrule();
! push(@ret_subrules, $subrule) if defined $subrule;
! last unless (defined($item->{'min'}) && $item->{'min'} == 0)
}
! return @ret_subrules;
}
sub checkleftmost($)
*************** sub checkleftmost($)
*** 571,576 ****
--- 575,581 ----
}
elsif (@items==1 && ($items[0]->describe||"") =~ /<rulevar|<autoscore/)
{
+ return 0;
# Do nothing
}
elsif (@items &&