Ajuda com Shift / Reduzir conflito - Tentando modelo (X A) * (X B) *

Question

Im tentando modelar a expressão EBNF

("declare" "namespace" ";")* ("declare" "variable" ";")*

Eu construí o yacc (Im usando MPPG) gramática, que parece representar isso, mas ele não consegue corresponder a minha expressão de teste.

O caso de teste eu estou tentando jogo é

declare variable;

O fluxo de token do lexer é

KW_Declare
KW_Variable
Separator

A análise gramática diz que há um "Shift / reduzir conflitos, estado 6 na KW_Declare". Tentei resolver isso com "% esquerda PrologHeaderList PrologBodyList", mas nem solução funciona.

Program                     : Prolog;
Prolog                      : PrologHeaderList PrologBodyList;

PrologHeaderList            : /*EMPTY*/
                            | PrologHeaderList PrologHeader;
PrologHeader                : KW_Declare KW_Namespace Separator;

PrologBodyList              : /*EMPTY*/
                            | PrologBodyList PrologBody;
PrologBody                  : KW_Declare KW_Variable Separator;

KW_Declare KW_Namespace KW_Variable Separator são todas as fichas com valores de "declarar", "naemsapce", "variável", ";"

.

Answer 1

Tem sido um longo tempo desde que eu tenho qualquer coisa usada yacc-like, mas aqui estão algumas sugestões que podem ou não ajuda.

Parece que você precisa de um lookahead 2 em token nesta situação. O analisador fica para a última PrologHeader , e tem que decidir se a próxima construção é a PrologHeader ou PrologBody , e ele não pode dizer que a partir do KW_Declare. Se há uma directiva para aumentar lookahead nesta situação, ele provavelmente irá resolver o problema.

Você também pode introduzir contexto em suas ações: em vez de definir PrologHeaderList e PrologBodyList , definir PrologRuleList e ter as ações lançar um erro se um cabeçalho aparece depois de um corpo. Feio, mas às vezes você tem que fazê-lo:. O que parece simples, em uma gramática pode não ser simples no analisador gerado

Uma abordagem hackish seria combinar os sinais: em vez de KW_Declare e KW_Variable , ter o seu lexer reconhecer o espaço e uso KW_Declare_Variable . Uma vez que ambos são palavras-chave, você não vai ter problemas namespace colisão.

Answer 2

A gramática no topo é regular assim IIRC você pode traçar-lo como um DFA (ou um NDA e convertê-lo para um DFA) e, em seguida, converter o DFA para uma gramática. É de feijão de um tempo, então eu vou deixar o trabalho como um exercício para o leitor.