Im wesentlichen besteht diese Datenstruktur aus zwei Komponenten: einer Klasse (Expression) und einer STL-Vektor-Tabelle (ExpressionList). Beide Komponenten wurden im obigen Beispiel zur Grammatik bereits kurz erläutert. Die Klasse (Expression) hat drei Memberkomponenten:

  • Operationsname vom Typ String
  • Konstantenwert ebenfalls vom Typ String
  • Liste verbundener Expressions (ExpressionList)

Eine (ExpressionList) ist ein Vektor von (Expressions) und nutzt die Template-Klasse (vector). Diese rekursiv angelegte Datenstruktur erlaubt es, alle Fälle der Grammatik abzubilden. Vorteil solch rekursiver Strukturen ist, daß man Verschachtelungen ohne Aufwand abbilden und abarbeiten kann, insbesondere bei einer so minimalistischen Darstellung. Das gesamte Programm wird schlicht als (ExpressionList) abgelegt und später sukzessiv abgearbeitet. Eine (while)-Schleife ist nichts weiter als eine (Expression) mit einem besonderen Namen (_while) und der Bedingung sowie dem Schleifenkörper als Argumenten. Der Schleifenkörper kann hierbei selbstverständlich aus mehreren Ausdrücken bestehen ? dies ermöglicht die (ExpressionList). Ein ganz ähnlicher Ansatz liegt den Funktionsdeklarationen zu Grunde. Eine Hilfs-Map bildet Funktionsnamen auf (Expressions) ab, welche die eigentliche Funktionsdefinition enthalten. Im einzelnen gelten folgende Aufbauregeln:

  • Alle Werte, auch numerische, werden als Zeichenkette gespeichert.
  • Konstanten werden abgebildet, in dem das Feld (operation) mit einem Leerstring und das Feld (constvalue) belegt werden.
  • Funktionsaufrufe und Infixoperatoren wie (+) und (-) werden durch Belegung des Feldes (operation) mit dem Funktionsnamen und den Argumenten in der Liste der Argumente (arguments) abgelegt. (constvalue) erhält die leere Zeichenkette zugewiesen.
  • Die Zuweisung wird als Funktionsaufruf behandelt. Dies hat den Nebeneffekt, daß, wie in C, die Zuweisung einen Rückgabewert besitzt.
  • Schleifen, Bedingungen, Funktionsdeklarationen usw. werden wie Funktionsaufrufe abgebildet, wobei das Feld (operation) mit der Bezeichnung des Konstrukts und einem vorangestellten Unterstrich belegt wird. Solche Namen können vom Benutzer per Definition nicht verwendet werden. Namen müssen mit einem Buchstaben beginnen.

Die Datei (ast.h) enthält die Definition dieser beiden Klassen und einiger weniger Methoden. Insbesondere definiert sie den Ausgabeoperator (>>) für beide Kernklassen. Es ist stets empfehlenswert, eine Ausgabemöglichkeit für den Syntaxbaum zu schaffen. Verschachtelte Strukturen interaktiv zu debuggen ist recht arbeitsintensiv und dagegen ist der Aufwand für solche Ausgabefunktionen vernachlässigbar gering.