ANTLR4

Question

我正在使用 Antlr sintaxe 为语言 LUA 编写语法，但在 exp_prefixo、variavel 和 [=14= 之间出现相互左递归错误].我阅读了很多其他帖子中给出的解决方案，但无法使其适用于我的具体情况，因为它们中的大多数都是直接递归或只有两个相互递归规则。

下面是相互左递归的规则集：

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
            ;

这是我的语法文件：

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' 
                    | '#'
            ;

任何人都可以提供一些关于如何消除此错误的初始分步提示吗？我已经理解了 "theoretical" 问题。我真的很难实施解决方案。

谢谢！

Answer 1

要解决间接递归，您通常会用规则代码本身替换对规则的调用。这最终将导致 direct 左递归（以及可能相当混乱的语法规则）。喜欢：

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

正在替换 c：

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

正在替换 b：

a: a | C | B | A;

现在从这里开始重构 a，将所有左递归规则保留在 a 中，并将其余的移入子规则（如果需要）。

解决问题的另一种选择是盯着规则看一会儿，直到找到一种完全不用左递归来制定语法的方法。大多数时候都有其他选择。取表达式，经常这样写：

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

等等。

这可以用非递归的方式表述：

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

等这种方式也使运算符优先级更加明显，但可能会略微改变优先级，具体取决于转换的完成方式。

ANTLR4 - 消除间接相互左递归规则集

ANTLR4 - Eliminate indirect mutually left-recursive set of rules

recursion

antlr

grammar

left-recursion