7. Implementation eines Fuzzy-Parsers
Ein Fuzzy-Parser kann nur bedingt die Methoden und Toolkits des klassischen Compilerbaus [AhoSethiUllmann 88] nutzen. Dies liegt darin begründet, daß beim klassischen Compilerbau alle (auch noch so geringfügigen) Abweichungen von der Syntax gefunden werden sollen. Für die erfolgreiche Arbeit eines Fuzzy-Parsers ist nur insoweit eine syntaktische Korrektheit erforderlich, als einige wenige Schlüsselelemente erkannt werden müssen. Mehr sollte aus obigen Gründen nicht vorausgesetzt werden.
Die lexikalische Analyse ist beiden Methoden gemeinsam. Hier könnte ein automatisch generierter Scanner verwendet werden. Da der Scanner aber der kleinere Teil des Scanner/Parser-Gespanns ist, habe ich ihn zunächst ebenfalls von Hand geschrieben. (Da die meisten Generatoren, z.B. Lex, ohnehin nur C-Code generieren, müßte man ihn wohl ohnehin in einer Klasse kapseln.) Bei der Syntaxprüfung gelten andere Ziele: Es sollen nicht die vorhandenen Fehler gefunden, sondern trotz möglicher Fehler so viel wie möglich Informationen extrahiert werden. Auf Typprüfungen o.ä. wird gänzlich verzichtet.
Zur Syntaxanalyse bei Fuzzy-Parsern eignen sich Top Down-Verfahren wie die Methode des rekursiven Abstiegs besser als Bottom Up-Verfahren (z.B. Shift-Reduce Methode), da sie nicht so eng an den Produktionen (Regeln) hängen und es erlauben, bestimmte Teile des Token-Stream zu überlesen, da zu jedem Zeitpunkt klar ist, in welchem semantischen Zusammenhang man sich befindet. Compiler-Generatoren (z.B. YACC, Cocktail) erzeugen meist Shift-Reduce Parser, da diese schneller arbeiten und mächtigere Grammatiken verarbeiten können.
Der von mir erstellte Fuzzy-Parser sammelt deutlich weniger Informationen über den Quelltext als ein traditioneller Parser, wie beispielsweise der bereits beschriebene ep.
Ein Nachteil eines von Hand gebauten Parsers ist, daß er auf eine spezielle Aufgabe (hier: als Back-End eines Browsers) zugeschnitten ist und die auszuführenden Operationen im Quelltext nicht von der Syntax und dem Prozeß der Informationsgewinnung getrennt sind. Bei generierten Parsern sind das eigentliche Parsen und die Verwendung der gewonnenen Operationen konzeptionell besser getrennt und werden erst vom Generator in den Parser integriert (siehe z.B. Action-Teil eine YACC-Regel). Diesem Problem kann man begegnen, indem man den Parser als Framework realisiert (siehe Abschnitt über die von mir gewählte Architektur).
Dieser Nachteil ist gleichzeitig auch ein Vorteil: Da zu jedem Zeitpunkt genau bekannt ist, welche Informationen noch benötigt werden, wird nicht zuviel Quelltext exakt geparst, sondern kann weitläufig überlesen werden, was der Fuzzy-Eigenschaft (d.h. der Fehlertoleranz) sehr entgegenkommt.
7.1. Architektur
Die klassische Aufteilung in Scanner und Parser kann und sollte auch bei Fuzzy-Parsern beibehalten werden. Die Anforderungen an den Scanner eines Fuzzy-Parsers unterscheiden sich kaum von denen an einen traditionellen Scanner (mit Ausnahme der Tatsache, daß Fehler nicht zu einem Abbruch führen dürfen, was bei Scannern aber ohnehin unüblich ist.)
Scanner und Parser sind bei mir in der Art eines Frameworks (nach [Gamma 92] "Framework im kleinen") zur Verfeinerung durch den Klienten konstruiert. Ich habe also einen (in Grenzen) allgemeinen Eiffel-Parser implementiert, der dann vom Parser für Sniff+ verfeinert wird. Auf diese Weise wird eine strikte Trennung erreicht zwischen dem Extrahieren (Beschaffen) der Informationen über den Quelltext und der Verwendung dieser Informationen.
Die Verfeinerung erfolgt durch Konkretisierung (d.h. Implementierung) einiger speziell dafür vorgesehener Methoden. Diese Methoden werden an passenden Stellen (z.B. beim Auffinden einer Klasse) aufgerufen. Im allgemeinen Eiffel-Parser sind diese Methoden leer. (Man kann / sollte sie sich als abstrakt vorstellen, da es kaum Sinn macht, den Parser ohne jegliche Verwendung der gewonnenen Informationen überhaupt zu benutzen. Da oft jedoch nur einige der Methoden benötigt werden, habe ich alle im allgemeinen Parser als leer implementiert, so daß sie in den Verfeinerungen nicht beachtet werden müssen.)
Alle zur Konkretisierung vorgesehenen Methoden in EiffelScanner und EiffelParser heißen ActOn...() (z.B. ActOnClassname(), ActOnFeature() etc.).
Abb. 13: Klassendiagramm
In den Klassen EiffelScanner und EiffelParser wird durch die eben beschriebene Konstruktion der zum Teil recht komplexe Algorithmus zum Scannen bzw. Parsen gekapselt. Nach [Gamma 92] bezeichnet man dieses Muster als "Verfahrensklassen mit einer White-Box-Schnittstelle". Die Kapselung erleichtert die eventuelle Auswechslung des verwendeten Algorithmus des rekursiven Abstiegs gegen einen anderen Algorithmus (z.B. Shift-Reduce Algorithmus).
Im Mittelpunkt der Verfahrensklasse steht eine Run()-Methode, die den Algorithmus nach seiner Parametrisierung ablaufen läßt. Da nur zu den wenigsten vom Scanner generierten Token Zusatzinformationen benötigt werden, läuft der EiffelScanner nicht ohne Unterbrechung durch, sondern wird jeweils aufgefordert, einen weiteren Token zu lesen. Somit entfällt die Notwendigkeit, die Zusatzinformationen längerfristig vorzuhalten. Sie sind immer nur zum aktuellen Token verfügbar. Der in Abschnitt 5.1 beschriebene Tokenstrom vom Scanner zum Parser ist also nur konzeptionell vorhanden.
Im Nachhinein habe ich festgestellt, daß der in der Klassenbibliothek ET++ für die dort integrierte Programmierumgebung ET++PE verwendete (C++-) CodeAnalyser exakt die gleiche Struktur aufweist. (Ich betrachte dies als zusätzliche Bestätigung meines Designs.) Da dort wesentlich weniger Informationen extrahiert werden, ist dort jedoch auf die Trennung von Scanner und Parser verzichtet worden.
Neben dem für Sniff+ spezialisierten Parser habe ich als weitere Verfeinerungen des Eiffel-Parsers eine Ausgabe der Vererbungshierarchie als Eingabe für ein Graphen-Layout Programm (VCG) realisiert bzw. eine Variante mit Textausgabe (für das Debugging des Parsers). (In dieser Art könnte man beispielsweise auch das traditionelle Eiffel-Werkzeug short mit meinem Parser realisieren.)
Eine Schwachstelle dieses Design ist, daß die Zahl und Art der zur Konkretisierung vorgesehenen Methoden zu Anfang nur auf (eher vagen) Annahmen beruhen, welche Informationen die abgeleiteten Klassen benötigen werden. Wie bei den meisten Frameworks sind mehrere Redesign-Zyklen nötig, bis sich diese Schnittstelle stabilisiert. Bei Änderungen an den Parametern dieser Methoden sind Änderungen in allen abgeleiteten Klassen notwendig. (Der Änderungsbedarf wird allerdings vom Compiler erkannt, so daß die Änderungen nicht vergessen werden können.) Da die Methoden leer und nicht abstrakt implementiert sind, bereitet hingegen das Hinzufügen neuer ActOn...()-Methoden keine Probleme.
7.2. Error-Recovery
Error-Recovery dient dazu, den Parser nach einem Syntaxfehler wieder mit der syntaktischen Struktur seiner Eingabedaten zu synchronisieren. Bei traditionellen Parsern wird Error-Recovery dazu verwendet, um mehr als einen Syntaxfehler je Parserlauf finden zu können. Je nachdem, wie gut die eingesetzte Error-Recovery-Strategie ist, kann der Parser seine Arbeit (evtl. nach einigen Folgefehlern) fortsetzen.
Bei einem Fuzzy-Parser ist es ebenfalls notwendig, Error-Recovery einzusetzen. Obwohl keine Fehler gesucht werden, kann es leicht vorkommen, daß ein Syntaxfehler erkannt wird. Um trotzdem noch maximal viele Informationen über die Struktur des Quelltextes sammeln zu können, ist die Synchronisation mit den Eingabedaten auch hier sehr wichtig.
Um die Synchronisation mit den Eingabedaten zu erreichen, gibt es (nach [Watson 89]) zwei Möglichkeiten: Entweder werden zusätzliche Symbole in den Eingabestrom hinzugefügt (sog. Konstruktiv-orientierte Recovery), oder es werden solange Eingabesymbole übergangen, bis für den Parser erkennbar ist, welches syntaktische Konstrukt im Eingabestrom gerade beginnt (sog. Panische Recovery).
Die Strategie des Hinzufügens von Symbolen ist nur sehr eingeschränkt einsetzbar, da hierzu mit hinlänglicher Sicherheit festgestellt werden muß, was der Programmierer eigentlich wollte bzw. welches Symbol er vergessen hat. Sie hat (wenn sie gelingt) den Vorteil, daß keinerlei Informationen durch den Fehler verloren gehen. In meinem Fuzzy-Parser wird diese Strategie für fehlende Kommas und Semikolons eingesetzt.
Das Ignorieren von Eingabedaten ist potentiell mit Informationsverlust verbunden. Daher sollten so wenig wie möglich Daten ignoriert werden. Die Zustände, in denen der Parser mit (relativer) Sicherheit erkennen kann, welches syntaktische Konstrukt in seiner Eingabe vorliegt, nennt man Wiederaufsetzpunkte.
Als Wiederaufsetzpunkt nach Fehlern in Eiffel-Programmen kann spätestens das Dateiende (was auf jeden Fall mit dem Klassenende zusammenfällt) verwendet werden. So geht maximal die Information über den Teil der Klasse zwischen Fehler und Klassenende verloren, sofern dazwischen nicht noch ein anderer Wiederaufsetzpunkt liegt, der den Verlust weiter minimiert.
Innerhalb des Klassenheaders dienen die Schlüselworte INDEXING, DEFERRED, EXPANDED, CLASS, OBSOLETE, INHERIT und CREATION als Wiederaufsetzpunkte; d.h. ein Syntaxfehler in einer dieser Deklarationen führt nicht dazu, daß der Rest der Headers falsch interpretiert wird.
Auf ein Wiederaufsetzen innerhalb der Feature-Deklarationen wurde mangels geeigneter Wiederaufsetzpunkte verzichtet.
7.3. Test des Fuzzy-Parsers
Da der Fuzzy-Parser von Hand erstellt wurde, muß man damit rechnen, daß er mehr Fehler enthält als ein automatisch generierter Parser. Ein großes Problem beim Test des Fuzzy-Parsers war, daß sich seine Struktur nur grob an den einzelnen Produktionen der Grammatik orientiert und oft mehrere Produktionen zusammengefaßt sind. Weiterhin werden z.T. Fehler antizipiert (z.B. Verwechslung von Komma und Semikolon), so daß sich die Struktur des Fuzzy-Parsers noch weiter von der Grammatik entfernt.
Um möglichst ausgiebig zu testen, wurde der Fuzzy-Parser auf die mir zur Verfügung stehenden Quelltexte der Standardbibliothek von SiG Eiffel/S angewendet. Bei den enthaltenen ca. 10.000 Zeilen Quelltext ist kein Fehler aufgetreten.
Weiterhin wurde der Parser getestet mit dem von Neil Wilson[8] entwickelten Eiffel Torture Test (siehe [Wilson 94b], [Wilson 94c] und [Wilson 94d]). Dieser Test bemüht sich, möglichst viele syntaktischen Varianten zu enthalten / zu testen. Es handelt sich allerdings nicht um eine vollständige Validations-Suite, wie sie beispielsweise für COBOL verfügbar ist. Immerhin wird aber eine sehr große Zahl der syntaktischen Varianten abgedeckt.
Durch den Einsatz des Eiffel Torture Test habe ich während der Entwicklung des Parsers eine ganze Reihe von Fehlern gefunden, die mir beim Testen mit eher zufällg ausgewählten Beispielprogrammen sicher entgangen wären.