[antlr-interest] A rule can be mutually left-recursive with itself?

[Gavin Lambert]

At 12:14 29/09/2007, Jeremy Sheldon wrote:
 >I'm still parsing the rest of your email.  In the meantime,
 >however, a question comes to mind.  You say that they're
 >recursive with themselves, yet Antlrworks does not detect
 >them as being left-recursive.  As well, the refactoring tool
 >for removing left-recursions will not refactor this rule.
 >Does this mean that being 'recursive with themselves' is
 >different than being 'left-recursive'?  Or does this mean
 >that they are left-recursive but in a way which is
 >unrecognized by Antlrworks?

A bit of both :)

"Recursive with itself" (or "self-recursive") simply means that 
the rule calls itself directly (as opposed to "recursive with 
another rule" (or "indirectly recursive") which means that it 
(directly or indirectly) calls another rule which calls the 
original rule.  This is not actually a problem in itself, and is 
sometimes required for certain kinds of grammar -- often whenever 
you have equal-precedence operators, in fact.

"Left recursive" means that the rule (whether directly or 
indirectly) ends up calling itself again without consuming any 
tokens.  If this path exists, it means that it will be able to 
continue doing so infinitely, since it never consumes any input 
and thus is completely unbounded (at least until you run out of 
stack space).  This is strictly forbidden -- but even ANTLR can't 
always detect when you're doing it.

ANTLRworks' recursion detection and refactoring only really work 
on simple cases; it's not too hard to create a construct that it 
can't figure out.  That doesn't mean it's not left-recursive, it 
just means that it can't help you solve it automatically.  The 
auto-refactoring version always translates the recursion to 
something involving a * case (similar to the first example I 
posted) -- but with your grammar it's not possible to do that 
without changing the behaviour of the parser, which a refactoring 
shouldn't do.  So it's not surprising that it didn't offer to fix 
it for you :)  (The second example should keep the same behaviour 
as your original design, but again it's a little complicated for a 
little automated refactorer to figure out!)