Lex, Yacc und C++

Wie oben bereits angedeutet, sind Lex und Yacc die wohl bekanntesten Compilerbauwerkzeuge. Diese Programme wurden in den 70er Jahren entwickelt und sind heute auf nahezu allen Rechnerplattformen verfügbar. Altersbedingt unterstützen sie allerdings moderne Programmiersprachen wie C++ nicht direkt. Dies bedeutet jedoch nicht, dass man diese Kombination nicht für die Entwicklung hoch effizienter Übersetzer verwenden kann. Nachfolgende Beschreibung erläutert anhand eines einfachen Sprachinterpreters, wie man die Flexibilität von Lex und Yacc mit der Leistungsfähigkeit von C++ kombinieren kann.

Weshalb C++?

Lex generiert Scanner, Yacc generiert Parser. Diese lösen in Kombination das Problem, eine Eingabe anhand einer vorgegebenen Grammatik zu erkennen. Dies ist jedoch quasi nur die halbe Miete. Die Aktionen, also das, was beim Erkennen eines Konstruktes tatsächlich zu tun ist, muß der Entwickler in herkömmlicher Weise in Form sog. Semantic Actions selbst beschreiben. Hierzu ist zunächst einmal reines C vorgesehen. Nun liegt es in der Natur der Aufgabe, dass aus Eingaben gemäß der Grammatik sog. Syntaxbäume generiert werden müssen, Datenstrukturen also, die gemäß der Semantik ein Abbild der Eingabe darstellen, auf welches hinterher zwecks Interpretation oder anderweitiger Verarbeitung zugegriffen werden soll. Genau hier hat C jedoch weniger zu bieten als C++. Mit der Standard Template Library (STL), welche inzwischen zum C++- Sprachumfang gehört, lassen sich nahezu beliebig komplexe Datenstrukturen erstellen und effizient verwalten. Wer schon einmal einen Binärbaum, eine Map (Verzeichnis) oder Menge in C implementiert hat weiß, wie zeitraubend und fehleranfällig dies ist. Mit den Template-Klassen der STL stehen hingegen getestete und optimierte Container zur Verfügung, so dass man sich bei der Programmierung auf die eigentliche Aufgabe des Parsens und Interpretierens konzentrieren kann. Als Beispiel soll eine winzige Programmiersprache entwickelt werden, welche zwar für sich genommen wenig praxistauglich ist, jedoch problemlos als Basis für komplexere Projekte verwendet werden kann. Folgende Anforderungen soll die Sprache erfüllen:

  • Berechnung üblicher arithmetischer Ausdrücke wie [(3 + 4) * 7]
  • Zuweisen von Ausdrücken und Zeichenketten an Variablen
  • Variablen werden bei erster Verwendung initialisiert und müssen nicht deklariert werden
  • Variablen können nach den üblichen Namenskonventionen gebildet werden
  • es steht eine Print-Funktion zur Datenausgabe zur Verfügung
  • eine While-Schleife in C-ähnlicher Syntax wird implementiert
  • Kommentare im C++-Stil sind zulässig
  • Groß- und Kleinschreibung wird ignoriert (case-insensitive)
  • es lassen sich Funktionen definieren, die mit einer Liste von Argumenten aufgerufen werden können (formale Parameter)
  • lokale Variablen innerhalb von Funktionen werden unterstützt
  • ein bedingter Ausdruck der Form [if – else – end] steht zur Verfügung
  • eine einfache Erweiterbarkeit um neue Konstrukte ist möglich

Die zu erstellende Sprache – Easy genannt – soll dabei durch einen Interpreter übersetzt werden. Zunächst wird aus der Eingabe ein Syntaxbaum erzeugt, welcher dem Interpreter im zweiten Schritt als Eingabe für die effiziente Abarbeitung dient. Dieses Projekt umfaßt rund 450 Codezeilen und ist damit durchaus überschaubar. Man benötigt dazu folgende Module:

  • easyscan.l – der Scanner (Lex)
  • easypars.yy – der Parser (Yacc)
  • main.cpp – ein rudimentäres Hauptprogramm zum Aufruf des Parsers und des Interpreters
  • ast.h ast.cpp – Definition und Implementation der Datenstruktur für den Syntaxbaum
  • global.h global.cpp – einige globale Hilfsvariablen
  • interpret.cpp – der Programminterpreter
  • MAKEFILE – Übersetzungsregeln