ANTLR4 — исключить непрямой взаимно леворекурсивный набор правил

Я пишу грамматику для языка LUA, используя синтаксис Antlr, но я получаю ошибку взаимной левой рекурсии между exp_prefixo, variavel и chamada_de_funcao. Я прочитал много решений, приведенных в других сообщениях, но не смог заставить его работать для моего конкретного случая, поскольку большинство из них являются прямыми рекурсиями или имеют только два взаимно рекурсивных правила.

Вот взаимно леворекурсивный набор правил:

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

Может ли кто-нибудь дать несколько советов с некоторыми начальными шагами о том, как устранить эту ошибку? Я уже понял "теоретическую" проблему. Я действительно изо всех сил пытаюсь реализовать решение.

Спасибо!


antlr antlr4 recursion grammar left-recursion
person user3624492    schedule 26.05.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Для решения косвенных рекурсий вы обычно заменяете вызов правила самим кодом правила. В конечном итоге это приведет к прямой левой рекурсии (и, возможно, довольно запутанным правилам грамматики). Нравится:

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

и т. д. Этот способ также делает приоритет оператора более очевидным, но может немного изменить приоритет, в зависимости от того, как было выполнено преобразование.

person Mike Lischke    schedule 27.05.2017
comment
Я не понимаю, можно сформулировать нерекурсивно? что, если мой orExpr должен иметь другой orExpr? учитывая приведенную выше грамматику, я не вижу способа? как сделать например: expr or expr or expr ? - person user1870400; 12.02.2020
comment
Пожалуйста, задайте отдельный вопрос по вашей проблеме и подробно объясните, что у вас не работает. - person Mike Lischke; 12.02.2020
comment
stackoverflow.com/questions/60186343/ - person user1870400; 12.02.2020