Bug #49455 for Regexp-Grammars: Wrong answer from the calculator example

Sun Sep 06 01:29:13 2009 mschwern [...] cpan.org - Ticket created

Subject:

Wrong answer from the calculator example

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.

Sun Sep 06 02:27:42 2009 damian [...] conway.org - Correspondence added

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>

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

Sun Sep 06 02:27:43 2009 The RT System itself - Status changed from 'new' to 'open'

Sun Nov 07 17:07:55 2010 gelbman [...] gmail.com - Correspondence added

From:

gelbman [...] gmail.com

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

Mon Nov 08 14:41:10 2010 damian [...] conway.org - Correspondence added

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>

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