ANTLR4 - Eliminate indirect mutually left-recursive set of rules

Question

I'm writing a grammar for the language LUA using Antlr sintaxe, but I'm getting a mutual left recursion error between exp_prefixo, variavel and chamada_de_funcao. I read a lot of solutions given in other posts, but couldn't make it work for my specific case, since most of them are direct recursions or have only two mutually recursive rules.

Here are the mutually left-recursive set of rules:

exp_prefixo
            :       variavel
                    | chamada_de_funcao
                    | '(' expressao ')' 
            ;

chamada_de_funcao
            :       exp_prefixo args
                    | exp_prefixo ':' NOME args
            ;
variavel
            :       NOME 
                    | exp_prefixo '[' expressao ']'
                    | exp_prefixo '.' NOME
            ;

And this is my grammar file:

programa
            :       trecho
            ;

trecho
            :        (comando (';')?)* (ultimo_comando (';')?)?
            ;

bloco
            :       trecho
            ;

comando
            :       lista_variaveis '=' lista_expressoes
            |       chamada_de_funcao
            |       'do' bloco 'end'
            |       'while' expressao 'do' bloco 'end'
            |       'repeat' bloco 'until' expressao
            |       'if' expressao 'then' bloco ('elseif' expressao 'then' bloco)* ('else' bloco)? 'end'
            |       'for' NOME '=' expressao ',' expressao (',' expressao)? 'do' bloco 'end'
            |       'for' lista_de_nomes 'in' lista_expressoes 'do' bloco 'end'
            |       'function' nome_da_funcao corpo_da_funcao
            |       'local' 'function' NOME corpo_da_funcao
            |       'local' lista_de_nomes ('=' lista_expressoes)?
            ;

ultimo_comando
            :       'return' (lista_expressoes)? 
                    | 'break'
            ;

nome_da_funcao
            :       NOME ('.' NOME)* (':' NOME)?
            ;

lista_variaveis
            :       variavel (',' variavel)*
            ;

variavel
            :       NOME 
                    | exp_prefixo '[' expressao ']'
                    | exp_prefixo '.' NOME
            ;

lista_de_nomes
            :        NOME (',' NOME)*
            ;

lista_expressoes
            :       (expressao ',')* expressao
            ;

expressao
            :       'nil'
                    | 'false' 
                    | 'true'
                    | NUMERO 
                    | CADEIA 
                    | '...'
                    | funcao
                    | exp_prefixo
                    | construtor_tabela
                    | expressao opbin expressao
                    | opunaria expressao
            ;

exp_prefixo
            :       variavel
                    | chamada_de_funcao
                    | '(' expressao ')' 
            ;

chamada_de_funcao
            :       exp_prefixo args
                    | exp_prefixo ':' NOME args
            ;

args 
            :       '(' (lista_expressoes)? ')' 
                    | construtor_tabela 
                    | CADEIA
            ;

funcao
            :       'function' corpo_da_funcao
            ;

corpo_da_funcao
            :       '(' (lista_par)? ')' bloco 'end'
            ;

lista_par
            :       lista_de_nomes (',' '...')? 
                    | '...'
            ;

construtor_tabela
            :       '{' (lista_de_campos)? '}'
            ;

lista_de_campos
            :       campo (separador_de_campos campo)* (separador_de_campos)?
            ;

campo
            :       '[' expressao ']' '=' expressao 
                    | NOME '=' expressao 
                    | expressao
            ;

separador_de_campos
            :       ',' 
                    | ';'
            ;

opbin
            :       '+' 
                    | '-' 
                    | '*' 
                    | '/' 
                    | '^' 
                    | '%' 
                    | '..' 
                    | '<' 
                    | '<=' 
                    | '>' 
                    | '>=' 
                    | '==' 
                    | '~=' 
                    | 'and' 
                    | 'or'
            ;

opunaria
            :       '-' 
                    | 'not' 
                    | '#'
            ;

Could anyone give some tips with some initial step-by-step on how to eliminate this error? I already understood the "theoretical" problem. I'm really struggling to implement a solution.

Thanks!

Answer 1

To solve indirect recursions you usually replace the invocation of a rule by the rule code itself. This will ultimately lead to a direct left recursion (and potentially quite messy grammar rules). Like:

a: b | A;
b: c | B;
c: a | C;

Replacing c:

a: b | A;
b: a | C | B;

Replacing b:

a: a | C | B | A;

Now start from here and refactor a in a way which keeps all left recursive rules in a and move the rest into subrules (if desired).

Another option to solve the issue is to stare a while at the rules until you find a way to formulate the grammar without a left recursion at all. Most of the time there are alternatives. Take expressions, which are often written like this:

expr:
    expr AND expr
    | expr OR expr
    | primary // There must be at least one non-recursive alt.
;

and so on.

This can be formulated non-recursively:

expr:
    andExpr
    | primary
;
andExpr: orExpr AND orExpr;
orExpr: ... OR ...;

etc. This way also makes operator precedence more obvious, but might change precedence slightly, depending on how the transformation was done.