Robert Sedgewick: Algorithmen

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


21. Syntaxanalyse (Parsing)



Bottom-Up-Syntaxanalyse

Obwohl das obige Programm mehrere rekursive Aufrufe enthält, ist es eine nützliche Übung, die Rekursion systematisch zu beseitigen. Aus Kapitel 5 wissen wir, daß jeder Prozeduraufruf durch ein Ablegen in einem Stapel und jeder Rücksprung aus einer Prozedur durch ein Entnehmen aus einem Stapel ersetzt werden kann, dadurch wird das Verhalten eines Pascal-Systems bei der Rekursion imitiert. Ebenso wissen wir, daß viele Aufrufe, die rekursiv zu sein scheinen, nicht wirklich rekursiv sind. Wenn ein Prozeduraufruf die letzte Anweisung einer Prozedur ist, so kann eine einfache goto-Anweisung benutzt werden. Dies verwandelt Ausdruck und Term in einfache Schleifen, die gemischt und mit Faktor kombiniert werden können, so daß eine einzige Prozedur mit einem echten rekursiven Aufruf (dem Aufruf von Ausdruck in Faktor) erzeugt wird.

Diese Betrachtung führt unmittelbar zu einer sehr einfachen Methode, wie geprüft werden kann, ob reguläre Ausdrücke zulässig sind. Nachdem alle Prozeduraufrufe beseitigt worden sind, sehen wir, daß jedes terminale Symbol einfach durchlaufen wird, wenn es angetroffen wird. Die einzige echte Verarbeitung, die erfolgt, besteht in der Prüfung, ob für jede linke Klammer eine zugehörige rechte Klammer vorhanden ist, ob nach jedem »+« entweder ein Buchstabe oder eine Klammer »(« folgt und ob jedes »*« entweder einem Buchstaben oder einer Klammer »)« folgt. Das heißt, daß die Prüfung, ob ein regulärer Ausdruck zulässig ist, im wesentlichen zu einer Prüfung auf korrekte Klammernsetzung äquivalent ist. Dies läßt sich leicht implementieren, indem man einen mit 0 initialisierten Zähler führt, der inkrementiert wird, wenn eine linke Klammer angetroffen wird, und dekrementiert, wenn eine rechte Klammer vorgefunden wird. Wenn der Zähler am Ende des Ausdrucks den Wert 0 hat, keine schließende Klammer direkt auf eine öffnende folgte und die Symbole »+« und »*« im Ausdruck den obengenannten Forderungen genügen, so war der Ausdruck zulässig.

Natürlich gehört zur Syntaxanalyse mehr als die einfache Prüfung, ob die eingegebene Zeichenfolge zulässig ist; die Hauptaufgabe besteht in der Produktion des Syntaxbaumes für die weitere Verarbeitung (selbst wenn dies wie beim Top-Down-Parser nur implizit erfolgt). Es zeigt sich, daß sich dies mit Programmen realisieren läßt, die ähnlich strukturiert sind wie das im vorigen Abschnitt vorgestellte Programm für die Überprüfung der Klammern. Ein Typ eines Parsers, der in dieser Weise abläuft, ist der sogenannte shift-reduce-Parser. Die Idee besteht darin, einen Stapel zu verwenden, der terminale und nichtterminale Symbole aufnimmt. Jeder Schritt der Syntaxanalyse ist entweder ein verschiebender (shift) Schritt, bei dem das nächste eingegebene Zeichen einfach im Stapel abgelegt wird, oder ein reduzierender (reduce) Schritt, bei dem die im Stapel oben befindlichen Zeichen auf Übereinstimmung mit der rechten Seite einer Produktion in der Grammatik geprüft und auf das auf der linken Seite dieser Produktion befindliche nichtterminale Symbol »reduziert« (d. h. durch dieses ersetzt) werden. (Die Hauptschwierigkeit bei der Erstellung eines shift-reduce-Parser besteht darin zu entscheiden, wann zu schieben und wann zu reduzieren ist. Dies kann je nach Grammatik eine komplizierte Entscheidung sein.) Letztendlich werden alle eingegebenen Zeichen im Stapel abgelegt, und schließlich wird der Stapel auf ein einziges nichtterminales Symbol reduziert. Ein einfaches Beispiel für einen solchen Parser stellen die in den Kapiteln 3 und 4 angeführten Programme dar, die ausgehend von einem zunächst in einen Postfix umgewandelten Infix-Ausdruck einen Syntaxbaum erzeugen.

Für reale Programmiersprachen wird im allgemeinen die Bottom-Up-Syntaxanalyse als zu bevorzugende Methode betrachtet, und es existiert eine umfangreiche Literatur zur Erstellung von Parsern für umfangreiche Grammatiken des Typs, der für die Beschreibung einer Programmiersprache benötigt wird. Unsere kurze Beschreibung streift lediglich die Oberfläche der damit zusammenhängenden Fragen.


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