Parser - Wie Code intern speichern

milan1612

Mein aktuelles Projekt ist ein Compiler der eine eigene kleine Sprache
nach C++ übersetzen soll. Allerdings ist die Sprache einerseits schon
zu komplex um sie in einem Zug direkt übersetzen zu können (also mit
einem One-Pass-Compiler) und andererseits möchte ich schon die Gelegenheit
nutzen etwas tiefer in den Compilerbau einzusteigen.

Soweit so gut, das Frontend ist eigentlich fertig, das heißt der Input der
Dateien und das Scannen der Tokens funktioniert tadellos.

Die Tokens sind der Einfachheit halber wie folgt gespeichert:

struct Token {
  TokenID ID;
  string Value;
};
//...
vector<Token> tokens;

Wobei TokenID ein simples enum für allerlei Typen ist (Klammer auf, Semicolon, Identifier...)

Nun zu meiner eigentlichen Frage, ich möchte aus diesem Tokenstream eine
Art interne Repräsentation der Codelogik aufbauen. Ich habe allerdings
keine Ahnung wie ich das anfangen soll, nicht einmal wie diese Struktur
aussehen soll. Wie würdet ihr das machen, und wie soll das Parsen von statten gehen?

Danke schon mal fürs lesen, ich freu mich auf eure Antworten...

PS: Wenn ihr weitere Details braucht -> Bitte einfach fragen

Nexus

Selber kenne ich mich in dem Bereich nicht gut aus, aber vielleicht hilft dir der Artikel über Compilerbau etwas weiter.

Unter Linux gibt es 2 Tools, die Hand in Hand arbeiten: Flex und Bison bzw. Lex und Yacc. Auf den zugehoerigen Seiten findest du auch ausfuehrliche Tutorials, wie ein kleiner Taschenrechner zu implementieren ist. Aufbauend auf diesen Erkenntnissen kannst du dann eine eigene Sprache entwerfen.

Auch die Paper bezueglich Lisp/Scheme etc. sind vielleicht hilfreich.

milan1612

Nexus schrieb:

Selber kenne ich mich in dem Bereich nicht gut aus, aber vielleicht hilft dir der Artikel über Compilerbau etwas weiter.

Siehe Punkt 12 in dem Artikel - allerdings hilft mir der Begriff "Parserbaum"
schon etwas weiter. Gleich mal googlen...

@knivil
Ich möchte bewusst kein Tool dafür verwenden, sondern alles per Hand schreiben.

Die Tools erzeugen c-Sourcedateien, die keinerlei externe Abhaengigkeiten aufweisen. Und du wirst noch genug selbst machen muessen. Natuerlich kannst du dich auch damit aufhalten, einen Matcher fuer regulaere Ausdruecke zu schreiben (flex) und einen Parser fuer Ableitungsbaeume (bison) zu entwickeln. Vielleicht solltest du dir trotzdem flex/bison ansehen, damit du begreifst, was im Hintergrund so abgeht.

Fellhuhn

Abstrake Syntax- und Semantikbäume sind noch eventuelle Stichpunkte die dir weiterhelfen können.

milan1612

Also, ich hab jetzt mal ne Weile nach diesen Begriffen gegoogelt und glaube
dass ich jetzt eine grobe Vorstellung von dem habe was noch auf mich zukommt.
Ich denke ich werd jetzt einfach mal ein bisschen rumprobieren, vielleicht
kommt ja was dabei raus. Wenn ich noch spezielle Fragen hab, meld ich mich wieder.

milan1612 schrieb:

Also, ich hab jetzt mal ne Weile nach diesen Begriffen gegoogelt und glaube
dass ich jetzt eine grobe Vorstellung von dem habe was noch auf mich zukommt.
Ich denke ich werd jetzt einfach mal ein bisschen rumprobieren, vielleicht
kommt ja was dabei raus. Wenn ich noch spezielle Fragen hab, meld ich mich wieder.

Entwirf das doch zuerst einmal mit Hilfe von lex/yacc und anschließend von Hand. Nicht gleich alles auf einmal versuchen!

Badestrand

milan1612 schrieb:

Nun zu meiner eigentlichen Frage, ich möchte aus diesem Tokenstream eine
Art interne Repräsentation der Codelogik aufbauen. Ich habe allerdings
keine Ahnung wie ich das anfangen soll, nicht einmal wie diese Struktur
aussehen soll.

Häufig kann man Code in zwei Dinge aufteilen: Die Struktur (Funktionen, Klassen, ...) und Ausdrücke (sowas wie i*2+7 ). Eine Datei besteht dann z.B. aus einer Reihe Funktionen (mit jeweils Rückgabetyp, Name, Parameter-Namen und -Typen und eventuellen Modifizierern wie z.B. "static"), Klassen (mit Name, Membervariablen, Memberfunktionen, evtl Operatoren, Konstruktoren usw) und anderen "Strukturen".
An "Code" hast du meist den Code in Funktionen, welcher sich in Codezeilen wie return-Anweisungen, Schleifen, if-Verzweigungen, Variablen-Deklarationen etc und Ausdrücken ausdrücken lässt (z.B. eine Codezeile Variablendeklaration mit Typ=int, Name=foo, Init-Ausdruck=5+7 oder eine while-Schleife mit dem Ausdruck b>7 als Bedingung). Dann gibt's noch "Code" außerhalb von Funktionen, z.B. bei dem Initialisierungs-Code von globalen Variablen-Deklarationen.

Ausdrücke werden dabei meist mit "Abstract Syntax Tree"s repräsentiert, der Rest mit Property-Sammel-Klassen wie deine Token-Struktur.

So könnte das in etwa aussehen:

File
  -> Function[] funcs
  -> VarDecl[]  vars

Function
  -> string     name
  -> Type       return_type
  -> Param[]    params
  -> CodeLine[] codelines

Param
  -> Type       type
  -> string     name

VarDecl
  -> Type      type
  -> string    name
  -> Expression* init_code // Optional falls Initialisierung vorhanden

CodeLine : CodeLineReturn | CodeLineWhile | CodeLineIf | CodeLineVarDecl | ...

CodeLineReturn
  -> Expression* expr  // Optional, falls ein "leeres" return möglich ist

CodeLineVarDecl
  -> VarDecl[] vars

CodeLineWhile
  -> Expression condition
  -> CodeLine[] code_block
...

Expression : ExprBinaryOperator | ExprUnaryOperator | ExprStatement | ...

ExprBinaryOperator
  -> Operator op
  -> Expression left
  -> Expression right

ExprStatement
  -> string text

...