[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