# New Ticket Created by Patrick R. Michaud
# Please include the string: [perl #36452]
# in the subject line of all future correspondence about this issue.
# <URL: https://rt.perl.org/rt3/Ticket/Display.html?id=36452 >
On Thu, Jun 30, 2005 at 02:56:27PM -0400, Will Coleda wrote:
> Attempting to come up with a simplistic math grammar that has one possible
> operand (A) and one possible operator (*) - so that things like A, A*A, and
> A*A*A*A*A are all parsed. This simplistic example (thanks to spinclad on
> #perl6) cause PGE to explode.
>
> $ cat ta.p6r
> grammar f;
> rule atom { A }
> rule binary { <expr> \* <atom> }
> rule expr { <binary> }
> $ ./parrot compilers/pge/demo.pir
Well.... yes, of course, since there's a left-recursive rule there it's
very likely to explode. (f::expr calls <binary>, which calls <expr>,
which calls <binary>, which calls <expr>, which calls <binary>, which ... )
It's basically the same as what one would get from doing
sub binary { expr(); atom(); }
sub expr { binary(); }
and I'm not sure PGE should be responsible -- at least not yet --
for trapping such infinite loops.
If you rewrite the grammar to be right-recursive I think you'll
find it works fine:
grammar f;
rule atom { A }
rule binary { <atom> \* <expr> }
rule expr { <binary> }
> Also, $ ./parrot compilers/pge/demo.pir
> ...
> input "rule <pattern>", "glob <pattern>", "save <name>",
> target string, "pir", "exp", "trace", "next", or "use <file>"
> rule <f::expr>
>
> input "rule <pattern>", "glob <pattern>", "save <name>",
> target string, "pir", "exp", "trace", "next", or "use <file>"
> A
Well, "A" isn't a valid match for f::expr in the grammar you've
provided -- the f::expr rule calls <binary>, which absolutely
requires at least one \* . If you want to match "A", "A*A", "A*A*A",
etc., I suggest:
grammar f;
rule atom { A }
rule binary { <atom> [ \* <atom> ]? }
rule expr { <binary> }
which eliminates the recursion altogether as well as recognizing a
single <atom> as a valid expression.
Pm
