Interpreterbau - Ein Anfang



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



  • Hier der bereits für deine Ziele abgeänderte Code aus dem ersten Beitrag. Du siehst die Funktionen wie start(), multiplikation, ...
    Die gaben jeweils einen int zurück, weil das für das einfache Beispiel gereicht hat. Jetzt brauchst du int oder float oder sonst was. Also geben wir eine Struktur zurück, die genau diese Information beinhaltet.

    class Parser
    {
        private:
            Scanner myScanner;
            Token myTok; // Zuletzt gelesenes Token
    
        public:
            Parser(const std::string& input);
    
            ValueWithType parse();
    
        private:
            ValueWithType start();
            ValueWithType multiplikation();
            ValueWithType klammer();
            ValueWithType zahl();
    
            void accept(TokenType type);
            void getNextToken();
    };
    

    Hier ein einfaches Beispiel für so eine Struktur:

    enum Type {TypeInt,TypeFloat,TypeNone};
    
    struct ValueWithType
    {
     // Datentyp
     Type type;
    
     // Wert - je nach Typ ist intVal oder floatVal gesetzt
     int intVal;
     float floatVal;
    
     // am Anfang mal auf ungültig und 0 setzen
     ValueWithType():type(TypeNone),intVal(0),floatVal(0.0){}
    
    };
    

    Und statt int gibtst du jetzt eben deine befüllte ValueWithType Struktur zurück.
    Wenn du nun an der Stelle bist, wo du das Modulo ausführst, baust du eben noch die Typprüfung ein. Als left und right bezeichne ich den Wert links und rechts vom Modulo (%) Zeichen:

    if(left.type==TypeInt && right.type==TypeInt)
    {
     ValueWithType res;
     res.type=TyoeInt;
     res=left.intVal%right.intVal;
     return res;
    }
    else
    {
     ShowError("Modulo: nur int % int erlaubt");
     ...
    }
    


  • Hey vielen Dank!
    Ich hatte es leider schon selber genauso (!) gelöst.
    Nur habe ich die Typenprüfung nicht in die Anwendung der Operatoren gepackt. In meinen Augen sollte dort tatsächlich nur diese ausgeführt werden. Die Typenprüfung kann schon vorher geschehen.

    Gestern ist mir aber eine neue Frage in den Sinn gekommen:
    Im Artikel wird die Überprüfung auf Division durch Null bei der Erstellung des Parsebaumes durchgeführt. Dabei spielten jedoch Identifier keine Rolle. Diese können aber zur Laufzeit natürlich "illegale" Werte annehmen. Jetzt müsste ich natürlich bei Berechnung der Division nochmals auf Division durch Null prüfen, ist irgendwie eklig doppelt gemoppelt. Auf der anderen Seite würde ich gerne schon vorher illegale Divisionen durch Null erkennen und dem User anzeigen können.

    Ich seh schon, da gibt es keinen Königsweg, ich muss an beiden Stellen prüfen.



  • Ich habe auch noch eine Frage...
    Ich habe bei mir die Möglichkeit eingeführt eigene Funktionen zu definieren und diese auch abzuleiten (nicht numerisch). Dabei können auch partielle Ableitungen durchgeführt werden. Dazu wird die Variable die abgeleitet wird, in der Symboltabelle markiert und bei der Ableitung entsprechend nicht auf 0 gesetzt. Soweit funktioniert es auch.
    Ich denke mir aber auch gerne ganz spezielle Beispiele aus, um zu testen, ob es wirklich bei jedem Fall funktioniert... Nun ist das Problem, dass ich für den folgenden Fall absolut keine Lösungsmöglichkeit finde:
    Wenn man eingibt

    function f(x) = x^2
    function g(x,y) = f(y) + x^3
    

    und dann

    g(3,2)'(0) ("(0)" bedeutet, der Nullte Parameter wird abgeleitet)
    

    ist klar, dass das Ergebis 27 sein muss. Das Programm gibt aber 31 aus. Warum?
    Es wird die Variable "x" als Variable nach der abgeleitet wird eingetragen.
    Dann wird y eingetragen und die Ableitung von f berechnet. Da f aber genau

    f(x) = x^2
    

    ist, wird x als Variable und nicht als Zahl aufgefasst, trotzdem es sich um ein gänzlich anderes "x" handelt.
    Wie kann ich das lösen?



  • Kann mir keiner helfen, oder habe ich meine Frage so schlecht beschrieben, dass niemand mein Problem versteht?



  • henriknikolas schrieb:

    Kann mir keiner helfen, oder habe ich meine Frage so schlecht beschrieben, dass niemand mein Problem versteht?

    wie wärs mit einem C-Marko-ähnlichen Ansatz?
    Du ersetzt einfach den Aufruf gegen den tatsächlichen Funktionskörper mitsamt Ersetzen der Variablennamen.
    g(x)=2x
    f(x,y)=3*x+2*g(y)
    =3*x+2*(2
    y) <-- einsetzen der Funktionskörpers von g(x) - wobei "x" durch "y" ersetzt werden muss

    und erst nach dem Einsetzen leitest du dann symbolisch ab.



  • Hallo, erstmal vielen Dank für die Antwort. Generell habe ich dein Konzept verstanden, aber ich habe noch zwei Fragen:
    1. Gibt es für dieses Konzept auch einen speziellen Namen?
    2. Meine Funktion ist als Baum gespeichert. Das bedeutet, dass wenn ich die Werte in die Funktion einsetze die Variablenn dementsprechend ersetzt werden müssen. Aber wie implementiere ich das am besten? Einfach jedem Node eine Funktion zum Ersetzen hinzufügen?

    Das Konzept verstehe ich, nur wie ich es Umsetzen soll, weiß ich noch nicht richtig, da das ganze System aus Symboltabelle, den Knoten für Funktionen, ...
    alles sehr komplex ist.



  • Hallo,

    das Tutorial fand ich sehr gut, großes Lob an dieser Stelle 👍

    Hätte da aber auch noch eine Frage wegen einer Grammatik. Mal C als Beispiel genommen, da kann man eine Variablen-Deklaration in der Grammatik ja ungefähr so ausdrücken (ich lasse jetzt mal der Einfachheit halber mehrere deklarationen in der gleichen Zeile außen vor):

    variable_declaration = identifier, identifier, [ "=", initializer ], ";"
    

    was also zum Beispiel folgendem C code wiederspiegeln würde:

    int i = 1;
    

    Allerdings könnte man die Grammatik ja auch so definieren:

    variable_declaration = type_name, identifier, [ "=", initializer ], ";"
    

    Die Frage ist jetzt, was ist günstiger/besser? Sollte man während dem parsen schon überprüfen ob ein identifier auch ein gültiger Typ ist oder erst danach mit einem semantischen Analyser? Wie wird das üblicherweise gemacht?



  • in einer einfachen Sprache in der man keine eigenen Typen erstellen kann würd ich schreiben:
    varDecl := typeName id ["=" constVal] ";"
    typeName := "int" | "float" | ...

    In einer komplexeren dann eben
    varDecl := id id ["=" constVal] ";"
    Ob es den Typen mit dem Namen gibt oder nicht kannst du dann ja in einer Tabelle nachschlagen.

    Kannst ja z.B. mal einen Blick in einen C Parser werfen:
    https://github.com/MatzeB/cparser



  • hgfhgfh schrieb:

    Ob es den Typen mit dem Namen gibt oder nicht kannst du dann ja in einer Tabelle nachschlagen.

    Ja schon (die Sprache hat benutzdefinierte Typen), die Frage ist halt ob ich das direkt während dem parsen machen sollte, oder erst mal den Baum aufbauen und danach seperat solche Sachen checken.

    Also mir ist die Trennlinie halt nicht ganz klar, was jetzt noch zum Parser gehört und was zum semantischen Analyser (oder auch wann und wieso man einen solchen überhaupt braucht/dieser sinnvoll ist). Der Übergang

    Lexer -> Parser

    ist relativ klar und deutlich. Aber der Übergang

    Parser -> Analyser

    eben nicht...



  • Es kann so oder so sinnvoll/möglich sein. Ob eine Variable deklariert wurde, kann bzw. muss man sogar beim Parsen prüfen. Denn da wird dann die Symboltabelle geführt und die entsprechenden Adressen an den Baum weitergegeben.



  • ghjhgjghj schrieb:

    Es kann so oder so sinnvoll/möglich sein. Ob eine Variable deklariert wurde, kann bzw. muss man sogar beim Parsen prüfen. Denn da wird dann die Symboltabelle geführt und die entsprechenden Adressen an den Baum weitergegeben.

    Warum "muss"? Man kann doch erstmal den Baum komplett aufbauen und danach nochmal drüber laufen und dann die Symboltabelle führen und die Adressen im Baum entsprechend setzen?

    Oder verstehe ich dich jetzt falsch?



  • happystudent schrieb:

    ghjhgjghj schrieb:

    Es kann so oder so sinnvoll/möglich sein. Ob eine Variable deklariert wurde, kann bzw. muss man sogar beim Parsen prüfen. Denn da wird dann die Symboltabelle geführt und die entsprechenden Adressen an den Baum weitergegeben.

    Warum "muss"? Man kann doch erstmal den Baum komplett aufbauen und danach nochmal drüber laufen und dann die Symboltabelle führen und die Adressen im Baum entsprechend setzen?

    Oder verstehe ich dich jetzt falsch?

    gibt ja keine Regeln wie man einen Compiler bauen muss.
    Ich z.B. bin bei einer Skriptsprache folgendermaßen vorgegangen:
    1. Lexer
    2. Parser erster Lauf: nur Funktionsköpfe einlesen (Symboltabelle mit Funktionsnamen/typen)
    3. Parser zweiter Lauf: komplette Quelldatei einlesen. Gleichzeitig Aufbau Symboltabelle je Funktion und vollständige Typprüfung.



  • happystudent schrieb:

    ghjhgjghj schrieb:

    Es kann so oder so sinnvoll/möglich sein. Ob eine Variable deklariert wurde, kann bzw. muss man sogar beim Parsen prüfen. Denn da wird dann die Symboltabelle geführt und die entsprechenden Adressen an den Baum weitergegeben.

    Warum "muss"? Man kann doch erstmal den Baum komplett aufbauen und danach nochmal drüber laufen und dann die Symboltabelle führen und die Adressen im Baum entsprechend setzen?

    Oder verstehe ich dich jetzt falsch?

    Ja, natürlich kann man das machen. Aber wenn man z.B. einen Fehler entdeckt, dass eine Variable nicht deklariert wurde, dann kann man direkt aufhören und stellt das nicht erst später fest.



  • Ok gut, das mit dem früher aussteigen wegen Fehlern macht Sinn. Allerdings will ich sowieso alle Fehler finden (und in einer Liste speichern), daher werd ich das dann wohl erst in der Analyser-Phase machen.



  • happystudent schrieb:

    Ok gut, das mit dem früher aussteigen wegen Fehlern macht Sinn. Allerdings will ich sowieso alle Fehler finden (und in einer Liste speichern), daher werd ich das dann wohl erst in der Analyser-Phase machen.

    Du wirst feststellen, dass das gar nicht so einfach sein kann. Denn manche Fehler bedingen andere Fehler, die wieder andere Fehler bedingen, etc.



  • Vielen Dank für den Artikel!

    Leider schaffe ich es, trotz der guten Beschreibung und weiteren Posts, nicht den Code um eine Potenzoperator zu erweitern.

    Kann bitte jemand die nötigen Änderungen für die Erweiterung um den Potenzoperator "^" posten.

    Bisher habe ich nur die Funktion pow() eingebaut. Für ein neues Projekt möchte ich aber Formeln die in Excel vorhanden sind verwenden...



  • Unverschämt schrieb:

    Vielen Dank für den Artikel!

    Leider schaffe ich es, trotz der guten Beschreibung und weiteren Posts, nicht den Code um eine Potenzoperator zu erweitern.

    Kann bitte jemand die nötigen Änderungen für die Erweiterung um den Potenzoperator "^" posten.

    Bisher habe ich nur die Funktion pow() eingebaut. Für ein neues Projekt möchte ich aber Formeln die in Excel vorhanden sind verwenden...

    falls du es auf gleicher Ebene wie Multiplikation/Division anordnen willst, ginge es z.B. so:

    Syntaxdefinition:

    Multiplikation = (Klammer) { ("*" | "/" | "^") (Klammer) } ;
    

    Parser:

    // Multiplikation = (Klammer) { ("*" | "/") (Klammer) } ;  
    int Parser::multiplikation() 
    { 
         int res = klammer(); 
    
         while (myTok.equal(TT_MUL) || myTok.equal(TT_DIV) || myTok.equal(TT_POW)) 
         { 
             switch (myTok.getType()) 
             { 
                 case TT_MUL: 
                     getNextToken(); 
                     res *= klammer(); 
                     break; 
    
                 case TT_DIV: 
                     getNextToken(); 
                     res /= klammer(); 
                     break; 
    
                 case TT_POW: // Scanner muss TT_POW (also ^) erkennen 
                     getNextToken(); 
                     res = my_pow(res,klammer()); // my_pow führt x^y aus
                     break; 
             } 
         } 
    
         return res; 
    }
    

    ... so in etwa könnte es funktionieren.



  • Besser du erstellst dafür eine weitere Funktion, denn der Operator hat ohnehin die höchste Priorität.

    Ungetestet, aber das Konzept sollte dafur klar werden. Es ist eigentlich recht simpel, wenn man es einmal verstanden hat. 🤡

    int Parser::multiplikation()
    {
         int res = pow();
    
         while (myTok.equal(TT_MUL) || myTok.equal(TT_DIV))
         {
             switch (myTok.getType())
             {
                 case TT_MUL:
                     getNextToken();
                     res *= pow();
                     break;
    
                 case TT_DIV:
                     getNextToken();
                     res /= pow();
                     break;
             }
         }
    
         return res;
    }
    
    // Multiplikation = (Klammer) { ("*" | "/") (Klammer) } ;  
    int Parser::pow()
    {
         int res = klammer();
    
         while (myTok.equal(TT_POW))
         {
             switch (myTok.getType())
             {
                 case TT_POW:
                     getNextToken();
                     res = std::pow(res, klammer());
                     break;
             }
         }
    
         return res;
    }
    

Anmelden zum Antworten