Shift reduce conflicto

Question

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í es la gramática de GPPG (es un compilador de bisonte como compilador ... y que no 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 
     ; 

Aquí está la salida de conflictos:

// 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é 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.

Agradecerí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 trabajo Simplemente termina como 'sparghetti grammar syndrome' .

Éstos son algunos enlaces:

http://nitsan.org/~maratb/cs164/bison.html

http://compilers.iecc.com/comparch/article/98-01-079

GPPG, the parser I'm using

Bison manual

Answer 1

Su regla ELSEIF revisada no tiene marcadores para una condición: nominalmente debe tener '(' y ')'.

Más en serio, ahora tiene 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'.

estaría muy inclinados a utilizar 'opt_elseifs' reglas 'opt_else', y 'final':

flow : '#' IF '(' ')' statements opt_elseifs opt_else end 
    ; 

opt_elseifs : /* Nothing */ 
      | opt_elseifs '#' ELSIF '(' ')' statements 
      ; 

opt_else : /* Nothing */ 
     | '#' ELSE statements 
     ; 

end : '#' END 
    ; 

no ha corrido esto a través de un generador de análisis, pero me parece que esta relativamente fácil entender.

Answer 2

Creo que el problema es en la cláusula elseif.

elseifs : elseifs '#' ELSEIF statements else 
     | '#' ELSEIF statements else 
     ; 

creo que la primera versión no es necesario, ya que la cláusula else remite a elseif todos modos:

else : '#' END 
    | '#' ELSE statements '#' END 
    | elseifs 
    ; 

¿Qué pasa si cambia elseif ?:

elseifs : '#' ELSEIF statements else 
     ; 

Answer 3

I' Todavía estoy cambiando cosa, y mi pregunta original tenía algunos errores ya que la secuencia elseifs tenía un else siempre al final que estaba mal. Aquí es otra toma en la pregunta, esta vez consigo dos turnos/reducir los conflictos:

flow : '#' IF '(' ')' statements elsebody 
    ; 

elsebody : else 
     | elseifs else 
     ; 

else : '#' ELSE statements '#' END 
    | '#' END 
    ; 

elseifs : /* empty */ 
     | elseifs '#' ELSEIF statements 
     ; 

Los conflictos son ahora: reglas

// 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 

vacíos solo agravan la GPPG estoy participaban. Pero parecen tan naturales de usar que sigo probándolos.

Ya sé recursión correcta resuelve el problema como 1800 INFORMACIÓN ha dicho. Pero estoy buscando una solución con recursividad en la cláusula elseifs.

Answer 4

elsebody : elseifs else 
     | elseifs 
     ; 

elseifs : /* empty */ 
     | elseifs '#' ELSEIF statements 
     ; 

else : '#' ELSE statements '#' END 
    ; 

Creo que esto debería dejarse recurrir y terminar siempre.

Answer 5

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 instaría a volver a escribir las reglas sin duplicar las secuencias 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, le sugiero que consulte la precedencia y 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.

Answer 6

OK - aquí hay una gramática (no mínima) para if blocks. Lo desenterré de algún código que tengo (llamado adhoc, basado en el código fuente de Kernighan & de Plauger "El entorno de programación UNIX"). 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 
    ; 

%% 

I utilizado 'número' como elemento postizo, en lugar de las cosas, y yo solía 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.

Hubo una razón por la que pensé que necesitaba usar la recursión correcta en lugar de la recursión a la izquierda normal, pero creo que tenía que ver con la estrategia de generación de código que estaba utilizando, 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é esta compilación no tiene conflictos y lo que describí anteriormente no lo hace. Espero que ayude.