Interpreterbau - Ein Anfang

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.

henriknikolas

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?

henriknikolas

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*(2y) <-- einsetzen der Funktionskörpers von g(x) - wobei "x" durch "y" ersetzt werden muss

und erst nach dem Einsetzen leitest du dann symbolisch ab.

henriknikolas

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.

happystudent

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

happystudent

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.

happystudent

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.

happystudent

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;
}

Danke gfhfghfgh!

Kannst Du bitte auch noch die Definitionen von Parser::start und Parser::klammer posten?

Danke gfhfghfgh!

Kannst Du bitte auch noch die Definitionen von Parser::start und Parser::klammer posten?

Danke gfhfghfgh!

Kannst Du bitte auch noch die Definitionen von Parser::start und Parser::klammer posten?