Die Grammatik reformieren, um die Verschiebung zu entfernen den Konflikt in if-then-else zu reduzieren

Question

Wie entferne ich den Shift-Reduce-Konflikt für Bison für die gegebene Grammatik?

Eine Lösung mit der modifizierten Grammatik würde sehr geschätzt werden.

Answer 1

Es gibt eine viel einfachere Lösung. Wenn Sie wissen, wie LR Parser arbeiten, dann wissen Sie, dass der Konflikt geschieht hier:

if (expression) statement * else statement 

wo der Stern die aktuelle Position des Cursors markiert. Die Frage, die der Parser beantworten muss, lautet: "Soll ich verschieben, oder sollte ich reduzieren?". Normalerweise möchten Sie den else an den nächsten if binden, was bedeutet, dass Sie den else Token jetzt verschieben möchten. Reduzieren würde jetzt bedeuten, dass Sie die else warten möchten, um an eine "ältere" if gebunden zu werden.

Jetzt wollen Sie Ihren Parser-Generator zu „sagen“, dass „wenn es eine Verschiebung/reduzieren Konflikt zwischen dem Token "else" und die Regel ist‚stm -> if (exp) stm‘, dann muss das Token gewinnen“. Um dies zu tun, geben Sie dem Vorrang Ihrer Regel einen Namen (z. B. "then") und geben Sie an, dass "then" weniger Vorrang hat als "else". Etwas wie:

// Precedences go increasing, so "then" < "else". 
%nonassoc "then" 
%nonassoc "else" 
%% 
stm: "if" "(" exp ")" stm   %prec "then" 
    | "if" "(" exp ")" stm "else" stm 

mit Bisonsyntax.

Eigentlich meine Lieblingsantwort ist sogar "then" und "else" die gleiche Priorität geben. Wenn die Vorbedingungen gleich sind, um die Verbindung zwischen dem Token, das verschoben werden soll, und der Regel, die reduziert werden soll, zu durchbrechen, wird Bison/Yacc auf Assoziativität schauen. Hier wollen Sie mit der rechten Assoziativität zu fördern, um zu sprechen (genauer gesagt, wollen Sie „shift“ fördern), so:

%right "then" "else" // Same precedence, but "shift" wins. 

genügt.

Answer 2

Sie müssen die Tatsache erkennen, dass die mittlere statement in der If-else-Fall kann nicht sein (oder mit enden) ein Dangling wenn (ein If mit sonst keiner.) Der einfachste Weg, dies zu tun ist die stmt Regel zu teilen in zwei:

stmt -> stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if 
stmt-not-ending-with-dangling-if -> 
    if (expression) stmt-not-ending-with-dangling-if else stmt-not-ending-with-dangling-if | 
    ...other statements not ending with dangling if... 
stmt-ending-with-dangling-if -> 
    if (expression) stmt | 
    if (expression) stmt-not-ending-with-dangling-if else stmt-ending-with-dangling-if | 
    ...other statements ending with dangling if... 

jede anderen stmt -> whatever Regel wo whatever mit einem stmt nicht in der stmt-not-ending-with-if Regel geht zu beenden, während jede stmt Regel, das Ende in stmt get Spaltung in zwei Versionen DOES; eine not-ending-with-if Version in der not-ending-with-if Regel und eine dangling-if Version in der dangling-if Regel.

bearbeitet

Eine vollständigere Grammatik mit anderen Produktionen:

stmt : stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if 
stmt-not-ending-with-dangling-if : 
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-not-ending-with-dangling-if | 
    WHILE '(' expr ')' stmt-not-ending-with-dangling-if | 
    DO stmt WHILE '(' expr ')' ';' | 
    expr ';' | 
    '{' stmt-list '}' 
stmt-ending-with-dangling-if: 
    IF '(' expr ')' stmt | 
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-ending-with-dangling-if | 
    WHILE '(' expr ')' stmt-ending-with-dangling-if 

Regeln wie WHILE (expr) stmt get in zwei Teile gespalten (wie sie mit stmt enden), während Regeln wie expr; nicht.

Answer 3

machen, wenn sonst höher als normale Aussagen, wie:

statements: 
    statements lineEnd statement 
| statements lineEnd IfStat 
| statements lineEnd IfElseStat 
| IfStat 
| IfElseStat 
; 
IfStat: 
    if (statement) 
; 
IfElse: 
    IfStat else statement 
;