Wie löse ich einen bison reduce/reduce Konflikt?
In einer anderen Frage dachte ich mir, dass es schöner wäre (alle anderen nicht...😋), wenn das Vorzeichen zur Zahl gehören würde, so dass das Potenzieren nicht das Vorzeichen abbindet... Da wollte ich mal sehen, ob man nicht einen Parser bauen kann, der es wie folgt versteht:Das läuft auch ganz gut, allerdings gibt es massenhaft sogenannte reduce/reduce Konflikte... Die bison Anleitung sagt zwar, dass diese Konflikte in meinem Sinne gelöst werden (die Regel, die zuerst kommt, die kriegt den Zuschlag), aber: Wie krieg ich die warning trotzdem weg?
Das da ist mein yy-file (auszugsweise):
exp:
"-" "num" { std::cout << "NUMinv" << $2 << std::endl; }
| "num" { $$ = new Float($1); std::cout << "num" << $1 << std::endl; }
| "-" exp { std::cout << "inv" << $2 << std::endl; }
| exp "^" exp { std::cout << '^' << std::endl; }
| "name" { std::cout << "var read:" << $1 << std::endl; };
bison sagt dann:
> bison -o viz-yy.c viz.yy -Wcounterexamples
viz.yy: warning: 10 reduce/reduce conflicts [-Wconflicts-rr]
viz.yy: warning: reduce/reduce conflict on tokens "+", "-", "*", "/", "^", ")", "]", "}", ",", ";" [-Wcounterexamples]
Example: "-" "num" •
First reduce derivation
exp
↳ 5: "-" "num" •
Second reduce derivation
exp
↳ 8: "-" exp
↳ 6: "num" •
2 Antworten
Siehe zum Beispiel:
https://www.gnu.org/software/bison/manual/html_node/Reduce_002fReduce.html
Ich habe mir blöderweise nicht aufgeschrieben, wie man Konflikte löst, aber die Lösung dürfte vermutlich darin liegen, Rekursion zu vermeiden, durch Links- oder Rechtsfaktorisierung, bzw. allgemein durch Verwendung nicht-doppeldeutiger Grammatiken.
Man kann auch einen Look-Ahead verwenden, um Konflikte zu behandeln, dann muss die Grammatik aber auch entsprechend parsbar sein. Wenn ich mich nicht irre baut das Bison von selbst, wenn die Grammatik das hergibt. Wobei es da glaube ich auch ein Flag gab, mit dem man zwischen normalem LR und einer Sonderform (ich glaube LALR) umschalten konnte.
https://www.gnu.org/software/bison/manual/html_node/Lookahead.html
https://www.gnu.org/software/bison/manual/html_node/LR-Table-Construction.html
Eine weitere Möglichkeit, Konflikte zu behandeln, die aber eigene Probleme mit sich bringt, ist das festlegen von Operatorpräzedenzen (auch wenn das eigentlich keine wirklichen Präzedenzen sind, sondern das nur der Konfliktbehandlung dient).
Ich würde dir empfehlen:
1.) Die Grammatik zu faktorisieren.
2.) Die Bison-Doku durchzulesen und genaueres in Erfahrung zu bringen und zu lernen über den Parser-Generator (zumindest ein Teil der Kapitel dort ist sicherlich sher aufschlussreich).
https://www.gnu.org/software/bison/manual/html_node/index.html#SEC_Contents
jetzt läuft es so, wie ich will. 😋 😛 😝 😜 🤪
ich habe diese Regel in dem yy-file gelöscht:
"-" "num" { ... }
danach habe ich das ll-file total umgestrickt (jetzt verwendet flex bestimmte reguläre Ausdrücke nur, wenn unmittelbar zuvor bestimmt Ausdrücke erkannt wurden... yay):
%s nosinum
%%
";" BEGIN(INITIAL); return yy::parser::make_EOC(loc);
"+" BEGIN(INITIAL); return yy::parser::make_ADD(loc);
"-" BEGIN(INITIAL); return yy::parser::make_SUB(loc);
"^" BEGIN(INITIAL); return yy::parser::make_POT(loc);
"(" BEGIN(INITIAL); return yy::parser::make_BROP(loc);
")" BEGIN(nosinum); return yy::parser::make_BRCL(loc);
(<INITIAL>[+-])?{float} BEGIN(nosinum); return make_FLOAT(yytext,loc);
%%