Allgemein

Aufgabe des lexikalischen Scanners ist die Realsierung der ersten Compilerphase. In der lexikalischen Analysephase wird der Zeichenstrom des Quellcodes zeichenweise auf nach definierten Mustern entsprechenden zusammenhängenden Einheiten hin untersucht. Gefundene Übereinstimmungen, auch Lexeme genannt, werden weiterhin zu logischen Einheiten gruppiert, den sogenannten Token. Ein Token setzt sich aus einem Namen sowie einem aus dem Lexem abgeleiteten Attributwert zusammen. Der Lexer liefert als Ausgabe einen Tokenstrom. Ein Lexergenerator bietet darüber hinaus dem Anwender die Möglichkeit zur Spezifikation des Lexers per reguläre Ausdrücke.

Überblick

Die Architektur des Lexergenerators verteilt die zu realisierenden Aufgaben im wesentlichen auf die Komponenten RegexToDfaConverter, Dfaprovider, TokenMatcher mit Fehlerbehandlung und BufferdReader. Die zur Verarbeitung notwendigen Daten bezieht der Lexer aus den Dateien TokenDefinition, SourceCode und PersistentDfa.

Die in der Datei zur Tokendefinition hinterlegten regulären Ausdrücke werden zunächst eingelesen und entsprechend aufbereitet an die RegexToDfaConverter-Komponente geliefert. Diese erstellt einen minimierten deterministischen endlichen Automaten (DEA/DFA) je nach Einstellung direkt oder indirekt über einen nichtdeterministischen endlichen Automaten (NEA/NFA). Der endliche Automat (EA/FSM) ist als Zustandsautomat über mit Übergängen verbundene Zustände implementiert. Der Vorgang der Automatenerstellung ist zeitintensiv. Und da sich bei gleichbleibende Definition der Automat nicht ändert, ist das Vorhalten eines einmal erstellten Automaten naheliegend. Das gegebenfalls Neuerstellen eines Automaten sowie das damit einhergehende Abspeichern als persistentes Objekt als auch das einfache schnelle Laden einer vorhandenen Zustandsmaschine händelt der DfaProfider. Der TokenMatcher liest zeichenweise die Quellcodedatei über den BufferdReader ein und erkennt mittels des Zustandsautomaten Lexeme, aus denen mittels der an die Endzustände gebundenen Zusatzinformation Token erzeugt werden.

Tokendefinition

Tokendefinitionen sind aufgebaut in einen deklarativen und einen Regelteil. Der Regelteil wird durch %% abgetrennt. Im deklarativen Teil können Definition erstellt werden, die im Regelteil benutzt werden können. Außerdem dürfen Definition selber Definition enthalten. Namen für Definitionen dürfen nur aus alphabetischen Zeichen bestehen, also [a-zA-Z]. Eine Definition besteht aus einem regulären Ausdruck und einem Bezeichner für den regulären Ausdruck. Ein Bespiel wäre:

[a-zA-Z]          {alpha}
[0-9]             {num}  
({alpha}|{num})*  {alphanumeric}
%%

Die regulären Ausdrücke müssen mit Tabs von den Bezeichner seperariert werden. Definition sind optional allerdings muss der Seperator %% immer vorhanden sein.

Der Regelteil besteht aus regulären Ausdrücken und aus Regeln, die angewandt werden sollen, wenn der Ausdruck auf eine Zeichenkette passt. Das Matching folgt identisch dem Pattern-Matching von Haskell von oben nach unten. Das erzwingt, dass Bezeichner die gleiche Präfixe wie Keywords enthalten können, immer nach den Keywords definiert werden müssen. In den geschweiften Klammern stehen die Aktionen, dort gibt man den Token-Namen an und optional noch den Value. Für primitive Datentypen ist es möglich Funktionen anzugeben, die nicht den Attributwert des Keywords zurückliefern, sondern gleich den tatsächlichen Wert. Ein Beispiel für die Syntax:

<=                              {return("OP", "LE")}
>=                              {return("OP", "GE")}
==                              {return("OP", "EQ")}
!=                              {return("OP", "NEQ")}    
break                           {return("KEYWORD", "BREAK")}
while                           {return("KEYWORD", "WHILE")}
{num}                           {return("NUM", parseInt())}
{num}?\.{num}                   {return("RAT", parseDouble())}
[a-z]+[a-zA-Z0-9]*              {return("ID", parseString())}

Von der Tokendefinition zum DFA

Die Komponente RegexToDfaConverter sorgt für den Aufbau eines DFA aus gegebenen regulären Ausdrücken. Der Weg vom regulären Ausdruck hin zum DFA geht wahlweise indirekt über den RegexToNfaConverter und NfaToDfaConverter oder direkt über den RegexToDfaConverter. Schließlich stellt der DfaMinimizer sicher, dass der Dfa in minimaler Ausführung als MinimalDfa zur Weitergabe vorliegt.

Indirekte Übersetzung

Die indirekte Übersetzung eines regulären Ausdrucks in einen DFA besteht aus zwei Vorgängen. Zum einen muss zunächst aus dem Regex r ein NFA n erstellt werden, so dass L(r) = L(n), wobei L(r) die durch r spezifizierte Sprache und L(n) die Menge aller durch n erkannten Wörter ist. Zum anderen muss anschließend noch aus dem eben erstellten NFA ein DFA erzeugt werden, der wiederum die gleiche Sprache erkennt, wie der NFA.

Reguläre Ausdrücke zu NFA

Der erste Teil der indirekten Übersetzung (RegexToNfaConverter) beruht auf dem Algorithmus von McNaughton-Yamada-Thompson (siehe Drachenbuch 3.7.4). Der Algorithmus ist syntaxgerichtet, d.h. er arbeitet auf einem Parsebaum und erzeugt für jeden Teilbaum (hier: Teilausdruck) einen neuen NFA. Anschließend werden alle erzeugten NFA's zu einem NFA zusammengefasst. Dies wird durch eine Oder-Verknüpfung der NFA's realisiert. Dabei wird ein neuer Startzustand erstellt und von diesem ein Epsilon-Übergang zu allen anderen NFA erstellt.

NFA zu DFA

Für den zweiten Teil ist die Klasse NfaToDfaConverter und ihre Methode convertToDfa zuständig. Die Übersetzung eines NFA's in einen DFA wird mithilfe der Potenzmengenkonstruktion erledigt (siehe Drachenbuch 3.7.1). Die Zustände des DFA's werden aus den Elementen der Potenzmenge der Zustände des NFA's gebildet. Somit kann der DFA in einem Zustand alle Zustände des NFA's, in denen er sich zu einem bestimmten Zeitpunkt befinden könnte, simulieren.

Direkte Übersetzung

Bei der direkten Übersetzung kann nicht der Weg über die Konvertierung in einen NFA mit dem Algorithmus von McNaughton-Yamada-Thomson [Drachenbuch 3.7.4] durch Einfügen von Epsilon-Übergängen an geeigneter Stelle als Zwischenschritt gegangen werden. Stattdessen kann nach dem im Drachenbuch Kapitel 3.9.5 "Direkte Konvertierung eines regulären Ausdrucks in einen DFA" verfahren werden. Dieses Verfahren setzt auf einen abstrakten Syntaxbaum auf, über dem die Funktionen Nullable, FirstPos, LastPos und FollowPos berechnet wurden. Zur Erstellung des Syntaxbaumes wird ein ItemAutomat eingesetzt, welcher die Grammatik für reguläre Ausdrücke zum Aufbau der Parsetabelle überreicht bekommt, mit welcher dann schließlich der Operatorbaum erstellt wird. Der im Buch aufgezeigte Algorithmus eignet sich zum Aufbau eines DFA, mit welchem getestet werden kann, ob eine Eingabe von dem dem Automaten zugrunde liegenden regulären Ausdruck abgedeckt wird, oder auch nicht. Zum Erkennen eines Lexems ist es aber notwendig, dass jedem Tokentyp ein eigener Endzustand zugeordnet ist. Der Algoritmus musste also dahingehend abgewandelt werden.

Automatenminimierung

Minimiert den gegebenen Dfa mittels Markierungsalgorithmus basierent auf dem Satz von Myhill-Nerode.

Der Algorithmus: Der Algorithmus basiert darauf, dass festgestellt wird, welche Zustände unterschiedliche Pfade repräsentieren und das man die Zustände, die nicht zusammengefasst werden können, herausfindet und dann die restlichen verschmilzt. Zuerst wird eine Übersicht erstellt, wo tabellarisch disjunkte Zuständspaare aufgeführt sind. Dann wird jedes Paar, bei dem einer der Zustände ein Endzustand ist, markiert. (diese Zustände können nicht zusammengefasst werden) Als nächstes werden alle möglichen Kombinationen aus den Paaren und Übergängen in der Tabelle eingetragen, was zu einer Menge an Einträgen aus Übergangspaaren führt. Anschließend wird überprüft, welche Einträge der Übergangspaare in der Tabelle bereits markiert sind. Die Paare, deren Übergangspaar markiert ist, werden ebenfalls markiert. Diesen Vorgang wiederholt man bis keine Änderung mehr eintritt. Die restlichen Paare können dann jeweils zu einem Zustand zusammengefasst werden.

Bereithaltung des Dfa

Der DfaProvider stellt den DFA für den TokenMatcher bereit. Die Erzeugung des DFA delegiert der DfaProvider an den RegexToDfaConverter. Den erhaltenen DFA speichert der DfaProvider zunächst als persistentes Objekt für die spätere Wiederverwendung. Sofern solch ein persistentes Objekt zu einer bekannten Sprache bereits vorhanden ist, wird anstelle der erneuten Erzeugung eines DFA das gespeicherte Objekt geladen und bereitgestellt.

Der genaue Programmablauf innerhalb des DfaProviders ist der obigen Abbildung zu entnehmen. Dabei sind die zwei wichtigsten Eingabeparameter (1) die reguläre Definitionsdatei und (2) der MinimalDfaBuilder (Schnittstellenkomponente des RegexToDfaConverter). Alle weiteren Parameter bezüglich der Deserialisierung oder Serialisierung sowie der persistent abgespeicherte Automat (mit zusätzlichen Parametern) sind optional und können bei Bedarf weggelassen werden.

TokenMatcher

Fordert auf Anfrage des Parsers nach einem weiteren Token den Quellcode an momentaner Position zeichenweise vom BufferedReader an und ändert entsprechend den aktuellen Zustand im DFA. Dabei werden bedeutungslose Leerräume sowie Kommentare herausgefiltert. Liefert bei erfolgreichem Erkennen eines Lexem das zugehörige Token zurück. Bei Auftreten etwaiger Fehler wird zunächst mit gewählter Fehlerbehandlungsmethode versucht, diese abzufangen.

(TODO ...)

ErrorHandler

Führt die Fehlerbehandlung im gewählten Fehlerbehebungsmodus durch. Zur verfügung stehen PanikMode und PhraseLevelMode mit den entsprechenden die Aktionen Löschen, Einfügen, Ersetzen und Vertauschen von Zeichen.

(TODO ...)

BufferedReader

Liest den Quellcode in ein Pufferpaar mit Wächtern. Liefert auf Anfrage das nächste Zeichen im Lookahead oder ermöglicht gegebenenfalls auch Rückschritte.

(TODO ...)