BlitzMax Lexer / Parser schreiben

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	Artemis Betreff: BlitzMax Lexer / Parser schreiben	Mo, Mai 12, 2008 10:42 Antworten mit Zitat
Moin, ich bin im Moment dabei einen BlitzMax Lexer zu schreiben. Ich orientiere mich so ein bisschen an dem C-Beispiel auf englischen flex-Wikipedia-Seite. Ich frage mich jetzt, wie weit der Lexer den Code aufbereiten soll und un wie weit der Parser das macht. Die Frage ist z.B. ob der Lexer aus Rem Kommentar EndRem ein T_MULTILINE_COMMENT machen soll oder ob der Parser das macht. Eine weitere Frage ist, ob der Lexer Keywords schon zu speziellen Tokens macht, also Function MachWas() zu T_FUNCTION …. Artemis.

Artemis

Betreff: BlitzMax Lexer / Parser schreiben

Mo, Mai 12, 2008 10:42
Antworten mit Zitat

Moin,

ich bin im Moment dabei einen BlitzMax Lexer zu schreiben.

Ich orientiere mich so ein bisschen an dem C-Beispiel auf englischen flex-Wikipedia-Seite.

Ich frage mich jetzt, wie weit der Lexer den Code aufbereiten soll und un wie weit der Parser das macht.

Die Frage ist z.B. ob der Lexer aus
Rem
Kommentar
EndRem
ein T_MULTILINE_COMMENT machen soll oder ob der Parser das macht.

Eine weitere Frage ist, ob der Lexer Keywords schon zu speziellen Tokens macht, also Function MachWas() zu T_FUNCTION ….

Artemis.

	Blitzcoder Newsposter	Mo, Mai 12, 2008 11:47 Antworten mit Zitat
In der Regel zerlegt der Lexer den Code nur in Token. Das heißt, es gibt gewisse Trennerzeichen, die Token trennen(Leerzeichen, Klammern, Kommata, Punkte etc.). Die Zuordnug als Kommentar sollte eigentlich auch erst der Parser machen, indem er beim Token "rem" alles bis zum "endrem" bzw. "end rem" ausblendet. In meiner IDE hab ich Lexer und Parser zusammengepackt, also immer wenn der Lexer ein Token findet wird processToken() aufgerufen.
P4 3 Ghz@3,55Ghz\|GF 6600GT 256MB\|Samsung 80GB \| 2x Samsung 160GB\|2048MB DDR-400 RAM\|6 Mbit Flatrate \| Logitech G15 \| Samsung 225BW-TFT \| Ubuntu Gutsy Linux \| Windows Vista \| Desktop \| Blog \| CollIDE \| Worklog ________________ \|°°°°°°°°°°°°°°\|\|'""\|""\__,_ \|______________ \|\|__ \|__\|__ \|) \|(@) \|(@)"""\|(@)(@)**\|(@)

Blitzcoder

Newsposter

Mo, Mai 12, 2008 11:47
Antworten mit Zitat

In der Regel zerlegt der Lexer den Code nur in Token. Das heißt, es gibt gewisse Trennerzeichen, die Token trennen(Leerzeichen, Klammern, Kommata, Punkte etc.). Die Zuordnug als Kommentar sollte eigentlich auch erst der Parser machen, indem er beim Token "rem" alles bis zum "endrem" bzw. "end rem" ausblendet.

In meiner IDE hab ich Lexer und Parser zusammengepackt, also immer wenn der Lexer ein Token findet wird processToken() aufgerufen.

P4 3 Ghz@3,55Ghz|GF 6600GT 256MB|Samsung 80GB | 2x Samsung 160GB|2048MB DDR-400 RAM|6 Mbit Flatrate | Logitech G15 | Samsung 225BW-TFT | Ubuntu Gutsy Linux | Windows Vista | Desktop | Blog | CollIDE | Worklog
________________
|°°°°°°°°°°°°°°||'""|""\__,_
|______________ ||__ |__|__ |)
|(@) |(@)"""**|(@)(@)****|(@)

	Artemis	Mo, Mai 12, 2008 12:13 Antworten mit Zitat
Und wie sieht das bei Einzel-Zeilen-Kommentaren aus, und bei Strings? Ich tendiere eher zu der Variente, dass der Lexer auch alle "Blöcke" (Strings, Kommentare) zu Tokens umwandelt. Denn wenn man das macht, spart man bei einem großen Kommentar relativ viel Speicher und es sollte auch schneller laufen. EDIT: Aber so etwas wie $12 muss der Lexer schon in ein T_HEXADECIMAL umwandeln, oder? Würe ja sonst schon Probleme bei $FF geben. EDIT2: So, ich habe den Lexer so weit fertig, dass er alles schön in Token aufteilt. Das einzige was ich unschön finde, ist dass alles handcoded ist, vor allem das Ende eines Rem-Kommentars sind viele Ifs. Ich habe den Lexer jetzt auch die Blöcke machen lassen, denn: Wenn irgendwo in einem String / Kommentar ein \ oder € o.ä. auftaucht, weiß der Lexer nichts damit anzufangen und wirft nen Fehler, da die Zeichen in Code auch nichts verloren haben. Nur mit den Blöcken kann ich das ganze kompensieren. Btw: Blitzcoder, was meinste, ist das langsam, wenn der Lexer für die Datei pub.mod/glew.mod/glew.bmx knappe 500ms braucht?

Artemis

Mo, Mai 12, 2008 12:13
Antworten mit Zitat

Und wie sieht das bei Einzel-Zeilen-Kommentaren aus, und bei Strings?

Ich tendiere eher zu der Variente, dass der Lexer auch alle "Blöcke" (Strings, Kommentare) zu Tokens umwandelt.

Denn wenn man das macht, spart man bei einem großen Kommentar relativ viel Speicher und es sollte auch schneller laufen.

EDIT: Aber so etwas wie $12 muss der Lexer schon in ein T_HEXADECIMAL umwandeln, oder? Würe ja sonst schon Probleme bei $FF geben.

EDIT2: So, ich habe den Lexer so weit fertig, dass er alles schön in Token aufteilt. Das einzige was ich unschön finde, ist dass alles handcoded ist, vor allem das Ende eines Rem-Kommentars sind viele Ifs.

Ich habe den Lexer jetzt auch die Blöcke machen lassen, denn: Wenn irgendwo in einem String / Kommentar ein \ oder € o.ä. auftaucht, weiß der Lexer nichts damit anzufangen und wirft nen Fehler, da die Zeichen in Code auch nichts verloren haben. Nur mit den Blöcken kann ich das ganze kompensieren.

Btw: Blitzcoder,
was meinste, ist das langsam, wenn der Lexer für die Datei pub.mod/glew.mod/glew.bmx knappe 500ms braucht?

	E. Urbach ehemals "Basicprogger"	Di, Mai 13, 2008 16:43 Antworten mit Zitat
Zitat: ist das langsam, wenn der Lexer für die Datei pub.mod/glew.mod/glew.bmx knappe 500ms braucht? Wenn ich mich mal einmischen darf: Ja, ist langsam, zumindest geht es schneller. Mein BMax-Lexer/Parser braucht bei glew.bmx fürs Parsen, Umwandeln in XML-Code und die Ausgabe in eine XML-Datei bei glew.bmx etwa 270 ms, allerdings ist dieser auch in C++ geschrieben, was vielleicht den Speedunterschied erklären könnte. Wenn der Lexer/Parser in BMax programmiert wurde, dann sind 500 ms für ca. 3500 Zeilen durchaus nicht schlecht. Zitat: vor allem das Ende eines Rem-Kommentars sind viele Ifs. Welchen Algorithmus benutzt du, um das Ende von mehrzeiligen Kommentaren zu erkennen? Eigentlich dürften es gar nicht so viele Ifs sein...
The box said, "Requires Windows XP or better", so I installed Ubuntu \| Linux is NOT Windows Flua :: Profiler für BB und BMax :: Partikel-Engine für BMax :: Lyphia-Projekt Quellcode (BMax) :: Automatische Parallelisierung :: Meine Musik

E. Urbach

ehemals "Basicprogger"

Di, Mai 13, 2008 16:43
Antworten mit Zitat

Zitat:

ist das langsam, wenn der Lexer für die Datei pub.mod/glew.mod/glew.bmx knappe 500ms braucht?

Wenn ich mich mal einmischen darf: Ja, ist langsam, zumindest geht es schneller.
Mein BMax-Lexer/Parser braucht bei glew.bmx fürs Parsen, Umwandeln in XML-Code und die Ausgabe in eine XML-Datei bei glew.bmx etwa 270 ms, allerdings ist dieser auch in C++ geschrieben, was vielleicht den Speedunterschied erklären könnte.
Wenn der Lexer/Parser in BMax programmiert wurde, dann sind 500 ms für ca. 3500 Zeilen durchaus nicht schlecht.

Zitat:

vor allem das Ende eines Rem-Kommentars sind viele Ifs.

Welchen Algorithmus benutzt du, um das Ende von mehrzeiligen Kommentaren zu erkennen?
Eigentlich dürften es gar nicht so viele Ifs sein...

The box said, "Requires Windows XP or better", so I installed Ubuntu | Linux is NOT Windows
Flua :: Profiler für BB und BMax :: Partikel-Engine für BMax :: Lyphia-Projekt Quellcode (BMax) :: Automatische Parallelisierung :: Meine Musik

	Artemis	Di, Mai 13, 2008 20:02 Antworten mit Zitat
Zur Zeit läuft das so, dass ich als input einen Stream habe, damit große Dateien nicht vollständig in den Speicher geladen werden müssen. Aus diesem Stream hole ich mir das nächste Zeichen und prüfe dann, was es ist. Bei einem + z.B. erstelle ich sofort ein neues Token und nehme mir wieder das nächste Zeichen. Stoße ich auf ein " hole ich mir solange das nächste Zeichen, bis ich wieder auf ein " Treffe. Dann ist ein String fertig. Bei Rem sieht das so aus, dass ich einen Identifier prüfe ob er gleich "rem" ist. Ist dem so, laufe ich weiter und hole mir weiter die Zeichen. Da ein EndRem nur am Anfang einer neuen Zeile - ggf. Leerzeichen und Tabs vorher - sieht das so aus: (PSEUDO-Code) Code: [AUSKLAPPEN] [EINKLAPPEN] while not eof() while zeichen = leerzeichen oder zeichen = tab nächsteszeichen() wend if zeichen = e then nächteszeichen() if zeichen = n then ... ' usw =d, (= ,) =r, =e, =m endif endif while zeichen <> neuezeile nächteszeichen() wend wend Ich glaube schon, dass man das ganze effizienter lösen kann, vor allem wenn man die Dateien cached, dann könnte ich einfach einen regex auf den rest-string schicken. Momentan prüfe ich, wie es aussieht, dass der Lexer keine vollständigen Strings und Kommentare erkkent und bei unbekannten Zeichen einfach ein Token UNKNOWN erstellt. Das ganze kommt dann an den Parser (bisher nicht vorhanden), der dann erst ganze Strings und Kommentare baut, wobei er UNKNOWN Tokens in Strings und Kommentaren erlaubt, sonst aber einen Fehler ausgibt. Ich melde mich, wenn ich soweit fertig bin, dass ich die beiden Ergebnisse (bisher <> neu) vergleichen kann. Wenn jemand noch einen Vorschlag hat, der melde sich.

Artemis

Di, Mai 13, 2008 20:02
Antworten mit Zitat

Zur Zeit läuft das so, dass ich als input einen Stream habe, damit große Dateien nicht vollständig in den Speicher geladen werden müssen.

Aus diesem Stream hole ich mir das nächste Zeichen und prüfe dann, was es ist. Bei einem + z.B. erstelle ich sofort ein neues Token und nehme mir wieder das nächste Zeichen.
Stoße ich auf ein " hole ich mir solange das nächste Zeichen, bis ich wieder auf ein " Treffe. Dann ist ein String fertig.

Bei Rem sieht das so aus, dass ich einen Identifier prüfe ob er gleich "rem" ist. Ist dem so, laufe ich weiter und hole mir weiter die Zeichen.
Da ein EndRem nur am Anfang einer neuen Zeile - ggf. Leerzeichen und Tabs vorher - sieht das so aus: (PSEUDO-Code)
Code: [AUSKLAPPEN]

while not eof()
while zeichen = leerzeichen oder zeichen = tab
nächsteszeichen()
wend
if zeichen = e then
nächteszeichen()
if zeichen = n then
... ' usw =d, (= ,) =r, =e, =m
endif
endif
while zeichen <> neuezeile
nächteszeichen()
wend
wend

Ich glaube schon, dass man das ganze effizienter lösen kann, vor allem wenn man die Dateien cached, dann könnte ich einfach einen regex auf den rest-string schicken.

Momentan prüfe ich, wie es aussieht, dass der Lexer keine vollständigen Strings und Kommentare erkkent und bei unbekannten Zeichen einfach ein Token UNKNOWN erstellt. Das ganze kommt dann an den Parser (bisher nicht vorhanden), der dann erst ganze Strings und Kommentare baut, wobei er UNKNOWN Tokens in Strings und Kommentaren erlaubt, sonst aber einen Fehler ausgibt.

Ich melde mich, wenn ich soweit fertig bin, dass ich die beiden Ergebnisse (bisher <> neu) vergleichen kann. Wenn jemand noch einen Vorschlag hat, der melde sich.

	Farbfinsternis	Di, Mai 13, 2008 20:39 Antworten mit Zitat
Es existieren doch diverse Möglichkeiten per BMax einen String zu parsen ... warum erfindest Du das Rad nochmal neu? Ich maße mir nicht an einen Lexer oder einen Parser schreiben zu können ... aber zumindest Kommentare bekomme ich wirksam mit Boardmitteln aus dem Source ... Code: [AUSKLAPPEN] [EINKLAPPEN] CodeLine = stream.ReadLine(); CodeLine.Trim() If Left(CodeLine, 2) = "/* Repeat CodeLine = stream.ReadLine() Until Left(CodeLine, 2) <> "*/" Or stream.Eof() End If if Left(CodeLine, 2) = "//" ' Überspringe diese Zeile End If Den Code komplett von unnötigen Zeilen befreien und dann durch den Lexer schicken. Mit dem PreCompiler können auch gleich alle Tabs und unnötigen Spaces entfernt werden um direkt einen String wie "myVar=1234" zu trennen. Das ein Compiler mit all seinen Eigenheiten komplex ist, ist mir bewusst. Was ich aber nicht verstehe ist: Warum sollte man einen Stream zeichenweise lesen wenn BMax es möglichmacht gleich eine ganze Zeile zu bekommen und diese bequem zu zerlegen.
Farbfinsternis.tv

Farbfinsternis

Di, Mai 13, 2008 20:39
Antworten mit Zitat

Es existieren doch diverse Möglichkeiten per BMax einen String zu parsen ... warum erfindest Du das Rad nochmal neu? Ich maße mir nicht an einen Lexer oder einen Parser schreiben zu können ... aber zumindest Kommentare bekomme ich wirksam mit Boardmitteln aus dem Source ...
Code: [AUSKLAPPEN]

CodeLine = stream.ReadLine();
CodeLine.Trim()

If Left(CodeLine, 2) = "/*
Repeat
CodeLine = stream.ReadLine()
Until Left(CodeLine, 2) <> "*/" Or stream.Eof()
End If

if Left(CodeLine, 2) = "//"
' Überspringe diese Zeile
End If

Den Code komplett von unnötigen Zeilen befreien und dann durch den Lexer schicken. Mit dem PreCompiler können auch gleich alle Tabs und unnötigen Spaces entfernt werden um direkt einen String wie "myVar=1234" zu trennen.

Das ein Compiler mit all seinen Eigenheiten komplex ist, ist mir bewusst. Was ich aber nicht verstehe ist: Warum sollte man einen Stream zeichenweise lesen wenn BMax es möglichmacht gleich eine ganze Zeile zu bekommen und diese bequem zu zerlegen.

Farbfinsternis.tv

	Vertex	Di, Mai 13, 2008 21:24 Antworten mit Zitat
Weil Lexer i. d. R. DEA sind. Eine Sprache wird meist in EBNF formuliert und da ist ein DEA eine Art Eins-zu-Eins-Umsetzung in Programmcode. Das Literale und Bezeichner schon vom Lexer "konvertiert" werden, ist gängige Praxis. Bei Kommentaren kann man sich natürlich streiten, ob ein Parser erst ein AST erzeugen muss, um den Kommentar zu auf Syntaxregeln zu prüfen. Praxistauglicher ist aber das schon im Lexer zu handhaben. Der Kommentar wird einfach übersprungen, oder bei Auftreten des EOF-Zeichens vor EndRem ein Fehler geworfen. Wichtig ist aber, das weiter der Code analysiert wird! Das immer nur der erste Fehler, wie bei Blitz, ausgeworfen wird, ist falsch (zumindest laut N. Wirth in "Grundlagen und Techniken des Compilerbaus") mfg olli
vertex.dreamfall.at \| GitHub

Vertex

Di, Mai 13, 2008 21:24
Antworten mit Zitat

Weil Lexer i. d. R. DEA sind. Eine Sprache wird meist in EBNF formuliert und da ist ein DEA eine Art Eins-zu-Eins-Umsetzung in Programmcode.

Das Literale und Bezeichner schon vom Lexer "konvertiert" werden, ist gängige Praxis. Bei Kommentaren kann man sich natürlich streiten, ob ein Parser erst ein AST erzeugen muss, um den Kommentar zu auf Syntaxregeln zu prüfen. Praxistauglicher ist aber das schon im Lexer zu handhaben. Der Kommentar wird einfach übersprungen, oder bei Auftreten des EOF-Zeichens vor EndRem ein Fehler geworfen.

Wichtig ist aber, das weiter der Code analysiert wird! Das immer nur der erste Fehler, wie bei Blitz, ausgeworfen wird, ist falsch (zumindest laut N. Wirth in "Grundlagen und Techniken des Compilerbaus")

mfg olli

vertex.dreamfall.at | GitHub

	Artemis	Mi, Mai 14, 2008 13:41 Antworten mit Zitat
Also, erstmal um jedem Verdacht vorzubeugen, ich versuche nicht einen Compiler zu schreiben, sondern nur einen Lexer samt Parser. Ich möchte eventuell ein Dokumentationstool machen, welches Module und andere BMax-Dateien dokumentieren kann. Auch andere Anwendungsmöglichkeiten kann ich mir vorstellen. @Farbfinsternis Das mit dem eine ganze Zeile holen, überlege ich mir mal. So einfach, wie es dein Codebeispiel aussehen lässt, ist es aber nicht. Eine Zeile kann ja auch so aussehen: Code: [AUSKLAPPEN] [EINKLAPPEN] Print "Ich gebe ein ' aus." Wenn ich einfach ab einem ' alles danach als Kommentar sehe würde das dabei zu Problemen führen. Da müsste ich dann immer nach ' und " suchen, und gucken welches zuerst ist usw. Natürlich würde das kein Problem machen, verkompliziert den eigentlich simplen Ansatz eines Lexers (Zeichen für Zeichen) aber. Auch das Entfernen von Spaces und/oder Kommentaren ist nicht mein Ziel, im Gegensatz, sie sollen/müssen drin bleiben. Wenn ich beispielsweise daraus ein Dokumentationstool machen möchte müssen sie drin bleiben, genauso wie bei einem Highlighter o.ä. @Vertex Ich habe mir das so vorgestellt, dass ich die EBNF nicht für die einzelnen Tokens mache, d.h. die Erkennung von $F0 als Hexadezimale Zahl ist hardgecoded. Den Parser möchte ich dann aber mit EBNF fütter beispielsweise Code: [AUSKLAPPEN] [EINKLAPPEN] Framework-Definition = 'Framework', Identifier, '.', Identifier bzw. als Token ausgedrückt. Code: [AUSKLAPPEN] [EINKLAPPEN] Framework-Definition = IDENTIFIER:'Framework' IDENTIFIER MEMBER_ACCESS IDENTIFIER Also ein AST für einen Kommentar is übertrieben, oder? Ich meine in einem Kommentar darf alles drinstehen, so wie in einem String. Wobei man bei einem String wieder auf so Dinge wie ~~, ~q usw. achten kann/muss. Zitat: Der Kommentar wird einfach übersprungen, oder bei Auftreten des EOF-Zeichens vor EndRem ein Fehler geworfen. Stimmt nicht. Ein Rem-Kommentar muss anscheinend nicht beendet werden. Folgendes Beispiel funktioniert ohne Probleme: Code: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict Print "test" Rem test EDIT: Ist zwar eher ne Schönheitsfrage, aber wie sollte man die Tokens nennen? Das was es ist, oder die Bedeutung, die es hat. Also DOLLAR oder STRING_TYPE für $? Vor allem bei # und ~, was ja verschiedene Bedeutungen haben kann ist das die Frage. # = FLOAT_TYPE, LABEL ~ = BITWISE_COMPLEMENT, BITWISE_XOR

Artemis

Mi, Mai 14, 2008 13:41
Antworten mit Zitat

Also, erstmal um jedem Verdacht vorzubeugen, ich versuche nicht einen Compiler zu schreiben, sondern nur einen Lexer samt Parser. Ich möchte eventuell ein Dokumentationstool machen, welches Module und andere BMax-Dateien dokumentieren kann. Auch andere Anwendungsmöglichkeiten kann ich mir vorstellen.

@Farbfinsternis
Das mit dem eine ganze Zeile holen, überlege ich mir mal.
So einfach, wie es dein Codebeispiel aussehen lässt, ist es aber nicht. Eine Zeile kann ja auch so aussehen:
Code: [AUSKLAPPEN]

Print "Ich gebe ein ' aus."

Wenn ich einfach ab einem ' alles danach als Kommentar sehe würde das dabei zu Problemen führen. Da müsste ich dann immer nach ' und " suchen, und gucken welches zuerst ist usw. Natürlich würde das kein Problem machen, verkompliziert den eigentlich simplen Ansatz eines Lexers (Zeichen für Zeichen) aber.
Auch das Entfernen von Spaces und/oder Kommentaren ist nicht mein Ziel, im Gegensatz, sie sollen/müssen drin bleiben. Wenn ich beispielsweise daraus ein Dokumentationstool machen möchte müssen sie drin bleiben, genauso wie bei einem Highlighter o.ä.

@Vertex
Ich habe mir das so vorgestellt, dass ich die EBNF nicht für die einzelnen Tokens mache, d.h. die Erkennung von $F0 als Hexadezimale Zahl ist hardgecoded.
Den Parser möchte ich dann aber mit EBNF fütter beispielsweise
Code: [AUSKLAPPEN]

Framework-Definition = 'Framework', Identifier, '.', Identifier

bzw. als Token ausgedrückt.
Code: [AUSKLAPPEN]

Framework-Definition = IDENTIFIER:'Framework' IDENTIFIER MEMBER_ACCESS IDENTIFIER

Also ein AST für einen Kommentar is übertrieben, oder? Ich meine in einem Kommentar darf alles drinstehen, so wie in einem String. Wobei man bei einem String wieder auf so Dinge wie ~~, ~q usw. achten kann/muss.

Zitat:

Der Kommentar wird einfach übersprungen, oder bei Auftreten des EOF-Zeichens vor EndRem ein Fehler geworfen.

Stimmt nicht. Ein Rem-Kommentar muss anscheinend nicht beendet werden.
Folgendes Beispiel funktioniert ohne Probleme:
Code: [AUSKLAPPEN]

SuperStrict
Print "test"
Rem

test

EDIT:
Ist zwar eher ne Schönheitsfrage, aber wie sollte man die Tokens nennen?
Das was es ist, oder die Bedeutung, die es hat. Also DOLLAR oder STRING_TYPE für $?

Vor allem bei # und ~, was ja verschiedene Bedeutungen haben kann ist das die Frage.
# = FLOAT_TYPE, LABEL
~ = BITWISE_COMPLEMENT, BITWISE_XOR

Übersicht

BlitzMax, BlitzMax NG

Allgemein

Nach Oben

BlitzBasic Portal

BlitzMax Lexer / Parser schreiben

Betreff: BlitzMax Lexer / Parser schreiben