Wie YACC Verschiebung / reduzieren Konflikte aus der Post-Inkrementoperator zu beheben?
-
23-08-2019 - |
Frage
Ich schreibe eine Grammatik in YACC (eigentlich Bison), und ich habe eine Verschiebung / Problem reduzieren. Es ergibt sich aus der Postfix-Inkrement- und Dekrement-Operatoren einschließlich. Hier ist eine abgespeckte Version der Grammatik:
%token NUMBER ID INC DEC
%left '+' '-'
%left '*' '/'
%right PREINC
%left POSTINC
%%
expr: NUMBER
| ID
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| INC expr %prec PREINC
| DEC expr %prec PREINC
| expr INC %prec POSTINC
| expr DEC %prec POSTINC
| '(' expr ')'
;
%%
Bison sagt mir, es gibt 12 Schiebe- / reduzieren Konflikte, aber wenn ich die Leitungen für die postfix Erhöhungs- und Verringerungs Kommentar aus, es funktioniert gut. Wer weiß, wie um diesen Konflikt zu beheben? An diesem Punkt bin ich in Anbetracht auf einen LL (k) Parser-Generator zu bewegen, die es viel einfacher macht, aber LALR Grammatiken haben schien immer viel natürlicher zu schreiben. Ich erwäge auch GLR, aber ich weiß nicht jeden guten C / C ++ GLR-Parser-Generatoren.
Lösung
Bison / Yacc kann einen GLR-Parser generiert, wenn Sie %glr-parser
in der Option Abschnitt angeben.
Andere Tipps
Versuchen Sie folgendes:
%token NUMBER ID INC DEC
%left '+' '-'
%left '*' '/'
%nonassoc '++' '--'
%left '('
%%
expr: NUMBER
| ID
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '++' expr
| '--' expr
| expr '++'
| expr '--'
| '(' expr ')'
;
%%
Der Schlüssel ist, Postfix-Operatoren wie nicht assoziativ zu erklären. Sonst würden Sie in der Lage sein
++var++--
Die Klammer muß auch einen Vorrang gegeben wird Verschiebung zu minimieren / verringern Warnungen
Ich mag, um weitere Elemente zu definieren. Sie sollten das% links, rechts%,% prec Sachen nicht benötigen.
simple_expr: NUMBER
| INC simple_expr
| DEC simple_expr
| '(' expr ')'
;
term: simple_expr
| term '*' simple_expr
| term '/' simple_expr
;
expr: term
| expr '+' term
| expr '-' term
;
Spielen Sie mit diesem Ansatz.
Dieses grundlegende Problem ist, dass Sie keinen Vorrang für den INC
und DEC
Token haben, so dass er nicht weiß, wie Mehrdeutigkeiten aufzulösen einen Look-Ahead von INC
oder DEC
beteiligt ist. Wenn Sie fügen
%right INC DEC
am Ende der Rangliste (Sie wollen unaries höher seinen Vorrang und Postfix höher als Präfix), wird es beheben, und Sie können sogar alle PREINC
/ POSTINC
Sachen loszuwerden, wie es irrelevant ist.
Prä-und Postinkrement Betreiber haben nonassoc so definieren, dass in den Vortritt Abschnitt und in den Regeln der Vorrang dieser Operatoren stellen hohe durch %prec
mit