Problem mit Gleichungsanalyse



  • 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):

    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



  • 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.



  • 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



  • 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

    double liesSumme(...){
       double a=liesFaktor(...);
       liesPluszeichen(...);
       double b=liesFaktor(...);
       return a+b;
    }
    

    oder

    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.

    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.

    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;
       }
    }
    
    double Summe::auswerte(){
       return f1->auswerte()+f2->auswerte();
    }
    
    void Summe::compileToCMinusMinus(ostream& out){
       out<<"((";
       f1->compileToCMinusMinus(out);
       out<<")+(";
       f2->compileToCMinusMinus(out);
       out<<"))";
    }
    

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

    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ö).



  • Hallo,

    volkard schrieb:

    Da sehe ich keinen großen Unterschied.

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

    volkard schrieb:

    ....
    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:

    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.

    .....
    

    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:

    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



  • erik.vikinger schrieb:

    volkard schrieb:

    ....
    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 😉

    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 👍 Du wirst feststellen dass sich das sehr lohnen wird was Erweiterbarkeit, Performanz und Code-Eleganz angeht 🙂



  • Mini-Code zum Anschauen:

    #include <iostream>
    using namespace std;
    
    char programm[]="(2+2*3)/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.



  • parseZahl



  • Hallo,

    volkard schrieb:

    Mini-Code zum Anschauen:

    .....
    

    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



  • 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.



  • 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.



  • 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



  • 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.



  • 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.

    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'

    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.



  • 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:

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

    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



  • 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


Log in to reply