Wie am besten Parsen?

[malo]

Hi!

Ich hab mir mal überlegt eine kleine Scriptsprache zu entwickeln... allerdings weiß ich grade nicht, wie ich am besten den Script-Quellcode parsen kann (also welche Technik ich verwenden soll). Ich könnte ja prinzipiell den ganzen Code mit einer Schleife durchlaufen, aber das halte ich nicht für eine gute Idee... besonders, wenn ich nicht nach Zeichen suche, sondern nach Strings (und die mit solch einer Schleife schwieriger zu finden sind).

Kennt jemand zufällig einen Trick, wie man leicht den Code parsen kann? Oder hat überhaupt jemand Ideen, wie man das machen könnte?



Danke schonmal im Vorraus!

[Dax]

Ich habs zwar mal gemacht, aber im erklären bin ich nicht so sehr großartig ;-)

Also, wenn du eine Sprache haben willst, musst du verschiedene syntaktische Elemente festlegen, darunter auch Begrenzer für Statements usw. in Pascal gibt es jede Menge dieser Dinger: ";,()[] begin end for in do out var type" usw.. Du gehts eigentlich beim parsen nur von einem Begrenzer zum nächsten und wertest aus, was dazwischen steht, gekoppelt mit der Bedeutung des Begrenzers selbst.

[malo]

Zitat:

Zitat von Dax

Ich habs zwar mal gemacht, aber im erklären bin ich nicht so sehr großartig ;-)

Also, wenn du eine Sprache haben willst, musst du verschiedene syntaktische Elemente festlegen, darunter auch Begrenzer für Statements usw. in Pascal gibt es jede Menge dieser Dinger: ";,()[] begin end for in do out var type" usw.. Du gehts eigentlich beim parsen nur von einem Begrenzer zum nächsten und wertest aus, was dazwischen steht, gekoppelt mit der Bedeutung des Begrenzers selbst.

Aber wie lese ich die Begrenzer am besten aus? Mit Pos(PosEx)? Oder mit Copy? Oder wie genau sollte man das am besten machen? :gruebel:

[Ultimator]

Du könntest dir eine Funktion schreiben, die dir zurückgibt, ob ein Zeichen eine Ziffer ist, ein + oder - oder * oder / Zeichen ist oder ein Buchstabe.
Dann durchläufst du mit ner while-Schleife (z.B. ob ein Zeichen eine Ziffer ist) den String und suchst nach Zahlen.
Dann machst du das ganze mit den Rechenzeichen und schaust, wie alles gerechnet werden muss.

Natürlich musst du auf Klammern aufpassen ;)

[Sprint]

Ein sehr einfacher, aber hilfreicher Parser wäre z.B. die Klasse TParser aus der Unit Classes. Darauf könntest du deinen eigenen Parser aufbauen.

[malo]

Zitat:

Zitat von Sprint

Ein sehr einfacher, aber hilfreicher Parser wäre z.B. die Klasse TParser aus der Unit Classes. Darauf könntest du deinen eigenen Parser aufbauen.

Gibts da vielleicht eine Dokumentation oder so zu? Weil ich in der OH nichts unter "Parser" oder "TParser" finde :duck:

[Sprint]

Zitat:

Zitat von malo

Gibts da vielleicht eine Dokumentation oder so zu? Weil ich in der OH nichts unter "Parser" oder "TParser" finde :duck:

Hab bis jetzt noch keine Doku zu TParser gesehen. In Borland's Newsgroups zu Delphi kannst du einige Beispiele finden.

[malo]

Naja, ich such immer noch nach einer guten Methode, einen String nach anderen Teil-Strings zu durchsuchen.

Meine Script-Syntax soll in etwa so aussehen:

Code:

int $EineIntVariable; //an Sprachen wie PHP, Perl oder C angelehnt
$EineIntVariable = 10; //Wert 10 zuweisen
Message('Hier Text'); //Messagebox
int $ZweiteIntVariable; // noch eine IntVariable erstellen
$EineIntVariable = $ZweiteIntVariable + 1;

Etwa so... jetzt brauche ich aber eine vernünftige Möglichkeit, den Code von oben bis unten durchzulaufen und zu prüfen, ob eines der Schlüsselwörter zu finden ist bzw. ob eine Funktion aufgerufen wird. Mit Pos oder PosEx zu arbeiten halte ich für ungeschickt, weil ich den Quellcode ja von oben nach unten durcharbeiten will. Bei Pos sucht der ja nur nach einzelnen Schlüsselwörtern im Zeilstring... :?

@Dax: Wie hast du denn zum Beispiel in deiner Scriptsprache nach den Bezeichnern gesucht? Also mit welcher Funktion? Eine komplett selbstgeschriebene, oder wie genau?

[Dax]

Ich hab meine Funktion komplett selbst geschrieben, nur mit Pos, Schleifen und Pointern. Ziemlich unsichere Sache, die ich da hatte, und extrem spezifisch.. die hier zu posten und deinen Wünschen entsprechend umzuändern würde länger dauern, als eine komplett neue, flexiblere Funktion zu schreiben..

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

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

[Christian Seehase]

Moin Malo,

eigentlich brauchst Du Dir keinen Gedanken darum zu machen bestimmte Konstruktion zu suchen.
Als erstes solltest Du Deinen Sourcecode in einen Tokenstrom verwandeln. Ob diese dann syntaktisch richtig sind spielt zu diesem Zeitpunkt keine Rolle.

Wenn Du das Beispiel von Airblader nimmst:

x := 1;
x:=1;

Dein Tokenizer stösst auf das x
Es muss sich also um einen Bezeichner handeln.
Jetzt muss nur noch geprüft werden, wie lang dieser ist. Enden wird er an einem Trennzeichen, wobei es nun keine Rolle spielt, ob dieses Trennzeichen wieder der Beginn eines anderen Tokentyps sein kann (in diesem Falle : ) oder ein Whitespace-Zeichen ist (i.d.R. Tabulator, Leerzeichen).

Wurde der vollständige Bezeichner ermittelt, muss der Tokenizer nun alle Whitespace-Zeichen überspringen, bis er zu dem nächsten kommt, aus dem er ein Token machen kann, oder das den Ablauf steuert.

Hierbei wird er also auf ein : stossen und muss nun prüfen ob das alles ist, oder ob noch unmittelbar ein = folgt. Es könnte ja auch das Trennzeichen für ein Case-Label sein. Folgt ein = wurde ein := erkannt, und kann in die Tokenliste aufgenommen werden.

usw.

[malo]

Das würde aber meine Idee mit der Stringliste (den ganzen Code reinladen und bei Leerzeichen aufteilen) so ziemlich zunichte machen. Ich müsste alles per Hand trennen (also jedes mal einzeln prüfen, ob das zum ersten Token gehört, oder ob das Zeichen ein Begrenzer oder ein neues Token sein kann, was wahrscheinlich extrem auf die Performence gehen kann, wie ich fast schon fürchte :?

Oder geht das vielleicht noch einfacher?

Wenn nicht, dann werd ichs aber wahrscheinlich auf die "langsame" Methode machen... ;)

[Christian Seehase]

Moin Malo,

ich kann Dich beruhigen, dass geht mit Sicherheit nicht auf die Performance.
Bei dem beschriebenen Verfahren braucht mein Programm ca. 1 sek. / MB Sourcecode (C-Header).

[EDIT]
ausserdem klingt es schwieriger als es ist.
[/EDIT]

[Nils_13]

Schleifen und If Abfragen gehören dazu, kommst eh nicht drumrum.

[malo]

Zitat:

Zitat von Nils_13

Schleifen und If Abfragen gehören dazu, kommst eh nicht drumrum.

Ja, ist mir klar. Da wird der Delphi-Compiler wohl ne Menge if-Abfragen kompilieren müssen. Aber erstmal kümmere ich mich darum, überhaupt Variablen erzeugen und damit arbeiten zu können, das ist schon schwer genug. Die Sprache ist ja am Ende beliebig erweiterbar ;)

[Mephistopheles]

Zitat:

Zitat von Nils_13

Schleifen und If Abfragen gehören dazu, kommst eh nicht drumrum.

If braucht niemand. Da kann man auch while dafür nehmen. Oder gleich eine for-Schleife wie in C. :-D

[malo]

Zitat:

Zitat von Mephistopheles

Zitat:

Zitat von Nils_13

Schleifen und If Abfragen gehören dazu, kommst eh nicht drumrum.

If braucht niemand. Da kann man auch while dafür nehmen. Oder gleich eine for-Schleife wie in C. :-D

Dann muss man aber ein hässliches Break ans Ende der Schleife setzen... :?

[Christian Seehase]

Moin Malo,

das lässt sich bestens mit case lösen. (und einer while-Schleife, da man die Schleifenvariable u.U. manipulieren muss)

[malo]

Zitat:

Zitat von Christian Seehase

Moin Malo,

das lässt sich bestens mit case lösen. (und einer while-Schleife, da man die Schleifenvariable u.U. manipulieren muss)

Ich weiß aber grade nicht, ob ich wirklich nur ordinale Typen dafür abfragen muss, deshalb hab ich von if-Abfragen geredet. Wie das formal aufgebaut wird, kann ja noch ausgeklügelt werden. Die if-Abfragen sind im Moment noch nicht das Thema ;)

[Mephistopheles]

Zitat:

Zitat von malo

Dann muss man aber ein hässliches Break ans Ende der Schleife setzen... :?

Nicht bei einer C-for-Schleife :)

for(;Abbruchbedingung;) {} ...

[Christian Seehase]

Moin Malo,

Zitat:

Zitat von malo

Ich weiß aber grade nicht, ob ich wirklich nur ordinale Typen dafür abfragen muss,

lass es mich mal so sagen:
Es würde mich wundern, wenn nicht ;-)

[malo]

Zitat:

Zitat von Mephistopheles

Zitat:

Zitat von malo

Dann muss man aber ein hässliches Break ans Ende der Schleife setzen... :?

Nicht bei einer C-for-Schleife :)

for(;Abbruchbedingung;) {} ...

Mag sein, gehört jedoch nicht hierher ;)

[c.wuensch]

Hi Malo,

vor kurzem haben wir im Informatikunterricht Parser behandelt, und sogar einen Parser für ein (sehr stark vereinfachtes) Pascal geschrieben.

Besonders wichtig ist, zuerst eine klare Struktur zu haben (kann man schön in Syntaxdiagrammen darstellen).

Wenn du willst, kann ich dir den vereinfachten Parser ja mal schicken, vielleicht hilft dir das was!

Cu, Chris

[EDIT] habs mal angefügt [/EDIT]

[Ultimator]

Da es hier in dem Thread ja um u.a. Tokenizer geht, muss ich gleich mal was fragen :stupid:

Bisher hab ich meinen Tokenizer soweit, dass er mir alles schön zerlegt: Klammern, Zahlen und natürlich auch Rechenzeichen.
Das Problem ist nur: Das Minus ist ja sowohl Rechenzeichen als auch ein Vorzeichen. Wie mach ich meinem Tokenizer klar, ob ein Minus als Vorzeichen oder als Rechenzeichen zu sehen ist? :-?

[malo]

Zitat:

Zitat von Ultimator

Bisher hab ich meinen Tokenizer soweit, dass er mir alles schön zerlegt: Klammern, Zahlen und natürlich auch Rechenzeichen.
Das Problem ist nur: Das Minus ist ja sowohl Rechenzeichen als auch ein Vorzeichen. Wie mach ich meinem Tokenizer klar, ob ein Minus als Vorzeichen oder als Rechenzeichen zu sehen ist? :-?

Also, mathematisch gesehen gibt es ja eigentlich keinen wirklichen Unterschied zwischen Rechenzeichen und Vorzeichen (bei Addition und Subtraktion). Im Endeffekt wird halt eh alles addiert.

Code:

5-3=2

ist das selbe wie

Code:

5 + (-3) = 2

. Daher würde ich einfach ein Minus immer als Vorzeichen interpretieren. Dann soll der Parser nachher erkennen, dass, wenn zwei Zahlen nacheinander ohne Rechenzeichen (dafür aber einmal mit Vorzeichen) kommen, addiert werden sollen. ;)

Nur meine Idee ;)

[Dax]

Gar nicht. Das ist Sache des Parser, der Tokenizer zerlegt nur ;)

[Ultimator]

Zitat:

Zitat von malo

Also, mathematisch gesehen gibt es ja eigentlich keinen wirklichen Unterschied zwischen Rechenzeichen und Vorzeichen (bei Addition und Subtraktion).

Da liegt das Problem :mrgreen:

@Dax: Okay :lol:
Der Tokenizer soll das '-' also immer als ein Token ansehen?

[Dax]

Es sei denn, du willst auch strings parsen, dann sollte der Tokenizer das - in einem string nicht erkennen. Aber generell für Matheparser: ja.

[Ultimator]

Nein, Strings will ich nicht, ich will nur nen Matheparser ;)
Wie isses bei der Multiplikation, Division und (noch schlimmer :lol:) den Potenzen?
Wie lass ich das den Parser richtig auswerten, wo jetzt ein Minuszeichen dazugehört?

[alzaimar]

Ich misch mich mal ein: Der Tokenizer zerlegt den Inputtext (eine Folge von Zeichen) in eine Folge von 'Token', damit des der Parser einfacher hat. Aus dem Wort 'begin' wird der Token BEGIN, aus dem String 'ein String mit begin' wird der Token STRING (mit einem Verweis auf den String-inhalt), aus einem FooBar wird ein IDENTIFIER (mit dem Verweis auf den Namen 'FooBar') und aus dem Zeichen '-' wird das Token MINUS. Dabei gibt es schon ein paar Fallen. Was soll der Tokenizer z.B. aus ':=' machen? Zwei Token, nämlich COLON und EQUAL, oder ein Token, 'ASSIGNMENT'. Was ist '..', DECIMALPOINT DECIMALPOINT oder DOTDOT (oder was auch immer). Hier kann man z.B. vor den Tokenizer noch einen Präprozessor knallen, der mit einem Lookaheadbuffer das nächste Zeichen prüft und ggf. Metazeichen (z.B. #255, statt :=) an den Tokenizer übermittelt, damit der eben bei jeden 'Zeichen' weiss, woran er gerade ist. Zu kompliziert? Na, ein guter Tokenizer ist ja auch nicht so mal eben geschrieben.

Ein Tokenizer und Parser sollte Jeder ernsthafte Programmierer mal implementiert haben. Meine Meinung.

Eine Möglichkeit, die Punkt-Vor-Strichrechnung zu implementieren, ist die, die Grammatik erstmal zu formulieren und diese dann in Funktionen zu packen, z.B. so:

Code:

Term ::= <Ausdruck> [<StrichOp> <Term>] /* Das in [] angegeben kann, muss aber nicht angegeben werden
StrichOp ::= '+' | '-'
Ausdruck ::= <SimpleTerm> [ <MulOp> <Ausdruck> ]
MulOp ::= '*' | '/'
SimpleTerm ::= '(' <Term> ')'  | <Number> 
Number ::= [ <Sign> ] <Digits>
<Sign> ::= [<PlusOrMinus> [<Sign>]]
PlusOrMinus ::= '+' | '-'

Das kann man z.B. so programmieren:

Delphi-Quellcode:

Function IsTerm : Boolean;
Begin
  If IsAusdruck Then Begin
    If IsStrichOp then
      If IsTerm Then 
        Result := True
      else
        Error 'Term erwartet'
  end
  else
    Error 'Ausdruck erwartet'
End;

Function IsAusdruck : Boolean;
Begin
  If IsSimpleTerm Then Begin
    If IsMulOp then
      If IsAusdruck Then 
        Result := True
      else
        Error 'Ausdruck erwartet'
  end
  else
    Error 'SimpleTerm erwartet'
End;

Function IsStrichOp : Boolean;
Begin
  If (CurrentToken = PLUS) Or (CurrentToken = MINUS) Then Begin
    AdvanceToNextToken;
    Result := True;
  End
  Else
    Result := False;
End;
...

Man sollte sich aber mit formalen Grammatiken (z.B. in Backus-Naur Form) auskennen. Das wichtige an der Grammatik ist, das man zu jeden Zeitpunkt anhand des nächsten Token entscheiden kann, wohin die Reise geht. Bei einem mathematischen Ausdruck geht das noch, aber bei einer Programmiersprache wird das schon schwieriger...

Viel Spass!