6.4 LL($k$)-Grammatiken (nicht im Sommersemester 2025)

Grenzformen sind also diejenigen Wortformen, bei denen der Kellerautomat eine Entscheidung treffen muss, weil er eventuell mehrere Produktionen $A\to \beta$ zur Auswahl hat. In diesem Teilkapitel wollen wir herausarbeiten, unter welchen Umständen wir die richtige Auswahl treffen können, auch wenn wir nur wenige weitere Zeichen unseres Inputwortes lesen dürfen. Intuitiv gesprochen: wenn wir bereits eine ersten Teil $w$ unseres Zielwortes abgeleitet haben, dann können wir die nächste anzuwendende Produktion eindeutig bestimmen, indem wir die nächsten $k$ Zeichen des Zielwortes lesen. Sehen Sie, dass die LL($k$)-Bedingung der Aussage "der Backtrack-Baum hat keine langen Sackgassen" ähnelt (aber nicht völlig äquivalent dazu ist). Wenn $G$ eine LL($k$)-Grammatik ist und wir den Backtrack-Baum für ein Wort bauen, dann gilt: sobald wir in einer Sackgasse $k$ neue Terminalsymbole am "Terminalpräfix" der Wortform hergeleitet haben, merken wir, dass wir in einer Sackgasse sind. Mit Terminalpräfix meine ich den längsten Präfix einer Wortform, der ausschließlich aus Terminalen besteht. Allerdings muss nicht jeder Ableitungsschritt den Terminalpräfix wachsen lassen (Regeln wie $X\to YbZ$ zum Beispiel ersetzen einfach das erste Nichtterminal), aber "moralisch" geschieht etwas ähnliches).

Wenn umgekehrt eine Grammatik nicht LL($k$) ist, dann muss der Backtrack-Baum beiden Ableitungen $$\begin{array}{rl}wA\alpha & \Rightarrow w\beta \alpha \\ wA\alpha & \Rightarrow w\gamma \alpha \end{array}$$ mindestens so lange weiterverfolgen, bis der Terminalpräfix $k$ weitere Zeichen dazugewonnen hat. Der Baum bekommt also dementsprechend lange Sackgassen.

LL$(k)$-Grammatiken parsen

Wir wollen nun erarbeiten, wie wir für eine LL$(k)$-Grammatik einen Parser, also im Prinzip einen deterministischen Pushdown-Automaten schreiben können. Wir tasten uns langsam voran. Wir beginnen mit einer Verallgemeinerung von ${\text{first}}_k$ von Wörtern auf Wortformen (die also Nichtterminale beinhalten können). Wir können nun die LL$(k)$-Bedingung äquivalent formulieren:

Nehmen wir eine Momentaufnahme unseres Kellerautomaten. Er hat den Präfix $$ des Eingabewortes $$ gelesen und eine Linksableitung $$ durchgeführt. Die Wortform $$ ist genau das, was im Moment auf dem Stack des Automaten liegt (um ganz genau zu sein: $$ liegt auf dem Stack). Wenn $$ mit einem Terminalsymbol $$ beginnt, so ist klar, was wir machen müssen: wir schauen, ob $$ mit $$ beginnt. Wenn ja, lesen wir $$ und poppen es vom Stack. Der schwierige Fall ist, wenn $$ mit einem Nichtterminal beginnt.

Nochmal von vorn: im schwierigen Fall liegt auf dem Stack (oberhalb vom $$) eine Wortform, die mit einem Nichtterminal beginnt, also $$. Das bedeutet, dass der Automat per Linksableitung bis jetzt $$ hergeleitet hat. Der Automat muss sich nun zwischen allen Regeln für $$ entscheiden: $$ Der Automat betrachtet nun die nächsten $$ Eingabesymbole, also $$ (wir gehen mal davon aus, dass er das kann; programmieren könnten wir das auf jeden Fall; ob man es im strengen Framework des Kellerautomaten hinkriegt, werden wir später sehen). Wenn $$ eine LL$$-Grammatik ist, dann gibt es höchstens eine Regel $$ mit $$ da ja nach obiger Beobachtung diese Mengen disjunkt sind. Wenn $$ in keiner dieser Mengen enthalten ist, so kann die Ableitung offensichtlich nicht vervollständigt werden, und wir schließen, dass $$ ist. Wenn es genau ein $$ gibt mit $$, dann ist $$ die "richtige" Produktion. Wir wenden sie an, ersetzen also $$ auf dem Stack durch $$. Falls es zwei oder mehr Produktionen $$ gibt mit $$, dann ist die Grammatik nicht LL$$; wir beenden den Parsing-Prozess mit einer Laufzeitfehlermeldung. Hier ist ein Entwurf eines allgemeinen Algorithmus für LL$$-Grammatiken:

Die rot und fett gedruckte Zeile ist das "Herz" dieses Algorithmus. Um den Algorithmus implementieren zu können, müssen wir es schaffen, die Menge $$ zu berechnen.

$$ und $$ berechnen.

Im Allgemeinen gilt $$. In Worten: der $$-Operator bildet alle möglichen Kombinationen von Wörtern und nimmt von jedem die ersten $$ Zeichen.

Für ein Terminalsymbol $$ ist es trivial, $$ zu berechnen: es ist $$, da sich aus $$ natürlich nur das Wort $$ ableiten lässt. Für Nichtterminale müssen wir uns anstrengen. Die erste Idee ist, dass wir für $$ eine Gleichung schreiben können, die $$ verwendet.

Die Gleichungen $$ und $$ leuchten zwar ein, scheinen aber erstmal nicht hilfreich, diese Mengen auch tatsächlich zu berechnen. Denn eventuell taucht $$ selbst wieder auf einer rechten Seite auf, sagen wir $$. Um $$ zu berechnen, müssen wir also laut $$ die Menge $$ kennen; um diese zu berechnen, brauchen wir laut $$ allerdings zuerst unter Anderem die Menge $$. Wo sollen wir also anfangen?

In solchen Situationen, wo sich "die Katze in den Schwanz beißt", hilft es oft, die Definition vorerst komplexere un genauer zu machen. Wir führen nun, zusätzlich zu $$ und $$, noch eine feinere Unterteilung an:

Mit dieser Definition können wir nun Gleichungen für $$ und $$ angeben. Seien $$ die Produktionen mit $$ auf der linken Seite. Dann gilt für $$:

Die Gleichungen sagen, dass wir, falls wir $$ für alle Nichtterminale kennen, dann auch $$ berechnen können. Daraus folgt auch: wenn $$ für alle $$, dann auch $$ für alle $$, und somit werden die Mengen $$ für alle $$ von nun an gleich bleiben.