Interpreterbau - Ein Anfang

henriknikolas

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.

oenone

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/

henriknikolas

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.

Genauso meinte ich das auch, aber eine Eingabe die ein "=" Zeichen enthält würde ich nicht in den Parser stopfen, dann musste den ganzen Parser umschreiben. Ich würde einfach vorher (mit String vergleichen) überprüfen ob die Eingaben ein "=" enthält, dann den Variablennamen auslesen, und das was rechts vom "=" ist in den Parser stopfen. Ist vllt. nicht ganz so sauber und nicht ganz so allgemein, dafür aber wesentlich einfacher (vorrausgesetzt du willst wirklich nur noch Variablen hinzufügen, andernfalls kommst du wohl um einen umgeschriebenen Parser nicht rum)

volkard

SomeGuy schrieb:

Genauso meinte ich das auch, aber eine Eingabe die ein "=" Zeichen enthält würde ich nicht in den Parser stopfen, dann musste den ganzen Parser umschreiben. Ich würde einfach vorher (mit String vergleichen) überprüfen ob die Eingaben ein "=" enthält, dann den Variablennamen auslesen, und das was rechts vom "=" ist in den Parser stopfen. Ist vllt. nicht ganz so sauber und nicht ganz so allgemein, dafür aber wesentlich einfacher (vorrausgesetzt du willst wirklich nur noch Variablen hinzufügen, andernfalls kommst du wohl um einen umgeschriebenen Parser nicht rum)

Glaub mir, es ist einfacher, die Grammatik anzupassen, daß es halt noch eine AssignExpression gibt. Später auch IfExpression, LoopExpression. Vielleicht will man um nicht zu smalltalken Statements haben. Sobald man den mathematischen Parser gepackt hat, gehts doll flott von der Hand alles weitere zu implementieren. Aber niemals wegen einer Kleinigkeit den Fluß stören, Parser bleibe Parser.

Das Drachenbuch hab ich auch gelesen, es gab mir nicht viel. Alte Kamellen, so würde man es heute nicht mehr machen. Und kein Hinweis, wie man komplexere Typen oder gar Templates anzufassen hätte.

Mechanics

volkard schrieb:

Das Drachenbuch hab ich auch gelesen, es gab mir nicht viel. Alte Kamellen, so würde man es heute nicht mehr machen. Und kein Hinweis, wie man komplexere Typen oder gar Templates anzufassen hätte.

Kennst du bessere Bücher?

volkard

Mechanics schrieb:

Kennst du bessere Bücher?

Nein! Und das macht mich weinen. Darum habe ich meine Compilerbaupläne erstmal auf Eis gelegt (vor gefühlt 1000 Jahren).

oenone

volkard schrieb:

Das Drachenbuch hab ich auch gelesen, es gab mir nicht viel. Alte Kamellen, so würde man es heute nicht mehr machen. Und kein Hinweis, wie man komplexere Typen oder gar Templates anzufassen hätte.

Die Grundlagen gelten immer noch und werden auch noch so gemacht.

volkard

oenone schrieb:

volkard schrieb:

Das Drachenbuch hab ich auch gelesen, es gab mir nicht viel. Alte Kamellen, so würde man es heute nicht mehr machen. Und kein Hinweis, wie man komplexere Typen oder gar Templates anzufassen hätte.

Die Grundlagen gelten immer noch und werden auch noch so gemacht.

Ich würde viel mehr auf rekursiven Abstieg setzen.

henriknikolas

Hallo, ich habe den Parser jetzt so modifiziert, dass man auch eigene Variablen verwenden kann.
NodeIdent habe ich noch eine Konstruktor verpasst der zusätzlich zu einem string noch eine map erwartet. NodeIdent::eval() durchsucht zuerst die Konstanten und dann die map.
Für den Parser habe ich die Funktion variable() eingeführt:

NodeIdent* Parser::variable()
{
    string var_name = myTok.getStrvalue();
    accept(TT_IDENT);
    if(myTok.equal(TT_ASSIGN))
    {
        accept(TT_ASSIGN);
        table[var_name] = start()->eval());
    }
    return new NodeIdent(table, var_name);
}

variable() wird ausgeführt, wenn keine funktion() ausgeführt wird. Deshalb brauche ich bezeichner() nur noch für funktion().
Und der Konstruktor von Parser erwartet eine Referenz auf eine map, sodass dort dann die variablen eingetragen werden.
Wie hättet ihr das gemacht, oder kann bei mir noch etwas verbessert werden?

Ach ja, ich habe meinen Parser noch um den Potenzoperator erweitert. Nur ist der bei mir jetzt linksassoziativ und nicht rechtsassoziativ. Wie kann ich das ändern?

henriknikolas

henriknikolas schrieb:

Ach ja, ich habe meinen Parser noch um den Potenzoperator erweitert. Nur ist der bei mir jetzt linksassoziativ und nicht rechtsassoziativ. Wie kann ich das ändern?

Ich habe das jetzt auch alleine gelöst, war eigentlich "voll trivial" wie unser alter Mathematiklehrer zu sagen pflegte, einfach die EBNF so ändern:

Potenz = Klammer {^ Potenz}

In dem Beitrag wurde ja schön gezeigt, wie man einen Mathe "Interpreter" baut. Ein echtes Program besteht ja aber meistens nicht nur aus einem Befehl, sondern aus mehreren. Legt ein echter Interpreter also ein Array von ASTs an und führt die der Reihe nach aus? Und was für einen Syntaxbaum bekommt eine While-Schleife, in deren Body mehrere Befehle stehen?

SomeRandomGuy schrieb:

In dem Beitrag wurde ja schön gezeigt, wie man einen Mathe "Interpreter" baut. Ein echtes Program besteht ja aber meistens nicht nur aus einem Befehl, sondern aus mehreren. Legt ein echter Interpreter also ein Array von ASTs an und führt die der Reihe nach aus? Und was für einen Syntaxbaum bekommt eine While-Schleife, in deren Body mehrere Befehle stehen?

Wenn man die Grammatik entsprechend festlegt, dann ergibt sich das von alleine. Dann gibt es z.B. einen AST namens Block und der hat wiederum Äste. Diese Äste sind dann entweder vom Typ Assignment, FuncCall oder wie auch immer. Wenn man dann noch eine Schleif drum rum packt und ein Ast Condition auswertet, dann kann man so eine Schleife, Abfrage, etc. implementieren.

Es ist nicht mehr ganz so trivial, aber es ist auch nicht wirklich schwierig.

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

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

henriknikolas

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 -3² 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.

henriknikolas

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.