Il cambio riduce il conflitto
https://stackoverflow.com/questions/196179
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto riscontrando un problema nel comprendere lo spostamento / riduzione del conflitto per una grammatica che so non avere ambiguità. Il caso è uno del tipo if else, ma non è il problema "dangling else" poiché ho clausole END obbligatorie che delimitano i blocchi di codice.
Ecco la grammatica di gppg (è un compilatore di compilatori simili a Bison ... e che non era un'eco):
%output=program.cs
%start program
%token FOR
%token END
%token THINGS
%token WHILE
%token SET
%token IF
%token ELSEIF
%token ELSE
%%
program : statements
;
statements : /*empty */
| statements stmt
;
stmt : flow
| THINGS
;
flow : '#' IF '(' ')' statements else
;
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Ecco l'output del conflitto:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 10: else -> elseifs
Shift "'#'": State-22 -> State-23
Items for From-state State 22
10 else: elseifs .
-lookahead: '#', THINGS, EOF
11 elseifs: elseifs . '#' ELSEIF statements else
Items for Next-state State 23
11 elseifs: elseifs '#' . ELSEIF statements else
// End conflict information for parser
Ho già cambiato tutto e so come risolverlo, ma quella soluzione implica rinunciare alla ricorsione a sinistra su "elseif" per una ricorsione a destra.
Ho esaminato tutta la scarsa documentazione che ho trovato su Internet riguardo a questo problema (inserisco alcuni link alla fine) e non ho ancora trovato una soluzione elegante. Conosco ANTLR e non voglio considerarlo in questo momento. Limitare la soluzione ai parser Yacc / Bison.
Gradirei soluzioni eleganti, sono riuscito a farlo eliminando le regole / * empty * / e la duplicazione di tutto ciò che necessitava di un elenco vuoto ma nella grammatica più ampia su cui sto lavorando finisce solo come "sindrome grammaticale sparghetti".
Ecco alcuni link:
http://nitsan.org/~maratb/cs164/bison.html
http://compilers.iecc.com/comparch/article/98- 01-079
Soluzione
La tua regola ELSEIF rivista non ha marcatori per una condizione - dovrebbe essere nominalmente '(' e ')' aggiunti.
Più seriamente, ora hai una regola per
elsebody : else
| elseifs else
;
e
elseifs : /* Nothing */
| elseifs ...something...
;
Il 'nulla' non è necessario; è implicitamente curato dall '"altro" senza gli "altri".
Sarei molto propenso a usare le regole 'opt_elseifs', 'opt_else' e 'end':
flow : '#' IF '(' ')' statements opt_elseifs opt_else end
;
opt_elseifs : /* Nothing */
| opt_elseifs '#' ELSIF '(' ')' statements
;
opt_else : /* Nothing */
| '#' ELSE statements
;
end : '#' END
;
Non ho eseguito questo tramite un generatore di parser, ma lo trovo relativamente facile da capire.
Altri suggerimenti
Penso che il problema sia nella clausola elseifs.
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Penso che la prima versione non sia richiesta, poiché la clausola else si riferisce comunque a elseifs:
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
Cosa succede se cambi altro ?:
elseifs : '#' ELSEIF statements else
;
La risposta di Jonathan sopra sembra che sarebbe la migliore, ma poiché non funziona per te ho alcuni suggerimenti che potresti provare che ti aiuteranno nel debug dell'errore.
In primo luogo hai preso in considerazione l'idea di rendere il simbolo hash / sharp parte dei token stessi (ovvero #END, #IF, ecc.)? In modo che vengano eliminati dal lexer, il che significa che non devono essere inclusi nel parser.
In secondo luogo, ti esorto a riscrivere le regole senza duplicare alcun flusso di token. (Parte del principio Don't Repeat Yourself.) Quindi la regola " '#' Dichiarazioni ELSEIF altro " dovrebbe esistere solo in un posto in quel file (non due come sopra).
Infine, suggerisco di esaminare la precedenza e l'associatività dei token IF / ELSEIF / ELSE. So che dovresti essere in grado di scrivere un parser che non lo richiede, ma potrebbe essere la cosa di cui hai bisogno in questo caso.
Sto ancora cambiando le cose e la mia domanda originale aveva degli errori dato che la sequenza elseif aveva sempre un altro alla fine che era sbagliato. Ecco un'altra interpretazione della domanda, questa volta ottengo due turni di spostamento / riduzione:
flow : '#' IF '(' ')' statements elsebody
;
elsebody : else
| elseifs else
;
else : '#' ELSE statements '#' END
| '#' END
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
I conflitti ora sono:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 12: elseifs -> /* empty */
Shift "'#'": State-10 -> State-13
Items for From-state State 10
7 flow: '#' IF '(' ')' statements . elsebody
4 statements: statements . stmt
Items for Next-state State 13
10 else: '#' . ELSE statements '#' END
11 else: '#' . END
7 flow: '#' . IF '(' ')' statements elsebody
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 13: elseifs -> elseifs, '#', ELSEIF, statements
Shift "'#'": State-24 -> State-6
Items for From-state State 24
13 elseifs: elseifs '#' ELSEIF statements .
-lookahead: '#'
4 statements: statements . stmt
Items for Next-state State 6
7 flow: '#' . IF '(' ')' statements elsebody
// End conflict information for parser
Le regole vuote non fanno altro che aggravare il gppg che ho paura. Ma sembrano così naturali da usare che continuo a provarli.
So già che la giusta ricorsione risolve il problema come ha detto 1800 INFORMAZIONI . Ma sto cercando una soluzione con ricorsione a sinistra nella clausola elseifs .
elsebody : elseifs else
| elseifs
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
else : '#' ELSE statements '#' END
;
Penso che questo dovrebbe lasciare la recessione e terminare sempre.
OK - ecco una grammatica (non minima) per i blocchi if. L'ho estratto da un codice che ho (chiamato adhoc, basato su hoc da Kernighan & amp; Plauger "L'ambiente di programmazione UNIX"). Questo schema grammaticale viene compilato con Yacc senza conflitti.
%token NUMBER IF ELSE
%token ELIF END
%token THEN
%start program
%%
program
: stmtlist
;
stmtlist
: /* Nothing */
| stmtlist stmt
;
stmt
: ifstmt
;
ifstmt
: ifcond endif
| ifcond else begin
| ifcond eliflist begin
;
ifcond
: ifstart cond then stmtlist
;
ifstart
: IF
;
cond
: '(' expr ')'
;
then
: /* Nothing */
| THEN
;
endif
: END IF begin
;
else
: ELSE stmtlist END IF
;
eliflist
: elifblock
| elifcond eliflist begin /* RIGHT RECURSION */
;
elifblock
: elifcond else begin
| elifcond endif
;
elifcond
: elif cond then stmtlist end
;
elif
: ELIF
;
begin
: /* Nothing */
;
end
: /* Nothing */
;
expr
: NUMBER
;
%%
Ho usato 'NUMBER' come elemento fittizio, invece di THINGS, e ho usato ELIF invece di ELSEIF. Include THEN, ma è facoltativo. Le operazioni 'inizio' e 'fine' sono state usate per afferrare il contatore del programma nel programma generato - e quindi dovrebbero essere rimovibili da questo senza influenzarlo.
C'era una ragione per cui pensavo di dover usare la ricorsione giusta invece della normale ricorsione sinistra - ma penso che avesse a che fare con la strategia di generazione del codice che stavo usando, piuttosto che con qualsiasi altra cosa. Il punto interrogativo nel commento era nell'originale; Ricordo di non esserne soddisfatto. Il programma nel suo insieme funziona - è un progetto che è stato in secondo piano negli ultimi dieci anni circa (hmmm ... ho fatto un po 'di lavoro alla fine del 2004 e all'inizio del 2005; prima di ciò, era il 1992 e 1993).
Non ho passato il tempo a capire perché questo compila senza conflitti e ciò che ho descritto in precedenza non lo fa. Spero che sia d'aiuto.
