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