Aiuto con Shift / ridurre il conflitto - Cercando di modellare (X A) * (X B) *

Question

Nel tentativo di modellare l'espressione EBNF

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

Ho costruito il yacc (Im usando MPPG) grammatica, che sembra rappresentare questo, ma non riesce a soddisfare la mia espressione di prova.

Il caso di test che sto cercando di abbinare è

declare variable;

Il flusso di token dal lexer è

KW_Declare
KW_Variable
Separator

Il parse grammatica dice che c'è un "Shift / ridurre i conflitti, stato 6 su KW_Declare". Ho cercato di risolvere questo problema con "% lasciato PrologHeaderList PrologBodyList", ma nessuno dei due soluzione funziona.

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 separatore sono tutti i token con valori "dichiarare", "naemsapce", "variabile", ""

.

Answer 1

E 'passato molto tempo da quando ho usato nulla di yacc-like, ma qui ci sono un paio di suggerimenti che possono o non possono aiutare.

Sembra che avete bisogno di un lookahead 2-token in questa situazione. Il parser arriva all'ultima PrologHeader , e deve decidere se il prossimo costrutto è un PrologHeader o PrologBody , e non può dire che dal KW_Declare. Se c'è una direttiva per aumentare lookahead in questa situazione, probabilmente risolvere il problema.

Si potrebbe anche introdurre contesto nelle vostre azioni: invece di definire PrologHeaderList e PrologBodyList , definire PrologRuleList e hanno le azioni gettare un errore se un'intestazione appare dopo un corpo. Brutto, ma a volte bisogna farlo:. Ciò che appare semplice in una grammatica non può essere semplice nel parser generato

Un approccio hacker potrebbe essere quella di combinare i gettoni: invece di KW_Declare e KW_Variable , avere il vostro lexer riconoscere lo spazio e usare KW_Declare_Variable . Dal momento che entrambi sono parole chiave, non stai andando a correre in problemi namespace di collisione.

Answer 2

La grammatica in alto è regolare in modo IIRC è possibile tracciare fuori come un DFA (o di una NDA e convertirlo in un DFA) e poi convertire il DFA per una grammatica. E 'di fagioli un po' così lascio il lavoro come esercizio per il lettore.