Robert Sedgewick: Algorithmen

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


21. Syntaxanalyse (Parsing)



Es wurden verschiedene grundlegende Algorithmen entwickelt, um zulässige (korrekte) Programme zu erkennen und sie in einer Weise zu zerlegen, die eine weitere Verarbeitung ermöglicht. Diese Operation, die Syntaxanalyse oder Parsing genannt wird, besitzt auch außerhalb der Informatik Anwendungen, da sie unmittelbar mit der Untersuchung der Struktur von Sprachen im allgemeinen zusammenhängt. Zum Beispiel spielt die Syntaxanalyse in Systemen, die versuchen, natürliche (menschliche) Sprachen zu verstehen, eine ebenso wichtige Rolle wie in Systemen für die Übersetzung aus einer Sprache in eine andere. Von Interesse ist auch der Spezialfall der Übersetzung aus einer höheren Programmiersprache, wie etwa Pascal (geeignet für die Benutzung durch den Anwender), in eine Assembler- oder Maschinensprache (geeignet für die Ausführung durch den Computer). Ein Programm für die Realisierung einer solchen Übersetzung
wird Compiler genannt. Übrigens haben wir bereits eine Methode der Syntaxanalyse gestreift, und zwar in Kapitel 4, als wir einen Baum konstruierten, der einen arithmetischen Ausdruck darstellt.

Zwei grundsätzliche Vorgehensweisen werden für die Syntaxanalyse genutzt. Top-Down-ablaufende Methoden überprüfen ein Programm auf Zulässigkeit, indem sie zuerst die Teile eines zulässigen Programms bestimmen, dann Teile von Teilen usw., bis die Teile klein genug sind, um direkt auf Übereinstimmung mit den Eingabedaten geprüft werden zu können. Bottom-Up-Methoden setzen Teile der Eingabedaten in einer strukturierten Weise so zusammen, daß immer größere Teilstücke entstehen, bis ein zulässiges Programm konstruiert worden ist. Im allgemeinen sind Top-Down-Methoden rekursiv, Bottom-Up-Methoden dagegen iterativ; Top-Down-Methoden lassen sich gewöhnlich leichter implementieren, Bottom-Up-Methoden gelten dagegen als effizienter. In Kapitel 4 hatten wir es mit einem Bottom-Up-Verfahren zu tun; im vorliegenden Kapitel untersuchen wir eine Top-Down-Methode ausführlich.

Eine vollständige Behandlung der mit der Entwicklung von Parsern (Syntaxanalyse-Programmen) und Compilern zusammenhängenden Fragen würde mit Sicherheit über den Rahmen dieses Buches hinausgehen. Trotzdem werden wir in der Lage sein, einige der dabei verwendeten Grundideen zu betrachten, indem wir einen einfachen »Compiler« erstellen, der den Pattern Matching-Algorithmus aus dem vorangegangenen Kapitel vervollständigt. Zunächst konstruieren wir einen Parser für eine einfache Sprache, die der Beschreibung regulärer Ausdrücke dient. Danach modifizieren wir diesen Parser so, daß er reguläre Ausdrücke in Pattern Matching-Automaten umwandelt, die von der Prozedur match aus dem vorangegangenen Kapitel benutzt werden können.

Unsere Absicht besteht in diesem Kapitel darin, ein gewisses Gefühl für die Grundprinzipien der Syntaxanalyse und Kompilierung zu vermitteln und dabei gleichzeitig einen nützlichen Pattern Matching-Algorithmus zu entwickeln. Die hierbei auftretenden Fragen können wir sicherlich nicht so gründlich behandeln, wie sie es verdient hätten. Wenn der Leser denselben Ansatz auf ähnlich gelagerte Probleme anwenden will, sollte er sich dessen bewußt sein, daß eine Vielzahl kniffliger Probleme auftreten können. Der Compilerbau ist jedoch ein sehr weitentwickeltes Gebiet, daß für ernsthafte Anwendungen eine Vielzahl leistungsfähiger Verfahren zur Verfügung stellt.


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