5.6 Der DK-Automat

Von der Grammatik \(\hat{G}\) zu einem nichtdeterministischen endlichen Automaten

Um den \(LR(0)\)-Parser gemäß Algorithmus 5.5.10 zu implementieren, müssen wir den Test \(\gamma \stackrel{?}\in \textnormal{SLRB}(G)\) durchführen und, falls die Antwort ja ist, die Blüte finden. Dies gelingt uns, indem wir die Grammatik \(\hat{G}\) in einen endlichen Automaten umwandeln. Theorem 4.3.8 und die ihm vorhergehende Konstruktion zeigen, wie man das macht. Anstatt allerdings das Theorem als "black box" zu verwenden, gehen wir die Konstruktion für die Grammatik \(\hat{G}\) Schritt für Schritt durch, weil uns das weitere Erkenntnisse erschließen wird. Wir demonstrieren die Konstruktion anhand der Grammatik \begin{align*} G & : \\ S & \rightarrow aS \\ S & \rightarrow B \\ B & \rightarrow aBb \\ B & \rightarrow ab \end{align*} Warnung: dies ist keine LR(0)-Grammatik, wie wir bald sehen werden. Die Grammatik \(\hat{G}\) und der DK-Automaten aber können für alle kontextfreien Grammatiken \(G\) konstruiert werden, ob LR(0) oder nicht. Ich konstruiere nun den nichtdeterministischen Automaten für die Sprache \(\textnormal{SLRB}(G)\):

Todo: beschreiben, wie man von \(\hat{G}\) zu dem Automaten mit den Punkt-Zuständen kommt.

Im konkreten Fall kann das recht kompliziert werden. Das Prinzip ist aber einfach. Jeder Zustand hat eine \(\epsilon\)-Kanten für jede Produktion \(X \rightarrow \beta\), und diese führt zum Zustand . Ein Zustand , wo auf den Punkt ein Terminalsymbol folgt, hat eine ausgehende Kante:

Wenn auf den Punkt ein Nichtterminal folgt, also

, hat zwei ausgehende Kanten:

Den Automaten deterministisch machen

Wir wissen ja bereits, wie man einen nichtdeterministischen Automaten deterministisch macht: die Potenzmengenkonstruktion aus Kapitel 4.3. Hier können wir diese leider nicht direkt anwenden, da der obige Automat \(\epsilon\)-Übergänge hat. Wie geht das also nun? Im deterministischen Automaten ist wie bei der Potenzmengenkonstruktion jeder Zustand eine Menge \(R\) von Zuständen des nichtdeterministischen Automaten. Wenn wir nun in eine solche Menge \(R\) einen Zustand \(q\) einfügen, dann fügen wir auch alle Zustände \(q'\) hinzu, zu denen es einen \(\epsilon\)-Übergang \(q \step{\epsilon} q'\) gibt. Für den obigen nichtdeterministischen Automaten sieht das dann so aus: