C/C++ Forum :: Problem mit Gleichungsanalyse

erik.vikinger Mitglied 12:02:15 11.03.2010 Titel:

Hallo,

ich hab ein paar Fragen zur Gleichungsanalyse :

Ich bin so weit das ich eine Gleichung von ihrer Textform in eine lineare Liste umwandeln kann, also z.B. "-(90+9+-0)" in "Sign-Neg , Klammer-Auf , Zahl 90 , Operator-ADD , Zahl 9 , Operator-ADD , Sign-Neg , Zahl 0 , Klammer-Zu". Dabei hat jedes Objekt eine Klammern-Ebene und die Operatoren eine Priorität.
Ich möchte das ganze jetzt in einen Baum umwandeln (Vorzeichen haben nur 1 Kind Operatoren haben 2 Kinder):

Code:
Sign-Neg Operator-ADD Operator-ADD Zahl 90 Zahl 9 Sign-Neg Zahl 0

Code:
Sign-Neg Operator-ADD Operator-ADD Zahl 90 Zahl 9 Sign-Neg Zahl 0

Code:
Sign-Neg Operator-ADD Operator-ADD Zahl 90 Zahl 9 Sign-Neg Zahl 0

um diesen Baum dann später von den Blättern hin zur Wurzel auszurechen, also "-((90+9)+(-0))".
Ich hab mir überlegt das ich mir immer zuerst den Teil-Bereich aus der Liste suche der die höchste Klammer-Ebene hat und dann in diesem Bereich den ersten Operator mit der höchsten Priorität (von links nach rechts) suche, diesen Operator wandle ich dann in einen Teil-Baum um und ersetze damit den Operator und die zwei umgeben Objekte in der Liste. Das mache ich so lange bis die Liste nur noch ein Element, den neuen Baum, enthält.

Klingt das Konzept sinnvoll?
Hab ich was übersehen?
Gibt es bessere Wege um zu meinem Ziel zu kommen?
Andere Hinweise oder Kommentare?

Es ist mir wichtig das dieser Vorgang möglich kompatibel zu C ist, also der Benutzer keine neuen Vorrang-Regeln bzw. Assoziativitäts-Regeln lernen muss. Ausrechen geht nicht gleich da anstatt Zahlen auch Labels vorkommen können die zu dem Zeitpunkt noch nicht auflösbar sind.

Grüße und Danke für alle hilfreichen Antworten!
Erik

Bashar Mitglied 12:30:56 11.03.2010 Titel:

Lies dir mal was grundlegendes zum Thema Compilerbau an. Da böte sich ein ganz simpler Recursive-Descent-Parser an, sowas kann man von Hand schreiben.

erik.vikinger Mitglied 14:06:10 11.03.2010 Titel:

Hallo,

Bashar schrieb:

Lies dir mal was grundlegendes zum Thema Compilerbau an.

Ja, das sollte ich wohl wirklich mal tun. Ich schreibe eigentlich "nur" einen Assembler und wollte gerne um das komplexe Thema Compilerbau herum kommen, aber das ist offensichtlich eine Fehleinschätzung meinerseits.

Bashar schrieb:

Da böte sich ein ganz simpler Recursive-Descent-Parser an,

Was ich dazu im Internet gefunden hab sieht eher nach der Lösung (ausrechnen) für die Gleichung aus, ich benötige aber auf jeden Fall den Baum und kein mathematisches Ergebnis. Natürlich ist es schön wenn ich den Baum unmittelbar nach der Erstellung optimieren kann (manchmal, aber nicht immer, kommt dabei auch bereits ein fertiges Ergebnis raus) aber der Baum muss später verarbeitet werden.

Den eigentlichen Parser und Tokenizer hab ich bereits fertig, die lineare Liste hab ich auch bereits auf Korrektheit geprüft, ich muss nur noch die Liste in einen Baum überführen. Ich denke das ich fast fertig bin und wollte daher wissen/diskutieren ob mein Weg noch stimmt.

Grüße
Erik

volkard Moderator 14:32:22 11.03.2010 Titel:

Wie Bashar sagte, rekursiver Abstieg.

erik.vikinger schrieb:

Was ich dazu im Internet gefunden hab sieht eher nach der Lösung (ausrechnen) für die Gleichung aus, ich benötige aber auf jeden Fall den Baum und kein mathematisches Ergebnis.

Da sehe ich keinen großen Unterschied.
Ob Du nun

C/C++ Code:
double liesSumme(...){ double a=liesFaktor(...); liesPluszeichen(...); double b=liesFaktor(...); return a+b; }

C/C++ Code:
double liesSumme(...){ double a=liesFaktor(...); liesPluszeichen(...); double b=liesFaktor(...); return a+b; }

C/C++ Code:
double liesSumme(...){ double a=liesFaktor(...); liesPluszeichen(...); double b=liesFaktor(...); return a+b; }

oder

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13	1 2 3 4 5 6 7 8 9 10 11 12 13	class Summe{ Term* f1; Term* f1; ... Summe(Term* a,Term* b) ... }; Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13	class Summe{ Term* f1; Term* f1; ... Summe(Term* a,Term* b) ... }; Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13	class Summe{ Term* f1; Term* f1; ... Summe(Term* a,Term* b) ... }; Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

schreibst, ist egal.

Zitat:

Natürlich ist es schön wenn ich den Baum unmittelbar nach der Erstellung optimieren kann (manchmal, aber nicht immer, kommt dabei auch bereits ein fertiges Ergebnis raus) aber der Baum muss später verarbeitet werden.

Klar.

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14	1 2 3 4 5 6 7 8 9 10 11 12 13 14	Term* Summe::optimize(){//virtual f1=f1->optimize(); f2=f2->optimize(); if(f2->IsZero()){ Term* result=f2; delete this; return result; } if(gleich(f1,f2)){ Term* result(f1,new Zahl(2)); delete this; return result; } }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14	Term* Summe::optimize(){//virtual f1=f1->optimize(); f2=f2->optimize(); if(f2->IsZero()){ Term* result=f2; delete this; return result; } if(gleich(f1,f2)){ Term* result(f1,new Zahl(2)); delete this; return result; } }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14	Term* Summe::optimize(){//virtual f1=f1->optimize(); f2=f2->optimize(); if(f2->IsZero()){ Term* result=f2; delete this; return result; } if(gleich(f1,f2)){ Term* result(f1,new Zahl(2)); delete this; return result; } }

C/C++ Code:
double Summe::auswerte(){ return f1->auswerte()+f2->auswerte(); }

C/C++ Code:
double Summe::auswerte(){ return f1->auswerte()+f2->auswerte(); }

C/C++ Code:
double Summe::auswerte(){ return f1->auswerte()+f2->auswerte(); }

C/C++ Code:
void Summe::compileToCMinusMinus(ostream& out){ out<<"(("; f1->compileToCMinusMinus(out); out<<")+("; f2->compileToCMinusMinus(out); out<<"))"; }

C/C++ Code:
void Summe::compileToCMinusMinus(ostream& out){ out<<"(("; f1->compileToCMinusMinus(out); out<<")+("; f2->compileToCMinusMinus(out); out<<"))"; }

C/C++ Code:
void Summe::compileToCMinusMinus(ostream& out){ out<<"(("; f1->compileToCMinusMinus(out); out<<")+("; f2->compileToCMinusMinus(out); out<<"))"; }

Sowas ähnliches hab ich mal gemacht und es ging supi.

Zitat:

Ich denke das ich fast fertig bin und wollte daher wissen/diskutieren ob mein Weg noch stimmt.

Er stimmt. Dein Vorgehen liest man auch in Büchern (vor allem in älteren, höhö).

erik.vikinger Mitglied 20:51:18 11.03.2010 Titel:

Hallo,

volkard schrieb:

Da sehe ich keinen großen Unterschied.

Okay, dann muss ich mir das wohl noch mal genauer ansehen.

volkard schrieb:

C/C++ Code:
.... Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

C/C++ Code:
.... Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

C/C++ Code:
.... Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

Was ich mich noch frage ist wieso das so fest codiert ist, die Gleichung hat doch der Nutzer meines Programms geschrieben und mein Code muss damit immer zurecht kommen, solange alle Syntax-Regeln eingehalten wurden. Ich vermute mal das dort in Wirklichkeit ein großes switch hin muss, so wie in meinem Code der die lineare Liste erstellt.

volkard schrieb:

Zitat:

Natürlich ist es schön wenn ich den Baum unmittelbar nach der Erstellung optimieren kann (manchmal, aber nicht immer, kommt dabei auch bereits ein fertiges Ergebnis raus) aber der Baum muss später verarbeitet werden.

Klar.

C/C++ Code:
.....

C/C++ Code:
.....

C/C++ Code:
.....

Sowas ähnliches hab ich mal gemacht und es ging supi.

Ich bin mir nicht ganz sicher ob ich deinen Code richtig verstanden hab, ich möchte es eher so machen:

C/C++ Code:
1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9	TreeElement* TreeOperator::optimize() { child1 = child1->optimize(); child2 = child2->optimize(); if ((child1->getType == TreeTypeZahl) && (child2->getType == TreeTypeZahl)) { return rechne(this->operatorType,child1,child2); } //berechne Ergebnis, in abhängigkeit vom Operator-Type, und speichere die Ergebnis-Zahl in einem neuen Tree-Objekt und geb das zurück else { return this; } //konnte nicht optimieren, gibt sich selbst zurück }

C/C++ Code:
1 2 3 4 5 6 7 8 9	TreeElement* TreeOperator::optimize() { child1 = child1->optimize(); child2 = child2->optimize(); if ((child1->getType == TreeTypeZahl) && (child2->getType == TreeTypeZahl)) { return rechne(this->operatorType,child1,child2); } //berechne Ergebnis, in abhängigkeit vom Operator-Type, und speichere die Ergebnis-Zahl in einem neuen Tree-Objekt und geb das zurück else { return this; } //konnte nicht optimieren, gibt sich selbst zurück }

C/C++ Code:
1 2 3 4 5 6 7 8 9	TreeElement* TreeOperator::optimize() { child1 = child1->optimize(); child2 = child2->optimize(); if ((child1->getType == TreeTypeZahl) && (child2->getType == TreeTypeZahl)) { return rechne(this->operatorType,child1,child2); } //berechne Ergebnis, in abhängigkeit vom Operator-Type, und speichere die Ergebnis-Zahl in einem neuen Tree-Objekt und geb das zurück else { return this; } //konnte nicht optimieren, gibt sich selbst zurück }

volkard schrieb:

vor allem in älteren, höhö

Aha.

Ich weiß das mein Zwischenschritt mit der linearen Liste nicht unbedingt die maximale Performance bringt aber dafür kann ich die Liste recht einfach auf Fehler prüfen (z.B. dürfen nicht 2 Operatoren hintereinander kommen) und auch ordentliche/nützliche Fehlermeldungen ausgeben. Ist vielleicht etwas oldfashion aber "Teile und Herrsche" ist IMHO ein gutes Design-Paradigma.

Grüße
Erik

Blue-Tiger Mitglied 21:47:56 11.03.2010 Titel:

erik.vikinger schrieb:

volkard schrieb:

C/C++ Code:
.... Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

C/C++ Code:
.... Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

C/C++ Code:
.... Summe* liesSumme(...){ Term* a=liesFaktor(...);//smart pointer liesPluszeichen(...); Term* b=liesFaktor(...); return new Summe(a,b); }

Was ich mich noch frage ist wieso das so fest codiert ist, die Gleichung hat doch der Nutzer meines Programms geschrieben und mein Code muss damit immer zurecht kommen, solange alle Syntax-Regeln eingehalten wurden. Ich vermute mal das dort in Wirklichkeit ein großes switch hin muss, so wie in meinem Code der die lineare Liste erstellt.

Da hast du rekursiven Abstieg wohl noch nicht so ganz verstanden. Da ist nicht allzu viel fest codiert

Zitat:

volkard schrieb:

vor allem in älteren, höhö

Aha.

Ich weiß das mein Zwischenschritt mit der linearen Liste nicht unbedingt die maximale Performance bringt aber dafür kann ich die Liste recht einfach auf Fehler prüfen (z.B. dürfen nicht 2 Operatoren hintereinander kommen) und auch ordentliche/nützliche Fehlermeldungen ausgeben. Ist vielleicht etwas oldfashion aber "Teile und Herrsche" ist IMHO ein gutes Design-Paradigma.

Mit rekursiven Abstieg kannst du wunderbar sehr passende Fehlermeldungen ausgeben, und das Ganze ist vermutlich noch wesentlich eleganter als dein aktueller Code; und "Divide & Conquer" passt auf Rekursiven Abstieg vermutlich auch besser als auf deinen Code, schliesslich erlaubt dir der Rekursive Abstieg, fuer jeden Operator (bzw. jede Produktion deiner Grammatik, wenn man genau sein will) unabhaengig eine Parsefunktion zu schreiben. Du kannst damit dann jederzeit deine Grammatik erweitern, ohne sehr viel Code schreiben zu muessen. Ach ja, und du kannst direkt einen Parse-Tree erstellen anstatt den Umweg ueber die lineare Liste zu gehen.

Also auch von mir ganz klar der Rat: schau dir Rekursiven Abstieg genauer an :live:

Du wirst feststellen dass sich das sehr lohnen wird was Erweiterbarkeit, Performanz und Code-Eleganz angeht

volkard Moderator 22:05:57 11.03.2010 Titel:

Mini-Code zum Anschauen:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84	#include <iostream> using namespace std; char programm[]="(2+23)/2(3-1)"; char pos=&programm[0]; char* peek() { return pos; } void* pop() { ++pos; } double parseTerm(); double parseProdukt() { double result=parseTerm(); while(peek()==''\|\|peek()=='/') { char* type=peek(); pop(); double rest=parseTerm(); if(type=='') result=rest; else result/=rest; } return result; } double parseZahl() { if(isdigit(peek())) { double result=peek()-'0'; pop(); return result; } cout<<"compilerfehler"; return 0; } double parseSumme() { double result=parseProdukt(); while(peek()=='+'\|\|peek()=='-') { char type=peek(); pop(); double rest=parseProdukt(); if(type=='+') result+=rest; else result-=rest; } return result; } double parseTerm() { if(peek()=='+') { pop(); return parseTerm(); } if(peek()=='-') { pop(); return -parseTerm(); } if(peek()=='(') { pop(); double result=parseSumme(); pop(); return result; } return parseZahl(); } int main() { cout<<parseSumme(); return 0; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84	#include <iostream> using namespace std; char programm[]="(2+23)/2(3-1)"; char pos=&programm[0]; char* peek() { return pos; } void* pop() { ++pos; } double parseTerm(); double parseProdukt() { double result=parseTerm(); while(peek()==''\|\|peek()=='/') { char* type=peek(); pop(); double rest=parseTerm(); if(type=='') result=rest; else result/=rest; } return result; } double parseZahl() { if(isdigit(peek())) { double result=peek()-'0'; pop(); return result; } cout<<"compilerfehler"; return 0; } double parseSumme() { double result=parseProdukt(); while(peek()=='+'\|\|peek()=='-') { char type=peek(); pop(); double rest=parseProdukt(); if(type=='+') result+=rest; else result-=rest; } return result; } double parseTerm() { if(peek()=='+') { pop(); return parseTerm(); } if(peek()=='-') { pop(); return -parseTerm(); } if(peek()=='(') { pop(); double result=parseSumme(); pop(); return result; } return parseZahl(); } int main() { cout<<parseSumme(); return 0; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84	#include <iostream> using namespace std; char programm[]="(2+23)/2(3-1)"; char pos=&programm[0]; char* peek() { return pos; } void* pop() { ++pos; } double parseTerm(); double parseProdukt() { double result=parseTerm(); while(peek()==''\|\|peek()=='/') { char* type=peek(); pop(); double rest=parseTerm(); if(type=='') result=rest; else result/=rest; } return result; } double parseZahl() { if(isdigit(peek())) { double result=peek()-'0'; pop(); return result; } cout<<"compilerfehler"; return 0; } double parseSumme() { double result=parseProdukt(); while(peek()=='+'\|\|peek()=='-') { char type=peek(); pop(); double rest=parseProdukt(); if(type=='+') result+=rest; else result-=rest; } return result; } double parseTerm() { if(peek()=='+') { pop(); return parseTerm(); } if(peek()=='-') { pop(); return -parseTerm(); } if(peek()=='(') { pop(); double result=parseSumme(); pop(); return result; } return parseZahl(); } int main() { cout<<parseSumme(); return 0; }

ALso ich finde, das fühlt sich recht ordentlich an.

Unregistrierter

Zitat:

parseZahl

erik.vikinger Mitglied 08:20:40 12.03.2010 Titel:

Hallo,

volkard schrieb:

Mini-Code zum Anschauen:

C/C++ Code:
.....

C/C++ Code:
.....

C/C++ Code:
.....

ALso ich finde, das fühlt sich recht ordentlich an.

Danke für Deinen Code, aber ich muss leider zugeben das ich nicht sehe wo der flexibel ist. Entweder brauch ich einen kräftigeren Wink oder nen größeren Pfahl.
Die Verarbeitung der Text-Form scheint mir über alles verteilt zu sein, das finde ich persönlich nicht gut. Ich sehe auch nicht wo ich ansetzen müsste wenn ich eine andere Operator-Priorität haben möchte z.B. Strichrechnung vor Punktrechnung (das ist natürlich Quatsch sollte aber möglich sein), bei mir muss ich nur die Tabelle mit den Operator-Prioritäten anpassen und schon hab ich ein anderes Ergebnis. Auch kann ich nicht erkennen wo man die Unterscheindung bei '+' und '-' zwischen Vorzeichen und Rechen-Operator machen müsste.
Entschuldige bitte wenn ich was übersehen hab (ich weiß natürlich auch das Du mir keinen fertigen Code ablieferst), gibt es irgendwo ein gutes Tutorial wo sowas verständlich erklärt wird?

Blue-Tiger schrieb:

Da hast du rekursiven Abstieg wohl noch nicht so ganz verstanden.

Ja, das sehe ich ganz genau so.

Blue-Tiger schrieb:

und das Ganze ist vermutlich noch wesentlich eleganter als dein aktueller Code;

Wenn ich es verstehen würde wohl schon, aber momentan stehe ich echt aufm Schlauch.

Blue-Tiger schrieb:

und "Divide & Conquer" passt auf Rekursiven Abstieg vermutlich auch besser als auf deinen Code,

Momentan macht meine Haupt-Funktion folgendes (6 Unterfunktionen aufrufen):

Textform in lineare Liste umwandeln. (hier sind '+' und '-' noch undefiniert)
'+' und '-' auflösen (dazu muss ich den Type der umliegenden Objekte nur grob bestimmen, es reicht zu wissen ob davor ein Operator kommt aber es ist unwichtig welcher Operator es ist)
Liste auf syntaktische Korrektheit prüfen (diese Funktion muss auch nicht wissen was es so alles an Operatoren gibt, ab hier sollte dann kein Fehler mehr auftreten können)
Klammern aus der Liste entfernen (das ist so primitiv das sich fast keine eigene Funktion gelohnt hätte)
Liste in Baum umwandeln, unter Berücksichtigung der Klammerebenen und der Operator-Prioritäten (so wie in meinem Ursprungspost beschrieben)
Baum optimieren

Ich persönlich finde das sehr gut verteilt und übersichtlich, wenn ich z.B. auf Uni-Code umsteigen wollte bräuchte nur die erste Funktion neu gemacht werden oder wenn ein neuer Operator kommt dann muss auch nur die erste Funktion erweitert, das Operator-Type-Enum ergänzt und in der Operator-Baum-Klasse eine weitere Rechen-Funktion hinzugefügt werden. Das Ändern der Operator-Prioritäten geht einfach in einer Tabelle welche von der vorletzten Funktion benutzt wird.
Jede Änderung erfordert nur eine oder wenige Stellen im Code und wenn ich bei mehreren was vergessen sollte kommt entweder ein Compilerfehler oder zur Laufzeit ne Meldung das der Code nicht weiß was er tun soll (die Operator-Klasse z.B. wird sich beschweren wenn sie nicht weiß was gerechnet werden soll wenn sie den gespeicherten Operator nicht kennt).

Blue-Tiger schrieb:

fuer jeden Operator (....) unabhaengig eine Parsefunktion zu schreiben.

Allzu unabhängig dürfen diese Funktionen nicht sein, gerade für '+' und '-' muss man doch wissen was drumherum ist damit man korrekt zwischen Vorzeichen und Rechen-Operator unterscheidet.

Blue-Tiger schrieb:

Du kannst damit dann jederzeit deine Grammatik erweitern, ohne sehr viel Code schreiben zu muessen.

Das glaube ich Dir gerne aber ich sehe es leider noch nicht. Meine momentane Lösung ist aber IMHO auch sehr pflegeleicht.

Blue-Tiger schrieb:

Ach ja, und du kannst direkt einen Parse-Tree erstellen anstatt den Umweg ueber die lineare Liste zu gehen.

Das ist natürlich ein schöner Gedanke.

Blue-Tiger schrieb:

Also auch von mir ganz klar der Rat: schau dir Rekursiven Abstieg genauer an

Danke, versuche ich. Leider hab ich im Internet kein anfängertaugliches Tutorial dafür gefunden.

Blue-Tiger schrieb:

Du wirst feststellen dass sich das sehr lohnen wird was Erweiterbarkeit, Performanz und Code-Eleganz angeht

Das wäre schön, ich will ja auch was neues lernen.

Grüße
Erik

Bashar Mitglied 11:49:32 12.03.2010 Titel:

Die Idee besteht darin, den Entwicklungsprozess zweizuteilen. Zuerst stellst du die Grammatik auf. Die sollte bestimmten Regeln gehorchen, damit sie eindeutig ist und wie gewünscht implementierbar ist (z.B. keine Linksrekursion enthalten). Die Operatorvorrangregeln stecken in den Regeln der Grammatik. Wenn man die ändern will, muss man die Grammatik ändern. Lies dir z.B. mal den Anhang mit der Syntaxbeschreibung im C- oder C++-Standard durch, um ein Gefühl dafür zu bekommen.

Wenn man die Grammatik dann hat, kann man sie relativ mechanisch 1:1 in Code umsetzen.

Sehr flexibel ist das natürlich nicht, wenn man irgendwelche Sprachregeln ändern will, muss man zuerst in die Grammatik, und dann die Implementierung anpassen (und dabei hoffentlich keine Fehler machen).

Man kann sich einen Parser auch mit Werkzeugen wie boost::spirit bauen, oder von Parsergeneratoren wie antlr oder bison erzeugen lassen.

Für einfache Fälle, wie sie vermutlich bei dir vorliegen, kann man auch einen Operator-Precedence-Parser verwenden. Der funktioniert nur unter bestimmten, sehr engen Voraussetzungen an die Grammatik, aber wenn man nur so Produktionen wie E -> E + E oder E -> ( E ) hat, sollte es gehen.