Robert Sedgewick: Algorithmen

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


21. Syntaxanalyse (Parsing)



Kontextfreie Grammatiken

Bevor wir ein Programm zur Bestimmung der Zulässigkeit eines in einer gegebenen Sprache erstellten Programmes schreiben können, benötigen wir eine Beschreibung, die angibt, woraus genau ein zulässiges Programm zusammengesetzt ist. Diese Beschreibung wird Grammatik genannt; der Sinn dieser Terminologie ist leicht einzusehen, wenn man sich vorstellt, daß es sich um die deutsche Sprache handelt und in dem vorangegangenen Satz das Wort »Programm« durch »Satz« ersetzt (außer beim ersten Auftreten). Programmiersprachen werden oft durch einen speziellen Grammatiktyp beschrieben, der kontextfreie Grammatik genannt wird. Als Beispiel wird nachfolgend die kontextfreie Grammatik angegeben, die die Menge aller zulässigen regulären Ausdrücke definiert (so wie sie im vorangegangenen Kapitel beschrieben wurde).

    <Ausdruck> ::= <Term> | <Term> + <Ausdruck>
        <Term> ::= <Faktor> | <Faktor> <Term>
      <Faktor> ::= (<Ausdruck>) | v | (<Ausdruck>)* | v*

Diese Grammatik beschreibt reguläre Ausdrücke von der Art, wie wir sie im letzten Kapitel verwendet haben, wie etwa (1+01)*(0+1) oder (A*B+AC)D. Jede Zeile in der Grammatik wird eine Produktion (production) oder Regel genannt. Die Produktionen bestehen aus den in der beschriebenen Sprache benutzten terminalen Symbolen (, ), + und * (»v«, ein spezielles Symbol, steht für einen beliebigen Buchstaben oder eine beliebige Ziffer), weiterhin aus den nichtterminalen Symbolen <Ausdruck>, <Term> und <Faktor>, die interne Symbole der Grammatik sind, sowie aus den Metasymbolen ::= und |, die verwendet werden, um die Bedeutung der Produktionen zu beschreiben. Das Symbol ::=, das »ist ein« gelesen werden kann, definiert die linke Seite der Produktion mit Hilfe der rechten Seite, und das Symbol |, welches als »oder« gelesen werden kann, gibt mögliche Alternativen an. Die verschiedenen Produktionen entsprechen trotz dieser knappen Schreibweise auf einfache Weise einer intuitiven Beschreibung der Grammatik. Beispielsweise könnte die zweite Produktion im angegebenen Beispiel einer Grammatik wie folgt gelesen werden: »Ein <Term> ist ein <Faktor> oder ein <Faktor>, dem ein <Term> folgt«. Ein nichtterminales Symbol, in diesem Falle <Ausdruck>, ist in dem Sinne herausragend, daß eine Folge von terminalen Symbolen dann und nur dann der durch die Grammatik beschriebenen Sprache angehört, wenn es eine Möglichkeit gibt, unter Anwendung der Produktionen diese Folge aus dem herauragenden nichtterminalen Symbol abzuleiten, indem man (in beliebig vielen Schritten) ein nichtterminales Symbol durch irgendeine der Alternativen auf der rechten Seite einer Produktion für dieses nichtterminale Symbol ersetzt.

Ein natürlicher Weg zur Beschreibung des Ergebnisses dieses Ableitungsprozesses ist ein Syntaxbaum (parse tree), ein Diagramm der vollständigen grammatischen Struktur der Zeichenfolge, für die die Syntaxanalyse vorgenommen wird. Beispielsweise zeigt der in Abbildung 21.1 dargestellte Syntaxbaum, daß die Zeichenfolge (A*B+AC)D in der durch die obige Grammatik beschriebenen Sprache enthalten ist. Syntaxbäume dieser Art werden manchmal für die deutsche Sprache benutzt, um einen Satz in Subjekt, Prädikat, Objekt usw. zu zerlegen.

Abbildung 21.1
Abbildung 21.1 Syntaxbaum für (A*B+AC)D.

Die Hauptaufgabe eines Parsers besteht darin, Zeichenfolgen, die auf diese Weise abgeleitet werden können, anzunehmen bzw. die, bei denen das nicht möglich ist, zurückzuweisen, indem er versucht, für eine beliebige gegebene Zeichenfolge einen Syntaxbaum zu konstruieren. Das bedeutet, daß der Parser erkennen kann, ob eine Zeichenfolge in der durch die Grammatik beschriebenen Sprache enthalten ist, indem er feststellt, ob für die Zeichenfolge ein Syntaxbaum existiert oder nicht. Top-Down-Parser tun dies, indem sie den Baum in der Weise aufbauen, daß sie mit dem herausragenden nichtterminalen Symbol oben beginnen und dann abwärts in Richtung auf die unten befindliche zu erkennende Zeichenfolge vorgehen. Bottom-Up-Parser arbeiten, indem sie mit der Zeichenfolge unten beginnen und rückwärts nach oben in Richtung auf das herausragende nichtterminale Symbol vorgehen. Wie wir noch sehen werden, kann der Parser durch Umwandlung in eine interne Darstellung auch die Weiterverarbeitung erleichtern, wenn der Inhalt der erkannten Zeichenfolgen eine solche Weiterverarbeitung benötigt.

Ein weiteres Beispiel für eine kontextfreie Grammatik ist im Anhang des Pascal User Manual and Report zu finden: Diese Grammatik beschreibt zulässige Pascal-Programme. Die im vorliegenden Abschnitt betrachteten Prinzipien für die Erkennung und Verwendung zulässiger Ausdrücke lassen sich unmittelbar auf die komplexe Aufgabe der Kompilierung und Ausführung von Pascal-Programmen anwenden. Zum Beispiel beschreibt die folgende Grammatik eine sehr kleine Teilmenge von Pascal, nämlich arithmetische Ausdrücke, in denen Addition und Multiplikation vorkommen:

    <Ausdruck> ::= <Term> | <Term> + <Ausdruck>
        <Term> ::= <Faktor> | <Faktor> * <Term>
      <Faktor> ::= (<Ausdruck>) | v

Diese Regeln beschreiben in einer formalen Weise das, was wir in Kapitel 4 als gegeben annehmen konnten: Es sind die Regeln, die festlegen, woraus »zulässige« arithmetische Ausdrücke bestehen. Auch hier ist v ein spezielles Symbol, das für einen beliebigen Buchstaben steht, doch in dieser Grammatik bezeichnen die Buchstaben gewöhnlich Variablen, die Zahlenwerte annehmen. Beispiele zulässiger Zeichenfolgen für diese Grammatik sind A+(B*C) und A*(((B+C)*(D*E))+F). Für den letzteren Ausdruck haben wir bereits in Kapitel 4 einen Syntaxbaum angegeben, doch jener Baum entspricht nicht der obigen Grammatik; zum Beispiel sind Klammern nicht explizit enthalten.

Gemäß unseren Definitionen sind gewisse Zeichenfolgen sowohl als arithmetische Ausdrücke als auch als reguläre Ausdrücke absolut zulässig. Zum Beispiel könnte A*(B+C) bedeuten »addiere B zu C und multipliziere das Ergebnis mit A« oder »nehme eine beliebige Anzahl von As, denen entweder B oder C folgt«. Dies verdeutlicht die offensichtliche Tatsache, daß die Prüfung der Zulässigkeit einer Zeichenfolge eine Angelegenheit ist, die Interpretation ihrer Bedeutung jedoch eine ganz andere. Wir werden zu dieser Frage zurückkehren, nachdem wir gesehen haben, wie die Syntaxanalyse einer Zeichenfolge vorzunehmen ist, um zu prüfen, ob sie durch eine bestimmte Grammatik beschrieben wird oder nicht.

Jeder reguläre Ausdruck ist selbst ein Beispiel für eine kontextfreie Grammatik: Jede Sprache, die durch einen regulären Ausdruck beschrieben werden kann, kann auch durch eine kontextfreie Grammatik beschrieben werden. Die Umkehrung gilt nicht: Zum Beispiel kann die Forderung des »Ausgleichens« von Klammern mit regulären Ausdrücken nicht erfaßt werden. Andere Arten von Grammatiken können Sprachen beschreiben, die kontextfreie Grammatiken nicht beschreiben können. Zum Beispiel sind kontextsensitive Grammatiken ebensolche Grammatiken wie die obigen, mit dem Unterschied, daß die linken Seiten von Produktionen nicht einzelne nichtterminale Symbole sein müssen. Die Unterschiede zwischen Sprachklassen und einer Hierarchie von Grammatiken für ihre Beschreibung sind sehr gründlich untersucht worden und bilden eine sehr schöne Theorie, die zum Kern der Informatik gehört.


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