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:

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]

[DP-Maintenance]

Dieses Thema wurde von "Christian Seehase" von "Object-Pascal / Delphi-Language" nach "Programmieren allgemein" verschoben.
Bislang ein allgemeines Problem

[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:

Zitat von 3_of_8

Meinst du eine formale Grammatik?

Ja.

Zitat:

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:

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:

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:

Zitat von marabu

Ja.

Gut.

Zitat:

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

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:

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?

[marabu]

Hallo Manuel,

Zitat:

Zitat von 3_of_8

... momentan stehe ich kurz davor. ...

vor den ersten Ergebnissen oder vor dem Motivationsverlust?

Zitat:

Zitat von 3_of_8

... Stackautomat mit GoTo-Tabelle ...

das scheint mir der gleiche zu sein, den ich mit LALR bezeichnet habe.

Zitat:

Zitat von 3_of_8

... Kein Semikolon? Hab ich bei Wikipedia aber anders gesehen. ...

Wikipedia ist ein Wiki - da darf jeder irgendwas schreiben. Aber ich muss zugeben, dass die ISO-Standardisierung des Semikolon als Indikator für Line-End Kommentare unbemerkt an mir vorüber ging. Ich selbst würde mich aber weiterhin auf ganzzeilige Kommentare beschränken.

Zitat:

Zitat von 3_of_8

... Produktionen nummerieren? Was bringt das? Was meinst du mit Produktionen? Die Ableitungen?

Eine Produktion (Ableitung) ohne fortlaufende Nummer kann nur über ihr non-terminales Symbol identifiziert werden - und das können Wort-Ungetüme sein. Bei P42 weiß jeder, dass es sich um die Produktion (42) handelt. Die Nummern dienen nicht nur der Bequemlichkeit. Beim Aufbau deiner Tabellen wirst du sie brauchen.

Übrigens: Ein wesentlicher Unterschied zwischen den beiden von mir genannten Parsertypen ist der, dass ich einen Recursive-Descent Parser oft selbst schreibe, aber einen tabellengesteuerten LALR Parser in der Regel von einem Generator erstellen lasse. Der streng formale Ansatz beim LALR macht ihn zum idealen Kandidaten einer Automatisierung.

Freundliche Grüße

[3_of_8]

Vor dem Motivationsverlust. ;)

Wie genau gehe ich denn jetzt an diesen LALR-Parser ran? Was soll ich zuerst erstellen und wie soll ich ihn implementieren?

[3_of_8]

*push*

[Sidorion]

@topic: das Zauberwort heisst XML!
Dein Text ist das TXMLDocument, die Unit das DocumentElement dieses TXMLDocument. Dessen NodeName wäre 'Unit' und dieser hätte ein Attribut namens 'Name' mit dem Wert 'Test'.
In diesem DocumentElement befindet sich nun der Knoten 'includes', in diesem wieder ein Knoten 'include' mit dem Attribut 'name' und Wert 'io.*'...
.. und vóilà: eine Baubstruktur.

p.s.: die XML-Knoten kann man dann noch typisieren.

[H4ndy]

Ich bin gerade selber dran, einen Parser zu schreiben (VRML).
Allerdings habe ich auch noch nicht so richtig einen Plan,
wie ich diesen rein programmtechnisch umsetzen soll. Man findet
im Netz nur tonnenweise theoretische Grundlagen zu Parsern allgemein.
Gibt es da nicht irgendwas, was man sich anschauen kann, wie man
effizient den Text durchläuft und solche "Knoten" dann anlegt (Objekte?).

Bis jetzt suche ich einfach relativ "doof" und dreckig nach bestimmten
Schlüsselwörtern und versuche dann die einzelnen Properties zu lesen.
Allerdings wird das ein riesen Code um alle benötigten Teil abzudecken -.-

[3_of_8]

Das Programm selbst ist nicht das Problem, ein LR-Parser ist relativ leicht zu implementieren. Ich überlege mir gerade das wirklich Schwere an der Sache: Die Aktions- und GoTo-Tabelle.

[St.Pauli]

Vieleicht kann dir das freie Buch "Parsing Techniques - A Practical Guide" von Dick Grune und Ceriel J.H. Jacobs weiterhelfen.