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 - 消除間接相互左遞歸的一套規則

回答

相關問題