ANTLR4 - 消除间接相互左递归的一套规则

我正在写一本语法使用ANTLR的sintaxe语言LUA，但我越来越exp_prefixo，variavel和chamada_de_funcao之间的相互左递归误差。我阅读了其他帖子中给出的很多解决方案，但无法使其适用于我的具体情况，因为其中大多数都是直接递归或只有两个相互递归的规则。ANTLR4 - 消除间接相互左递归的一套规则

这里是相互左递归的一套规则：

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

谁能给一些初步的一步一步的一些技巧如何消除这个错误？我已经理解了“理论”问题。我非常努力地实施解决方案。

谢谢！

来源

2017-05-26 user3624492

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

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 ...;

等等。这样也使得运算符优先级比较明显，但可能会稍微改变优先级，这取决于改造是怎么做的。

来源

2017-05-27 09:34:07

ANTLR4 - 消除间接相互左递归的一套规则

回答

相关问题