Der Parser erzeugt zu einem lexikalisch und auch syntaktisch korrekten Tinyray-Quellprogramm einen entsprechenden Syntaxbaum. Sobald der vollständige Syntaxbaum erstellt ist, wird der Scanner als auch der Parser nicht mehr benötigt. Alles Weitere geschieht dann mit dem Syntaxbaum als Grundlage.










Der Syntaxbaum zum vorliegenden, korrekten Tinyray-Quellprogramm …

… sieht beispielsweise wie folgt aus.

Dieser Syntaxbaum ist von links nach rechts zu lesen; links befindet sich die Wurzel namens Tinyray und rechts befinden sich die Blätter. Die ovalen Knoten repräsentieren die Nichtterminale der Tinyray-Grammatik und die rechteckigen Knoten repräsentieren die für die weitere Verarbeitung relevanten Terminalsymbole.

Der vorliegende Syntaxbaum ist ein sogenannter abstrakter Syntaxbaum (AST), „abstrakt” — weil die unbedeutenden, überflüssigen Token bzw. Produktionen fehlen, beispielsweise sind die Klammern und Kommata im abstrakten Syntaxbaum nicht zu sehen. Kommentare würden in einem abstrakten Syntaxbaum ebenfalls nicht erscheinen.

Dieser Syntaxbaum wurde mit dem Tinyray-DotCode erzeugt — ein recht nützliches Feature von Tinyray, da freut sich der Compilerbauer! :-)

Beim Scannen ging es ja hauptsächlich darum, Tokens quasi Terminalsymbole T in einem Quellprogramm zu erkennen. Beim Parsen geht es vielmehr darum, Nichtterminale N in einem Tokenstrom zu erkennen. Die atomaren Bestandteile eines Nichtterminals sind Terminalsymbole, die der Scanner liefert. Deshalb benötigt der Parser den Scanner, um aus dem Tokenstrom des Scanners die Nichtterminale zu erkennen. Da aber Nichtterminale in anderen Nichtterminalen enthalten sind, ergibt sich aus dem Parse-Vorgang eine Baumstruktur von Nichtterminalen und Terminalen, wohingegen der Scanner nur eine listenartige Struktur von Terminalen liefert.

Um den Parse-Vorgang etwas besser nachvollziehen zu können, sollten Sie sich in der folgenden Grammatik TG das Startsymbol S, welches die Zusammensetzung aller nur möglichen Tinyray-Programme definiert, herauspicken. Und beginnen Sie dann in Gedanken oder auf einem Blatt Papier sich durch die Produktionen P zu navigieren und merken Sie sich dabei nur die Terminalsymbole, die Sie auf dem Weg finden, wie zum Beispiel:

1. Wegen dem Startsymbol S stoße ich auf das Nichtterminal Tinyray und notiere meine ersten Terminale
2. TINYRAY LBRACE
3. Jetzt könnte ich den geklammerten Ausdruck
   1. (Global | Defaults | Geo | Sun)*
   beliebig oft wiederholen oder einfach nur überspringen. Ich könnte jetzt zum Beispiel mit dem Nichtterminal Sun fortsetzen, die folgenden beiden Terminale würden SUN LBRACE lauten. Aus Bequemlichkeit überspringe ich aber diesen Ausdruck und stoße dabei auf das letzte Terminalsymbol des Nichtterminals Tinyray.
4. RBRACE
5. Und erhalte im Gesamten drei Terminale.
6. TINYRAY LBRACE RBRACE
7. Wenn ich diese Terminale T rücktransformiere, erhalte ich das kürzest mögliche Tinyray-Programm.
8. Tinyray { }

Suchen Sie nicht nach der Bedeutung von dem, was dabei herauskommt! Es geht lediglich um die Aneinanderreihung einzelner Terminale gemäß gegebener Grammatik. Beispielsweise kann nach TINYRAY nur ein LBRACE folgen, wohingegen die Aneinanderreihung „TINYRAY SUN” nicht von dieser Grammatik akzeptiert werden würde.

Ohne Firstmengen ist praktisch kein Parsen möglich. Was nun Firstmengen sind, möchte ich anhand der Tinyray-Grammatik erläutern.

Wenn Sie sich mal die Startproduktion Tinyray ansehen, sehen Sie, dass diese mit dem Terminalsymbol TINYRAY gefolgt vom LBRACE-Terminal beginnt. Es gibt keine andere Möglichkeit die Produktion Tinyray zu beginnen, also ist das erste Symbol der Produktion Tinyray das Terminalsymbol TINYRAY. Die Firstmenge dazu sieht dann wie folgt aus:

1. First(Tinyray) = { TINYRAY }

Mit der Produktion Vector verhält es sich analog mit dem Ergebnis:

1. First(Vector) = { LBRACKET }

Der Vector beginnt also immer mit dem Terminalsymbol LBRACKET.

Folgende Produktionen sind ähnlich einfach gelagert:

1. First(Defaults) = { DEFAULTS }
2. First(Sun) = { SUN }
3. First(Camera) = { CAMERA }
4. First(Background) = { BACKGROUND }
5. First(Ambience) = { AMBIENCE }
6. First(Fog) = { FOG }
7. First(Bounding) = { BOUNDING }
8. First(Triangle) = { TRIANGLE }
9. First(Sphere) = { SPHERE }
10. First(Plane) = { PLANE }

Die Produktion Parameters beginnt aber mit dem Nichtterminal Vector, demnach wäre also die Produktion Vector in der Firstmenge von Parameters, doch ganz so ist es nicht. In einer Firstmenge können sich nur Terminalsymbole befinden, da aber bekannt ist, mit welchem Terminalsymbol die Produktion Vector beginnt, kann die Firstmenge von Vector übernommen werden:

1. First(Parameters) = First(Vector) = { LBRACKET }

Irgendwie logisch — wenn also Parameters mit einem Vector beginnt und Vector mit einem LBRACKET beginnt, dann beginnt natürlich auch Parameters mit einem LBRACKET (Transitivität).










Preisfrage: Wie lautet nun die Firstmenge von Global?










Die Produktion Global könnte mit der Produktion Camera beginnen, könnte aber auch mit den Produktionen Background, Ambience oder Fog beginnen; hat also vier Möglichkeiten. Die Firstmenge von Global setzt sich deshalb wie folgt zusammen:

1. First(Global)
= First(Camera) v First(Background) v First(Ambience) v First(Fog)
= { CAMERA } v { BACKGROUND } v { AMBIENCE } v { FOG }
= { CAMERA, BACKGROUND, AMBIENCE, FOG }

Aus diesem Grunde spricht man von einer Firstmenge einer Produktion und nicht von einem Firstterminal. Die Produktion Global kann also mit den Terminalsymbolen CAMERA oder BACKGROUND oder AMBIENCE oder FOG beginnen.

Mit Geo verhält es sich analog:

1. First(Geo)
= First(Bounding) v First(Triangle) v First(Sphere) v First(Plane)
= { BOUNDING } v { TRIANGLE } v { SPHERE } v { PLANE }
= { BOUNDING, TRIANGLE, SPHERE, PLANE }

Die Produktion Geo kann also mit den Terminalsymbolen BOUNDING oder TRIANGLE oder SPHERE oder PLANE beginnen.

Nun wissen Sie also, was Firstmengen überhaupt sind und wie man sie bestimmen kann. Doch wie die Firstmengen den Parse-Vorgang unterstützen können, habe ich noch gar nicht erwähnt. Lesen Sie hierzu im Folgenden die Bedeutung der Firstmengen.

Der Parser erhält vom Scanner nur Tokens, also Terminalsymbole der Grammatik. Der Scanner kennt nämlich keine Nichtterminale. Es ist die Aufgabe des Parsers, aus dem Tokenstrom eines Scanners einen Syntaxbaum gemäß den Produktionen einer Grammatik aufzubauen.

Woher weiß also der Parser, welche Produktion der Grammatik greifen muss, wenn er ein Token vom Scanner erhält?
Da es nun für jede Produktion eine Firstmenge gibt, muss man eigentlich nur noch nachsehen in welcher Firstmenge sich das vom Scanner erhaltene Token bzw. Terminalsymbol liegt und erhält somit die passende Produktion. Und die Produktion entspricht einem Teilbaum des Syntaxbaumes. Der Syntaxbaum kann Dank der Firstmengen erstellt werden.

Es gibt drei Terminalsymbole, die in der Tinyray-Grammatik TG nicht zu sehen sind, die aber vom Tinyray-Scanner als Token zurückgegeben werden können. Diese Terminalsymbole heißen wie folgt:

1. COMMENT
   Ein Kommentar kann praktisch an jeder Stelle in einem Tinyray-Quellprogramm vorkommen. Wenn also dieses Terminalsymbol korrekter Weise in die Grammatik TG aufgenommen werden würde, wäre diese Grammatik um ein Vielfaches größer — schlimmer noch — gar unlesbar!
2. UNKNOWN
   Es gibt praktisch kein unbekanntes Token in einem korrekten Tinyray-Quellprogramm. Deshalb liegt UNKNOWN nicht in dieser Grammatik. Erhält der Parser dieses Token, kommt es zu einer Exception, der Parse-Vorgang wird abgebrochen.
3. EOS
   Das Ende eines korrekten Tinyray-Programms kann nur nach Abarbeitung der Startproduktion Tinyray erreicht werden. Deshalb ist es vielleicht übersichtlicher, dieses Token nicht in die Grammatik aufzunehmen.

Zur Realisierung des Tinyray-Parsers werden die Klassen aus der lexikalischen Analyse sowie zusätzliche drei Dateien der syntaktischen Analyse benötigt:

1. ParseException.java
   Bei einem syntaktisch sowohl auch bei einem lexikalisch inkorrekten Tinyray-Quellprogramm wird eine Exception (hier: ParseException) geworfen.
2. ParseTreeKit.java
   Hierbei handelt es sich um ein Interface, welches die Schnittstelle für eine knotenerzeugende Klasse definiert.
3. Parser.java
   Ist der Parser instantiiert, kann mit der Methode parse() der Syntaxbaum erzeugt werden. Die Rückgabe von parse() ist der Wurzelknoten des Syntaxbaumes. Der Rückgabetyp wird von einer Implementierung des ParseTreeKit bestimmt.

Um ein kleines Anwendungsbeispiel des Parsers zeigen zu können, benötigt man zu allererst eine Implementierung des abstrakten ParseTreeKit (Interface). Eine prägnante Implementierung des ParseTreeKit, welche zudem auch die Struktur des Syntaxbaumes gut hervorhebt, heißt im Folgenden XMLTreeKit. Der XMLTreeKit erzeugt die Knoten des Syntaxbaumes als String-Listen „List<String>”, welche jeweils XML-Code-Fragmente enthalten. Das Anwendungsbeispiel heißt XMLTree und gibt den Syntaxbaum als XML-Baum aus.

Keine Angst! Es ist der einzige XML-Part zum Tinyray-Projekt. :-)

Dieses rudimentäre Beispiel soll Sie auf weitere Implementierungen des ParseTreeKit vorbereiten, die da heißen: Tinyray-LanguageKit und Tinyray-RaytracerKit.

Ein kurzes Tinyray-Quellprogrämmchen …

… kann Dank XMLTreeKit auch recht kurz und ausdrucksstark als Syntaxbaum in XML-Format ausgegeben werden.

Jedoch ein etwas längerer Tinyray-Code …

… fabriziert schon extrem langen und unüberschaubaren XML-Code.

Bei längerem Code sollte man vielleicht die grafische Darstellung von Tinyray-DotCode der XML-Darstellung vorziehen.

Es ist aber auch möglich, die grafische Darstellung etwas kompakter zu machen.