Lexikalische Analyse mit Lex

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

Lexer für einen kleinen Compiler
In der Übung Übersetzerbau geht man nun noch einen Schritt weiter. Wir stellen uns vor, dass wir einen kleinen Compiler bauen wollen. Einerseits haben wir darin die vorher besprochene Kommentarbehandlung. Andererseits natürlich diverse Schlüsselwörter, a la `if`, `while` und so weiter. Neben diversen unären und binären Operationen (`!` für not, `!=` für ungleich, und so weiter) gibt's dann noch Variablen und Konstanten. Der folgende `scanner.lex` löst die dritte Übersetzerbau-Aufgabe der TU-Wien aus dem Wintersemenster 2004 zu 100 %.

Lexer für einen kleinen Compiler

In der Übung Übersetzerbau geht man nun noch einen Schritt weiter. Wir stellen uns vor, dass wir einen kleinen Compiler bauen wollen. Einerseits haben wir darin die vorher besprochene Kommentarbehandlung.

Andererseits natürlich diverse Schlüsselwörter, a la if, while und so weiter. Neben diversen unären und binären Operationen (! für not, != für ungleich, und so weiter) gibt's dann noch Variablen und Konstanten.

Der folgende scanner.lex löst die dritte Übersetzerbau-Aufgabe der TU-Wien aus dem Wintersemenster 2004 zu 100 %.

scanner.lex
`1 /* scanner.lex` `2 (c) 2004 René C. Kiesler` `3` `4 please visit http://www.kiesler.at/` `5 for further informations & support.` `6 /` `7` `8` `9 #include <math.h>` `10` `11 int num_lines = 1;` `12 int last_open_sighting = -1;` `13` `14` `15 KEYWORD func\|where\|end\|if\|then\|else\|not\|hd\|tl\|islist\|and` `16 OPERATOR \\;\|\,\|\=\|\-\|\+\|\\|\<\|\(\|\)` `17 LEXEM {KEYWORD}\|{OPERATOR}` `18` `19 HEXZAHL 0x[0-9a-fA-F]+` `20 DECZAHL [0-9]+` `21` `22 IDENTIFIER [a-zA-Z][0-9a-zA-Z]` `23` `24 WHITESPACE [ \t]+` `25 COMMENT_START \(\` `26 COMMENT_END \\)` `27` `28 NEWLINE \n` `29` `30 ANYCHAR .` `31` `32` `33 %x COMMENT` `34 %%` `35` `36` `37 {COMMENT_START} { BEGIN(COMMENT);` `38 last_open_sighting = num_lines;` `39 }` `40 <COMMENT>{COMMENT_END} BEGIN(INITIAL);` `41 <COMMENT><<EOF>> { fprintf(stderr,` `42 "unmatched opening comment in line %d, %s\n",` `43 last_open_sighting, "eof reached.");` `44 exit(1);` `45 }` `46 <COMMENT>\n num_lines++;` `47 <COMMENT>. / alles im Kommentar ignorieren /` `48` `49 {WHITESPACE} / Whitespace, wird ignoriert /` `50 {NEWLINE} num_lines++;` `51` `52 {LEXEM} printf("%s\n", yytext);` `53` `54 {DECZAHL} printf("num 0x%x\n", atoi(yytext));` `55 {HEXZAHL} printf("num 0x%x\n", strtol(yytext, 0, 16));` `56` `57 {IDENTIFIER} printf("ident %s\n", yytext);` `58` `59 {ANYCHAR} { fprintf(stderr,` `60 "unknown character '%s' in line %d.\n",` `61 yytext, num_lines);` `62 exit(1);` `63 }` `64` `65 %%` `66` `67` `68 main(int argc, char *argv) {` `69 yyin=argc>1 ? fopen(argv[1], "r") : stdin;` `70 yylex();` `71 exit(0);` `72 }` `73`

scanner.lex

1 /*                      scanner.lex
2                         (c) 2004 René C. Kiesler
3
4                         please visit http://www.kiesler.at/
5                         for further informations & support.
6 */
7
8
9                         #include <math.h>
10
11                         int num_lines = 1;
12                         int last_open_sighting = -1;
13
14
15 KEYWORD                 func|where|end|if|then|else|not|hd|tl|islist|and
16 OPERATOR                \\;|\,|\=|\-|\+|\*|\<|\(|\)
17 LEXEM                   {KEYWORD}|{OPERATOR}
18
19 HEXZAHL                 0x[0-9a-fA-F]+
20 DECZAHL                 [0-9]+
21
22 IDENTIFIER              [a-zA-Z][0-9a-zA-Z]*
23
24 WHITESPACE              [ \t]+
25 COMMENT_START           \(\*
26 COMMENT_END             \*\)
27
28 NEWLINE                 \n
29
30 ANYCHAR                 .
31
32
33 %x COMMENT
34 %%
35
36
37 {COMMENT_START}         {       BEGIN(COMMENT);
38                                 last_open_sighting = num_lines;
39                         }
40 <COMMENT>{COMMENT_END}  BEGIN(INITIAL);
41 <COMMENT><<EOF>>        {       fprintf(stderr,
42                                         "unmatched opening comment in line %d, %s\n",
43                                         last_open_sighting, "eof reached.");
44                                 exit(1);
45                         }
46 <COMMENT>\n             num_lines++;
47 <COMMENT>.              /* alles im Kommentar ignorieren */
48
49 {WHITESPACE}            /* Whitespace, wird ignoriert */
50 {NEWLINE}               num_lines++;
51
52 {LEXEM}                 printf("%s\n", yytext);
53
54 {DECZAHL}               printf("num 0x%x\n", atoi(yytext));
55 {HEXZAHL}               printf("num 0x%x\n", strtol(yytext, 0, 16));
56
57 {IDENTIFIER}            printf("ident %s\n", yytext);
58
59 {ANYCHAR}               {       fprintf(stderr,
60                                         "unknown character '%s' in line %d.\n",
61                                         yytext, num_lines);
62                                 exit(1);
63                         }
64
65 %%
66
67
68                         main(int argc, char **argv) {
69                                 yyin=argc>1 ? fopen(argv[1], "r") : stdin;
70                                 yylex();
71                                 exit(0);
72                         }
73

makefile zu scanner.lex
`1 #` `2 # makefile for scanner` `3 # (c) 2004 René C. Kiesler` `4 #` `5 # please visit http://www.kiesler.at/` `6 # for further informations & support` `7 #` `8` `9` `10 scanner: scanner.c` `11 gcc -o scanner scanner.c -lfl` `12` `13 scanner.c: scanner.lex` `14 flex -oscanner.c scanner.lex` `15` `16 test:` `17 /usr/ftp/pub/ublu/test/scanner/test 2>&1` `18` `19 clean:` `20 rm -f scanner scanner.c`

makefile zu scanner.lex

1 #
2 #       makefile for scanner
3 #       (c) 2004 René C. Kiesler
4 #
5 #       please visit http://www.kiesler.at/
6 #       for further informations & support
7 #
8
9
10 scanner: scanner.c
11         gcc -o scanner scanner.c -lfl
12
13 scanner.c: scanner.lex
14         flex -oscanner.c scanner.lex
15
16 test:
17         /usr/ftp/pub/ublu/test/scanner/test 2>&1
18
19 clean:
20         rm -f scanner scanner.c

Funktionsweise im Schnelldurchlauf
scanner.lex `11-12` Für einfachere Fehlersuche im Quelltext merken wir uns sowohl die aktuelle Zeilennummer, als auch das Vorkommniss der letzten Kommentaröffnung. `15-17` Alles, was irgendwie nach Schlüsselwort aussieht, wird hier zusammengefasst. Möchte man das ganze mal später Parsen, kommt man mit so einem Breitbandantibiotikum allerdings nicht mehr weit. `19-20` Unser Compiler soll sowohl Dezimalzahlen, als auch Hexadezimalzahlen unterstützen. `22` Funktionsnamen, Variablennamen und Parameternamen -- kurz: Identifier -- müssen bei uns mit einem Buchstaben anfangen und bestehen weiters nur aus Buchstaben und Zahlen. `38` Hier merken wir uns, wann zuletzt ein Kommentar eröffnet wurde... `41` ...und geben dieses Wissen im Fehlerfall an den Benutzer weiter. `52` wird ein Lexem erkannt, wird dieses Kommentarlos ausgegeben. `54-55` Zahlen werden mit der C-Bibliotheksfunktion `atoi()` für Dezimalzahlen bzw. `strtol()` für Hexzahlen (danke, Soulmerge! ;-)) umgewandelt und dann einheitlich als Hexzahl mit Kleinbuchstaben ausgegeebn. `59` Sollte eine unerwartete Eingabe festgestellt werden, wird das dem Benutzer inklusive Zeilennummer ausgegeben. Das Programm wird dann mit Fehlercode 1 beendet. makefile zu scanner.lex `16-17` Vom Computerspracheninstitut wird eine sehr mächtige Testsuite zur Verfügung gestellt. Das 2>&1 besagt, dass die Ausgaben von Stderr zu Stdout hinzugefügt werden sollen. Ein `make test \| less` wird dadurch viel besser lesbar. `19-20` Macht man vor dem editieren ein `make clean`, wird die Ausgabe von `ls` weit übersichtlicher. Auch sinnvoll, wenn man sein Programm archivieren möchte -- wozu die Compilate mitarchivieren?

Funktionsweise im Schnelldurchlauf

scanner.lex

11-12 Für einfachere Fehlersuche im Quelltext merken wir uns sowohl die aktuelle Zeilennummer, als auch das Vorkommniss der letzten Kommentaröffnung.

15-17 Alles, was irgendwie nach Schlüsselwort aussieht, wird hier zusammengefasst. Möchte man das ganze mal später Parsen, kommt man mit so einem Breitbandantibiotikum allerdings nicht mehr weit.

19-20 Unser Compiler soll sowohl Dezimalzahlen, als auch Hexadezimalzahlen unterstützen.

22 Funktionsnamen, Variablennamen und Parameternamen -- kurz: Identifier -- müssen bei uns mit einem Buchstaben anfangen und bestehen weiters nur aus Buchstaben und Zahlen.

38 Hier merken wir uns, wann zuletzt ein Kommentar eröffnet wurde...

41 ...und geben dieses Wissen im Fehlerfall an den Benutzer weiter.

52 wird ein Lexem erkannt, wird dieses Kommentarlos ausgegeben.

54-55 Zahlen werden mit der C-Bibliotheksfunktion atoi() für Dezimalzahlen bzw.
strtol() für Hexzahlen (danke, Soulmerge! ;-)) umgewandelt und dann einheitlich als Hexzahl mit Kleinbuchstaben ausgegeebn.

59 Sollte eine unerwartete Eingabe festgestellt werden, wird das dem Benutzer inklusive Zeilennummer ausgegeben. Das Programm wird dann mit Fehlercode 1 beendet.

makefile zu scanner.lex

16-17 Vom Computerspracheninstitut wird eine sehr mächtige Testsuite zur Verfügung gestellt. Das 2>&1 besagt, dass die Ausgaben von Stderr zu Stdout hinzugefügt werden sollen. Ein make test | less wird dadurch viel besser lesbar.

19-20 Macht man vor dem editieren ein make clean, wird die Ausgabe von ls weit übersichtlicher. Auch sinnvoll, wenn man sein Programm archivieren möchte -- wozu die Compilate mitarchivieren?