Interpreterbau - Ein Anfang



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



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


Log in to reply