6. Möglichkeiten zur Erstellung der Datenbasis für den Browser
Es wäre wünschenswert, wenn der Browser die entsprechenden Informationen vom jeweils verwendeten Eiffel-Compiler bereitgestellt bekommen würde. Man würde so das Wissen über den syntaktischen Aufbau der Sprache mit all seinen Details in einem Werkzeug kapseln. Es wird sich jedoch zeigen, daß die existierenden Compiler aufgrund der unterschiedlichen Anforderungen von Browsern und Compilieren dieser Anforderung nicht gerecht werden können.
Es gibt mehrere Wege, um an die für den Browser notwendigen Informationen über die Struktur des zu untersuchenden Programms zu kommen:
aus dem Laufzeitsystem,
aus der Datenbank des Compilers,
aus dem Quelltext.
6.1. Aus dem Laufzeitsystem
Die erste Möglichkeit besteht darin, die Informationen vom Laufzeitsystem zu gewinnen. Da Eiffel das Vorhandensein von Typinformationen zur Laufzeit voraussetzt, stellt das Laufzeitsystem einiger Eiffel-Umgebungen diese Informationen auch dem Anwendungsprogrammierer zur Verfügung. Die Typinformationen werden vom Laufzeitsystem für Typprüfungen, z.B. beim "reverse assignment attempt", benötigt, bei dem versucht wird, einer Variablen der Unterklasse eine Variable der Oberklasse zuzuweisen.
Die zur Verfügung stehenden Informationen umfassen aber meist wenig mehr als die Vererbungshierarchie und die Methoden der einzelnen Klassen. Man könnte mit diesen Informationen also wenig mehr machen, als einen Vererbungsgraph aufzuzeigen. Schon die Zuordnung der Klassen zu ihren Quelltexten ist nicht immer feststellbar.
Auch ist die Schnittstelle, um diese Informationen zu bekommen, stark von der verwendeten Eiffel-Implementation abhängig, so daß diese Informationsquelle für einen vom Compiler unabhängigen Browser nicht brauchbar ist.
Zudem wäre es nur möglich, Programme zu browsen, die tatsächlich lauffähig sind. Da in der Entwicklung befindliche Programme die meiste Zeit nicht ablauffähig sind (zumindest in den Momenten, in denen sie gerade geändert werden und der Browser am nötigsten gebraucht wird), scheidet diese Möglichkeit vollends aus.
6.2. Aus der Datenbasis des Compilers
Eine andere Möglichkeit, an die Informationen zu kommen, wird ebenfalls von vielen Eiffel-Implementationen angeboten: Nachdem in der ersten Stufe des Eiffel-Compilers der Quelltext analysiert wurde, werden die gewonnenen Informationen in einer lokalen Datenbasis abgelegt. Der Eiffel-Compiler benötigt sie für seine weitere Arbeit. Die Struktur dieser Datenbasis wird bei einigen Compilern offengelegt, so daß ein Browser darauf zugreifen könnte.
Die in der Datenbasis des Compilers verfügbaren Informationen reichen für die meisten Belange eines Browsers aus. Daher greifen die von den Compiler-Herstellern mitgelieferten Browser, z.B. bei ISE Eiffel 3, Eon/Eiffel (vergl. [Eon 94]), meist auf diese Datenbasis zu. Bei dieser Methode müßte das zu untersuchende Programm nicht ablauffähig sein, sondern nur syntaktisch korrekt. Bereits dies stellt aber eine starke und für das Browsen unnötige Einschränkung dar.
Das Problem, daß die Schnittstelle zu den Daten stark herstellerabhängig ist, besteht hier allerdings ebenfalls, so daß einem von einer speziellen Eiffel-Implementation unabhängigen Browser der Zugriff auf die Datenbasis des Compilers nicht offensteht (oder er zumindest eine Anpassung für jede Eiffel-Implementation benötigen würde). In [Strunk 92] wird ein Browser beschrieben, der die Datenbasis von ISE Eiffel 2 benutzt.
6.3. Aus dem Quelltext
Als letzte Informationsquelle steht der zu untersuchende Quelltext selbst zur Verfügung, den der Browser natürlich auch direkt analysieren kann. Dies macht ihn von jedem verwendeten Eiffel-Compiler unabhängig. Der nötige Zusatzaufwand bei der Erstellung macht jedoch auch den Einsatz spezieller Analyse-Techniken möglich, die mit syntaktisch nicht korrekten Programmen umgehen können.
Im Gegensatz zum Compiler benötigt der Browser sehr viel weniger Informationen aus dem Quelltext. Für ihn ist nur die grobe Struktur wichtig, die sich meist auch aus einem unkorrekten Quelltext ablesen läßt.
Der Eiffel-Compiler dagegen muß auf der korrekten Syntax (wie definiert in [Meyer 91]) bestehen. Insbesondere in den Feature-Implementationen (dort, wo ausführbarer Code erzeugt werden muß) kann z.B. das Fehlen eines Semikolon zu einer anderen Interpretation des Programmtextes führen. Da der Programmierer aber nicht in syntaktischen Konstrukten, sondern in höheren Abstraktionen von Klassen und deren Umgangsformen denkt, sind solche Fehler recht häufig. Nötig ist also eine Analyse-Methode, die, soweit möglich, die Struktur des Quelltextes analysiert, aber die anderen Teile des Quelltextes (und die möglicherweise darin enthaltenen syntaktischen Fehler) ignoriert.
6.3.1. Kurzeinführung Compilerbau
Der Compilerbau (die Erstellung von Compilern) ist eine der älteste Sparten der Informatik. Basierend auf der Automatentheorie wurden Methoden entwickelt, um formale Sprachen (z.B. mit Hilfe von Grammatiken) exakt zu beschreiben.
Eines der klassischen Probleme der Automatentheorie ist das sog. Wortproblem. Es untersucht, ob eine Zeichenkette zu einer formalen Sprache gehört (und somit ein Wort der Sprache ist) oder nicht. Man kann die formalen Sprachen anhand der Struktur ihrer Grammatiken in Klassen unterteilen, bei denen das Wortproblem jeweils mit einer bestimmten Zeitkomplexität gelöst werden kann.
Übertragen auf Programmiersprachen stellt ein Programm (bzw. eine einzeln compilierbare Einheit) ein Wort der Sprache dar. Für dieses Programm ist zu prüfen, ob es Element der Sprache (d.h. syntaktisch korrekt) ist oder nicht. Um diese Aufgabe zu bewältigen, kann man aus der Grammatik einen sog. akzeptierenden Automaten konstruieren, der das zu untersuchende Wort (sprich Programm) als Eingabe erhält und als Ergebnis die Korrektheit des Programms bestätigt oder eben nicht.
Die Entwicklung ist schon seit langem so weit, daß solche (sogar minimale) akzeptierenden Automaten nach festen Regeln aus der Grammatik erzeugt werden können. (Dies gilt nur für eine bestimmte Klasse von Sprachen (die sog. kontextfreien Sprachen). Da die in diesem Zusammenhang wichtigen Programmiersprachen aber praktisch alle so entworfen sind, daß sie dieser Klasse angehören, vernachlässige ich die Diskussion anderer Sprachklassen.)
Die Grammatik, die eine Sprache beschreibt, besteht u.a. aus einem Startsymbol, Ableitungsregeln (sog. Produktionen) und einem Alphabet, aus dem die Worte der Sprache gebildet werden können.
Zur vollständigen Beschreibung von Programmiersprachen reichen Grammatiken und formale Sprachen jedoch nicht aus. Zum einen muß zusätzlich noch die Sematik (Bedeutung) der Konstrukte beschrieben werden, und zum anderen werden häufig über die Grammatik hinaus noch zusätzliche Regeln für die Syntax verwendet[7].
Bei Programmiersprachen besteht ein Zeichen des Alphabets jedoch, der menschlichen Lesbarkeit wegen, meist aus mehreren (ASCII-)Zeichen. Im Compilerbau ist daher die erste Stufe die sog. lexikalische Analyse. Sie fügt die (ASCII-)Zeichen des Programmquelltextes zu Zeichen der Sprache zusammen. Dieser Programmteil wird Scanner genannt. Die erkannten lexikalischen Einheiten werden in sog. Token (üblicherweise in Aufzählungstypen) kodiert, die die lexikalischen Symbole (Schlüsselworte, Bezeichner, Operatoren etc.) darstellen.
Das Beschreibungsmittel, um festzulegen, welche (ASCII-)Zeichen zu einem Zeichen der Sprache zusammengefügt werden dürften, sind reguläre Ausdrücke. Die Erzeugung von Scannern aus regulären Ausdrücken kann automatisch erfolgen. Das bekannteste Werkzeug hierzu ist Lex (siehe [LevMasBro 92]).
Abb. 10: Die Phasen eines Compilers
Die zweite Stufe eines Compilers ist die sog. syntaktische Analyse. Sie entspricht dem akzeptierenden Automaten und stellt fest, ob ein Programm syntaktische Fehler beinhaltet. Dieser Programmteil wird Parser genannt. Entsprechend der automatischen Konstruktion der akzeptierenden Automaten können auch Parser automatisch aus einer Grammatik generiert werden.
Während der syntaktischen Analyse wird eine sog. Symboltabelle aufgebaut, die alle verwendeten Symbole (Funktionsnamen, Variablen etc.) sowie ihren Typ (und diverse Zusatzinformationen) speichert.
Der Parser arbeitet ausschließlich auf dem Strom von sog. Token, die der Scanner liefert. (Zusätzlich kann er Angaben über den Ort des Auftretens und andere Details zum aktuellen Token vom Scanner erfragen.)
Abb. 11: Aufgabenteilung zwischen Scanner und Parser
Die beiden wichtigsten Methoden zur Implementierung eines Parsers sind der rekursive Abstieg (engl. recursive descent), der Top-Down vom Startsymbol aus vorgeht, und die Shift-Reduce Methode, die Bottom-Up arbeitet.
Eine sehr kompakte Anleitung, wie man Parser nach der Methode des rekursiven Abstiegs von Hand aus den Syntaxgraphen einer Sprache erstellen kann, findet sich in [Wirth 77].
Bisher nicht erwähnt habe ich, daß die syntaktische Prüfung ja kein Selbstzweck ist, sondern der Erzeugung eines ablauffähigen Programms dienen soll. Hierzu wird vom Parser üblicherweise ein sog. Ableitungsbaum erzeugt, der beschreibt, welche Produktionen der Grammatik angewendet wurden. Die Produktionen tragen die Semantik der Programmiersprache. Die folgenden Stufen des Compilers heißen daher semantische Analyse und Code-Generierung, d.h. aus dem Ableitungsbaum wird ein ausführbares Programm erzeugt. (Da dieser Vorgang für mich im weiteren keine Rolle spielt, gehe ich nicht weiter darauf ein.)
Abb. 12: Beispiel für einen Ableitungsbaum (vergl. [LevMasBro 92])
Ebenso wie die Scanner können auch die Parser weitgehend automatisch aus der Grammatik erzeugt werden. Der bekannteste Parser-Generator ist YACC (Yet Another Compiler-Compiler, siehe [LevMasBro 92]). Ein weiteres recht verbreitetes Werkzeug, das sowohl einen Scanner-Generator als auch einen Parser-Generator enthält, ist das Cocktail-Toolkit (siehe [Grosch 92]).
Das übliche Vorgehen beim Compilerbau ist es, die Grammatik der Programmiersprache mit einer Grammatik (und regulären Ausdrücken) zu beschreiben und dann automatisch einen Scanner und einen Parser generieren zu lassen. Meist wird nur die Code-Generierung "von Hand" programmiert. Die so erstellten Compiler sind aufgrund der ausgereiften Automatentheorie recht effizient und vor allen recht einfach zu erzeugen.
6.3.2. Traditionelle Parser
Im ersten Anlauf zu dieser Studienarbeit habe ich mich bemüht, einen frei verfügbaren Parser für Eiffel 3 zu finden, um mir die Arbeit zu ersparen, einen eigenen schreiben zu müssen. Ich hatte die Hoffnung, diesen Parser dann nur geringfügig modifizieren zu müssen, um ihn fehlertolerant zu machen.
Von der Freien Universität Berlin stammt der frei verfügbare Eiffel 3 Parser ep [Groeber 92a]. Er wurde mit dem Cocktail-Toolkit erstellt und erzeugt als Ausgabe einen abstrakten Syntaxbaum (AST - abstract syntax tree), der eine Mischung aus Ableitungsbaum und Symboltabelle darstellt. (Da der Shareware Eiffel-Compiler Eon/Eiffel ebenfalls mit dem Cocktail-Toolkit erstellt worden ist (vergl. [Leonard 94]), wäre es sogar denkbar gewesen, später diesen Compiler und meinen Browser auf einer gemeinsamen Datenbasis arbeiten zu lassen.)
ep ist mit ca. 4000 Zeilen / Sek. (laut [Groeber 92b]) recht schnell und entspricht exakt der Eiffel 3 Syntax aus der Sprachdefinition [Meyer 91]. Meine Hoffung, ihn als Unterbau für einen Browser verwenden zu können, hat sich aber trotzdem nicht erfüllt.
Bei der Verwendung von ep wurde sehr schnell die Schwäche von traditionell erstellten Parsern als Grundlage für einen Browser deutlich: Jede kleine syntaktische Unkorrektheit führt zu einer Fehlermeldung (und bei ep sogar zu einem Abbruch) des Parsers. Bei Versuchen mit ep wurde deutlich, wie weit sich die wenigen verfügbaren Eiffel-Implementationen vom Sprachstandard ([Meyer 91]) entfernt haben. Nicht einmal 50% der nach Ansicht der jeweiligen Compiler korrekten (!) Beispielprogramme der Compiler von SiG bzw. ISE konnten vollständig geparst werden. In der Entwicklung befindliche Programme haben sicherlich kaum eine Chance, mit diesem Parser erfolgreich bearbeitet zu werden.
Die Änderungen am Quelltext der Beispielprogramme, um sie an den Parser ep anzupassen, waren zwar minimal, für einen Praxiseinsatz ist es jedoch nicht zu vertreten, daß man sich beim Schreiben des Quelltextes an die Schnittmenge zweier unterschiedlicher Compiler-Syntaxen halten muß. Damit hatte sich ep als Unterbau für einen Browser als unbrauchbar erwiesen.
Dieses Problem liegt nicht bei ep, sondern in der Art, wie die automatisch generierten Parser üblicherweise arbeiten. Zwar gibt es Ansätze zum Wiederaufsetzen nach einem Fehler (zur Fortsetzung der Analyse), aber ihre Hauptaufgabe liegt im Finden von syntaktischen Fehlern und nicht im Erkennen der Programmstruktur.
Ein Lösungsansatz, die Probleme traditioneller Parser im Hinblick auf ihre Fehlertoleranz zu beheben, wäre, die Grammatiken der von ihnen akzeptieren Sprachen zu modifizieren (sog. Fehlerproduktionen hinzuzufügen). So können einige Probleme (z.B. fehlende oder überzählige Semikolons etc.) beseitigt werden. Auf diese Weise kann man aber nicht alle möglichen Fehler antizipieren. Problematisch werden dabei auch die in der Grammatik auftretenden Mehrdeutigkeiten. Dieses Vorgehen ist meiner Ansicht nach nur bei Sprachen mit sehr einfacher Grammatik praktikabel.
6.3.3. Fuzzy-Parser
Ein Lösungsansatz wird in [Bischofberger 92] vorgeschlagen: Fuzzy-Parser. Bischofberger schreibt
"...we have developed a fuzzy recursive descent parser which has only partial understanding of C++, which can deal with incomplete software systems containing errors, and extracts information about where and how the symbols (e.g., classes, members, variables) of a software system are declared and where they are defined. This way only declarations and the headers of (member) functions (i.e., return code, name and argument list) have to be parsed while the executable code in the bodies of (member) functions can be ignored."
Unter einem Fuzzy-Parser versteht man also einen Parser, der versucht, die Struktur des Quelltextes trotz syntaktischer Fehler zu analysieren. Er ist speziell auf die Bedürfnisse eines Browsers zugeschnitten und bemüht sich, nur diese Informationen zu sammeln, so daß ihn Fehler in anderen Bereichen nicht stören können.
Ein Fuzzy-Parser ermöglicht es auch, den Browser mit verschiedenen Eiffel-Dialekten zu verwenden, die eine leicht abweichende Syntax haben (siehe z.B. [Wilson 94a], [SiG 92]).
Da Fuzzy-Parser völlig andere Zielsetzungen haben als traditionelle Parser, sind die Konstruktionsmethoden auch nur bedingt übertragbar. Bei der Beschreibung der Implementation des Fuzzy-Parsers für Eiffel werde ich hierauf noch weiter eingehen.
Ein Beispiel für die abweichende Syntax verschiedener Eiffel-Compiler war die Zulässigkeit bzw. Verpflichtung, an bestimmten Stellen Semikolons zu setzen. Ein Fuzzy-Parser erkennt die Struktur trotzdem, während ein Parser, der auf die korrekte Syntax Wert legt, einen Fehler meldet.
Da ein Fuzzy-Parser nur an der Struktur des Quelltextes interessiert ist, ist er von allen Änderungen, die den ausführbaren Teil des Quelltextes betreffen, vollkommen unberührt.