5.5 LR-Grammatiken

Motivation und Intuition

Die LL-Parser, die wir im letzten Teilkapitel gesehen haben, versuchen, eine Linksableitung Schritt für Schritt zu konstruieren. Eine Hauptschwäche ist, dass Sie von einer Wortform die nächste Ableitungsregel bestimmen müssen, ohne das "Endergebnis" von überhaupt vollständig gelesen zu haben. Sie müssen also erkennen, dass der rote / mit "?" markierte Pfeil in der Ableitung die richtige Entscheidung ist, obwohl sie von dem aus abgeleiteten Wort nur die ersten Buchstaben sehen. Wäre es nicht besser, der Maxime zu folgen:

Ich will diese Maxime an einem Beispiel demonstrieren. Betrachten wir die Grammatik

Die von der Grammatik erzeugte Sprache ist also: mindestens ein und mindestens so viele s wie s. Die Sprache ist nicht LL: Die Ableitungen unterscheiden sich bereits in der ersten angewandten Produktion; trotzdem stimmen die Endergebnisse in den ersten (ja sogar ) Zeichen überein. Ich will nun aber zeigen, wie man eine Ableitung findet, wenn man die obige Maxime befolgt. Hierfür arbeiten wir uns von hinte nach vorne durch: statt mit anzufangen und zu hinzuarbeiten, fangen wir mit an und versuchen, und zu hin zurückzuarbeiten. In der folgenden Animation ist der Teil des Wortes, den unser Parser gelesen hat, schwarz markiert; der noch nicht gelesene Teil ist grau.

Wir erhalten eine Rechtsableitung, allerdings in verkehrter Reihenfolge, vom Zielwort hin zum Startsymbol. Daher schreiben wir in der obigen Animation auch $$ statt $$ geschrieben. Wenn Sie die Animation in verkehrter Reihenfolge anschauen (also immer auf klicken), dann sehen Sie die Rechtsableitung $$ in der "üblichen" Reihenfolge.

Notation

Da aus der Sicht unseres neuen Parsers die Rückwärtsanwendung einer Produktion $$, also der Schritt $$ einen Fortschritt darstellt und zeitlich auch nach vorne geht, verwende ich ab jetzt ein neues Pfeilsymbol, das von links nach rechts geht und daher dem in Europa üblichen Gefühlt, dass die Zeit von links nach rechts verläuft, mehr entgegen kommt: $$.

Beobachtung: Wenn wir einen Linksreduktionsschritt $$ betrachten, also $$ so sehen wir, dass das am weitesten rechts stehende Nichtterminal ersetzt worden ist; Linksreduktionen entsprechen also einer Rechtsableitung.

Vorsicht. Verfallen Sie nicht in verfrühte Euphorie. Das Prinzip der Linksreduktion ist immer noch nichtdeterministisch. Die folgende Abbildung illustriert, dass manchmal mehrere Reduktionen anwendbar sind:

Uns als Betrachter ist klar, dass nur die obere Alternative zum Erfolg führt; wie das der Parser aber im Allgemeinen entscheiden soll, ist uns zu diesem Zeitpunkt noch nicht klar und wird uns für den Rest dieses Kapitels beschäftigen.

Überlegen wir nun, welche Situationen schlecht wären für unser Vorhaben, einen Parser ohne Sackgassen zu implementieren.

1. Schlechter Fall 1: Es gibt für eine Wortform $$ zwei korrekte Linksreduktionsschritte: $$ und $$. In diesem Falle gäbe es zwei verschiedene Rechtsableitungen $$ (wir nehmen an, dass man aus jedem Nichtterminal mindestens ein Wort $$ ableiten kann; andernfalls kann man solche nutzlosen Nichtterminale eliminieren). Das Wort $$ hat also zwei verschiedene Ableitungsbäume. Die Grammatik ist somit mehrdeutig. Mit uneindeutigen Grammatiken beschäftigen wir zunächst gar nicht; sie sind von einem praktischen Standpunkt aus auch unattraktiv: wenn z.B. eine Programmiersprache eine mehrdeutige Grammatik hätte, dann wäre ja für gewisse Programme nicht eindeutig festzustellen, was damit gemeint ist. Wir nehmen also an, dass die Grammatik $$ eindeutig ist und somit dieser Fall nicht eintreten kann.
2. Schlechter Fall 2: Der Linksreduktionsschritt $$ ist korrekt, aber der Schritt $$ ist nicht korrekt, obwohl $$ eine gültige Wortform ist. Dieser Fall ist schlecht, weil der Parser zum Zeitpunkt $$, wenn er also $$ gelesen hat, aber noch nicht $$, sich nicht sicher sein kann, dass der Reduktionsschritt korrekt ist. Korrektheit hängt davon ab, was weiter rechts davon kommt.

Es stellen sich unmittelbar zwei zentrale Fragen:

1. Wie können wir verifizieren, ob eine gegebene Grammatik die $$-Bedingung erfüllt?
2. Falls sie es tut, wie können wir für eine gegebene Wortform $$ den korrekten Reduktionsschritt $$ finden? Insbesondere die Zerlegung in $$?

Beide Aufgaben können mit Hilfe eines endlichen Automaten, des DK-Automaten erledigt werden (DK steht als Abkürzung für Donald Knuth, der als erstes diese Idee hatte).

Gültige Wortformen und deren Ableitungsbäume

Zu jeder Ableitung $$ können wir eindeutig einen Ableitungsbaum zeichnen. Wenn die Grammatik eindeutig ist, so hängt auch der Baum nur vom Wort $$ ab und nicht von der Ableitung $$. Allerdings können wir für Zwischenformen $$ auch einen Ableitungsbaum zeichnen, und der unterscheidet sich stark, abhängig davon, ob $$ eine Rechtsableitung, Linksableitung oder sonst was ist. Ich zeige Ihnen jetzt ein Beispiel für eine Grammatik und eine Handvoll Ableitungen samt Ableitungsbaum. $$ Es ist zu diesem Zeitpunkt irrelevant, ob $$ eindeutig oder sogar $$ ist. Ich interessiere mich gerade nur für Ableitungsbäume von Wortformen.

Fällt Ihnen etwas auf? Schauen Sie sich bitte noch ein weiteres Beispiel an für den Ableitungsbaum einer in einer gültigen Wortform, also von einer, die in einer Rechtsableitung vorkommen kann:

Sie sehen: links vom Stamm gibt es nur Blätter. Rechts vom Stamm ist jedes Blatt ein Terminalsymbol. Wir erkennen auch, was der letzte Ableitungsschritt war, der zu diesem Baum geführt hat: die Blüte ist hinzugekommen, in diesem Fall also $$. Wir definieren nun eingeführten Begriffe formal:

Wir können also, ausgehend von der Wortform $$, eine Linksreduktion $$ finden, indem wir den Ableitungsbaum von $$ zeichnen und immer wieder die Blüte abschneiden:

Um für eine Wortform $$ den korrekten Reduktionsschritt zu finden, reicht es also aus, linken Rand und Blüte zu bestimmen, also $$ und $$, so dass $$ und $$ korrekt ist ($$ steht hier für das Nichtterminal, mit dem der Elternknoten der Blüte beschriftet ist). Linken Rand und Blüte zu finden scheint keine leichte Aufgabe zu sein: schließlich müssen wir dafür doch den Ableitungsbaum von $$ bilden, was selbst wieder eine Parsing-Aufgabe ist???

An dieser Stelle zeigt sich die Genialität des DK-Ansatzes: der Ableitungsbaum von $$ kann beliebig verschachtelt sein, aber Stamm, linker Rand und Blüte haben zusammen eine einfache, beinahe linear anmutende Struktur. Schematisch:

Die Aussage "Stamm, linker Rand und Blüte haben eine einfache Struktur" können wir formalisieren:

Hier ist etwas Mentalgymnastik vonnöten: aus Sicht der Sprache SLRB sind $$ Terminalsymbole. Sie können ja schließlich in den Wörtern der Sprache auftauchen. Die Grammatik $$ hat also die Terminalsymbole $$. Darüberhinaus hat sie die Nichtterminale $$, also für jedes Nichtterminal $$ von $$ ein Meta-Nichtterminal $$. Das $$ entspricht dem $$ in den obigen Bäumen, wo also $$ als Blatt vorkommt; das $$ entspricht dem , also wo $$ als innerer Knoten vorkommt. Bevor ich $$ formal definiere, zeige ich den obigen Ableitungsbaum (ohne rechten Rand, weil der ja bei SLRB eh fehlt) und annotiere jeden Knoten auf dem Stamm mit der entsprechenden $$-Produktion.

Strenggenommen ist $$ eine erweitert reguläre Grammatik, weil manche Regeln mehrere Terminale hintereinander haben.

Nochmals: Produktionen wie $$ sind regulär (strenggenommen: erweitert regulär), weil $$ aus Sicht von $$ beides Terminalsymbole sind. Wir können nun unseren $$-Parser beschreiben: