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

[Kay Roepke]

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