[antlr-interest] Help with mutually left-recursion

[John B. Brodie]

on Tue, 09 Jan 2007 10:14:06, Nicolai Mainiero asked:
>Hello,

Hi!

>I try to write a grammar for Lua and have a problem with mutually  
>left-recursion in the grammar definition. Here ist the section from  
>the grammar so far.

i do not know Lua so the following is probably bogus, but here is what
i did to remove the left recursion (using antlr 3.0b5):

//----------begin lua.g----------
grammar lua;

start : prefixexp EOF ;

// original rules:
//prefixexp    : '('exp')' | var | functioncall ;
//functioncall : prefixexp args | prefixexp ':' NAME args ;
//var          : NAME | prefixexp '['exp']' | prefixexp '.' NAME ;

// step 1: left factor var and functioncall
//prefixexp    : '('exp')' | var  | functioncall ;
//functioncall : prefixexp (':' NAME)? args ;
//var          : NAME | (prefixexp ('['exp']' | '.' NAME)) ;

// step 2: collapse into a single rule.
//prefixexp
//    : '('exp')'
//    | NAME | (prefixexp ('['exp']' | '.' NAME)) /*var*/
//    | prefixexp (':' NAME)? args /*functioncall*/
//    ;

// step 3: re-arrange and left factor again
//prefixexp
//    : ( '('exp')' | NAME )
//    | prefixexp ( '['exp']' | '.' NAME | (':' NAME)? args )
//    ;

// step 4: remove left recursion
prefixexp
    : ( '('exp')' | NAME )
        ( '['exp']' | '.' NAME | (':' NAME)? args )*
    ;

exp : 'exp' ;
args : 'args' ;

NAME : 'name' ;
//----------end lua.g----------

hope this helps...
   -jbb