Wie man einen Shift-Reduce-Konflikt in einer eindeutigen Grammatik löst

Question

Ich versuche, eine einfache Grammatik mit einem LALR (1) Parser-Generator zu analysieren (Bison, aber das Problem ist nicht spezifisch für dieses Tool), und ich treffe ein Shift-Reduce-Konflikt. Die Dokumentation und andere Quellen, die ich gefunden habe, um diese Festsetzung neigen dazu, eine zu sagen oder mehrere der folgenden Optionen:

• Wenn die Grammatik nicht eindeutig ist (zB if-then-else Mehrdeutigkeit), ändern Sie die Sprache, die Mehrdeutigkeit zu beheben .
• Wenn es sich um ein Operator-Vorrangproblem handelt, geben Sie den Vorrang explizit an.
• Übernehmen Sie die Standardauflösung und sagen Sie dem Generator, dass er sich nicht darüber beschweren soll.

jedoch keiner von ihnen scheint meine Situation anzuwenden: die Grammatik eindeutig ist, soweit ich das beurteilen kann (obwohl es natürlich mit nur einem Charakter von Look-Ahead-mehrdeutig ist), hat es nur einen Betreiber und die Die Standardauflösung führt dazu, dass Fehler bei richtiger Eingabe analysiert werden. Gibt es Techniken zur Überarbeitung der Definition einer Grammatik, um Shift-Reduce-Konflikte zu entfernen, die nicht in die obigen Buckets fallen?

Für Konkretion, hier ist die Grammatik in Frage:

%token LETTER 

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

Die Absicht ist, durch Semikolons getrennt Zeilen der Form "[A-Za-z] +" oder „[A-Za-z parsen ] -> [A-Za-z] + ".

Answer 1

Mit der Solaris-Version von yacc, erhalte ich:

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 

Also, das Problem ist, da es sehr häufig ist, die leere Regel - insbesondere der leere Nachfolger. Es ist nicht ganz klar, ob Sie ein Semikolon als gültige Eingabe zulassen wollen - im Moment ist es das. Wenn Sie die Nachfolgerregel wie folgt geändert haben:

successor: LETTER | successor LETTER; 

ist der Shift/Reduce-Konflikt beseitigt.

Answer 2

Danke, dass Sie die Grammatik verfeinert und gepostet haben. Ändern der Nachfolgeregel zu -

successor:  /* empty */ | LETTER successor; 

... arbeitete für mich. ITYM die Sprache sah eindeutig aus.