Wie am besten Parsen?

**Christian Seehase**

Moin Malo,

als erstes solltest Du Dir mal darüber Gedanken machen, was für Bestandteile die Sprache haben soll, und wie diese aufgebaut sein sollen.

Beispiel:
Bezeichner (für Variablen, Keywords, Datentypen):
Regel : dürfen nur aus Buchstaben und Ziffern bestehen, müssen mit einem Buchstaben anfangen.

Zahlen:
Regel : dürfen nur aus Ziffern bestehen, müssen mit einer Ziffer ungleich 0 beginnen, Wertebereich von / bis.

Strings:
Regel : müssen mit ' beginnen, müssen mit ' enden.

Operatoren:
Regel : erlaubt sind +,-,*,/,=,; (in Deinem Beispiel noch $ als Kennzeichen, dass eine Variable folgt)

Jeder dieser Bestandteile ist ein Token, dass sich aus Typ und Attribut zusammensetzt.
Bei einem Bezeichner wäre das dann z.B. Typ: Bezeichner, Attribut: EineIntVariable
oder das =: Typ: Operator Zuweisung, Attribut: <Keines erforderlich>

Wenn Du jetzt also Deine Bestandteile und die Regeln, wie sie gebildet werden hast, kannst Du anfangen die Quelldatei "auseianderzunehmen".

Hierbei musst Du dann Zeichen für Zeichen durchgehen, und bei jedem entscheiden, wie es weitergehen kann.
Wieder auf Dein Beispiel bezogen:
Du triffst auf ein i (das aus int).
Da es sich um einen Buchstaben handelt, muss es sich um irgendeinen Bezeichner handeln. Jetzt kannst Du also von hier aus, bis zum ersten Trennzeichen durchgehen (hier ein Blank), und hast anschliessend Deinen Bezeichner int.
1. Token: IDENTIFIER:int

Als nächstes triffst Du auf $
2. Token: OperatorVariable:$

jetzt folgt wieder ein Bezeichner usw.

Wenn Du auf einen Kommentar triffst, kannst Du diesen natürlich überlesen, denn er hat ja mit dem Ablauf nichts zu tun.

Als Interpreter solltest Du eine ganze Zeile am Stück in Token verwandeln (gekennzeichnet bei Dir durch

, und kannst anschliessend darangehen die Zeile auszuwerten:
1. Token ist ein Datentyp
=> jetzt muss ein $ folgen
=> jetzt muss ein Bezeichner folgen, der kein Keyword ist (hier: OK, kann in die Liste der Variablen als integer-Variable aufgenommen werden)
=> jetzt muss ein logisches Zeilenende folgen

Jetzt bis zum "physikalischen"-Zeilenende (#13#10) wieder von Vorne, da nur noch ein Kommentar folgt geht's weiter:
Ist diese aufgespalten:
1. Token ein $
=> Jetzt muss eine Variable folgen. In der Liste ist diese, als kann es weitergehen, sonst Fehler
=> Jetzt muss eine Zuweisung folgen.
=> Da es sich um eine integer-Variable handelt, muss jetzt ein numerischer Ausdruck folgen (Variablen, Zahlen, Operatoren)
=> eine 10, also wird der Variablen in der Liste jetzt dieser Wert zugeordnet.

....

Das ist jetzt nur einmal grob vereinfacht dargestellt.

Als Suchbegriffe zu diesem Thema kannst Du es mal mit Compilerbau, DEA (Determinierender endlicher Automat), Zustandsautomat versuchen.
Zum Thema Hier im Forum suchen

Compilerbau solltest Du sogar hier fündig werden. Letztens hat hier jemand auf ein gutes Online-Buch zum Thema verlinkt gehabt.

Im Moment zur Hand habe ich diesen

Compilerbau

**malo**

Zitat von Mephistopheles:

Such mal nach "Tokenizer". Der kommt nämlich noch vor dem Parser. Der Tokenizer zerlegt Quelltext in seine Bestandteile (z.B. Schlüsselwörter, Stringliterale, Numerische Konstanten, Operatoren) und danach kommt der Parser, der ja auch weiß, ob bestimmte Token in einer gewissen Reihenfolge auftauchen dürfen. Nehmen wir mal:

for x := 0 do 78 to Der Tokenizer würde hier finden: for, x, :=, 0, do, 78, to!

Aber erst der Parser kann ermitteln, daß das DO zwischen den beiden Zahlen syntaktisch inkorrekt ist.

Alternativ kannst du bei Bloodshed mal nach CoPascal suchen - einem Miniinterpreter von N. Wirth, dem Erfinder von Pascal - dort sind ja alle benötigten Techniken mehr oder minder implementiert.

Das ist Ne Idee!

auch, wenn ich noch nicht viel sinnvolles zu "Tokenizer" gefunden hab (es soll zwar eine tokenizer.pas geben, die ich jedoch noch nicht gefunden hab), ist das mal ein vernünftiger Ansatz. Prinzipiell könnte ich ja den ganzen Quellcode in StringListen packen (eventuell für jede Zeile eine eigene, also bis zum Semikolon immer, aber darüber kann man ja noch diskutieren). Dann prüfe ich einen Eintrag nach dem anderen, ob die in die Syntax passt. Aber das ist mal 'ne Idee...

//edit: Auf Christians Beitrag antworte ich später noch mal, hab grad nich so viel zeit...

**Christian Seehase**

Moin Malo,

wenn Du erst einmal weisst aus was sich die Sprache zusammensetzen soll ist ein Tokenizer noch das kleinste Übel

**DGL-luke**

der tokenizer muss doch den text nur mit den begrenzungszeichen [' ',';',','] zerteilen. und am besten noch sagen, welches begrenzungszeichen es denn war.

**Airblader**

@DGL

und sie siehts anstatt mit

x := 1; hiermit aus?

x:=1; Da brauchst du als Trennzeichen '', was dann aber jedes Zeichen separiert.
Gut, in einer "Anfangssprache" kann man halt erzwingen, damit man Leerzeichen setzen muss

air

Zitat von DGL-luke:

der tokenizer muss doch den text nur mit den begrenzungszeichen [' ',';',','] zerteilen. und am besten noch sagen, welches begrenzungszeichen es denn war.

Wie sieht's aus mit Begrenzern innerhalb von Stringliteralen? Muß alles beachtet werden. Also von "nur" würde ich hier nicht reden.

**malo**