21.10 lex/flex und yacc/bison 
Für den anspruchsvollen angehenden Profi-Programmierer seien in diesem Kapitel auch noch einige Sätze zu den Tools flex und yacc gesagt. lex (unter Linux in der Regel flex) ist ein Tool zur lexikalischen Analyse, yacc und das ähnliche Tool bison sind zur syntaktischen Analyse gedacht.
flex, lex
Bei der lexikalischen Analyse wird eine Eingabe, also etwa eine Quellcode- oder Konfigurationsdatei, in einzelne Bestandteile, sogenannte Tokens zerlegt. Dabei werden einzelne Muster erkannt und als Token X identifiziert. Diese Muster werden bei flex und lex in Form von regulären Ausdrücken angegeben. Der Input-String sqrt(2); beispielsweise würde in einen Funktionsnamen (sqrt), eine geöffnete Klammer, einen Integer-Wert (2), eine geschlossene Klammer und ein Semikolon zerlegt werden.
yacc, Bison
Bei der Syntaxanalyse hingegen werden die einzelnen Token in ihrer Anwendungsreihenfolge (Syntax-Regel) einer Prüfung unterzogen. Die Syntax kann beispielsweise regeln, dass hinter einem Funktionsnamen beim Aufruf eine geöffnete Klammer stehen soll, dass dann die Funktionsparameter durch Kommata separiert folgen sollen usw.
Wir können leider nicht bis ins letzte Detail auf die Anwendung beider Tools eingehen – dazu wäre ein eigenes Buch notwendig --, sondern nur die wichtigsten Grundlagen für das Arbeiten mit flex und bison legen. Als hervorragende weiterführende Literatur empfiehlt sich [Herold03B]. Dieses Buch behandelt zwar nicht bison, aber dafür yacc.
21.10.1 flex grundlegend anwenden 
Ein flex-Skript teilt sich in drei Teile auf, die jeweils durch eine Zeile, in der nur die Zeichen %% stehen, unterteilt werden. Im oberen Teil wird C-Code definiert, der Variablen, Funktionsprototypen und Ähnliches enthält, die später zur Verfügung stehen soll, im mittleren Teil werden die Muster für Tokens definiert, und im unteren Teil werden C-Funktionen implementiert. Die Verwendung des oberen und unteren Skriptteils ist optional.
Soll zum Beispiel mithilfe von flex ein simpler Taschenrechner realisiert werden, der Addition und Subtraktion durchführen kann, würde man ein Token für die Addition, eines für die Subtraktion und eines für die Zahlen benötigen. In flex umgesetzt, könnte dies so aussehen:
%{
#include <stdio.h>
#define TOK_ADD 0x01
#define TOK_SUB 0x02
#define TOK_NUM 0x03
int tmpv=0;
int token;
%}
%%
\+ { return TOK_ADD; }
- { return TOK_SUB; }
[0-9]+ { tmpv=atoi(yytext); }
[\n\t ]+ {}
%%
int main ()
{
int value=0;
while(token=yylex()) {
switch(token) {
case TOK_ADD:
value+=tmpv;
break;
case TOK_SUB:
value-=tmpv;
break;
}
tmpv=0;
printf("\t -> %i\n", value);
}
}Listing 21.57 calc.l
Zunächst haben wir, eingebettet in %{ und %}, den C-Code für den oberen Teil des flex-Programms festgelegt. Dort binden wir für die spätere Nutzung die stdio.h ein und vergeben mit der Präprozessor-Anweisung define drei Token-Werte.
Im Muster-Teil des Programms wird festgelegt, welche Aktionen durchgeführt werden sollen, wenn ein bestimmtes Muster auftritt. Beachten Sie, dass wir das Plus-Zeichen escapt haben, damit es nicht als »mindestens ein Vorkommen eines Zeichens« im regulären Ausdruck interpretiert wird. Falls Sie das Kapitel zu regulären Ausdrücken nur überflogen oder bereits vergessen haben, sollen Sie es vor der Nutzung von flex nochmals durchlesen.
Die jeweilige Anweisung, die durchzuführen ist, wird durch Leerzeichen vom Muster getrennt und im Optimalfall in geschweifte Klammern eingebettet. Verwendet man nur eine einzelne Anweisung, kann man diese geschweiften Klammern jedoch auch weglassen.
Um keine Probleme mit der Eingabe einer neuen Zeile zu bekommen, fangen wir durch die Regel »\n { }« das Newline-Zeichen ab und führen einfach gar keine Anweisung für es aus.
Im Schlussteil holen wir uns über die Funktion yylex() das jeweilige Token und verarbeiten es in einer Schleife.
Übersetzen
Um aus diesem Code nun ein ausführbares Programm zu generieren, muss flex (bzw. lex) zunächst erst einmal den entsprechenden Quellcode für das Parsen der Text-Eingabe generieren. Dazu ruft man flex mit der jeweiligen Quelldatei auf. In unserem Fall heißt sie calc.l.
$ flex calc.l
Listing 21.58 C-Quellcode erstellen
Die nun erstellte Datei nennt sich standardmäßig lex.yy.c, ist in unserem Fall 35,5 KB groß und besteht aus 1550 Zeilen Quellcode. Es ist nicht sonderlich wichtig zu wissen, was flex dort im Detail generiert, wichtig ist, dass es den Code für einen generiert, ohne dass man es selbst tun muss, und dass es funkioniert. In diesem Fall muss dies tatsächlich nicht als schlampige Programmierung angesehen werden. Bei großen Projekten generiert flex nämlich durchaus mal einige zehntausend Zeilen an Quellcode, die sich bei jeder Übersetzung verändern – viel Spaß beim Fehlersuchen.
$ du -h lex.yy.c
36.0K lex.yy.c
$ wc -l lex.yy.c
1550 lex.yy.cListing 21.59 lex.yy.c
Nun muss der Quellcode mit dem C-Compiler übersetzt werden, und anschließend können wir das fertige Programm testen. Dazu muss die Flex-Library eingelinkt werden. Unter Linux ist das -lfl, unter BSD -ll:
$ gcc -o calc lex.yy.c -lfl
$ ./calc
100
+
-> 100
3
-
-> 97
96
-
-> 1
99
+
-> 100
^D
$Listing 21.60 Übersetzen und linken
21.10.2 bison/yacc grundlegend anwenden
Kommen wir nach diesem kleinen Einblick in flex/lex zur syntaktischen Analyse mittels bison. Dabei wird der Quellcode des Beispiels, das wir an dieser Stelle einbringen werden, auch für yacc anwendbar sein.
Der Aufbau eines bison-Programms ist ähnlich, wie es bei flex der Fall ist. Die von flex generierten Tokens werden dabei im Mittelteil über das Keyword %token eingebunden:
%token TOK_ADD %token TOK_SUM %token TOK_NUM
Listing 21.61 %token
Im unteren Programmteil werden die syntaktischen Möglichkeiten definiert. Zunächst kümmert man sich darum, dass mehrere Kommandos hintereinander stehen können, und definiert anschließend, welche möglichen Syntax-Kombinationen es gibt. Bei uns heißen sie »add« und »sub«.
commands: /**/ | commands command; command: add | sub;
Listing 21.62 commands
Nun wird jedes einzelne Kommando genau definiert. Dies beinhaltet die Aneinanderreihung von Tokens, die diesem Kommando entspricht, und die entsprechend auszuführenden Aktionen.
add:
TOK_NUM TOK_ADD TOK_NUM
{
printf("\t->%i\n", vtmp1+vtmp2);
};
sub:
TOK_NUM TOK_SUB TOK_NUM
{
printf("\t->%i\n", vtmp1-vtmp2);
};Listing 21.63 add und sub
Damit wird definiert, dass wir die Token-Reihenfolgen »Zahl + Zahl« und »Zahl – Zahl« abdecken.
Wie Sie eventuell bemerkt haben, verwenden wir die Variablen vtmp1 und vtmp2. In diesen müssen jeweils die letzten zwei vom Benutzer eingegebenen Zahlenwerte hinterlegt sein, was sich beispielsweise folgendermaßen lösen ließe:
%%
[0-9]+ { vtmp1=vtmp2;
vtmp2=atoi(yytext);
return TOK_NUM;
}Listing 21.64 An vtmp1 und vtmp2 kommen
Des Weiteren muss nun in der Main-Funktion im flex-Code der Bison-Mainloop aufgerufen werden, was durch einen einfachen Aufruf von yyparse(); geschieht.
Übersetzen
Nun muss zunächst mit lex die angepasste calc.l und anschließend mit bison die calc.y in C-Code umgewandelt werden. Daraufhin kann mit dem gcc alles zusammengelinkt werden.
$ flex calc.l $ bison calc.y --output-file=calc.tab.c $ gcc -o lex.yy.c calc.tab.c -ll
Listing 21.65 Code erzeugen und compilieren
