Interpreterbau - Ein Anfang

was ist der vorteil gegenueber wenn ich die grammatik in ebnf definiere anstatt in yacc?

Cherup

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>

Bashar

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.

kingcools

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!

Bashar

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.

kingcools

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.

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