Shift reduce el conflicto
https://stackoverflow.com/questions/196179
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo un problema para entender el cambio / reducir el conflicto para una gramática que sé que no tiene ambigüedad. El caso es uno de los tipos if else, pero no es el problema 'colgando más' ya que tengo cláusulas END obligatorias que delimitan bloques de código.
Aquí está la gramática para gppg (es un compilador de Bison como compilador ... y eso no fue 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
;
Aquí está la salida del conflicto:
// 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
Ya cambié alrededor de todo, y sé cómo resolverlo, pero esa solución implica renunciar a la recursión izquierda en 'elseif' por una recursión derecha.
He revisado toda la documentación escasa que he encontrado en Internet sobre este tema (publico algunos enlaces al final) y todavía no he encontrado una solución elegante. Sé sobre ANTLR y no quiero considerarlo en este momento. Limite su solución a los analizadores Yacc / Bison.
Apreciaría las soluciones elegantes, logré hacerlo al eliminar las reglas / * empty * / y duplicar todo lo que necesitaba una lista vacía pero en la gramática más amplia en la que estoy trabajando Simplemente termina como 'síndrome de gramática sparghetti'.
Aquí hay algunos enlaces:
http://nitsan.org/~maratb/cs164/bison.html
http://compilers.iecc.com/comparch/article/98- 01-079
Solución
Su regla ELSEIF revisada no tiene marcadores para una condición: nominalmente debería tener '(' y ')' agregado.
Más en serio, ahora tienes una regla para
elsebody : else
| elseifs else
;
y
elseifs : /* Nothing */
| elseifs ...something...
;
La 'nada' no es necesaria; está implícitamente atendido por el 'elsebody' sin los 'elseifs'.
Me inclinaría mucho a usar las reglas 'opt_elseifs', 'opt_else' y 'end':
flow : '#' IF '(' ')' statements opt_elseifs opt_else end
;
opt_elseifs : /* Nothing */
| opt_elseifs '#' ELSIF '(' ')' statements
;
opt_else : /* Nothing */
| '#' ELSE statements
;
end : '#' END
;
No ejecuté esto a través de un generador de analizadores, pero me parece relativamente fácil de entender.
Otros consejos
Creo que el problema está en la cláusula elseifs.
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Creo que la primera versión no es necesaria, ya que la cláusula else se refiere a elseifs de todos modos:
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
¿Qué sucede si cambias elseifs ?:
elseifs : '#' ELSEIF statements else
;
La respuesta de Jonathan anterior parece que sería la mejor, pero dado que no funciona para usted, tengo algunas sugerencias que podría probar para ayudarlo a depurar el error.
En primer lugar, ¿ha considerado hacer que el símbolo hash / sharp forme parte de los tokens (es decir, #END, #IF, etc.)? Para que sean eliminados por el lexer, lo que significa que no tienen que ser incluidos en el analizador.
En segundo lugar, le recomendaría que reescriba las reglas sin duplicar ninguna secuencia de tokens. (Parte del principio No te repitas.) Entonces la regla " '#' Sentencias ELSEIF más '' solo debe existir en un lugar en ese archivo (no dos como el que tiene arriba).
Finalmente, sugiero que analice la precedencia y la asociatividad de los tokens IF / ELSEIF / ELSE. Sé que debería poder escribir un analizador sintáctico que no lo requiera, pero podría ser lo que necesita en este caso.
Todavía estoy cambiando las cosas, y mi pregunta original tenía algunos errores ya que la secuencia elseifs tenía un else siempre al final que estaba mal. Aquí hay otra toma de la pregunta, esta vez tengo dos turnos / reducir conflictos:
flow : '#' IF '(' ')' statements elsebody
;
elsebody : else
| elseifs else
;
else : '#' ELSE statements '#' END
| '#' END
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
Los conflictos ahora son:
// 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
Las reglas vacías solo agravan el gppg que me da miedo. Pero parecen tan naturales de usar que sigo probándolos.
Ya sé que la recursión correcta resuelve el problema como lo ha dicho 1800 INFORMACIÓN . Pero estoy buscando una solución con recursividad izquierda en la cláusula elseifs .
elsebody : elseifs else
| elseifs
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
else : '#' ELSE statements '#' END
;
Creo que esto debería dejarse recurrente y siempre terminar.
OK: aquí hay una gramática (no mínima) para bloques if. Lo saqué de un código que tengo (llamado adhoc, basado en hoc de Kernighan & amp; Plauger's "The UNIX Programming Environment"). Esta gramática resumida se compila con Yacc sin conflictos.
%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
;
%%
Usé 'NUMBER' como elemento ficticio, en lugar de THINGS, y usé ELIF en lugar de ELSEIF. Incluye ENTONCES, pero eso es opcional. Las operaciones de "inicio" y "fin" se utilizaron para tomar el contador del programa en el programa generado y, por lo tanto, deberían eliminarse sin afectarlo.
Hubo una razón por la que pensé que necesitaba usar la recursión derecha en lugar de la recursiva izquierda normal, pero creo que tenía que ver con la estrategia de generación de código que estaba usando, en lugar de cualquier otra cosa. El signo de interrogación en el comentario estaba en el original; Recuerdo no haber sido feliz con eso. El programa en su conjunto funciona: es un proyecto que ha estado en segundo plano durante la última década más o menos (hmmm ... Hice un trabajo a fines de 2004 y principios de 2005; antes de eso, era 1992 y 1993).
No he pasado el tiempo averiguando por qué esto compila sin conflictos y lo que describí anteriormente no. Espero que ayude.
