30.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, wie zum Beispiel eine Quellcode- oder Konfigurationsdatei, in einzelne Bestandteile, sogenannte Tokens, zerlegt. Dabei werden 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 Integerwert (2), eine geschlossene Klammer und ein Semikolon zerlegt.

yacc, Bison

Bei der Syntax-Analyse hingegen werden die einzelnen Tokens 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, auf die dann die Funktionsparameter durch Kommas 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 legen nur die wichtigsten Grundlagen für das Arbeiten mit flex und bison. Als hervorragende weiterführende Literatur empfiehlt sich [Herold03B]. Dieses Buch behandelt zwar nicht bison, aber dafür yacc in aller Ausführlichkeit.

30.10.1 flex grundlegend anwenden

Ein flex-Skript gliedert sich in drei Teile, die jeweils durch eine Zeile, in der nur die Zeichen %% stehen, abgegrenzt werden. Im oberen Teil wird C-Code definiert, der Variablen, Funktionsprototypen und Ähnliches enthält, die später zur Verfügung stehen sollen. 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, so 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 wie folgt aussehen:

Listing 30.57 calc.l

%{
#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);
   }
}

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 Datei 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 escapet haben, damit es nicht als »mindestens ein Vorkommen eines Zeichens« im regulären Ausdruck interpretiert wird. Falls Sie das Kapitel 8 zu regulären Ausdrücken nur überflogen oder bereits vergessen haben, sollten 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 dafür 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 den entsprechenden Quellcode für das Parsen der Texteingabe generieren. Dazu ruft man flex mit der jeweiligen Quelldatei auf – in unserem Fall heißt sie calc.l.

Listing 30.58 C-Quellcode erstellen

$ flex calc.l

Die nun erstellte Datei nennt sich – sofern man das Programm nicht explizit zu einer anderen Benennung anweist – lex.yy.c, ist in unserem Fall 36 KB groß und besteht aus 1550 Zeilen Quellcode. Es ist nicht sonderlich wichtig zu wissen, was flex dort im Detail generiert, wichtig ist nur, dass es den Code für Sie generiert, ohne dass Sie es selbst tun müssen, und dass es funktioniert. In diesem Fall muss dies tatsächlich nicht als schlampige Programmierung gelten. Bei großen Projekten generiert flex nämlich durchaus mal einige Zehntausend Zeilen an Quellcode, die sich bei jeder Übersetzung verändern – viel Spaß bei der Fehlersuche.

Listing 30.59 lex.yy.c

$ du -h lex.yy.c
36.0K   lex.yy.c
$ wc -l lex.yy.c
    1550 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 geschieht dies mit -lfl, unter BSD mit -ll:

Listing 30.60 Übersetzen und Linken

$ gcc -o calc lex.yy.c -lfl
$ ./calc
100
+
         -> 100
3
-
         -> 97
96
-
         -> 1
99
+
         -> 100
^D

30.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.

Ein bison-Programm ist ähnlich aufgebaut wie ein flex-Programm. Die von flex generierten Tokens werden im Mittelteil über das Keyword %token eingebunden:

Listing 30.61 %token

%token TOK_ADD
%token TOK_SUM
%token TOK_NUM

Im unteren Programmteil werden die syntaktischen Möglichkeiten definiert. Zunächst kümmert man sich darum, dass mehrere Kommandos hintereinander stehen können. Anschließend wird definiert, welche möglichen Syntaxkombinationen es gibt. Bei uns heißen die Kombinationen add und sub.

Listing 30.62 commands

commands: /**/ | commands command;

command:  add | sub;

Nun wird jedes einzelne Kommando genau definiert. Dies beinhaltet die Aneinanderreihung von Tokens, die diesem Kommando entsprechen, und die entsprechend auszuführenden Aktionen.

Listing 30.63 add und sub

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);
   };

Mit diesem Quellcode wird definiert, dass wir die Token-Reihenfolgen Zahl + Zahl und Zahl – Zahl abdecken.

Wie Sie vielleicht 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 lässt:

Listing 30.64 An vtmp1 und vtmp2 kommen

%%
[0-9]+   { vtmp1=vtmp2;
            vtmp2=atoi(yytext);
            return TOK_NUM;
         }

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 Datei calc.l und anschließend mit bison die calc.y in C-Code umgewandelt werden. Daraufhin kann mit dem gcc alles zusammengelinkt werden.

Listing 30.65 Code erzeugen und compilieren

$ flex calc.l
$ bison calc.y --output-file=calc.tab.c
$ gcc -o lex.yy.c calc.tab.c -ll

Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.