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

[Chris Rebert]

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.

Thanks.

- Chris R.

Kay Roepke wrote:
> Hi Chris!
> 
> On 7. Sep 2006, at 6:54 Uhr, Chris Rebert wrote:
> 
>> "infinite recursion to rule expr from rule $some_grammar_production"
>>
>> when running ANTLR on it.
>> I think this has something to do with precedence in my grammar.
> 
> Actually, it has to do with the (non-immediate) left recursion involving 
> expr and type.
> I didn't check for other left recursion, but the same principle applies.
> 
> If you've got the Dragon Book (Compilers - Principles, Techniques, and 
> Tools by Aho et al) check out
> Chapter 2.4 Heading "Left Recursion", Chapter 2.5 and Chapter 4.3 
> "Elimination of Left Recursion". If you don't, get it ;)
> (Or look for those terms on Google, there should be a lot of material 
> available.)
> Anyway, here's the gist of it:
> 
> If you've got a rule like
>     expr : expr "+" term | term;
> it is left-recursive and cannot be recognized by a LL recursive-descent 
> parser like ANTLR. This is because
> expr would end up calling itself, being on the left edge of the rule, 
> endlessly and eventually you'd run out of
> stack space.
> A solution to this is to restructure like this:
>     expr : term expr_dash;
>     expr_dash : "+" term expr_dash | /* empty */;
> or alternatively without recursion:
>     expr : term ("+" term)*
> The problem with it is that + will not be left-associative anymore, but 
> instead right-associative, if you generate trees.
> Big Pain here. But you could stick the action inside the ("+" term)* 
> loop and calculate the value like this (as an example to achieve
> left-associativity, a bit contrived, but still ;) ):
>     expr : t:term {sum = $t.somehowGetValueHere(); }("+" t1:term { sum 
> += $t1.somehowGetValueHere();})*
> 
> In your case, you have the really nasty case of indirect left-recursion, 
> in that it takes a couple rule invocations to complete
> for the recursion to appear.
> This, naturally, is a bit more difficult to solve. I'm not gonna write 
> down the algorithm here, since it is available on the net (and I'm
> a lazy SOB and have a serious lack of coffee :)) See 
> http://web.cs.wpi.edu/~kal/courses/compilers/module2/mytopdown.html (at 
> the end of
> Section 2.1.2) for an example. This just popped out of Google, I'm sure 
> there are better presentations to be found (maybe even at wikipedia 
> *shudder*).
> 
>> I couldn't find any way to set the precedence of grammar rules like I
>> can in yacc in the docs.
>> If it's not possible to set precedence in this way, could someone advise
>> me (roughly) as to how I need to restructure my grammar?
> 
> As I outlined above, precedence in LL-grammars is determined with the 
> direction of recursion (right-recursion yields right-associativity).
> There is no mechanism to spell out precendence rules like in bison/yacc.
> Since left-recursion isn't possible, you'll have to hack around it 
> (unless Ter has a really smart idea *wink* ;))
> 
> Somehow this got more verbose than I intended it to be, but maybe it 
> will help and is not completely wrong, considering the aforementioned lack
> of fuel, err, coffee.
> 
> Good morning :),
> 
> -k
> --Kay Röpke <kroepke at classdump.org>
> classdump Software
> Key fingerprint = A849 0F2C C322 4022 379E  8661 7E1B FE0D 4CD2 A6D0
> 
> 
> 
>