Interpreterbau - Ein Anfang

Hallo, ich habe ein kleines Problem mit meinem eigenen Interpreter, nämlich: Was mache ich, wenn ich mehrere Ausdrücke hintereinander habe (z.B.:

i = 0;
a = 6;

)? Muss ich ein Array von Nodes machen? Und wie würde ich dann z.B. einen C++-SC in einen AST überführen? (ich weiß, dass das viel zu komplex ist ;))

Viel Dank im Voraus

C++ompiler schrieb:

Hallo, ich habe ein kleines Problem mit meinem eigenen Interpreter, nämlich: Was mache ich, wenn ich mehrere Ausdrücke hintereinander habe (z.B.:
i = 0;
a = 6;
)? Muss ich ein Array von Nodes machen? Und wie würde ich dann z.B. einen C++-SC in einen AST überführen? (ich weiß, dass das viel zu komplex ist ;))

Viel Dank im Voraus

Das kommt ganz auf den Anwendungsfall an. Wenn du eine Sprache entwickelst, bei der das Programm direkt ausgeführt bzw. in eine andere Sprache kompiliert werden soll, dann kann es Sinn machen, dass du für jede Deklaration ein Node anlegst. Dann könntest du zur Laufzeit den Speicher berechnen bzw. bei der neue Sprache so die Deklaration generieren.

Ansonsten musst du eine Symboltabelle haben (solltest du für die semantische Analyse ohnehin schon haben) und für die Variablen eine Adresse berechnen. Dann kann jeder Ident mit dem entsprechenden Eintrag in der Symboltabelle verknüpft werden und bei der Codegenerierung weiß der Compiler so, wie er den Code zu generieren hat.

Das ganze ist dann im Detail doch etwas anspruchsvoller, also am besten mal eine fertige Implementierung suchen und davon abschauen. Suchwörter sind jedenfalls Symboltabelle, Adressgenerierung, usw.

gilwell88

Hey,
dein Tutorital hat mir sehr geholfen. Allerdings so 100% habe ich es wohl noch nicht verstanden.
Gibt es eine Möglichkeit mir die Zwischenergebnisse anzuzeigen? Im Parser kann ich mir ohne Probleme das aktuelle Ergebnis res ausgeben lassen, aber wie kann ich mir die aktuell Zusammengefasste Rechnung ausgeben lassen?

gilwell88 schrieb:

Hey,
dein Tutorital hat mir sehr geholfen. Allerdings so 100% habe ich es wohl noch nicht verstanden.
Gibt es eine Möglichkeit mir die Zwischenergebnisse anzuzeigen? Im Parser kann ich mir ohne Probleme das aktuelle Ergebnis res ausgeben lassen, aber wie kann ich mir die aktuell Zusammengefasste Rechnung ausgeben lassen?

Schau dir mal das C# Programm an. Das stellt das ganze visuell dar und hilft vielleicht beim Verständnis. Oder was meinst du? Weil Zwischenergebnis und zusammengefasste Rechnung erscheinen mir identisch?

Bin mir nicht so sicher, wo dein Verständnisproblem genau ist und was du gerne als Hilfe ausgegeben haben willst.

gilwell88

Das C# habe ich mir angeschaut und auch gefunden wo der Baum erstellt wird, ich werde mal versuchen soetwas in C++ zu übertragen, mal sehen ob mir das gelingt.

Am liebsten wäre es mir, wenn in der Ausgabe solche Zwischenergebnisse ständen, wie man sie auch hat wenn man von Hand rechnet, also z.B.:
Eingabe: (20+1)/(2+1)
Ausgabe: = 21/(2+1)
Ausgabe: = 21/3
Ausgabe: =7
Diese Zwischenschritte sind alle irgendwie gespeichert und der Parser macht sie auch so, ich weiß nur nicht wie ich sie ausgebe.

Das ist wohl etwas tricky. Ich würde den AST nehmen und immer ein Node evaluieren lassen und die anhängenden löschen und durch das Ergebnis ersetzen. Dann Ausgeben. Und das ganze solange wiederholen bis man am Root Node ist...

Hi, vielen Dank für das Tutorial. Hat mir sehr geholfen! Habe deine EBNF übernommen.
Jetzt möchte ich aber für meinen Interpreter noch das Zeichen '^' implementieren, um Exponenten damit zu unterstützen.

Mein Problem ist nun, dass ich nicht weiß wie ich das in deiner EBNF korrekt formuliere, ohne die EBNF komplett zu verändern ... hätte da jemand einen Vorschlag? Ich steh auf dem Schlauch.

Vielen Dank schonmal!

Dummie

derp schrieb:

Hi, vielen Dank für das Tutorial. Hat mir sehr geholfen! Habe deine EBNF übernommen.
Jetzt möchte ich aber für meinen Interpreter noch das Zeichen '^' implementieren, um Exponenten damit zu unterstützen.

Mein Problem ist nun, dass ich nicht weiß wie ich das in deiner EBNF korrekt formuliere, ohne die EBNF komplett zu verändern ... hätte da jemand einen Vorschlag? Ich steh auf dem Schlauch.

Vielen Dank schonmal!

Eigentlich ist das ziemlich trivial:

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

Multiplikation = (Potenz) { ("*" | "/") (Potenz) } ;

Potenz = (Klammer) { "^" (Klammer) } ;

Klammer = ["+" | "-"] ((Zahl) | "(" (Start) ")") ;

Zahl = (Ziffer) { (Ziffer) } ;

Ziffer = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Topaz

Vielleicht Offtopic, aber das Zeichen ^ für Potenzen zu nutzen halte ich für unglücklich. Jeder der aus der C-Welt kommt wird versuchen XOR mit dem Zeichen zu nutzen. Genauso gibt es jedoch den üblichen Einsteigerfehler ^ in C für Potenzen zu nutzen um sich dann zu wundern was da vor sich geht.. Also ein Dilema, gewissermaßen. Eine kleine Anregung - vielleicht findet sich ja eine bessere Lösung.

Ich sehe oft "**" als Potenz.

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.