[antlr-interest] Left recursion removal

[Gavin Lambert]

At 10:00 8/05/2007, Johannes Luber wrote:
 >I'm at a bit of loss here. I have tried to reform some mutually
 >left ecursive rules in my C# grammar and got down from 
originally
 >7 rules to 2 through inlining, as Gavin Lambert suggested in
 >another email (hopefully I didn't interpret it wrong). The two
 >rules are:
 >
 >
 >primary_expression
 >    :    (array_creation_expression
 >         |    literal
 >         |    simple_name
[...]
 >
 >element_access
 >    :    literal
 >    |    simple_name
[...]
 >
 >The problem is that I can't figure out how to merge both rules 
into
 >one.
 >Simple inlining requires parentheses over the whole 
subexpression
 >and prevents ANTLRworks to remove the last left recursion. And 
because
 >everywhere where one rule references the other rule there is 
some
 >trailing I can't remove the parentheses without changing the
 >grammar.

The first thing I'd do is to try extracting common 
subexpressions.  For example, just in the snippet I quoted above 
you can see that both rules accept either 'literal' or 
'simple_name', so you can create a third rule (as 'literal | 
simple_name') and reference that rule in place of those two 
alternatives.

Keep moving any alts that are completely common to both rules into 
this new rule, and eventually you should be left with much shorter 
rules that contain only the points of difference.  From there it 
should be easier to see how things need to be rearranged.

And yes, there are cases that the ANTLRworks recursion remover 
can't cope with at the moment; although usually you can rearrange 
and extract your way to something it can deal with, sometimes 
you'll just have to resolve it on your own.