Reformar la gramática para eliminar el cambio reducir el conflicto en if-then-else

Question

¿Cómo elimino el conflicto shift-reduce para bison para la gramática dada?

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

Una solución que ofrezca la gramática modificada sería muy apreciada.

Answer 1

Hay una solución mucho más simple. Si usted sabe cómo funcionan los análisis de LR, entonces usted sabe que el conflicto que 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 "¿Debería cambiar, o debería reducir?". Normalmente, desea vincular el else al if más cercano, lo que significa que desea cambiar el token else ahora. Reducir ahora significaría que desea que el else espere para estar vinculado a un "anterior" if.

Ahora quiere "decirle" a su generador de analizadores 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, "dar un nombre" a la prioridad de su regla (por ejemplo, "then") y especifique que "then" tiene menos prioridad 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 

usando la sintaxis de Bison.

En realidad, mi respuesta favorita es incluso dar a "then" y "else" la misma precedencia. Cuando las precedencias son iguales, para romper el empate entre el token que quiere ser desplazado, y la regla que quiere ser reducida, Bison/Yacc observará la asociatividad. Aquí, usted quiere promover asociatividad por la derecha por así decirlo (más exactamente, que desea promover "cambio"), por lo que:

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

será suficiente.

Answer 2

Debe reconocer que el medio statement en el caso if-else no puede ser (o finalizar con) un pendular (si no hay otro). La manera más fácil 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 cuando whatever no termina con un stmt va en la regla stmt-not-ending-with-if, mientras que cualquier regla stmt que termina en stmt dividida ponerse en dos versiones; una versión not-ending-with-if en la regla not-ending-with-if y una versión dangling-if en la regla dangling-if.

edición

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 dividida en dos (get, ya que terminan con stmt), mientras que las reglas como expr; no lo hacen.

Answer 3

hacer otra cosa si un nivel más alto que las declaraciones normales, como:

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