Interpreterbau - Ein Anfang



  • SomeRandomGuy schrieb:

    Das ganze Programm ist also später ein großer AST? Dann geh ich mal Grammatik entwerfen 😃

    so wie im Beispiel oben beliebig viele Multiplikationsterme addiert werden können, so kannst du das noch weiter verallgemeinern.

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

    wird noch erweitert sodass du beliebig viele Berechnungen hintereinander machen kannst (mit ";" getrennt)
    GesamtesProgram = {(Start) (";")}
    Start = (Multiplikation) { ("+" | "-") (Multiplikation) } ;

    Zuerst ging nur: 3*(4+5)
    Jetzt geht auch: 3*(4+5) ; 3*(99-1) ; 4+5 ; 4 ;

    Der Baum besteht jetzt also zuerst mal aus der Wurzel, und dann aus den 4 Knoten "Start", und die wiederum setzen sich zusammen aus Knoten "Multiplikation" usw...



  • Mir ist noch eine Kleinigkeit aufgefallen:
    Man kann beispielsweise nicht 3- -e rechnen oder -sqrt(4), da nicht überprüft wird, ob vor einer Funktion oder vor einem Bezeichner ein Vorzeichen kommt
    Man ändert klammer einfach:

    Node *Parser::klammer()
    {
        //...
        else if (myTok.equal(TT_IDENT))
        {
            // Ist das folgende Token eine öffnende Klammer?
            if (myScanner.getNextToken(true).equal(TT_LPAREN))
            {
                // Dann ist es eine Funktion
                return new NodeMul(funktion(), new NodeNumber(sign));
            }
            // Ansonsten eine Konstante
            return new NodeMul(bezeichner(), new NodeNumber(sign));
        }
        //...
    }
    

    Ich habe vor längerer Zeit den Operator ^ für Potenzen eingeführt, dabei bin ich nach der folgenden EBNF vorgegangen:
    ...
    potenz = klammer {^potenz}
    klammer = ["+" | "-"] ((funktion) | (variable {= start}) | (Zahl) | "(" (Start) ")")

    Jetzt gibt es aber das Problem wie Ausdrücke wie -32 interpretiert werden. Mathematisch richtig wäre das dann -9, nach der Grammatik hier aber +9, da potenz() klammer() aufruft, das -3 zurückgibt was mit 2 potenziert wird und dann 9 ergibt. Deshalb habe ich klammer so verändert, dass wenn ein Vorzeichen gefunden wurde, überprüft wird, ob das nächste Zeichen ein ^ ist.

    klammer sieht jetzt bei mir so aus:

    Node* Parser::klammer()
    {
      //Vorzeichen
      int sign = 1;
      if(myTok.equal(TT_PLUS) || myTok.equal(TT_MINUS))
      {
        if(myTok.equal(TT_MINUS))
          sign = -1;
        getNextToken();
        if(myScanner.getNextToken(true).equal(TT_POT))
          return new NodeMul(new NodeNumber(sign), potenz());
      }
      //...
    }
    

    Ach ja, potenz() noch:

    Node* Parser::potenz()
    {
      Node* ergb = klammer();
      if(myTok.equal(Type::TT_POT))
      {
        getNextToken();
        ergb = new NodePot(ergb, potenz());           
      }
      return ergb;
    }
    

    Jetzt die Fragen an die ⚠ Spezialisten:
    1. Ist die Vorgehensweise richtig, oder gibt es einen besseren Ansatz
    2. Hat eine Potenz nicht die gleiche Priorität wie eine Funktion oder eine Variable, sprich würde es sich nicht lohnen Potenzen in klammer() auszuwerten?

    Das war jetzt ziemlich viel Text :D...



  • Ich habe vor längerer Zeit den Operator ^ für Potenzen eingeführt, dabei bin ich nach der folgenden EBNF vorgegangen:
    ...
    potenz = klammer {^potenz}
    klammer = ["+" | "-"] ((funktion) | (variable {= start}) | (Zahl) | "(" (Start) ")")

    um dein Beispiel -3^2 korrekt auszuwerten reicht folgende Änderung:
    (Zahl){ "^" (Zahl) }

    klammer = ["+" | "-"] ((funktion) | (variable {= start}) | (Zahl){ "^" (Zahl) } | "(" (Start) ")")
    

    wenns auch ganze ausdrücke und nicht nur konstante zahlen sein dürfen, dann musst halt auch eine ähnliche regel dafür aufstellen.

    oder du machst es dir noch einfacher und führst eine funktion pow(basis,potenz) ein.



  • Ich hab mir die folgende EBNF dafür aufgestellt:
    ...
    Multiplikation = Vorzeichen { "*" Vorzeichen}
    Vorzeichen = ["+"|"-"] Potenz
    Potenz = Primary { "^" Vorzeichen}
    Primary = Funktion | Klammer | Variable | Zahl
    ...

    Dadurch haben Funktionen, Klammern, Variablen und Zahlen die höchste Priorität, danach kommen Potenzen, die als Argument einen positiven oder einen negativen Exponenten erwarten und dann kommen Vorzeichen.



  • henriknikolas schrieb:

    Ich hab mir die folgende EBNF dafür aufgestellt:
    ...
    Multiplikation = Vorzeichen { "*" Vorzeichen}
    Vorzeichen = ["+"|"-"] Potenz
    Potenz = Primary { "^" Vorzeichen}
    Primary = Funktion | Klammer | Variable | Zahl
    ...

    Dadurch haben Funktionen, Klammern, Variablen und Zahlen die höchste Priorität, danach kommen Potenzen, die als Argument einen positiven oder einen negativen Exponenten erwarten und dann kommen Vorzeichen.

    wenn du deinen Interpreter noch weiter ausbauen möchtest, kann ich dir folgendes Buch empfehlen: "Grundlagen und Techniken des Compilerbaus" von N. Wirth.
    Dort wird ein Compiler für die Sprache Oberon 0 (so ähnlich wie Pascal) entwickelt, und die Sprache kann eigentlich alles, was man sich so wünscht.



  • Dankeschön, ich werde mir das Buch mal ansehen.



  • Ich habe noch eine Frage zum Buch, der Compiler der dort entwickelt wird ist ja sicherlich in Pascal geschrieben. Kann man das dann auch als Pascal-Anfänger verstehen, ich programmiere halt nur in der Schule mit Pascal.



  • henriknikolas schrieb:

    Ich habe noch eine Frage zum Buch, der Compiler der dort entwickelt wird ist ja sicherlich in Pascal geschrieben. Kann man das dann auch als Pascal-Anfänger verstehen, ich programmiere halt nur in der Schule mit Pascal.

    Der Compiler wird in Oberon programmiert - und die Sprache die compiliert wird ist eine Untermenge von Oberon.
    Schau dir einfach ein Online Tutorial zu der Sprache an. Wenn du Pascal kannst, ist der Unterschied nicht allzu groß.

    Ich sehe die Sprache Oberon in dem Fall eher als "Pseudosprache" um zu zeigen, wie man einen Compiler implementieren kann. Es wird wohl kaum jemand auf die Idee kommen, tatsächlich Oberon zu verwenden 😉
    Das Gelernte ist nicht schwierig auf andere Programmiersprachen zu übertragen - ich hab parallel zum Lesen des Buchs eine Skriptsprache in C++ implementiert.



  • Das hat mich überzeugt, dankeschön. Dann werde ich mir das Buch mal bestellen.



  • was ist der vorteil gegenueber wenn ich die grammatik in ebnf definiere anstatt in yacc?



  • Hi,

    vielen Dank für dieses tolle Tutorial, das hat mir sehr weitergeholfen und einen guten Einblick in den Parser-Bau geliefert 🙂
    Ich habe jetzt das Problem, dass ich mit diesem Parser dynamische Formeln lösen möchte.
    Dazu hänge ich den AST in einen Struct, in dem die Formeln gespeichert werden. Das Problem dabei ist, dass Variablen eingesetzt werden müssen, die sich erst zur Laufzeit des Programms ändern (ist ja klar bei Variablen 😉 ).
    Diese Variablen sind ebenfalls in dem Struct gespeichert.
    Ich habe dazu die "klammer()"-Funktion um eckige Klammern erweitert, die eine Variable für den Scanner anzeigen sollen und auch einen entsprechenden Node angelegt.
    Nun meine Frage: Ich möchte das am liebsten über einen Pointer lösen, damit ich nicht immer die Formel neu "Übersetzen" muss. Aber wie bekomme ich den Pointer der Variablen in das entsprechende Token/den Node? Ist das möglich, ohne den Pointer durch alle Klassen durchschleifen zu müssen?



  • erweitere die Basisklasse zu:

    struct Context
    {
         // Zuordnung Variablenname - Variablenwert
         std::map<str::string,int> vars;
    
         // und was du halt sonst noch so zur Lautzeit brauchst ...
    };
    
    // Basisklasse 
    class Node 
    { 
        public: 
            virtual ~Node() { } 
    
            // Ergebnis berechnen 
            virtual int eval(Context& context) const = 0; 
    };
    
    // Zugriff auf Variable "myVar" in einer der eval Funktionen
    context.vars["myVar"]=123;
    // oder 
    return context.vars["myVar"];
    // usw.
    


  • Wollte mal ein großes Danke und "Super!" aussprechen, ist gerade genau das was ich suche^^ (also der ursprüngliche Beitrag, auh wenn die Abhandlung mit lauter "case's" mir irgendwie umständlich vorkommt)



  • huhu,

    ich überlege gerade, wie man das ganze am besten für die einführung von ints und floats sowie operatoren die nur für (unsigned) ints definiert sind funktioniert.

    Es kommt mir recht umständlich vor, separate Ableitungsregeln für diese zu erzeugen.
    Nehmen wir mal an ich würde den Moduloperator "%" mit gleicher Priorität wie "+" und "-" einführen wollen. Üblicherweise ist % nur für unsignes definiert (d.h. <uint> % <uint> ist legal, <float> % <x> nicht z.B.)

    Erster Gedanke:

    [b]Start[/b] = (Multiplikation) { ("+" | "-") (Multiplikation) } ;
    
    [b]Multiplikation[/b] = (Klammer) { ("*" | "/") (Klammer) } ;
    
    [b]Klammer[/b] = [b]["+" | "-"][/b] ((Zahl) | "(" (Start) ")") ;
    
    [b]Zahl[/b] = (Ziffer) { (Ziffer) } ;
    
    [b]Ziffer[/b] = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
    

    zu

    [b]Start[/b] = (Multiplikation) { ("+" | "-") (Multiplikation) } | (?) {"%"} (?) ;
    
    [b]Multiplikation[/b] = (Klammer) { ("*" | "/") (Klammer) } ;
    
    [b]Klammer[/b] = [b]["+" | "-"][/b] ((Zahl) | "(" (Start) ")") ;
    
    [b]Zahl[/b] (== UINT) = (Ziffer) { (Ziffer) } ;
    
    [b]Float[/b] = (Ziffer) {"."} (Ziffer);
    [b]Ziffer[/b] = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
    

    wobei nun unklar ist, was ich für "?" einsetzen soll. (falls das überhaupt so sinnvoll ist).
    Es scheint mir so, als müsste ich für Int und Float separate Ableitungsregeln definieren, denn offenkundig ist nach Standardregeln etwa <int><float> == <float><int> = <float>



  • Denk mal kurz darüber nach, was passiert, wenn du Variablen einführst. Wie würdest du a % 2 parsen?



  • gefühlsmäßig würde ich dem Modulo die gleiche Priorität wie * und / geben:
    Multiplikation = (Klammer) { ("*" | "/" | "%") (Klammer) } ;

    Das Parsen bleibt mal unabhängig vom Datentyp - du brauchst jetzt nicht neue EBNF Regeln für jeden Typen.

    Multiplikation = (Klammer) { ("*" | "/" | "%") (Klammer) } <- Hinweis: "%" nur bei (int) % (int) möglich

    Dafür ist dann die Typprüfung zuständig. Du schaust dir an, welchen Typen der linke und rechte Ausdruck hat, dann schaust du ob der Operator dafür anwendbar ist.
    3.1415 % 3 --> (float) % (int) --> nicht möglich.



  • das was du suchst ist "attributierte Grammatik".
    Das Parsen läuft ja kontextfrei ab - dem Parser ist es also egal in welchem Kontext z.B. ein c=a+b gefunden wird.

    Nun kann man aber den einzelnen Symbolen (oder Knoten im Syntaxbaum) zusätzliche Eigenschaften verpassen. Eine gefundene Konstante 5 hat neben dem int Wert 5 auch einen Datentyp zugeordnet - nämlich TypeInt.
    Eine Variable s1 könnte z.B. TypeString haben.

    Hat man nun z.B. eine Produktionsregel Multiplikant = Faktor * Faktor, so können zusätzlich Regeln definiert werden, wie die Attribute auszusehen haben, sodass das Symbol Multiplikant korrekt ist. Z.B. muss der Datentyp TypeFloat oder TypeInt sein. Man kann gar noch strenger sein und fordern dass beide Faktoren den gleichen Typ haben müssen, 5*3.14 ist dann nicht möglich.

    Am besten schaust du dir ein Buch wie z.B. "Grundlagen und Techniken des Compilerbaus" an. Wenn du das Buch nicht kaufen willst gibts das Buch (auf englisch) auch als PDF auf der Seite der ETH: http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
    Im PDF wird ab S. 26 das oben genannte Thema behandelt.



  • Hi, danke für eure Antworten!
    Der Reihe nach:

    Denk mal kurz darüber nach, was passiert, wenn du Variablen einführst. Wie würdest du a % 2 parsen?

    Wenn ich mit der im Thread verwendeten EBNF arbeiten würde, würde ich float und int bezeichner definieren und einen separaten Zweig beim Modulo verwenden.
    Anscheinend ist das auf jeden Fall der falsche Weg (mir ist auch schon aufgefallen, dass man dann, falls es überhaupt geht, sehr große Grammatiken benötigt).

    gefühlsmäßig würde ich dem Modulo die gleiche Priorität wie * und / geben:

    An sich ist das egal, ich habe jedoch eine Vorlage die ich reverse engineeren möchte, bei dieser haben + - und % die selbe Priorität.

    Dafür ist dann die Typprüfung zuständig

    Ok, an welcher Stelle kommt der zum Einsatz? Ich vermute nachdem der Parsebaum erstellt ist checke ich für jeden Operanden ob die Typen passen?
    Dann muss ich natürlich irgendwie speichern WAS für eine Zahl (im Artikel wird nicht unterschieden zwischen Int und Float) vorliegt d.h. ich würde separate Non-Terminals T_UInt (+- als Vorzeichen) und T_float definieren? Dann müsste ich jedoch überall wo bis jetzt eine Zahl steht immer T_UINT | T_FLOAT o.ä, schreiben. Ansonsten müsste ich die Tokendefinition erweitern um die Zusatzinformation "Zahlentyp" zu speichern, auch irgendwie ungut. Ich glaub ich habe das noch nicht so recht durcschaut.

    An sich wundert mich aber das alles etwas. Denn ich dachte die EBNF dient als Grammatik der Definition legaler Sätze der Sprache. Dann müsste man doch den (meistens) offenkundig illegalen Ausdruck <float> % <uint> aus dieser als Illegal finden können? An sich ist doch der Typ (float, int ...) nichts anderes als ein weiteres Token der Sprache?

    Nun kann man aber den einzelnen Symbolen (oder Knoten im Syntaxbaum) zusätzliche Eigenschaften verpassen. Eine gefundene Konstante 5 hat neben dem int Wert 5 auch einen Datentyp zugeordnet - nämlich TypeInt.
    Eine Variable s1 könnte z.B. TypeString haben.

    D.h. du würdest also der Tokenklasse im Artikel einen weiteren Member verpassen der Auskunft über spezifischere Informationen gibt? (also eben Int, String whatever)

    Ich hab mir aus der Bücherei auch das Dragonbook sowie n bissl anderen Krams rausgesucht, ist nur teilweise etwas überdimensioniert^^
    Danke für den PDF link, ziehs mir direkt rein!



  • kingcools schrieb:

    Wenn ich mit der im Thread verwendeten EBNF arbeiten würde, würde ich float und int bezeichner definieren

    Du willst also rein syntaktisch an einem Bezeichner erkennen, welchen Typ er hat? Wie stellst du dir das vor, sind das syntaktisch unterschiedliche Bezeichner, sowas wie ungarische Notation oder Basic? Oder machst du es wie in C mit dem typedef-Hack, dh Scanner und Parser arbeiten verzahnt, so dass der Scanner bei einem Bezeichner bereits je nach Typ unterschiedliche Tokens zurückliefert?

    An sich wundert mich aber das alles etwas. Denn ich dachte die EBNF dient als Grammatik der Definition legaler Sätze der Sprache.

    Die meisten Programmiersprachen lassen sich nicht durch kontextfreie Grammatiken darstellen. Deshalb benutzt man meist eine grobe kontextfreie Grammatik für das syntaktische Grundgerüst und erledigt Typprüfung und ähnliches in einer separaten Phase.



  • Bashar schrieb:

    kingcools schrieb:

    Wenn ich mit der im Thread verwendeten EBNF arbeiten würde, würde ich float und int bezeichner definieren

    Du willst also rein syntaktisch an einem Bezeichner erkennen, welchen Typ er hat? Wie stellst du dir das vor, sind das syntaktisch unterschiedliche Bezeichner, sowas wie ungarische Notation oder Basic? Oder machst du es wie in C mit dem typedef-Hack, dh Scanner und Parser arbeiten verzahnt, so dass der Scanner bei einem Bezeichner bereits je nach Typ unterschiedliche Tokens zurückliefert?

    Du hast recht, ich habe an einen anderen Fall gedacht. War also unsinn. Gut, kann also nicht gehen.

    An sich wundert mich aber das alles etwas. Denn ich dachte die EBNF dient als Grammatik der Definition legaler Sätze der Sprache.

    Die meisten Programmiersprachen lassen sich nicht durch kontextfreie Grammatiken darstellen. Deshalb benutzt man meist eine grobe kontextfreie Grammatik für das syntaktische Grundgerüst und erledigt Typprüfung und ähnliches in einer separaten Phase.

    Ok, danke! Sehe es auch gerade in dem verlinkten PDF von vorher. Dann ist mir erstmal klar denke ich, wie ich vorzugeben habe!


Anmelden zum Antworten