Cómo resolver un desplazamiento y reducción de conflictos en la gramática no ambigua

Question

Estoy tratando de analizar una gramática sencilla utilizando un LALR (1) generador de analizadores sintácticos (bisonte, pero el problema no es específico de esa herramienta), y yo estoy pegando un cambio a reducir los conflictos. Los documentos y otras fuentes que he encontrado sobre la fijación de éstos tienden a decir uno o más de los siguientes:

• Si la gramática es ambigua (por ejemplo if-then-else ambigüedad), cambiar el idioma para fijar la ambigüedad.
• Si se trata de un asunto de prioridad de operadores, precedencia especificar de forma explícita.
• Aceptar la resolución predeterminada y decirle al generador no a quejarse de ello.

Sin embargo, ninguno de ellos parece aplicarse a mi situación: la gramática es ambigua por lo que yo puedo decir (aunque, por supuesto que es ambigua con sólo un carácter de búsqueda hacia delante), que tiene un solo operador, y los cables de resolución predeterminada para analizar los errores en la entrada formado correctamente. ¿Hay algunas técnicas para la reelaboración de la definición de una gramática para eliminar el desplazamiento y reducción de conflictos que no entran en los cubos anteriores?

Para ser concretos, aquí está la gramática en cuestión:

%token LETTER

%%
%start input;
input:          /* empty */ | input input_elt;
input_elt:      rule | statement;
statement:      successor ';';
rule:           LETTER "->" successor ';';
successor:      /* empty */ | successor LETTER;
%%

La intención es analizar las líneas separadas por punto y coma de la forma "[A-Za-z] +" o "[A-Za-z] -> [A-Za-z] +"

.

Answer 1

El uso de la versión de Solaris de yacc, me sale:

1: shift/reduce conflict (shift 5, red'n 7) on LETTER
state 1
    $accept :  input_$end
    input :  input_input_elt
    successor : _    (7)

    $end  accept
    LETTER  shift 5
    .  reduce 7

    input_elt  goto 2
    rule  goto 3
    statement  goto 4
    successor  goto 6

Por lo tanto, el problema es que, ya que muy a menudo es, la regla de vacío - en concreto, el sucesor vacía. No está del todo claro si desea permitir que un punto y coma como una entrada válida - por el momento, lo es. Si ha modificado la regla sucesor:

successor: LETTER | successor LETTER;

el desplazamiento / reducción de conflictos es eliminado.

Answer 2

Gracias por tallar abajo de la gramática y la publicación de la misma. Cambiar la regla sucesor -

successor:      /* empty */ | LETTER successor;

... trabajó para mí. ITYM el idioma mirado sin ambigüedades.