bison - La reforma de la gramática para eliminar el cambio reduce el conflicto en if-then-else

shift-reduce-conflict

Question

¿Cómo elimino el conflicto de cambio y reducción de bison para la gramática dada?

 selection-stmt -> if ( expression ) statement |
                      if ( expression ) statement else statement

Una solución que dé la gramática modificada sería altamente apreciada.

Answer 1

Debe reconocer el hecho de que la statement intermedia en el caso if-else no puede ser (o terminar con) un estado de suspensión if (y si no hay otra cosa). La forma más sencilla de hacerlo es dividir la regla stmt en dos:

stmt -> stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if ->
    if ( expression ) stmt-not-ending-with-dangling-if else stmt-not-ending-with-dangling-if |
    ...other statements not ending with dangling if...
stmt-ending-with-dangling-if ->
    if ( expression ) stmt |
    if ( expression ) stmt-not-ending-with-dangling-if else stmt-ending-with-dangling-if |
    ...other statements ending with dangling if...

Cualquier otro stmt -> whatever regla donde whatever que no termine con un stmt va en la regla stmt-not-ending-with-if , mientras que cualquier regla del stmt que NO termine en stmt se divide en dos versiones; una versión que not-ending-with-if regla not-ending-with-if y una versión que dangling-if regla que dangling-if .

editar

Una gramática más completa con otras producciones:

stmt : stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if :
    IF ''('' expr '')'' stmt-not-ending-with-dangling-if ELSE stmt-not-ending-with-dangling-if |
    WHILE ''('' expr '')'' stmt-not-ending-with-dangling-if |
    DO stmt WHILE ''('' expr '')'' '';'' |
    expr '';'' |
    ''{'' stmt-list ''}''
stmt-ending-with-dangling-if:
    IF ''('' expr '')'' stmt |
    IF ''('' expr '')'' stmt-not-ending-with-dangling-if ELSE stmt-ending-with-dangling-if |
    WHILE ''('' expr '')'' stmt-ending-with-dangling-if

Reglas como WHILE (expr) stmt se dividen en dos (ya que terminan con stmt ), mientras que las reglas como expr; no haga.

Answer 2

Hacer más alto nivel que las declaraciones normales, como:

statements:
  statements lineEnd statement
| statements lineEnd IfStat
| statements lineEnd IfElseStat
| IfStat
| IfElseStat
;
IfStat:
  if ( statement )
;
IfElse:
  IfStat else statement
;

Answer 3

Hay una solución mucho más simple. Si sabe cómo funcionan los analizadores LR, entonces sabe que el conflicto ocurre aquí:

if ( expression ) statement * else statement

donde la estrella marca la posición actual del cursor. La pregunta que el analizador debe responder es "¿debo cambiar o reducir?". Por lo general, desea vincular el else al más cercano if , lo que significa que desea cambiar el token de else ahora. Reducir ahora significaría que quiere que la else espera espere a ser "antigua" if .

Ahora quiere "decirle" al generador de su analizador que "cuando hay un conflicto de cambio / reducción entre el token "else" y la regla" stm -> if (exp) stm ", entonces el token debe ganar". Para hacerlo, "dé un nombre" a la precedencia de su regla (por ejemplo, "then" ), y especifique que "then" tiene menos precedencia que "else" . Algo como:

// Precedences go increasing, so "then" < "else".
%nonassoc "then"
%nonassoc "else"
%%
stm: "if" "(" exp ")" stm            %prec "then"
   | "if" "(" exp ")" stm "else" stm

utilizando la sintaxis de Bison.

En realidad, mi respuesta favorita es incluso dar a "then" y "else" la misma prioridad. Cuando las precedentes son iguales, para romper el vínculo entre el token que se desea cambiar y la regla que se desea reducir, Bison / Yacc buscará la asociatividad. Aquí, desea promover la asociatividad por el derecho, por así decirlo (más exactamente, quiere promover el "cambio"), por lo que:

%right "then" "else" // Same precedence, but "shift" wins.

Será suficiente.