Comment résoudre un conflit de décalage-réduction en grammaire non ambiguë

Question

J'essaye d'analyser une grammaire simple en utilisant un générateur d'analyseur LALR (1) (Bison, mais le problème n'est pas spécifique à cet outil), et je frappe un changement-réduire le conflit. 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é .
• S'il s'agit d'un problème de priorité d'opérateur, spécifiez la priorité explicitement.
• Acceptez la résolution par défaut et dites au générateur de ne pas s'en plaindre.

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 la résolution par défaut entraîne des erreurs d'analyse sur une entrée correctement formée. Existe-t-il des techniques pour retravailler la définition d'une grammaire pour supprimer les conflits de décalage-réduction qui ne tombent pas dans les catégories 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; 
%% 

L'objectif est d'analyser les lignes des points-virgules séparées de la forme "[A-Za-z] +" ou « [A-Za-z ] -> [A-Za-z] + ".

Answer 1

En utilisant 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 

Ainsi, le problème est, car il est très souvent, la règle vide - Plus précisément, le successeur vide. Il n'est pas tout à fait clair si vous voulez autoriser un point-virgule en tant qu'entrée valide - pour l'instant, c'est le cas. Si vous avez modifié la règle de successeur pour:

successor: LETTER | successor LETTER; 

le conflit de décalage/réduction est éliminé.

Answer 2

Merci de réduire la grammaire et de l'afficher. Modification de la règle de successeur -

successor:  /* empty */ | LETTER successor; 

... travaillé pour moi. ITYM le langue regardé sans ambiguïté.