Skip Menu |
 

This queue is for tickets about the Regexp-Grammars CPAN distribution.

Report information
The Basics
Id: 49455
Status: open
Priority: 0/
Queue: Regexp-Grammars

People
Owner: Nobody in particular
Requestors: mschwern [...] cpan.org
Cc:
AdminCc:

Bug Information
Severity: Important
Broken in: (no value)
Fixed in: 1.001005



Subject: Wrong answer from the calculator example
Download (untitled) / with headers
text/plain 216b
Using the simple calculator example in the docs on this: 2*6/4^2*4/3 gave the incorrect answer, 0.5625 instead of 1. Test is attached. I don't see an obvious fault in the calculator grammar. (Its also really slow)
Subject: pemdas
Download pemdas
application/text 1.5k

Message body not shown because it is not plain text.

Subject: Re: [rt.cpan.org #49455] Wrong answer from the calculator example
Date: Sun, 6 Sep 2009 16:27:02 +1000
To: bug-Regexp-Grammars [...] rt.cpan.org
From: Damian Conway <damian [...] conway.org>
Download (untitled) / with headers
text/plain 798b
Show quoted text
> Using the simple calculator example in the docs on this: 2*6/4^2*4/3 > gave the incorrect answer, 0.5625 instead of 1.  Test is attached.
The problem is that it's treating exponentiation as a left-associative operator. The fix is to replace the rule with: <rule: Pow> <[Term]> ** \^ <MATCH= (?{ my $exp = pop @{$MATCH{Term}}; $exp = $_ ** $exp for @{$MATCH{Term}}; $exp; })> | <MATCH=Term> Show quoted text
> (Its also really slow)
Welcome to the limitations of recursive descent. :-( Hint: try adding a <debug:run> directive at the start of grammar, to see how much trial and error the grammar requires on nested constructs. Damian
From: gelbman [...] gmail.com
Download (untitled) / with headers
text/plain 2.4k
Im going to have to disagree with that fix. Actually, the pow rule was working correctly. The other rules are causing the calculator to fail because they need to reduce left to right, but the thing with recursive descent parsers is that they cant reduce into itself without causing an infinite loop, so you have to use the list quantifier, but not in the way shown above (which is neither reducing left or right). So what was really happening before in parsing 2*6/4^2*4/3 was this: 2*(6/(4^2*(4/3))) But it really should have been doing this: (((2*6)/4^2)*4)/3 or, more simply, 2-1+1 was becoming 2-(1+1) instead of (2-1)+1 Heres a fix: --- rgcalc.was.pl 2010-11-07 17:05:11.845642063 -0500 +++ rgcalc.pl 2010-11-07 17:03:26.794142189 -0500 @@ -4,26 +4,40 @@ my $calculator = do{ use Regexp::Grammars; qr{ <Answer> <rule: Answer> - <X=Mult> \+ <Y=Answer> - <MATCH= (?{ $MATCH{X} + $MATCH{Y} })> - | <X=Mult> - <Y=Answer> - <MATCH= (?{ $MATCH{X} - $MATCH{Y} })> - | - <MATCH=Mult> + <[Subt]> ** \+ + <MATCH= (?{ + my $val = shift @{$MATCH{Subt}}; + $val += $_ for @{$MATCH{Subt}}; + $val; + })> + + <rule: Subt> + <[Mult]> ** - + <MATCH= (?{ + my $val = shift @{$MATCH{Mult}}; + $val -= $_ for @{$MATCH{Mult}}; + $val; + })> <rule: Mult> - <X=Pow> \* <Y=Mult> - <MATCH= (?{ $MATCH{X} * $MATCH{Y} })> - | <X=Pow> / <Y=Mult> - <MATCH= (?{ $MATCH{X} / $MATCH{Y} })> - | <X=Pow> % <Y=Mult> - <MATCH= (?{ $MATCH{X} % $MATCH{Y} })> - | - <MATCH=Pow> + <[Divi]> ** \* + <MATCH= (?{ + my $val = shift @{$MATCH{Divi}}; + $val *= $_ for @{$MATCH{Divi}}; + $val; + })> + + <rule: Divi> + <[Pow]> ** / + <MATCH= (?{ + my $val = shift @{$MATCH{Pow}}; + $val /= $_ for @{$MATCH{Pow}}; + $val; + })> <rule: Pow> <X=Term> \^ <Y=Pow> <MATCH= (?{ $MATCH{X} ** $MATCH{Y}; })> |
Subject: Re: [rt.cpan.org #49455] Wrong answer from the calculator example
Date: Tue, 9 Nov 2010 06:40:21 +1100
To: bug-Regexp-Grammars [...] rt.cpan.org
From: Damian Conway <damian [...] conway.org>
Download (untitled) / with headers
text/plain 146b
Show quoted text
> Im going to have to disagree with that fix.
Thanks for pointing out the mistake. Much appreciated. I've fixed the example in the docs. Damian


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.