Lex und Yacc

Lex

Lex (Flex) ist ein Tool zur Generierung von Scannern, die lexikalische Muster in Texten identifizieren können. In einem ersten Schritt werden Zeichenketten (Strings) eines Source-Codes in Token konvertiert. Durch die Verwendung von sog. regulären Ausdrücken können in Lex-Files String-Muster (Pattern) definiert werden, nach denen Lex den Source-Code scannen kann. Zu jedem Muster kann eine Aktion definiert werden. Typischerweise ist dies die Rückgabe eines Tokens, der den erkannten String repräsentiert und im folgenden durch den Yacc-Parser genutzt werden kann. Lex übersetzt dabei die regulären Ausdrücke in endliche Zustandsautomaten, die sich leicht in ein C-Programm abbilden lassen. Endliche Zustandsautomaten (FSA) kennen dabei nur Zustände (states) und Übergänge zwischen den Zuständen (Transitionen). Aus diesem Grund ist es nicht möglich, verschachtelte Strukturen, die z.B. durch komplexere Klammerausdrücke (…) entstehen, abzubilden. Diese würden in Programmen durch eine Stack-Operation abgearbeitet. Lex hingegen kennt keinen Stack. Diese Funktionalität bleibt Yacc vorbehalten, der den FSA um einen Stack erweitert und dadurch auch Klammerausdrücke verarbeiten kann. Ein Lex-File ist in drei Sektionen unterteilt. Diese werden mit (%%) voneinander getrennt.

Sektionen

Definitionen

%%

Regeln (Token-Definitionen und Aktionen)

%%

C-Subroutinen

Jedes Muster muß im Lex-File in der ersten Spalte beginnen. Wird eine Zeile statt dessen eingerückt, so wird diese Zeile Wort für Wort in das C-File kopiert und nicht als Muster zur Umwandlung des Source-Codes genutzt. Dies wird z.B. genutzt, um C-Kommentare im Lex-File zu plazieren. Der Definitionsteil von Lex besteht z.B. aus einer C-basierten Liste von (#include)-Dateien. U.a. muß hier das File aufgeführt sein, in das Yacc die Token ablegen soll. In dem vorliegenden Beispiel ist das (easypars.hpp). Diese Header-Datei ist im Verzeichnispfad noch nicht vorhanden, sondern wird durch Yacc erzeugt. Dieser C-Code wird Wort für Wort in die Kopfzeilen des zu generierenden C-Files kopiert und muß geklammert %{…%} werden. Des weiteren können in dieser Sektion einfache reguläre Ausdrücke enthalten sein. z.B (DIGITS [0-9]). Diese regulären Ausdrücke werden dann bei der Rückgabe gemäß den vorgegebenen Regeln ersetzt. Der zweite Sektionsteil besteht aus regulären Ausdrücken (Mustern) für die Token, die erkannt werden sollen. Passend dazu lassen sich Aktionen definieren, die bei Erkennung eines Musters ausgeführt werden. Die Aktionen stehen dabei in geschweiften Klammern. Es können hier ein oder mehrere C-Ausdrücke verwendet werden. Im Lex-File des nachfolgenden Beispiels werden u.a. Ausdrücke wie (function) oder (while) in ein Return-Objekt umgewandelt. Dieses Objekt besteht jeweils aus einem Token [FUNCTION] bzw. [WHILE]. Diese Token finden sich im erstellten Header-File (in diesem Beispiel ist das [easypars.hpp]) innerhalb eines (enum)-Ausdrucks wieder. Den Token ist dabei stets ein Zahlenwert zugeordnet, der größer als 255 ist, da der ASCII-Zeichenvorrat nur 255 dezimale Werte kennt. Somit ergibt sich eine eindeutige Zuordnung des Tokens zu einem Dezimalwert, der keinem ASCII-Zeichen entspricht. Dies ist notwendig, da Token, die keiner Regel entsprechen, Zeichen für Zeichen zurückgegeben werden. Da jedes Zeichen eine ASCII-Repräsentation besitzt, muß dieser Wertebereich freigehalten werden. Vorteil ist jedoch, dass man nicht jede Zeichenfolge explizit deklarieren muß, wenn deren Funktion eindeutig ist. Dies ist z.B. bei mathematischen Operatoren (wie +,-,* usw.) der Fall. Der Scanner plaziert jeden Eingangscode im String (yytext). (yytext) ist dabei der Pointer auf den erkannten String. Der Abschnitt mit C-Subroutinen kann z.B. eine Definition eines (main) beinhalten, in dem die Standard-Funktion [yylex()] aufgerufen wird. [yylex()] ist die Einstiegsfunktion um Lex-Operationen aufzurufen. Die Subroutinen werden ebenfalls Wort für Wort in das entstehende C-File kopiert und erzeugen so z.B. eine (main)-Funktion im zu erstellenden C-File. Ansonsten läßt sich (main) auch separat erzeugen und per Makefile während der Erstellung der Compiler-/Interpreter-Datei hinzufügen (siehe Abbildung 3).

Beispiel für ein (main) in einer Subroutine:

%%

int main (void){

yylex();

return (0);

}

Yacc

Yacc (Bison) ist ein Tool zur Generierung von Parsern, d.h. zur Erkennung von grammatikalischen Strukturen in Programmen. Wie bereits erläutert bedeutet parsen, implizit einen Syntaxbaum aufzubauen. Dabei wird eine interne Repräsentation der Programmstruktur abgebildet. Diese Repräsentation basiert auf der rechten Seite (rhs) der Grammatikregeln. Sofern eine rechte Seite einer Regel erkannt wurde, wird der Code zu dem zugehörigen Nicht-Terminal der linken Seite (lhs) reduziert. Das Parsen ist beendet, wenn das gesamte Programm auf das Startsymbol der Grammatik reduziert wurde. Der Syntaxbaum muß ggf. noch durch weitere Module optimiert werden, sofern eine Vereinfachung des Baums als notwendig erachtet wird.

Yacc besteht wie Lex aus drei Sektionen:

C- und Parser-Deklarationen/-Definitionen

%%

Grammatikregeln und Aktionen

%%

C-Subroutinen

Die erste Sektion beinhaltet:

  • Token-Deklarationen, also eine Liste der Token, die vom Parser erwartet werden.
  • Vorrangregeln von Operatoren (+,-,* usw.) (Präzedenzen), die sich  durch die Reihenfolge der Nennung ergeben, in der das letztgenannte die höchstwertige Präzedenz hat (damit wird z.B. +,- vor *,/ genannt).
  • Assoziativitäten von Operatoren (in ANSI-C sind z.B. [+,-,*] links-assoziativ, während [++] rechts-assoziativ ist), die durch Angabe des Bezeichners (%left, %right) definiert werden.
  • gewöhnlichen C-Code, jeweils in speziellen Klammern %{…%}. Hier wird u.a. der zu exportierende Header mit den (#include)-Dateien angegeben. Außerdem werden hier zwei vom Parser erwartete Funktionen (yyparse) und (yyerror) deklariert.

Die zweite Sektion mit den Regeln beinhaltet die EBNF-Grammatik sowie deren zugehörige Aktionen. Die Zuweisung von Nicht-Terminal-Symbolen erfolgt dabei durch Doppelpunkt. Zusätzliche Regeln für den gleichen Ausdruck (E) lassen sich auch mittels eines sog. Alternativ-Operators (| Oder) schreiben. Vorheriges Beispiel zur formalen Grammatik würde dann folgende Regeln besitzen:

 E : E + E (R1)
| E * E (R2)
| id (R3)

Für jede Regel dürfen mehrzeilige Aktionen innerhalb geschweifter Klammern {} aufgeführt werden. Hier ist sowohl C- als auch C++ Code möglich. Im Bereich der Subroutinen können benutzerdefinierte C-Routinen abgelegt werden. Hier könnte z.B. wieder ein (main) definiert werden, in dem die Funktion [yyparse()] gerufen werden muß. Dies ist die Treiber-Funktion des Parsers. Grundsätzlich ist aber auch die Einbindung eines separaten (main) durch das Makefile möglich. Parsing-Fehler müssen über eine zu definierende Funktion [yyerror(const char *s)] übermittelt werden. Die Definition kann ebenfalls im Bereich der Subroutinen erfolgen oder bereits im ersten Sektions-Abschnitt, wo die Deklarationen für (yyparse) und (yyerror) vorgenommen werden.

Ergebnis

Die mit Lex und Yacc erstellten Dateien können unter Verwendung eines C-Compilers (etwa Gcc) in Objektcode und anschließend mittels eines Linkers in eine ausführbare Datei übersetzt werden. Das Ergebnis ist entweder ein Compiler oder ein Interpreter. Ein generierter Compiler ist eine ausführbare Datei, die in der Lage ist, eine Liste mit Worten einer vorher definierten Sprache zu übersetzen und eine ausführbare, maschinennahe Datei zu erzeugen. Dem gegenüber ist ein Interpreter eine ausführbare Datei, die in der Lage ist, eine Liste mit Worten einer vorher definierten Sprache sukzessiv zu übersetzen und zeilenweise auszuführen. Es ist möglich, durch Hinzufügen selbsterstellter Dateien und Funktionen das Endergebnis der Code-Generation zu steuern. Somit ist nicht festgelegt, ob Yacc einen Compiler oder einen Interpreter erzeugt. Dies ergibt sich erst aus der Funktionsweise der Ergebnisdatei und den darin eingebundenen Objektdateien. Nachfolgend wird der Einsatz von Lex und Yacc detailliert anhand eines Beispiels beschrieben.