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

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:

Delphi-Quellcode:

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

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

Delphi-Quellcode:

x := 1;

hiermit aus?

Delphi-Quellcode:

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

[Mephistopheles]

Zitat:

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]

Zitat:

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

Ja, darüber hab ich mir auch schon Gedanken gemacht. Wichtiger fand ich es zunächst jedoch, überhaupt einen Denkanstoß zu kriegen, wie man das ganze vom Prinzip her macht. Also, wie ich den Quellcode überhaupt überprüfen kann. Bevor ich da keine Ideen hab, bringt mir auch eine noch so ausgeklügelte Sprachgestaltung nichts ;)

Zitat:

Zitat von Christian Seehase

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)

Naja, da halte ich mich auch ein wenig an andere Programmiersprachen. Zahlen, die mit 0 beginnen (sofern es sich nicht wirklich um eine 0 haltet) sind ja auch ein wenig witzlos.
Ob man bei Strings nun ' oder " oder was ganz anderes verwendet, ist eher nebensächlich. Das, wo ich mir bisher die wenigsten Gedanken drüber gemacht hab, sind die Operatoren, die ja die wichtigsten sind... ;)

Zitat:

Zitat von Christian Seehase

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>

Ist mir auch schon so ziemlich klar, dass ich jedem Token diese Regeln zuweisen muss... ;)

Zitat:

Zitat von Christian Seehase

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

Wie speichere ich die denn am besten in meinem Programm? Eine Klasse für jedes Token und seine Regeln?

Zitat:

Zitat von Christian Seehase

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.

Jetzt wirds spannend... Das kann man ja prinzipiell ganz praktisch in einer Stringliste machen. Dann brauch ich mir keine Gedanken darüber machen, wie ich bis zum nächsten Leerzeichen gehe. Dann könnte ich ein Array nehmen, wo ich dann die Informationen reinschreib (die gleichen Indizen wie bei der Stringliste vorrausgesetzt). Ist der Ansatz soweit korrekt?

Zitat:

Zitat von Christian Seehase

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

Tja, das ist ja klar ;)

Zitat:

Zitat von Christian Seehase

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

Ja, mit der Stringliste könnte ich dann auch einen Index nach dem anderen durchgehen und abfragen, ob das so korrekt ist, oder nicht... ;)

Zitat:

Zitat von Christian Seehase

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.

Ich hätte dafür jetzt mal die Idee, dass ich ja prinzipiell ein Array of TStrings erstelle (also ein Array von Stringlisten). In jede StringListe schreib ich dann eine Zeile (Programmzeile, endet beim ; ) rein. Die Kommentare streich ich am besten ganz aus dem auszuwertenden Quelltext (bei einzeiligen Kommentaren ist das dann wohl die einzige Stelle, bei der ich auf "physikalische" Zeilenenden achten muss, glaub ich ;)

Zitat:

Zitat von Christian Seehase

....

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

Danke, ich werd dann mal suchen. Geld für Bücher will ich nicht unbedingt ausgeben, jedenfalls noch nicht. Solange es nur so eine poplige Scriptsprache ist... :mrgreen:

@Airblader: Verkompliziere das bitte nicht unnötig. Ich will dann halt immer Leerzeilen als Begrenzung haben, basta :mrgreen:
Gehört meiner Meinung auch zum guten Programmierstil... alles so eng zu schreiben ist eklig :?

[Christian Seehase]

Moin malo,

Zitat:

Zitat von malo

Zahlen, die mit 0 beginnen (sofern es sich nicht wirklich um eine 0 haltet) sind ja auch ein wenig witzlos.

das dürfte sehr von der Sprache abhängen.

Wenn Du in einem C(++)-Quelltext auf eine 0 triffst, kann es sein, dass es sich um eine einfach dezimale 0 handelt, es könnte aber auch der Beginn einer hexadezimalen Zahl (0x, 0X) oder einer oktalen Zahl sein. ;-)
Mal abgesehen davon, dass auch Gleitkommazahlen mit einer 0 beginnen können...

Was die Tokenliste angeht:

Ich habe es (vereinfacht) so gelöst:
Ein Aufzählungstyp der die verschiedenen Tokentypen enthält.
Ein Recordtyp der Typ und Attribut enthält.
Eine Klasse, die ein dynamisches Array des Recordtypen enthält, und für die sonstige Verwaltung der Token zuständig ist.
(z.B. Add, Delete, Insert...)

[Airblader]

@malo
gehört für mich auch dazu, aber in praktisch allen sprachen ist es erlaubt/möglich.
Da es ja deine Sprache ist, ist es dann aber auch deine Sache ;)

air

[malo]

Zitat:

Zitat von Airblader

Da es ja deine Sprache ist, ist es dann aber auch deine Sache ;)

So soll es nicht wirken. Ich bin natürlich jederzeit froh über Ratschläge und Tipps. Aber wenn ich auf sowas achten würde, müsste ich mein ganzes Konzept in den Müll werfen und neu anfangen (vom Programmiertechnischen her. Das mit den StringListen würde nämlich lauter Probleme aufbringen) ;)

Obwohl... grade eben kommt mir dazu die Idee, gezielt nach solchen Konstruktionen zu suchen (vor dem Aufteilen in StringListen!) und einfach Leerzeichen davor und dahinter setzen :mrgreen:

Problem wären dann nur ähnliche Konstruktionen in Strings :?