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

[Gavin Lambert]

At 09:06 29/09/2007, Jeremy Sheldon wrote:
 >[14:00:29] Aborting because the following rules are mutually
 >left-recursive:
 >    [table_reference]
 >    [non_join_query_term]
[...]
 >This leads me to believe that table_reference and
 >non_join_query_term are not mutually left-recursive
 >with each other.  Would this assumption be correct?

Kind of.  They're not recursive with each other, but they are 
recursive with themselves.

 >Here are the rules themselves:
 >
 >table_reference
 >	: table_name  correlation_specification?
 >	| derived_table correlation_specification
 >	| (table_reference CROSS JOIN table_reference
 >	| table_reference NATURAL? join_type? JOIN table_reference
 >join_specification?
 >	| LEFT_PAREN joined_table RIGHT_PAREN);

See, in table_reference you've got two alternatives that start 
with table_reference itself.  You can't do that in LL(*), since it 
leads to an infinite loop.  (It's ok to refer to the same rule 
away from the left edge, because it will consume some tokens each 
time and will eventually exit.  But on the left edge it can keep 
recursing in infinitely since it doesn't consume anything 
beforehand.)

(I'm also not sure why you've grouped the last three alts together 
as a single bigger alt of the main rule body.  That won't have any 
effect as far as I can tell.  And I don't know what 
join_specification contains, but by putting it after the 
table_reference like that it can end up pretty far away from the 
JOIN keyword that it's actually applying to.  Are you sure that's 
where it's supposed to go?)

You'll need to resolve this by creating another rule that contains 
only a subset of the alternatives, avoiding the recursion, or 
rearrange the rule structure so that you can put a * loop in a 
strategic place.  Or both :)  For example, this ought to work in 
this case (although it will alter the meaning subtly, so test it):

table_reference
   : table_ref_atom (NATURAL? join_type? JOIN table_ref_atom 
join_specification?)*
   ;

table_ref_atom
   : table_name correlation_specification?
   | derived_table correlation_specification
   | LEFT_PAREN joined_table RIGHT_PAREN
   ;

(Assuming you add CROSS to join_type.  And shouldn't NATURAL be 
part of join_type too?)

Alternatively, if you don't want to change the behaviour of the 
CROSS JOIN matching, then this ought to work too:

table_reference
   : table_ref_atom
     ( CROSS JOIN table_reference
     | NATURAL? join_type? JOIN table_reference 
join_specification?
     )?
   ;

table_ref_atom
   : table_name correlation_specification?
   | derived_table correlation_specification
   | LEFT_PAREN joined_table RIGHT_PAREN
   ;

Note that this uses right-recursion, which is ok.