Umschalt reduzieren Konflikt
https://stackoverflow.com/questions/196179
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
ich habe ein Problem mit Verständnis der Verschiebung / reduzieren confict für eine Grammatik, die ich kenne keine Zweideutigkeit hat. Der Fall ist einer der, wenn sonst Typ, aber es ist nicht die ‚baumelnd sonst‘ Problem, da ich zwingend END Klauseln abgrenzt Codeblöcke haben.
Hierist die Grammatik für GPPG (Es ist ein Bison wie Compiler Compiler ... und das war kein Echo):
%output=program.cs
%start program
%token FOR
%token END
%token THINGS
%token WHILE
%token SET
%token IF
%token ELSEIF
%token ELSE
%%
program : statements
;
statements : /*empty */
| statements stmt
;
stmt : flow
| THINGS
;
flow : '#' IF '(' ')' statements else
;
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Hier ist der Konflikt Ausgabe:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 10: else -> elseifs
Shift "'#'": State-22 -> State-23
Items for From-state State 22
10 else: elseifs .
-lookahead: '#', THINGS, EOF
11 elseifs: elseifs . '#' ELSEIF statements else
Items for Next-state State 23
11 elseifs: elseifs '#' . ELSEIF statements else
// End conflict information for parser
Ich schaltete bereits arround alles, und ich weiß, wie es zu lösen, aber diese Lösung beinhaltet die Linksrekursion auf ‚elseif‘ für eine rechte Rekursion Aufgeben.
Ive durch alle scarse Dokumentation ich im Internet zu diesem Thema gefunden haben (poste ich ein paar Links am Ende) und haben noch nicht eine elegante Lösung gefunden. Ich weiß, über ANTLR und ich will nicht, es zu prüfen, gerade jetzt. Bitte beschränken Sie Ihre Lösung zu Yacc / Bison-Parser.
I elegante Lösungen zu schätzen wissen würde, konnte ich es tun, indem eleminating das / * leer * / Regeln und Vervielfältigung alles, was eine leere Liste benötigte aber in der größeren Grammatik Im arbeiten an Es endet wie ‚sparghetti Grammatik-Syndrom‘.
Hier sind einige Links:
http://nitsan.org/~maratb/cs164/bison.html
Lösung
Ihre überarbeitete ELSEIF Regel hat keinen Marker für eine Bedingung -. Es sollte nominell haben ‚(‘ und ‚)‘ hinzugefügt
Noch gravierender ist, Sie haben jetzt eine Regel für die
elsebody : else
| elseifs else
;
und
elseifs : /* Nothing */
| elseifs ...something...
;
Das ‚Nichts‘ ist nicht erforderlich; es wird implizit gesorgt durch die ‚elsebody‘ ohne ‚elseifs‘.
würde ich sehr geneigt sein 'opt_elseifs' Regeln zu verwenden, 'opt_else' und 'Ende':
flow : '#' IF '(' ')' statements opt_elseifs opt_else end
;
opt_elseifs : /* Nothing */
| opt_elseifs '#' ELSIF '(' ')' statements
;
opt_else : /* Nothing */
| '#' ELSE statements
;
end : '#' END
;
Ich habe nicht laufen diese durch einen Parser-Generator, aber ich finde diese relativ einfach zu verstehen.
Andere Tipps
Ich denke, das Problem in der elseifs Klausel ist.
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Ich denke, die erste Version nicht erforderlich ist, da die else-Klausel zu elseifs verweist trotzdem:
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
Was passiert, wenn Sie elseifs ändern:?
elseifs : '#' ELSEIF statements else
;
Die Antwort von Jonathan scheint oben, wie es das Beste wäre, aber da es nicht für Sie arbeiten ich ein paar Vorschläge haben Sie versuchen könnten, dass Ihnen helfen, die Fehler bei der Fehlersuche.
Zum einen haben Sie als den Hash / scharf Symbol machen einen Teil der Token selbst (das heißt #END, #IF, usw.)? So dass sie von der Lexer herausgenommen bekommen, das heißt, sie müssen in den Parser enthalten nicht werden.
Zweitens möchte ich Sie bitten, die Regeln neu zu schreiben, ohne Token-Streams zu duplizieren. (Ein Teil des Do Repeat Yourself-Prinzips nicht.) So ist die Regel „‚#‘ELSEIF-Anweisungen else“ nur an einer Stelle in der Datei existieren soll (nicht zwei, wie Sie oben).
Schließlich schlage ich vor, dass man sich in Rangfolge und Assoziativität der IF / ELSEIF / ELSE-Token. Ich weiß, dass Sie in der Lage sein, einen Parser schreiben sollen, die nicht diese benötigt, aber es könnte die Sache, die Sie in diesem Fall benötigen.
Ich Schale noch Sache nahe, und meine ursprüngliche Frage hatte einige Fehler, da die elseifs Sequenz eine hatte sonst Immer am Ende, die falsch war. Hier ist eine andere nehmen an der Frage, diesmal ich zwei Schiebe- / reduzieren Konflikte:
flow : '#' IF '(' ')' statements elsebody
;
elsebody : else
| elseifs else
;
else : '#' ELSE statements '#' END
| '#' END
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
Die Konflikte sind jetzt:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 12: elseifs -> /* empty */
Shift "'#'": State-10 -> State-13
Items for From-state State 10
7 flow: '#' IF '(' ')' statements . elsebody
4 statements: statements . stmt
Items for Next-state State 13
10 else: '#' . ELSE statements '#' END
11 else: '#' . END
7 flow: '#' . IF '(' ')' statements elsebody
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 13: elseifs -> elseifs, '#', ELSEIF, statements
Shift "'#'": State-24 -> State-6
Items for From-state State 24
13 elseifs: elseifs '#' ELSEIF statements .
-lookahead: '#'
4 statements: statements . stmt
Items for Next-state State 6
7 flow: '#' . IF '(' ')' statements elsebody
// End conflict information for parser
Leere Regeln verschärfen nur die GPPG i affraid bin. Aber sie scheinen so natürlich ich zu verwenden, versuche sie.
Ich weiß schon, rechts Rekursion löst das Problem als 1800 INFORMATION gesagt hat. Aber ich bin auf der Suche nach einer Lösung mit Linksrekursion auf elseifs Klausel .
elsebody : elseifs else
| elseifs
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
else : '#' ELSE statements '#' END
;
ich denke, das sollte recurse links und immer beenden.
OK - hier ist eine Grammatik (nicht minimal) für wenn Blöcke. Ich grub sie aus einigen Code Ich habe (adhoc genannt, basiert auf hoc von Kernighan & Plauger "The UNIX Programming Environment"). Dieser Umriss Grammatik kompiliert mit Yacc ohne Konflikte.
%token NUMBER IF ELSE
%token ELIF END
%token THEN
%start program
%%
program
: stmtlist
;
stmtlist
: /* Nothing */
| stmtlist stmt
;
stmt
: ifstmt
;
ifstmt
: ifcond endif
| ifcond else begin
| ifcond eliflist begin
;
ifcond
: ifstart cond then stmtlist
;
ifstart
: IF
;
cond
: '(' expr ')'
;
then
: /* Nothing */
| THEN
;
endif
: END IF begin
;
else
: ELSE stmtlist END IF
;
eliflist
: elifblock
| elifcond eliflist begin /* RIGHT RECURSION */
;
elifblock
: elifcond else begin
| elifcond endif
;
elifcond
: elif cond then stmtlist end
;
elif
: ELIF
;
begin
: /* Nothing */
;
end
: /* Nothing */
;
expr
: NUMBER
;
%%
Ich habe ‚NUMBER‘ als Dummy-Element anstelle der Dinge, und ich ELIF statt ELSEIF. Es enthält eine DANN, aber das ist optional. Die ‚begin‘ und ‚end‘ Operationen verwendet wurden im generierten Programm die Programmzähler zu greifen - und soll daher von dieser entfernbar sein, ohne es zu beeinflussen
.Es gab einen Grund, warum ich dachte, ich brauchte anstelle der normalen linken Rekursion rechts Rekursion verwenden - aber ich glaube, es war mit der Code-Generierung Strategie zu tun, war ich mit, eher als alles andere. Die Fragezeichen in dem Kommentar waren im Original; Ich erinnere mich nicht glücklich mit ihm zu sein. Das Programm als Ganze funktioniert - es ist ein Projekt, das auf der Rückseite Brenner für die letzten zehn Jahre oder so (hmmm ... Ich habe einige Arbeit am Ende des Jahres 2004 und Anfang 2005 gewesen ist, vor, dass, war es 1992 und 1993).
Ich habe nicht die Zeit ausarbeitet verbracht, warum diese konfliktfrei kompiliert und was ich skizzierte früher nicht. Ich hoffe, es hilft.
