flex
Flex ist eine in der Funktionalität erweiterte GNU-Version von
lex. Mit flex kann man in einfacher Weise endliche Automaten
beschreiben. Dieser wird hier zur lexikalischen Analyse
(Tokenisierung) einer ddl-Datei eingesetzt.
Erste Aufgabe des Programmierers ist es, mit Hilfe regulärer Ausdrücke die Token zu definieren, die erkannt werden sollen. Flex übersetzt dies in einen C/C++-Quellcode, der entsprechend die einzelnen Token-Arten (wie Schlüsselwörter, Bezeichner, Konstanten) durch int-Werte repräsentiert.
Der Programmierer kann nun dem jeweils erkannten Token zusätzlich zum Typ noch einen Wert zuweisen, so hat "1234" etwa den Typ Integer-Konstante und den Wert 1234. Der Programmierer muß diese Übersetzung von der als Token erkannten Zeichenkette in einen Wert als C/C++-Code zur Verfügung stellen.
Flex baut diesen Code entsprechend in den endlichen Automaten ein, der dann in der Form benutzt wird, daß ihm eine Eingabedatei übergeben wird und er eine Funktion zur Verfügung stellt, über die nacheinander die in der Datei enthaltenen Token mit Typ und Wert abgefragt werden können.
bison
Bison ist eine in der Funktionalität erweiterte GNU-Version von
yacc. Mit bison kann man in einfacher Weise Parser (Programme zur
Erkennung von kontextfreien Grammatiken) beschreiben. Dieser wird hier zur
strukturellen Analyse einer ddl-Datei eingesetzt. Dabei wird eine
Datenstruktur aufgebaut, die dem Baum der kontextfreien Grammatik
entspricht. Der Baum wird durch einen Baum von Klassenobjekten
repräsentiert, die über Memberfunktionen die
semantische Analyse rekursiv vornehmen können. Ziel ist es
dabei insbesondere, einen C++-Quellcode zu erzeugen, der die Domain
repräsentiert und zur Erzeugung eines Domain-spezifischen Editors und
Simulators verwendet werden kann.
Der Programmierer muß die verwendeten Token-Typen (Terminale) und die Regeln der kontextfreien Grammatik angeben. Die flex-Schnittstellenfunktion wird verwendet um die Terminale und deren zugehörige Werte einzulesen. Der Programmierer muß nun in C/C++-Code angeben, wie bei Anwendung einer KFG-Regel dem entstehenden Nichtterminal ein Wert zugeordnet werden soll. In unserem Fall wird dabei normalerweise mehrere Bäume zu einem mit einer neuen Wurzel zusammengefaßt.
Flex übersetzt diese Spezifikation des Programmierers in einen
C/C++-Quelltext, der eine Funktion zur Verfügung stellt, mit dem der
Wert des Startsymbols der Grammatik herausgefunden wird.
In unserem Fall wird dadurch der komplette Syntaxbaum des ddl-Programms
aufgebaut. Wie oben erwähnt besitzt dieser schon selbst die
Fähigkeit zur Semantikanalyse.
Das Hauptprogramm muß also "nur" die von bison zur Verfügung
gestellte Funktion aufrufen und danach die Wurzel des Syntaxbaums
anweisen, die Semantikanalyse durchzuführen.
Dateien
Folgende Dateien werden vom Programmierer bearbeitet:
| Deklarations-Datei | Implementations-Datei | Aufgabe |
|---|---|---|
| Makefile | Automatische Übersetzung des DDL-Compilers | |
| Src/ddl_main.cc | C++-Hauptprogramm, das den Parsevorgang und die Semantische Analyse auslöst | |
| Includes/ddl_common.hh | Deklarationen, die sowohl im DDL-Compiler als auch im Simulator zur Verfügung stehen müssen | |
| Includes/komp_tools.hh | Deklarationen, die im Simulator
zur Verfügung stehen müssen; in den vom DDL-Compiler
erzeugten C++-Code wird automatisch ein #include auf
diese Datei eingefügt
| |
| Includes/error.hh | Src/error.cc | Fehler-Behandlung |
| Includes/cstring.hh | Src/cstring.cc | String-Klasse, die statt der C++-Strings (char*) benutzt wird |
| Includes/ddl_ds.hh | Datenstrukturen, die vom DDL-Compiler benutzt werden. | |
| Includes/ddl_nodes.hh | Src/ddl_nodes.cc | Datenstrukturen des DDL-Compilers für den Syntax-Baum |
| Src/ddl_lexer.l | flex-Quellcode | |
| Src/ddl_parser.y | bison-Quellcode |
Makefile
Die Benutzung eines Makefiles für normale C++-Projekte wird
als bekannt vorausgesetzt.
Zusätzlich müssen die Regeln für die Übersetzung des flex- und des bison-Quellcodes angegeben werden:
[...]
.y.cc:
$(YACC) $(YFLAGS) -o$@ $<
.l.cc:
$(LEX) $(LFLAGS) -o$@ $<
[...]
$(DDLSRCDIR)/ddl_lexer.o: $(DDLSRCDIR)/ddl_lexer.cc \\
$(DDLSRCDIR)/ddl_parser.cc.h \\
$(DDLINCLUDEDIR)/ddl_nodes.hh
[...]
$(DDLSRCDIR)/ddl_lexer.cc: $(DDLSRCDIR)/ddl_lexer.l
$(DDLSRCDIR)/ddl_parser.o: $(DDLSRCDIR)/ddl_parser.cc
[...]
$(DDLSRCDIR)/ddl_parser.cc: $(DDLSRCDIR)/ddl_parser.y
$(DDLSRCDIR)/ddl_parser.cc.h: $(DDLSRCDIR)/ddl_parser.y
$(YACC) $(YFLAGS) -o$(DDLSRCDIR)/ddl_parser.cc $(DDLSRCDIR)/ddl_parser.y
[...]
Als Besonderheit fällt hier die Datei ddl_parser.cc.h
auf. Diese wird von bison automatisch erstellt und wird als
#include in die flex-Quellcode-Datei eingefügt.
In bison werden symbolische Namen für Token vereinbart, die für
den erzeugten C++-Code in int-Werte übersetzt werden.
Gleichzeitig erzeugt bison die Datei ddl_parser.cc.h, welche
die symbolischen Namen und ihre int-Übersetzungen als
#defines enthält. Damit können im flex-Quellcode die
selben Namen verwendet werden und es ist sichergestellt, daß die
Überstzung konsisten ist.
Da die #include-Anweisung textuell in den von flex erzeugten
C++-Code übernommen wird, besteht die Abhängigkeit erst bei der
Erzeugung der .o-Datei, also der Anwendung des C++-Compilers,
nicht schon bei der Erzeugung des C++-Codes durch flex.