[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