[antlr-interest] Problem writing a Grammar

Johannes Luber jaluber at gmx.de
Fri May 4 04:33:39 PDT 2007


lists at mainiero.de wrote:
> Hi,
> 
> I'm trying to write a ANTLR grammar for Lua (www.lua.org). They have the
> syntax on the documentation pages, an I stated just copying this int
> ANTLRWorks and changing the syntax accordingly.
> It looked like a walk-trough but i got struggled as ANTLRWorks reported
> this in its console
> 
> Aborting because the following rules are mutually left-recursive:
>     [functioncall, prefixexp, var]
> 
> Perhaps anyone can have a look at it to give me hints or solutions how
> to get this grammar correct. I'm willing to donate this grammar, to
> make it available on the ANTLR side.
> 
> Thanks
> 
> Nicolai Mainiero

Left recursion means that the rule is in referenced in one of its
productions at the left edge. Look at the following example:

constructor_modifiers
   :   constructor_modifier
   |   constructor_modifiers   constructor_modifier
   ;

LL-Parsers like ANTLR end up in an infinite loop because of the way they
recognize grammars. The solution is to change the grammar. For the example:

constructor_modifiers
   :   constructor_modifier*
   ;

The problem in your grammar is a bit more complicated:

var has the left-edge production prefixexp. prefixexp has the left-edge
production var. Recursion loop 1.

functioncall has the left-edge production prefixexp. prefixexp has the
left-edge production functioncall. Recursion loop 2. (Interestingly,
both loops can be even combined to form a bigger one.)

Unfortunately I have no idea how the equivalent grammar change has to be
in your case, especially as I don't know Lua. Maybe Terence or someone
else more knowledgeable can help with that problem.

Best regards,
Johannes Luber


More information about the antlr-interest mailing list