Wie man einen Verschiebungskonflikt in eindeutiger Grammatik lösen

Question

Ich versuche, eine einfache Grammatik mit einem LALR (1) -Parser-Generator (Bison, aber das Problem für dieses Tool nicht spezifisch) zu analysieren, und ich schlage einen Schicht-Reduce-Konflikt. Die Dokumente und andere Quellen, die ich über diese festgestellt habe, neigen dazu, eine oder mehrere der folgenden zu sagen:

• Wenn die Grammatik nicht mehrdeutig ist (z. B. Unklarheit), ändern Sie die Sprache, um die Mehrdeutigkeit zu beheben.
• Wenn es sich um ein Vorrangbetreiberproblem handelt, geben Sie Vorrang ausdrücklich an.
• Akzeptieren Sie die Standardauflösung und sagen Sie dem Generator, er solle sich nicht darüber beschweren.

Nichts davon scheint jedoch auf meine Situation zu gelten: Die Grammatik ist eindeutig, soweit ich das beurteilen kann (obwohl sie natürlich mit nur einem Charakter von Lookahead mehrdeutig ist), hat es nur einen Operator, und die Standardauflösung führt dazu, dass Fehler analysiert werden auf korrekt geformte Eingabe. Gibt es Techniken zur Überarbeitung der Definition einer Grammatik zum Entfernen von Verschiebungskonflikten, die nicht in die oben genannten Eimer fallen?

Für die Konkretheit ist hier die fragliche Grammatik:

%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 es, semikolon-getrennte Linien der Form [a-za-z]+" oder [a-za-z]-> [a-za-z]+" zu analysieren.

Answer 1

Verwenden der Solaris -Version von yacc, Ich bekomme:

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

Das Problem ist also, wie es sehr oft ist, die leere Regel - insbesondere der leere Nachfolger. Es ist nicht ganz klar, ob Sie einem Semikolon als gültige Eingabe zulassen möchten - im Moment ist es das. Wenn Sie die Nachfolgerregel geändert haben:

successor: LETTER | successor LETTER;

Der Verschiebung/Reduzierenkonflikt wird beseitigt.

Answer 2

Danke, dass du die Grammatik niedergeschlagen und gepostet hast. Ändern der Nachfolgerregel auf -

successor:      /* empty */ | LETTER successor;

... arbeitete für mich. Itym der Sprache sah eindeutig aus.