Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


21. Syntaxanalyse (Parsing)



Compiler-Compiler

Das Programm für das allgemeine Pattern Matching regulärer Ausdrücke, das wir in diesem und im vorangegangenen Kapitel entwickelt haben, ist effizient und sehr nützlich. Eine Variante dieses Programms mit einigen zusätzlichen Erleichterungen (für die Behandlung von Jokern usw.) gehört sicherlich zu den am häufigsten benutzten Hilfsprogrammen in vielen Computersystemen.

Es ist interessant (man könnte auch sagen, verwirrend), von einem eher philosophischen Standpunkt aus über diesen Algorithmus nachzudenken. In diesem Kapitel haben wir Parser für die Aufschlüsselung der Struktur regulärer Ausdrücke betrachtet, die auf einer formalen Beschreibung regulärer Ausdrücke unter Benutzung einer kontextfreien Grammatik beruhen. Anders gesagt, wir benutzten die kontextfreie Grammatik, um ein spezielles »Muster« vorzugeben, eine Folge von Zeichen mit in zulässiger Weise verwendeten Klammern. Das bedeutet, das Syntaxanalyse und Pattern Matching im wesentlichen die gleiche Funktion ausführen! Hier wird geprüft, ob eine eingegebene Zeichenfolge durch eine bestimmte kontextfreie Grammatik definiert wird; dort wird geprüft, ob eine eingegebene Zeichenfolge durch einen bestimmten regulären Ausdruck definiert wird. Der Hauptunterschied besteht darin, daß kontextfreie Grammatiken in der Lage sind, eine weit umfangreichere Klasse von Zeichenfolgen zu beschreiben. Zum Beispiel können reguläre Ausdrücke nicht die Menge aller regulären Ausdrücke beschreiben.

Ein weiterer Unterschied zwischen den Programmen ist, daß die kontextfreie Grammatik in den Parser »eingebaut« ist, während die Prozedur match »tabellengesteuert« ist: Ein und dasselbe Programm funktioniert für alle regulären Ausdrücke, nachdem diese in das geeignete Format umgewandelt worden sind. Es erweist sich, daß es möglich ist, Parser zu bauen, die in der gleichen Weise tabellengesteuert sind, so daß das gleiche Programm verwendet werden kann, um die Syntaxanalyse aller Sprachen vorzunehmen, die mittels kontextfreier Grammatiken beschrieben werden können. Ein Parser-Generator ist ein Programm, das eine Grammatik als Eingabe verwendet und als Ausgabe einen Parser für die von dieser Grammatik beschriebene Sprache erzeugt. Man kann noch einen Schritt weiter gehen: Man kann Compiler herstellen, die sowohl hinsichtlich der Eingangs- als auch hinsichtlich der Ausgangssprache tabellengesteuert sind. Ein Compiler-Compiler ist ein Programm, das zwei Grammatiken (und eine Beschreibung des Zusammenhangs zwischen ihnen) als Eingabe verwendet und als Ausgabe einen Compiler erzeugt, der Zeichenfolgen aus einer Sprache in die andere übersetzt.

Parser-Generatoren und Compiler-Compiler stehen in vielen Datenverarbeitungssystemen für die allgemeine Benutzung zur Verfügung und sind sehr nützliche Werkzeuge, die verwendet werden können, um mit relativ geringem Aufwand effiziente und zuverlässige Parser und Compiler zu erzeugen. Andererseits sind rekursiv-absteigende Parser des hier betrachteten Typs sehr brauchbar für die einfachen Grammatiken, die in vielen Anwendungen auftreten. Demzufolge verfügen wir, wie bei vielen der von uns betrachteten Algorithmen, über eine sehr einfache Methode, die für Anwendungen geeignet ist, bei denen ein hoher Aufwand für die Implementation nicht gerechtfertigt ist, sowie über verschiedene höherentwickelte Methoden, die für umfangreichere Anwendungen zu beträchtlichen Verbesserungen der Leistungsfähigkeit führen können. Wie oben bereits gesagt wurde, haben wir nur die Oberfläche dieses sehr gründlich untersuchten Feldes berührt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]