[antlr-interest] More Infinite Recursion
jbb at acm.org
jbb at acm.org
Thu Jan 29 20:24:01 PST 2004
Jason :-
You wrote:
>Imagine I've got the following rule:
>
>memory:
> A B
> |
> memory C D
> |
> E F G
> |
> H I J
> |
> memory K
> |
> memory L
> |
> M N O
> ;
>which of course has multiple instances of infinite
>recursion. I've got ALOT of rules like this and I'm
>converting them to something like this:
>memory:
> (AB | EFG | HIJ | MNO) (CD)* (K)* (L)*
> ;
I think your rule should be:
memory:
( A B | E F G | H I J | M N O ) ( C D | K | L )+
;
consider the string: A B K C D K L C D L K
your original, left-recursive, rule will accept this string;
while your translation will not.
try this:
1) rearrange terms
memory:
( A B | E F G | H I J | M N O )
| memory C D
| memory K
| memory L
;
2) left factor second thru last alternatives
memory:
( A B | E F G | H I J | M N O )
| memory ( C D | K | L )
;
and now I hope you can see that the rule I suggest works better...
Hope this helps
-jbb
Yahoo! Groups Links
To visit your group on the web, go to:
http://groups.yahoo.com/group/antlr-interest/
To unsubscribe from this group, send an email to:
antlr-interest-unsubscribe at yahoogroups.com
Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list