[antlr-interest] newbie Q: infinite recursion in grammar

Kay Roepke kroepke at classdump.org
Thu Sep 7 21:57:04 PDT 2006


On 8. Sep 2006, at 2:16 Uhr, Chris Rebert wrote:

> Darn. Hmmm. In that case, could someone point me to a parser (if  
> any) that could parse this?
> Or does anyone else have some advice? I really would like to stick  
> with ANTLR if possible.
Hi Chris,

it isn't that bad, you only have to be aware of the fact. Also take a  
look at the mail by John yesterday.
Alternatively, I would suggest building trees and do your translation/ 
execution from that, after you fix up the tree (See [1] for a good  
abstract on
manually building trees with ANTLR).
Really take a look at the algorithm to remove non-immediate left- 
recursion [2]. It's not really intuitive at first, but
once you play around with a relatively simple example, you get the  
hang of it. Also, use ANTLRWorks to show you the tree that gets built.
And never underestimate the power of pen and paper! :)

[1] http://antlr.org/article/1137964510001/manual.tree.construction.txt
[2] Actually, in this case the wikipedia article <http:// 
en.wikipedia.org/wiki/Left_recursion> gives a pretty good picture of  
it. Who'd have thought?
     It even references a couple of papers that seems pretty good and  
also gives pictures of trees that should help. The second last  
external link
     is pretty much the stuff that's in the Dragon Book, FWIW.

Good luck!

-k
-- 
Kay Röpke <kroepke at classdump.org>
classdump Software
Key fingerprint = A849 0F2C C322 4022 379E  8661 7E1B FE0D 4CD2 A6D0





More information about the antlr-interest mailing list