grammar - literature - Shift reduce el conflicto
conflict definition literature (6)
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 hace referencia a elseifs de todos modos:
else : ''#'' END
| ''#'' ELSE statements ''#'' END
| elseifs
;
¿Qué sucede si cambias los elseifs ?:
elseifs : ''#'' ELSEIF statements else
;
Tengo un problema para entender el cambio / reducir el conflicto para una gramática que sé que no tiene ambigüedad. El caso es del tipo if else else, pero no es el problema de ''colgar el otro'' ya que tengo cláusulas END obligatorias que delimitan bloques de código.
Aquí está la gramática de gppg (Es un compilador de compilador de Bison ... 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á el resultado 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é de todo, y sé cómo resolverlo, pero esa solución implica renunciar a la recursividad a la izquierda en ''elseif'' para una recursión correcta.
He revisado toda la documentación 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 ahora. Por favor, limite su solución a los analizadores de Yacc / Bison.
Apreciaría las soluciones elegantes, logré hacerlo eleminando las reglas / * empty * / y la duplicación de todo lo que necesitaba una lista vacía, pero en la gramática más grande en la que estoy trabajando acaba terminando como ''sparghetti grammar syndrome''.
Aquí hay algunos enlaces:
http://nitsan.org/~maratb/cs164/bison.html
http://compilers.iecc.com/comparch/article/98-01-079
Su regla ELSEIF revisada no tiene marcadores para una condición: debe tener nominalmente ''('' y '')'' agregados.
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 he ejecutado esto a través de un generador de analizadores, pero encuentro esto relativamente fácil de entender.
Todavía estoy cambiando la situación, y mi pregunta original tenía algunos errores, ya que la secuencia elseifs tenía un else siempre al final, lo cual era incorrecto. Aquí hay otra opinión sobre la pregunta, esta vez tengo dos conflictos de cambio / reducción:
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. Tengo miedo. Pero parecen tan naturales de usar que sigo probándolos.
Ya sé que la recursión correcta resuelve el problema como ha dicho 1800 INFORMATION . Pero estoy buscando una solución con recursividad a la 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 recurrir y terminar siempre.
La respuesta de Jonathan anterior parece ser la mejor, pero como no funciona para ti, tengo algunas sugerencias que podrías intentar que te ayudarán a depurar el error.
En primer lugar, ¿ha considerado hacer del símbolo hash / sharp una parte de los tokens (es decir, #END, #IF, etc.)? Para que el lexer los elimine, lo que significa que no tienen que incluirse en el analizador sintáctico.
En segundo lugar, le recomendaría que reescriba las reglas sin duplicar ningún flujo de tokens. (Parte del principio No repetir). Por lo tanto, la regla "''#'' declaraciones ELSEIF else" solo debería existir en un lugar en ese archivo (no en dos como se mencionó anteriormente).
Por último, sugiero que busque la precedencia y la asociatividad de los tokens IF / ELSEIF / ELSE. Sé que debes poder escribir un analizador sintáctico que no lo requiera, pero podría ser lo que necesitas en este caso.
OK - aquí hay una gramática (no mínima) para los bloques. Lo desenterré de algún código que tengo (llamado adhoc, basado en hoc del "Entorno de programación UNIX" de Kernighan & Plauger). Esta gramática de esquema 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 el elemento ficticio, en lugar de COSAS, y utilicé ELIF en lugar de ELSEIF. Incluye un ENTONCES, pero eso es opcional. Las operaciones ''begin'' y ''end'' se usaron para tomar el contador del programa en el programa generado y, por lo tanto, deberían poder eliminarse sin afectarlo.
Había una razón por la que pensé que necesitaba usar la recursividad correcta en lugar de la recursión normal a la izquierda, 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 que no fui feliz con eso. El programa en su conjunto funciona, es un proyecto que ha estado en la sombra durante la última década (hmmm ... hice algún trabajo a fines de 2004 y principios de 2005; antes de eso, era 1992). y 1993).
No me he pasado el tiempo averiguando por qué esto compila sin conflictos y lo que describí antes no lo hace. Espero que ayude.