C/C++ Forum :: Problem mit Gleichungsanalyse

volkard Moderator 12:30:10 12.03.2010 Titel:

erik.vikinger schrieb:

Auch kann ich nicht erkennen wo man die Unterscheindung bei '+' und '-' zwischen Vorzeichen und Rechen-Operator machen müsste.

Die Vorzeichen stecken in parseTerm und die Rechen-Operatoren stecken in parseSumme, weil die Grammatik das so für Term und Summe vorgeschrieben hatte.

erik.vikinger Mitglied 23:51:39 12.03.2010 Titel:

Hallo,

volkard schrieb:

Die Vorzeichen stecken in parseTerm und die Rechen-Operatoren stecken in parseSumme,

Ja, ich hab es jetzt gesehen. Danke für den Hinweis. Ich will nicht unhöflich sein aber das ist IMHO ein Beispiel dafür wie man zu viel Logik in zu wenig Code versteckt.

Ich hab meinen Ansatz gerade fertig bekommen (naja es funktioniert mit ein paar Beispielgleichungen), es sind etwa 1200 Zeilen (inklusive vielen Kommentaren, einiges an Debug-Code aber ohne die knapp 500 Zeilen für den Zahlen-Decoder der aber schon alle möglichen Zahl-Formate, Zahl-Systeme und Darstellungen unterstützt (Oktal fehlt aber noch und Gleitkomma dürfte insgesamt noch mal ein paar größere Erweiterungen bringen)), es werden fast alle wichtigen Operatoren unterstützt (außer Schieben und Rotieren), das einzige wichtige was noch fehlt sind die Labels aber die werden fast immer genauso wie die Zahlen behandelt (also das ist eher was das noch in den Parser/Tokenizer rein muss). Die Baum-Optimierung geht auch schon, was natürlich mangels Labels immer auf eine einzige Zahl als konkretes Ergebnis hinaus läuft.

Bashar schrieb:

... und dann die Implementierung anpassen (und dabei hoffentlich keine Fehler machen).

Das klingt jedenfalls nicht sehr flexibel (eigentlich eher abschreckend unflexibel). Deine anderen Vorschläge schau ich mir mal am Wochenende an, Danke dafür.

Wenn ich z.B. in Volkard's Code einen neuen Operator mit einer Priorität zwischen Punktrechnung und Strichrechnung einfügen wollte muss ich, glaube ich zumindest, fast den gesamten Code anfassen. Stimmt das? Wenn nein, was hab ich übersehen?

Ich bin mir noch nicht sicher welchen genauen Umfang an Operatoren ich unterstützen möchte/muss, ich will mir derzeit aber auf keinen Fall etwas verbauen (Gleitkomma muss auch noch kommen). Was ich an Volkard's Code noch ungünstig finde ist das überall mit der Text-Darstellung gearbeitet wird, ich habe den (subjektiven) Eindruck der Parser/Tokenizer ist quer über den Interpreter verstreut. Im Prinzip ist die Text-Darstellung aber auch nur eine lineare Liste nur eben in einem anderen Format und mit weniger Kontext-Informationen, meine Liste enthält nur noch abstrakte Objekte welche generisch behandelt werden können und auch ne Menge an Kontext-Informationen ist enthalten z.B. die Klammern-Ebene. Ich kann somit beliebige Operatoren und/oder Prefixe dazu bauen ohne den Umwandler, von Liste nach Baum, dafür anfassen zu müssen. Meine Implementierung ist sicher einiges langsamer als ein "Recursive-Descent-Parser" aber dafür IMHO deutlich flexibler und wartbarer. Aber da meine Liste IMHO nicht so anders wie die Text-Darstellung ist interessiere ich mich immer noch für den "Recursive-Descent-Parser" um damit meine (saulahme) schleifenbasierte Umwandlung zu ersetzen, falls ich damit keine Flexibilität einbüße.

Blue-Tiger schrieb:

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

Also jetzt bin ich geneigt dem zu widersprechen, bis auf den Aspekt der Performance natürlich.

Wenn meine Ansichten total falsch sind dann sagt mir das Bitte! Ich möchte keine falschen Schlussfolgerungen aus eigenem Mist-Code ziehen.

Grüße
Erik

volkard Moderator 00:20:48 13.03.2010 Titel:

erik.vikinger schrieb:

ungünstig finde ist das überall mit der Text-Darstellung gearbeitet wird, ich habe den (subjektiven) Eindruck der Parser/Tokenizer ist quer über den Interpreter verstreut

Hängt von der Sprache ab. Würde ich eine haben wollen, wo erstmal Tokens klar definiert sind, würde ich wohl auch erstmal einen Tokenizer drüberjagen und die normale einfach verkette Liste erzeugen und den rekursiven Abstiegscompiler nicht auf die rohen Zeichen loslassen, sondern auf die Tokenliste.
Vielleicht hat der rekursive Abstiegscompiler erst die Nase voll vorn, wenn Du auch Konstanten wie PI, Funktionen wie sin und am Ende sogar zuweisbare Variablen und Schleifen einbaust.
Deine Implemetierung ist nicht spürbar langsamer. Änderbarkeit ist eher irrelevant. Eigentlich solltest Du besonders beim klasischen Ansatz die Grammatik vorher fertig haben. Wenn mich nicht alles täuscht, kann man beim Absteigscompiler die nuemodischen Fürze leichter einbauen.

Bashar Mitglied 00:43:56 13.03.2010 Titel:

erik.vikinger schrieb:

Hallo,

volkard schrieb:

Die Vorzeichen stecken in parseTerm und die Rechen-Operatoren stecken in parseSumme,

Ja, ich hab es jetzt gesehen. Danke für den Hinweis. Ich will nicht unhöflich sein aber das ist IMHO ein Beispiel dafür wie man zu viel Logik in zu wenig Code versteckt.

Die Logik steckt, wie gesagt, nicht im Code, sondern in der Grammatik, aus der der Code generiert wurde. Die muss man immer im Hinterkopf haben.

Das tolle an solche formalisierten Verfahren ist, dass es dazu seit 50 Jahren ausgefeilte Theorien gibt. Das Thema ist gut untersucht, das Problem ist gelöst. Man weiß, wofür es funktioniert und was man tun muss, wenn es mal nicht funktioniert. Man kann einen ganzen Compiler auf der Basis schreiben. Einigen Programmiersprachen (z.B. Pascal) sieht man auch sehr deutlich an, dass sie im Hinblick auf diese Methode (Top-Down-Syntaxanalyse) entworfen worden sind.

Dein Ansatz dagegen klingt nicht sehr vertrauenerweckend, aber das kann ich nicht beurteilen, ohne ihn zu kennen. Die Erfahrung zeigt nur, dass solche ad-hoc-Methoden oft in ungewöhnlichen (ungetesteten) Fällen versagen.

Zitat:

Wenn ich z.B. in Volkard's Code einen neuen Operator mit einer Priorität zwischen Punktrechnung und Strichrechnung einfügen wollte muss ich, glaube ich zumindest, fast den gesamten Code anfassen. Stimmt das? Wenn nein, was hab ich übersehen?

Na selbst wenn, das sind nur 84 Zeilen, die kann man schonmal insgesamt anfassen. Aber selbst das muss man nicht tun. Wenn du zwischen Summe und Produkt noch ein Foo einfügen willst, dann bedeutet das folgende Änderungen:
Neue Funktion parseFoo, die analog zu parseSumme aufgebaut ist.
parseSumme ruft statt parseProdukt parseFoo auf.

Das wars schon.

Wie ich die ganze Zeit schon sage, sollte man dabei die Grammatik im Auge haben. Die dürfte hier ungefähr so aussehen (ist in Extended Backus Naur Form mit *-Operator, der für beliebig viele Wiederholungen steht, weil Volkard das mit while-Schleifen implementiert hat. Die reine Lehre macht das mit mehr Rekursion in der Grammatik):

Summe -> Produkt ('+' Produkt | '-' Produkt)*
Produkt -> Term ('*' Term | '/' Term)*
Term -> '+' Term | '-' Term | '(' Summe <irgendwas> | Zahl
Zahl -> '0' | '1' | ... | '9'

bei dem "<irgendwas>" ist irgendein Zeichen erlaubt, da hat Volkard geschummelt. Eigentlich sollte auf ')' geprüft werden und sonst ein Syntaxfehler kommen.

Mit den Änderungen für die Foo-Operatoren # und &:

Summe -> Foo ('+' Foo | '-' Foo)*
Foo -> Produkt ('#' Produkt | '&' Produkt)*
Produkt -> Term ('*' Term | '/' Term)*
Term -> '+' Term | '-' Term | '(' Summe <irgendwas> | Zahl
Zahl -> '0' | '1' | ... | '9'

Zitat:

Ich bin mir noch nicht sicher welchen genauen Umfang an Operatoren ich unterstützen möchte/muss, ich will mir derzeit aber auf keinen Fall etwas verbauen (Gleitkomma muss auch noch kommen). Was ich an Volkard's Code noch ungünstig finde ist das überall mit der Text-Darstellung gearbeitet wird, ich habe den (subjektiven) Eindruck der Parser/Tokenizer ist quer über den Interpreter verstreut.

Das ist ja auch nur ein Minimalbeispiel mit keinem bzw. nur einem trivialen Scanner: Jedes Zeichen ist ein Token. Bei einem richtigen Parser würde da halt nicht isdigit(peek()) stehen sondern vielleicht peek()->tokenType == FLOAT_LITERAL o.ä.

Also ich würde vorschlagen, du ziehst das Projekt erstmal so durch wie geplant (scheint ja schon recht weit zu sein) und guckst dir dann mal die eine oder andere formale Syntaxanalysemethode an.

erik.vikinger Mitglied 10:44:57 13.03.2010 Titel:

Hallo,

Bashar schrieb:

erik.vikinger schrieb:

Ich will nicht unhöflich sein aber das ist IMHO ein Beispiel dafür wie man zu viel Logik in zu wenig Code versteckt.

Die Logik steckt, wie gesagt, nicht im Code, sondern in der Grammatik, aus der der Code generiert wurde. Die muss man immer im Hinterkopf haben.

Okay, diese Grammatik hab ich halt nicht in der Form im Kopf, ich kann Dir zwar ganz genau erklären welche Regeln es alles geben soll (was alles vor oder nach einem bestimmten Element kommen darf) aber sonst nichts. Ich hätte gestern wohl besser schreiben sollen das zu den gut 80 Zeilen Code noch gut 160 Zeilen Kommentare müssten. Für jemand der mit diesem Konzept vertraut ist ist der Code von Volkard sicher Glasklar, aber ich hab wirklich lange und intensiv auf den Code schauen müssen und bin mir eigentlich immer noch nicht sicher das ich verstehe was er tut.

Bashar schrieb:

Dein Ansatz dagegen klingt nicht sehr vertrauenerweckend, aber das kann ich nicht beurteilen, ohne ihn zu kennen. Die Erfahrung zeigt nur, dass solche ad-hoc-Methoden oft in ungewöhnlichen (ungetesteten) Fällen versagen.

Die lineare Liste prüfe ich schon sehr intensiv auf alles mögliche ab, dafür nehme ich mir auch gut 120 Zeilen. Nachdem ich die Unterstützung für Labels fertig hab werde ich einen kleinen Testbench schreiben um mit ner guten Anzahl an Test-Gleichungen den Literal-Parser zu testen.

Bashar schrieb:

Wenn du zwischen Summe und Produkt noch ein Foo einfügen willst, dann bedeutet das folgende Änderungen:
Neue Funktion parseFoo, die analog zu parseSumme aufgebaut ist.
parseSumme ruft statt parseProdukt parseFoo auf.
Das wars schon.

Ahja, das klingt nicht ganz so schlimm wie ich erst dachte. In meinem Code muss ich den neuen Operator nur in ein enum mit aufnehmen, ihm eine Priorität geben, eine Berechnung in TreeOperator::calc() einfügen (bis hier alles einzeilige Änderungen) und der Parser muss das oder die Text-Zeichen erkennen können. Das ist es was ich an meiner momentanen Implementierung gut finde, ich kann an jeder möglichen Fähigkeit drehen ohne viel Code anfassen zu müssen, der Code ist fast komplett nur von ein paar enum's abhängig.

Bashar schrieb:

Um ehrlich zu sein, ich verstehe nur Bahnhof.

Ich glaube ich sollte mich zum rechten Zeitpunkt mit dieser Thematik genauer beschäftigen.

Bashar schrieb:

Also ich würde vorschlagen, du ziehst das Projekt erstmal so durch wie geplant (scheint ja schon recht weit zu sein) und guckst dir dann mal die eine oder andere formale Syntaxanalysemethode an.

Ja, ich mach das noch so fertig wie ich angefangen, aber mich stört es schon das ich die Umwandlungs-Funktion, von Liste nach Baum, so oft aufrufen muss bis die Liste nur noch ein einziges Element, den Baum, enthält. Die Umwandlungs-Funktion sucht sich immer das Element mit der höchsten Priorität und erledigt das, dieser Vorgang ist IMHO sehr ineffizient (bei jedem erneutem Aufruf muss immer wieder neu gesucht werden).

volkard schrieb:

erik.vikinger schrieb:

ungünstig finde ist das überall mit der Text-Darstellung gearbeitet wird, ich habe den (subjektiven) Eindruck der Parser/Tokenizer ist quer über den Interpreter verstreut

Hängt von der Sprache ab. Würde ich eine haben wollen, wo erstmal Tokens klar definiert sind, würde ich wohl auch erstmal einen Tokenizer drüberjagen und die normale einfach verkette Liste erzeugen und den rekursiven Abstiegscompiler nicht auf die rohen Zeichen loslassen, sondern auf die Tokenliste.

Ich finde den Tokenizer schon allein deshalb sinnvoll weil der eigentliche Gleichungsinterpreter so von der Text-Darstellung unabhängig ist.

volkard schrieb:

Vielleicht hat der rekursive Abstiegscompiler erst die Nase voll vorn, wenn Du auch Konstanten wie PI, Funktionen wie sin und am Ende sogar zuweisbare Variablen und Schleifen einbaust.

Also Variablen oder Schleifen werde ich in einem Assembler hoffentlich nicht brauchen (Konstanten macht der Präprozessor), sin u.ä. würde ich als Präfix implementieren wobei ich dann allerdings die Regel das nicht mehrere Präfixe hintereinander stehen dürfen aufgeben müsste (sonst ginge ja nicht "- sin 5").

volkard schrieb:

Deine Implemetierung ist nicht spürbar langsamer.

Ich denke schon das meine momentane Implementierung sehr langsam ist, die Liste (ich nehme dafür vector) wird sehr oft immer wieder durchlaufen.

volkard schrieb:

Änderbarkeit ist eher irrelevant.

Wenn die Syntax-Definition fertig wäre vielleicht, aber ich möchte erstmal überhaupt vorwärts kommen und der Literal-Parser ist in einem Assembler nun mal von elementarer Wichtigkeit.

volkard schrieb:

Eigentlich solltest Du besonders beim klasischen Ansatz die Grammatik vorher fertig haben.

Also ein paar Grundregeln wie das Klammern die höchste Priorität haben, danach die Präfixe kommen und als letztes die Operatoren mit jeweils individueller Priorität. Mehr hab ich aber nicht wirklich festgelegt und wenn sich an diesen Basics was ändern würde müsste ich schon sehr viel Code anfassen.

volkard schrieb:

Wenn mich nicht alles täuscht, kann man beim Absteigscompiler die nuemodischen Fürze leichter einbauen.

Ich werde mich mit diesem Thema wohl definitiv genauer beschäftigen müssen, aber nicht heute.

Grüße und Danke für Eure Antworten!
Erik

erik.vikinger Mitglied 21:04:33 13.03.2010 Titel:

Hallo,

Bashar schrieb:

Die Erfahrung zeigt nur, dass solche ad-hoc-Methoden oft in ungewöhnlichen (ungetesteten) Fällen versagen.

Denkst Du bei den "ungewöhnlichen Fällen" an was bestimmtes?
Ich bin gerade dabei eine Sammlung Testcases (positive und negative) anzulegen, für zusätzliche Vorschläge wäre ich sehr dankbar.

Grüße
Erik