Parser

[3_of_8]

Morgen.

Ich habe gestern mal einen Lexer für eine ganz ganz kleine Skriptsprache fertiggestellt.

Das heißt: Ich habe eine schöne Tokenkette, also ich "weiß", was ein Bezeichner ist, was ein Schlüsselwort ist, was ein numerisches/String/Charliteral usw. ist.

Jetzt würde ich das ganze gerne in einen Baum kriegen, wobei man die "Kinder" eines Knotens immer aus diesem ableiten kann.

Also beispielsweise wäre "unit" der Root-Node, "inclusion" und "block" wären Subknoten, "inclusion" hätte als Subknoten mehrere "include"s, die wiederum bestehen aus einer Liste an Strings. Der Block besteht aus anderen Blöcken, Anweisungen, Bedingungen usw, eine Bedingung besteht aus einem Statement und einer Anweisung oder einem Block usw.

Der folgende Quellcode:

Code:

unit Test;

include io.*;
//...

x:=y+z;
//...

wird von meinem Lexer zu diesem Token-Strang:

Code:

unit: Keyword
Test: Identifier
;: Separator
include: Keyword
io: Identifier
.: Separator
*: Separator (in diesem Fall eigentlich ein Bezeichner, kann der Lexer aber nicht wissen)
;: Separator
x: Identifier
:: Separator
=: Separator
y: Identifier
+: Separator
z: Identifier
;: Separator

Daraus soll jetzt der Baum wie im Anhang geparst werden. (Wobei die ...-Knoten nichts anderes bedeuten als "hier könnte man jetzt nochmal so nen Knoten wie den anderen anhängen")

Mein Gedanke wäre jetzt gewesen, da durchzuiterieren, mir ein paar Flags zu setzen nach jedem abgeschlossenen Abschnitt (unit-Abschnitt, inclusion-Abschnitt) und größtenteils nach Schlüsselwörtern zu suchen.

Also in etwa so:

Code:

Keyword "unit" gefunden
Bezeichner "Test" gefunden
Separator ";" gefunden
Unit-Abschnitt abgeschlossen, Unitname ist "Test"

Keyword "include" gefunden
Bezeichner "io" gefunden
Separator "." gefunden
Separator "*" gefunden
Separator ";" gefunden
Include-Anweisung abgeschlossen, alle Units im Paket "io" werden eingebunden

Bezeichner "x" gefunden, kein weiteres Include, Inclusion-Abschnitt ist daher abgeschlossen.

Auf Bezeichner "x" folgen die Separatoren ":" und "=", es handelt sich daher um eine Zuweisung. Alles was zwischen "=" und ";" steht muss daher ein mathematischer Ausdruck sein, der dann mithilfe eines Parsers für mathematische Ausdrücke geparst wird.

Ist das eine sinnvolle Vorgehensweise?

EDIT: Hoppala, das hier sollte eigentlich alles nach "Sonstige Fragen zu Delphi"...

[Christian Seehase]

Moin Manuel,

ich glaube, Du hast da ein grundsätzliches Problem:
Die Unterteilung ist zu grob.
Üblicher Weise wird immer das längstmögliche Token gebildet, so dass Du, z.B. nicht : und = getrennt als Token hast, sondern :=
Ausserdem werden die Typen der Token nicht so recht unterschieden.

Ein + ist (für mich ) kein Separator, sondern ein Operator, ebenso wie := als (Zuweisungs)Operator zu verstehen wäre.

[EDIT]

Zitat von 3_of_8:

EDIT: Hoppala, das hier sollte eigentlich alles nach "Sonstige Fragen zu Delphi"...

also für mich gehört das nach "Programmieren allgemein" (wo ich es jetzt auch hinschieben werden).
Ausserdem haben wir für solche Fälle die "Beitrag melden"-Funktion
[/EDIT]

[marabu]

Hallo Manuel,

auch "io.*" ist ein einziges Token. Du solltest vor dem Implementieren des Lexical Analyzers eine Grammatik (EBNF) aufstellen, dann passieren dir solche Sachen nicht. Und wenn du die Grammatik hier einstellst, dann haben wir auch gleich eine Diskussionsgrundlage. Die Grammatik solltest du für den Anfang sehr klein halten und erst, wenn die Basisroutinen deines Parsers ausgetestet sind, würde ich die Grammatik erweitern.

Grüße vom marabu

[3_of_8]

Meinst du eine formale Grammatik?

Nun, die Einteilung habe ich rein intuitiv gemacht.

Separator war für mich alles das, was irgendein Zeichen war, das irgendwas getrennt hat. Dass := ein Token ist, war mir eigentlich klar, nur hatte ich ein Problem, das meinem Lexer beizubringen. Darum kümmere ich mich noch.

Dass io.* ein Token ist, wundert mich. Ist dann (z.B. in Delphi) Memo1.Lines.Add auch ein Token? Ich dachte ein Token ist eine atomare Einheit, und Memo1.Lines.Add lässt sich für mich noch aufteilen...

[marabu]

Hallo,

Zitat von 3_of_8:

Meinst du eine formale Grammatik?

Ja.

Zitat von 3_of_8:

Nun, die Einteilung habe ich rein intuitiv gemacht.

Das hältst du bei steigender Zahl der Produktionen wahrscheinlich nicht durch - oder deine Sprache nimmt chaotische Züge an.

Zitat von 3_of_8:

Separator war für mich alles das, was irgendein Zeichen war, das irgendwas getrennt hat.

Du musst auf den Kontext achten. Solche Zeichen können auch in Kommentaren und Literalen vorkommen.

Zitat von 3_of_8:

Dass io.* ein Token ist, wundert mich. Ist dann (z.B. in Delphi) Memo1.Lines.Add auch ein Token?

Bei "include io.*" scheint mir "include" ein Schüsselwort zu sein und "io.*" ein Literal. Bei "Memo1.Lines" handelt es sich um einen qualified name (QN), "Memo1" und "Lines" sind identifier und "." ist der QN-Separator.

Wenn "io.*" ein Literal ist, dann solltest du überlegen ob du eine einheitliche Schreibweise für Literale verwenden oder ob du Literale im Programmtext und bei den Meta-Befehlen (include?) unterschiedlich handhaben möchtest. Wenn "io.*" auch ein QN ist, dann sorry.

Freundliche Grüße

[3_of_8]

Zitat von marabu:

Ja.

Gut.

Zitat von marabu:

Das hältst du bei steigender Zahl der Produktionen wahrscheinlich nicht durch - oder deine Sprache nimmt chaotische Züge an.

Wenn sie das nicht schon hat.
Liste mir bitte mal alle wichtigen Typen von Tokens auf. Ich habe das so eingeteilt:

Delphi-Quellcode:

  TXeLexerTokenType=(ttInvalid, ttIdentifier, ttSeparator, ttNumericLiteral,
    ttCharacterLiteral, ttStringLiteral, ttBinDataLiteral, ttComment);

Zitat von marabu:

Du musst auf den Kontext achten. Solche Zeichen können auch in Kommentaren und Literalen vorkommen.

Da selbstverständlich nicht. Ich meinte das so: Da steht zum Beispiel der Code "wuppdi:=42;". Da sind ":=" und ";" jeweils Separatoren, weil sie Bezeichner/Litarale/usw. voneinander trennen. Das war meine intuitive Idee, ich weiß ja nicht, wie es "richtig" geht.

Zitat von marabu:

Bei "include io.*" scheint mir "include" ein Schüsselwort zu sein und "io.*" ein Literal. Bei "Memo1.Lines" handelt es sich um einen qualified name (QN), "Memo1" und "Lines" sind identifier und "." ist der QN-Separator.

include io.*; ist so ähnlich gedacht wie in Java: Binde alle Units des Packages "io" ein. Dürfte sich also um einen QualifiedName handeln. Ein Stringliteral ist in meiner "Sprache" immer durch Apostrophen begrenzt.

[3_of_8]

Ich hab mal so eine Grammatik gebastelt. Sehr einfach bis jetzt.

[marabu]

Hallo Manuel,

ein paar kleine Anmerkungen:

• Kein Semikolon am Ende einer Produktion
• Immer das top-level symbol an den Anfang stellen oder in einem Kommentar benennen
• Produktionen fortlaufend durchnummerieren (1) ... (2) ...

Irgendwie hast du es verdammt eilig, ich würde kleiner anfangen. Erstmal fixe Sätze parsen, dann Option, Alternative, Wiederholung hinzunehmen. Weißt du schon, welchen Parsertyp du bauen möchtest - recursive-descent (LL) oder tabellengesteuert (LALR)?

Magst du ein paar Grammatiken studieren? klick

Freundliche Grüße

[3_of_8]

Ich habs nicht so eilig, ich sehe aber gerne kleinere Ergebnisse, um nicht völlig die Motivation zu verlieren... momentan stehe ich kurz davor.

Ich habe an einen... *kratz* wie hieß das? An einen LR-Parser gedacht, dieser Stackautomat mit GoTo-Tabelle...

Zitat:

* Kein Semikolon am Ende einer Produktion
* Immer das top-level symbol an den Anfang stellen oder in einem Kommentar benennen
* Produktionen fortlaufend durchnummerieren (1) ... (2) ...

Kein Semikolon? Hab ich bei Wikipedia aber anders gesehen.
Top-Level-Symbol an den Anfang? Gute Idee, wird vielleicht übersichtlicher.
Produktionen nummerieren? Was bringt das? Was meinst du mit Produktionen? Die Ableitungen?