Die Grammatik

Hier sind der Kreativität kaum Grenzen gesetzt. Für dieses Beispiel wird eine eher schlanke Version implementiert, die aber bei Bedarf beliebig erweiterbar ist. Folgende Operatoren und Ausdrücke sind zur Zeit implementiert:

  • Addititon (+)
  • Subtraktion (-)
  • Multiplikation (*)
  • Wertezuweisung (=)
  • Vergleich (==)
  • größer (>), kleiner (<)
  • Vorzeichen (-x)
  • Klammerausdrücke ()
  • While-Schleife
  • konstante Werte (VALUE)
  • Bezeichner (NAME)
  • Funktionsaufrufe und Funktionsdeklarationen
  • Bedingter Ausdruck (if – else – end)

Beispiel: Grammatik-Regel für eine Addition im Parser

expression : expression ‚+‘ expression {

ExpressionList* a = new ExpressionList;

a->push_back(*$1);

a->push_back(*$3);

Expression* e = new Expression(„_plus“, *a, „“);

$$=e;

}

Die linke Seite der Grammatik-Regel ist ein Ausdruck (Expression), d.h. ein Nicht-Terminal. Diese ist der rechten Seite zugeordnet, die eine Addition zweier Nicht-Terminale beschreibt. Jedes Element der rechten Seite der Regel läßt sich dabei mit Markern der Form ($x) ansprechen. So ist die linke Seite der Addition ($1), das Additionszeichen ($2) und die rechte Seite der Addition ($3). Die zugehörige mehrzeilige Anweisung steht in Klammern {} und verwendet C++-Code. Diese Anweisung erzeugt zunächst einen Pointer (a) auf dem Heap, der vom Typ [ExpressionList] ist. [ExpressionList] wird im Modul (ast.h) deklariert und ist ein STL-Vector-Typ. Die STL stellt für Vector-Typen die Funktion (push_back) zur Verfügung. Diese Funktion fügt ein Element am Ende des Vektors an. Unter Verwendung der Marker ($x) werden somit die linke und rechte Seite der Addition, d.h. die beiden Summanden, in den Vector eingefügt. (Expression) ist eine Klasse, ebenfalls deklariert in (ast.h). Es wird ein Pointer (e) auf dem Heap deklariert, der vom Typ dieser Klasse ist. Die Klasse besitzt einen Copy-Konstruktor (definiert in [ast.cpp]), der die Übergabe von Parametern ermöglicht. Der erste Parameter ist dabei ein Identifikator-String, hier „_plus“. Er dient zur Markierung der mathematischen Operation. Der zweite Parameter ist der Pointer auf die (ExpressionList), also den Vektor, um die Summanden zu übergeben. Der dritte Parameter ist ein optionaler String, der hier nicht verwendet wird. Dieser wird einzig bei der Rückgabe einer Konstanten verwendet. Die Anweisung der Grammatik-Regel wird beendet, in dem der Klassen-Pointer (e) mittels Yacc-Anweisung ($$e) zurückgegeben wird. In (interpret.cpp) kann dann innerhalb der Definition der Klassen-Methode (calc) nach den Identifikatoren (hier „_plus“) gesucht und die zugehörige mathematische Operation (hier: Addition) auf die Operanden angewendet werden.

Natürlich läßt sich diese Grammatik beliebig dahin optimieren, semantisch unsinnige Konstrukte bereits bei der Syntaxprüfung zu erkennen. So macht der Ausdruck (3 * 7 = 4 * x) wenig Sinn, obwohl er auf obige Grammatik passen würde. Um den Codeumfang gering zu halten, wird hierauf jedoch zunächst verzichtet. Viele modernere Parsergeneratoren verfolgen den Ansatz, aus der Grammatik auch gleich eine Datenstruktur für den Syntaxbaum, vorzugsweise in Form von Klassen, zu generieren. Dies klingt zunächst einmal überzeugend, bringt jedoch zuweilen auch erhebliche Nachteile mit sich. Jede generierte Klasse muß später bei der Auswertung auch behandelt werden. Gerade in diesem Anwendungsfall kann man sich die Tatsache zu Nutze machen, dass man bezüglich der Datenstruktur, die das Programm aufnimmt, völlig frei ist und sich nicht an den Grammatikregeln orientieren muß. So kann man eine recht generische, äußerst schlanke Struktur verwenden, die alle Fälle abdeckt und mit extrem wenig Aufwand ausgewertet werden kann. Gerade diese Trennung von Grammatikregeln und der Datenstruktur des Syntaxbaumes erlaubt es, die semantischen Anforderungen bereits frühzeitig im Übersetzungsprozeß zu berücksichtigen.