Lexikalische Analyse mit Lex

Choose

Lexikalische Analyse mit Lex

updated by rck, 2004-08-27

In Unix finden sich viele Spezialisten. cat gibt dateien aus, cut zerschneidet sie spaltenweise, paste fügt sie wieder zusammen... und lex macht aus einer Text-Datei Tokens.

1 | 2 | 3 | 4 | 5 | 6

Zustände -- oder: wie werde ich Kommentare los?
Nehmen wir mal an, wir möchten mit unserem Lexer Kommentare in Quelldateien erkennen und verwerfen. Kommentare sind, auch wenn sie die Lesbarkeit von Programmen erhöhen können, schließlich für das Endergebnis irrelevant. Eine Möglichkeit wäre, einen regulären Ausdruck auf die Jagd zu schicken. Wenn unsere Kommentare von der Form `(* )` sind, könnten wir zB mit `(\[^\]\)` danach suchen. Kennen Sie sich noch aus? Wir sehen: Das wird sehr schnell sehr unübersichtlich. Und wir haben noch nichtmal eine Fehlerbehandlung für den Fall, dass ein Kommentar nicht abgeschlossen wurde. Das Carret (^) steht übrigens für nicht, matcht in diesem Fall also alles, was kein ist. Die \ vor den * benötigen wir, weil wir tatsächlich das Zeichen * matchen wollen.

Zustände -- oder: wie werde ich Kommentare los?

Nehmen wir mal an, wir möchten mit unserem Lexer Kommentare in Quelldateien erkennen und verwerfen. Kommentare sind, auch wenn sie die Lesbarkeit von Programmen erhöhen können, schließlich für das Endergebnis irrelevant.

Eine Möglichkeit wäre, einen regulären Ausdruck auf die Jagd zu schicken. Wenn unsere Kommentare von der Form (* *) sind, könnten wir zB mit (\*[^\*]*\*) danach suchen. Kennen Sie sich noch aus?

Wir sehen: Das wird sehr schnell sehr unübersichtlich. Und wir haben noch nichtmal eine Fehlerbehandlung für den Fall, dass ein Kommentar nicht abgeschlossen wurde.

Das Carret (^) steht übrigens für nicht, matcht in diesem Fall also alles, was kein * ist. Die \ vor den * benötigen wir, weil wir tatsächlich das Zeichen * matchen wollen.

Eine kleine C-Routine
Sie könnten jetzt in Versuchung zu kommen, die Arbeitsweise des Lexers durch eine C Funktion zu... ergänzen. Widerstehen Sie! Der Grund ist schnell erklärt. Einerseits gibt es in Flex viel 'schönere' Mechanismen dafür, die auch besser wartbar sind. Andererseits ist flex auf Geschwindigkeit optimiert und mit ziemlicher Sicherheit schneller als ihre Implementation (auch wenn das bei heutigen CPU-Geschwindigkeiten nur mehr zweitrangig ist)

Eine kleine C-Routine

Sie könnten jetzt in Versuchung zu kommen, die Arbeitsweise des Lexers durch eine C Funktion zu... ergänzen. Widerstehen Sie!

Der Grund ist schnell erklärt. Einerseits gibt es in Flex viel 'schönere' Mechanismen dafür, die auch besser wartbar sind. Andererseits ist flex auf Geschwindigkeit optimiert und mit ziemlicher Sicherheit schneller als ihre Implementation (auch wenn das bei heutigen CPU-Geschwindigkeiten nur mehr zweitrangig ist)

lexcom.lex
`1 /* lexcom: removing pascal-style comments from a file` `2` `3 see http://www.kiesler.at/ for further details` `4 /` `5` `6` `7 COMMENT_START \(\` `8 COMMENT_END \\)` `9 ANYCHAR .` `10` `11` `12 %x COMMENT` `13` `14 %%` `15` `16 {COMMENT_START} BEGIN(COMMENT);` `17 <COMMENT>{COMMENT_END} BEGIN(INITIAL);` `18 <COMMENT><<EOF>> {` `19 fprintf(stderr, "unmatched comment");` `20 exit(1);` `21 }` `22 <COMMENT>{ANYCHAR} / /` `23` `24` `25 %%` `26` `27 main(int argc, char *argv) {` `28 yyin=argc>1 ? fopen(argv[1], "r"):stdin;` `29 yylex();` `30 exit(0);` `31 }`

lexcom.lex

1 /*                      lexcom: removing pascal-style comments from a file
2
3                         see http://www.kiesler.at/ for further details
4 */
5
6
7 COMMENT_START           $\*
8 COMMENT_END             \*$
9 ANYCHAR                 .
10
11
12 %x COMMENT
13
14 %%
15
16 {COMMENT_START}         BEGIN(COMMENT);
17 <COMMENT>{COMMENT_END}  BEGIN(INITIAL);
18 <COMMENT><<EOF>>        {
19                                 fprintf(stderr, "unmatched comment");
20                                 exit(1);
21                         }
22 <COMMENT>{ANYCHAR}      /* */
23
24
25 %%
26
27                         main(int argc, char **argv) {
28                                 yyin=argc>1 ? fopen(argv[1], "r"):stdin;
29                                 yylex();
30                                 exit(0);
31                         }

makefile zu lexcom.lex
`1 lexcom: lexcom.lex` `2 flex -olexcom.c lexcom.lex` `3 gcc -o lexcom lexcom.c -lfl`

Beispiele
$ lexcom text Die Welt ist eine Kugel! $ $ echo 'this is (* bla *) some text' \| ./lexcom this is some text $

Beispiele

$ lexcom text Die Welt ist eine Kugel! $

$ echo 'this is (* bla *) some text' | ./lexcom this is some text $

Funktionsweise im Schnelldurchlauf
lexcom.lex `12` so unscheinbar und doch die wichtigste Stelle im Lex-Programm: Die Zustands-Variable. Stellen Sie sich als ein flag vor, dass festhält, ob wir innerhalb des Zustandes sind, oder nicht `16` Wenn wir auf den Kommentar-Anfang treffen, versetzen wir unser Programm in den Zustand `COMMENT` `17` Beim Kommentar-Ende in den Zustand `INITIAL`, das ist der Grundzustand, den man nicht zu definieren braucht. `18` Treffen wir innerhalb des Zustands `COMMENT` auf ein EOF (End of File -- keine weiteren Eingabedateien mehr), ist der Kommentar wohl unvollständig. Wir sehen auch: Möchte man, dass eine Regel nur innerhalb eines gewissen Zustands matcht, schreibt man den entsprechenden Zustand einfach in Spitzer Klammer vor die Regel. Ganz einfach! makefile Das Makefile kennen wir schon vom vorigen Beispiel

Funktionsweise im Schnelldurchlauf

lexcom.lex

12 so unscheinbar und doch die wichtigste Stelle im Lex-Programm: Die Zustands-Variable. Stellen Sie sich als ein flag vor, dass festhält, ob wir innerhalb des Zustandes sind, oder nicht

16 Wenn wir auf den Kommentar-Anfang treffen, versetzen wir unser Programm in den Zustand COMMENT

17 Beim Kommentar-Ende in den Zustand INITIAL, das ist der Grundzustand, den man nicht zu definieren braucht.

18 Treffen wir innerhalb des Zustands COMMENT auf ein EOF (End of File -- keine weiteren Eingabedateien mehr), ist der Kommentar wohl unvollständig.

Wir sehen auch: Möchte man, dass eine Regel nur innerhalb eines gewissen Zustands matcht, schreibt man den entsprechenden Zustand einfach in Spitzer Klammer vor die Regel. Ganz einfach!

makefile

Das Makefile kennen wir schon vom vorigen Beispiel

1 | 2 | 3 | 4 | 5 | 6

Geschichtlicher Hintergrund
Reguläre Ausdrücke
Word Count
Zustände -- oder: wie werde ich Kommentare los?
Lexer für einen kleinen Compiler
Fazit