Interpreterbau - Ein Anfang



  • Man schaue sich das hier einmal an:

    So wird es im Code definiert:

    case '}':
          readNextChar();
          Toki.push_back(TT_LBRACE);
          return Token(TT_LBRACE);
        case '{':
          readNextChar();
          Toki.push_back(TT_RBRACE);
          return Token(TT_RBRACE);
    

    Lets twist it bei der Ausgabe:

    Eingabe: "class a {"
    
    TT_CLASS = 0
    TT_STRING = 0
    TT_LBRACE = 0
    

    TT_LBRACE sollte eigentlich nach dem Code TT_RBRACE heißen...



  • Hallo,
    ich fände eine Weiterführung des Interpreters, vorallem aus dem mathematischen Raum hinaus eine wirklich interessante Artikelreihe 😃



  • 🙂



  • Ja, das stimmt natürlich und ich hatte es ja auch vor. Eventuell gehe ich das demnächst mal an. Es erfordert halt nur sehr viel Zeit. 😉

    Ich bin mir auch noch nicht sicher, was für eine Sprache es dann werden soll. Eventuell einfach eine Modellsprache, wie PL/0. Es geht ja in erster Linie um das Konzept. 🙂

    PL/0 ist grundsätzlich eine recht vollständige Sprache mit Abfragen, Schleifen und so weiter, aber kennt nur den Datentyp Integer. Der Vorteil ist auch, dass es dazu sehr viele fertige Projekte und anderes Material gibt. Da kann man sein Wissen dann noch zusätzlich vertiefen. Mal sehen. 😉



  • Hallo, Tutorials zu so leichten Sprachen findet man überall im Netz, ich fände ein Tutorial zu einem Webserver (für den man programmieren kann), also so wie PHP sehr viel spannender. Natürlich nicht so umfangreich 😃

    Danke



  • Hallo123 schrieb:

    Hallo, Tutorials zu so leichten Sprachen findet man überall im Netz, ich fände ein Tutorial zu einem Webserver (für den man programmieren kann), also so wie PHP sehr viel spannender. Natürlich nicht so umfangreich 😃

    Danke

    Schau dir mal Tntnet an: http://www.tntnet.org/



  • Hallo, ich habe ein kleines Problem mit meinem eigenen Interpreter, nämlich: Was mache ich, wenn ich mehrere Ausdrücke hintereinander habe (z.B.:

    i = 0;
    a = 6;
    

    )? Muss ich ein Array von Nodes machen? Und wie würde ich dann z.B. einen C++-SC in einen AST überführen? (ich weiß, dass das viel zu komplex ist ;))

    Viel Dank im Voraus



  • C++ompiler schrieb:

    Hallo, ich habe ein kleines Problem mit meinem eigenen Interpreter, nämlich: Was mache ich, wenn ich mehrere Ausdrücke hintereinander habe (z.B.:

    i = 0;
    a = 6;
    

    )? Muss ich ein Array von Nodes machen? Und wie würde ich dann z.B. einen C++-SC in einen AST überführen? (ich weiß, dass das viel zu komplex ist ;))

    Viel Dank im Voraus

    Das kommt ganz auf den Anwendungsfall an. Wenn du eine Sprache entwickelst, bei der das Programm direkt ausgeführt bzw. in eine andere Sprache kompiliert werden soll, dann kann es Sinn machen, dass du für jede Deklaration ein Node anlegst. Dann könntest du zur Laufzeit den Speicher berechnen bzw. bei der neue Sprache so die Deklaration generieren.

    Ansonsten musst du eine Symboltabelle haben (solltest du für die semantische Analyse ohnehin schon haben) und für die Variablen eine Adresse berechnen. Dann kann jeder Ident mit dem entsprechenden Eintrag in der Symboltabelle verknüpft werden und bei der Codegenerierung weiß der Compiler so, wie er den Code zu generieren hat.

    Das ganze ist dann im Detail doch etwas anspruchsvoller, also am besten mal eine fertige Implementierung suchen und davon abschauen. Suchwörter sind jedenfalls Symboltabelle, Adressgenerierung, usw.



  • Hey,
    dein Tutorital hat mir sehr geholfen. Allerdings so 100% habe ich es wohl noch nicht verstanden.
    Gibt es eine Möglichkeit mir die Zwischenergebnisse anzuzeigen? Im Parser kann ich mir ohne Probleme das aktuelle Ergebnis res ausgeben lassen, aber wie kann ich mir die aktuell Zusammengefasste Rechnung ausgeben lassen?



  • gilwell88 schrieb:

    Hey,
    dein Tutorital hat mir sehr geholfen. Allerdings so 100% habe ich es wohl noch nicht verstanden.
    Gibt es eine Möglichkeit mir die Zwischenergebnisse anzuzeigen? Im Parser kann ich mir ohne Probleme das aktuelle Ergebnis res ausgeben lassen, aber wie kann ich mir die aktuell Zusammengefasste Rechnung ausgeben lassen?

    Schau dir mal das C# Programm an. Das stellt das ganze visuell dar und hilft vielleicht beim Verständnis. Oder was meinst du? Weil Zwischenergebnis und zusammengefasste Rechnung erscheinen mir identisch? 🤡

    Bin mir nicht so sicher, wo dein Verständnisproblem genau ist und was du gerne als Hilfe ausgegeben haben willst. 😉



  • Das C# habe ich mir angeschaut und auch gefunden wo der Baum erstellt wird, ich werde mal versuchen soetwas in C++ zu übertragen, mal sehen ob mir das gelingt.

    Am liebsten wäre es mir, wenn in der Ausgabe solche Zwischenergebnisse ständen, wie man sie auch hat wenn man von Hand rechnet, also z.B.:
    Eingabe: (20+1)/(2+1)
    Ausgabe: = 21/(2+1)
    Ausgabe: = 21/3
    Ausgabe: =7
    Diese Zwischenschritte sind alle irgendwie gespeichert und der Parser macht sie auch so, ich weiß nur nicht wie ich sie ausgebe.



  • Das ist wohl etwas tricky. Ich würde den AST nehmen und immer ein Node evaluieren lassen und die anhängenden löschen und durch das Ergebnis ersetzen. Dann Ausgeben. Und das ganze solange wiederholen bis man am Root Node ist...



  • Hi, vielen Dank für das Tutorial. Hat mir sehr geholfen! Habe deine EBNF übernommen.
    Jetzt möchte ich aber für meinen Interpreter noch das Zeichen '^' implementieren, um Exponenten damit zu unterstützen.

    Mein Problem ist nun, dass ich nicht weiß wie ich das in deiner EBNF korrekt formuliere, ohne die EBNF komplett zu verändern ... hätte da jemand einen Vorschlag? Ich steh auf dem Schlauch.

    Vielen Dank schonmal!



  • derp schrieb:

    Hi, vielen Dank für das Tutorial. Hat mir sehr geholfen! Habe deine EBNF übernommen.
    Jetzt möchte ich aber für meinen Interpreter noch das Zeichen '^' implementieren, um Exponenten damit zu unterstützen.

    Mein Problem ist nun, dass ich nicht weiß wie ich das in deiner EBNF korrekt formuliere, ohne die EBNF komplett zu verändern ... hätte da jemand einen Vorschlag? Ich steh auf dem Schlauch.

    Vielen Dank schonmal!

    Eigentlich ist das ziemlich trivial:

    Start = (Multiplikation) { ("+" | "-") (Multiplikation) } ;

    Multiplikation = (Potenz) { ("*" | "/") (Potenz) } ;

    Potenz = (Klammer) { "^" (Klammer) } ;

    Klammer = ["+" | "-"] ((Zahl) | "(" (Start) ")") ;

    Zahl = (Ziffer) { (Ziffer) } ;

    Ziffer = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;



  • Vielleicht Offtopic, aber das Zeichen ^ für Potenzen zu nutzen halte ich für unglücklich. Jeder der aus der C-Welt kommt wird versuchen XOR mit dem Zeichen zu nutzen. Genauso gibt es jedoch den üblichen Einsteigerfehler ^ in C für Potenzen zu nutzen um sich dann zu wundern was da vor sich geht.. Also ein Dilema, gewissermaßen. Eine kleine Anregung - vielleicht findet sich ja eine bessere Lösung.



  • Ich sehe oft "**" als Potenz.



  • Hallo, vielen Dank erstmal für diesen großartigen Artikel. Da ich neu in der Materie bin, habe ich eine (vielleicht simple 😋 ) Frage:
    Wie schaffe ich es, dass man auch während der Laufzeit eigene Variablen erstellen kann, beispielsweise:
    r = 3.5
    2*r+3, sodass man als Ausgabe 10 erhält. Und meine 2. Frage ist, ob ihr mir das folgende Buch empfehlen würdet, oder nicht:
    http://www.cogito-ergo-sum.org/index.php/en/computer-science/10-parsertechniken-in-c, oder würdet ihr mir etwas anderes empfehlen, dann aber relativ verständlcih bitte, da ich erst in der 9. Klasse bin. Vielen Dank schonmal 👍



  • Das mit den eigenen Variablen ist relativ einfach zu lösen, du erstellst einfach eine globale (*grabs popcorn*) Liste aller Variablen und ihrer Werte (am einfachsten ist das wohl mit einer map möglich). Und in der NodeIdent schaust du im Falle, dass keine Konstante gefunden wurde einfach in der map nach und nimmst den Wert.



  • henriknikolas schrieb:

    oder würdet ihr mir etwas anderes empfehlen

    Bei Compiler-Bau geht nichts über das Dragon Book von Aho, Sethi, Ullman, Lam:
    http://www.amazon.de/Compiler-Prinzipien-Techniken-Werkzeuge-Pearson/dp/3827370973/



  • SomeGuy schrieb:

    Das mit den eigenen Variablen ist relativ einfach zu lösen, du erstellst einfach eine globale (*grabs popcorn*) Liste aller Variablen und ihrer Werte (am einfachsten ist das wohl mit einer map möglich). Und in der NodeIdent schaust du im Falle, dass keine Konstante gefunden wurde einfach in der map nach und nimmst den Wert.

    Gut, ich glaube ich habe mich etwas ungenau ausgedrückt, oder dich falsch verstanden. Ich meinte das so, dass r(siehe mein Beispiel) noch in keiner map enthalten ist, dass man gar nicht weiß, dass r eine Variable ist. Gibt man dann im laufenden Programm ein r = 8 wird r in einer map mit dem zugehörigen Wert gespeichert. Dann muss man ja noch bei TokenType TT_Assign(für die Zuweisung) hinzufügen. Wo und wie würdet ihr das = im Parser auswerten?

    oenone schrieb:

    Bei Compiler-Bau geht nichts über das Dragon Book von Aho, Sethi, Ullman, Lam:
    http://www.amazon.de/Compiler-Prinzipien-Techniken-Werkzeuge-Pearson/dp/3827370973/

    Das Buch habe ich mir schon in einer Bibliothek bestellt, es müsste bald ankommen, hoffe ich zumindest. Ich hoffe auch, dass ich es einigermaßen verstehe.


Log in to reply