Comment résoudre un conflit de décalage réduire la grammaire non ambiguë

Question

Je suis en train d'analyser une grammaire simple à l'aide d'un LALR (1) générateur d'analyseur (Bison, mais le problème est pas spécifique à cet outil), et je suis frappé un conflit de décalage réduire. Les documents et d'autres sources que j'ai trouvé sur la fixation de ceux-ci ont tendance à dire un ou plusieurs des éléments suivants:

• Si la grammaire est ambiguë (par exemple if-then-else ambiguïté), changer la langue pour corriger l'ambiguïté.
• Si c'est une question de priorité de l'opérateur, spécifiez la priorité explicitement.
• Accepter la résolution par défaut et dire le générateur ne pas se plaindre à ce sujet.

Cependant, aucun d'entre eux semblent s'appliquer à ma situation: la grammaire est sans ambiguïté pour autant que je peux dire (même si bien sûr il est ambigu avec un seul caractère de préanalyse), il n'a qu'un seul opérateur, et les pistes de résolution par défaut pour analyser les erreurs sur l'entrée correctement formé. Y a-t-il des techniques pour retravailler la définition d'une grammaire pour éliminer les quarts-de réduire les conflits qui ne tombent pas dans les seaux ci-dessus?

Pour concrétude, voici la grammaire en question:

%token LETTER

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

Le but est d'analyser les lignes point-virgule séparées de la forme "[A-Za-z] +" ou "[A-Za-z] -> [A-Za-z] +"

.

Answer 1

Utilisation de la version Solaris de yacc, je reçois:

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

Alors, le problème est, car il est très souvent, la règle vide - Plus précisément, le successeur vide. Il est pas tout à fait clair si vous voulez autoriser un point-virgule comme entrée valide - pour le moment, il est. Si vous avez modifié la règle de successeur:

successor: LETTER | successor LETTER;

le changement / réduire les conflits est éliminé.

Answer 2

Merci pour amenuisement la grammaire et l'afficher. Modification de la règle de successeur -

successor:      /* empty */ | LETTER successor;

... a fonctionné pour moi. ITYM langue regardé sans ambiguïté.