Direkt zum Inhalt

Lexikon der Mathematik: LR(0)-Analysator

deterministischer endlicher Automat, der Präfixe von Rechtsableitungen aus kontextfreien Grammatiken akzeptiert. Ein Präfix ist eine Satzform u mit der Eigenschaft, daß es eine Rechtsableitung S ⇒* vXv′ ⇒ vwv′ gibt, in der u Anfangsstück von vw ist.

Der LR(0)-Analysator kann aus der Grammatik konstruiert werden. Dabei dienen Mengen von Items bezüglich LR(k) als Zustände. Der Folgezustand z′ eines Zustandes z mit einem Terminaloder Nichtterminalzeichen x enthält alle Items [X, w1x.w2], für die [X, w1.xw2] in z enthalten ist, sowie alle Items [X′,.w], für die ein Item der Form [X, w1.Xw2] in z′ ist. Der Startzustand z0 entsteht aus allen Items der Form [S,. w] für das Startsymbol S, sowie allen Items [X′,. w], für die ein Item der Form [X,. Xw2] in z0 vorkommt.

Die Hinzunahme geeignet konstruierter Vorausschaumengen zu den Zuständen ändert nichts am Akzeptieren der Präfixsprache, liefert aber detailliertere Information über die Aktionen, die für eine Bottom-up-Analyse im aktuellen Zustand möglich sind.

In z ist ein Shift-Schritt möglich, falls für das aktuelle Eingabezeichen x ein Item [X, w1.xw2] in z ist. Ein Reduktionsschritt mit Regel [X, w] ist möglich, falls das Item [X, w.] in z ist (und ggf. die nächsten k Eingabesymbole in der Vorausschaumenge des Items enthalten sind).

Wegen den genannten Eigenschaften wird LR(0)-Analysator zur Steuerung von Bottom-Up-Analyseverfahren verwendet (LR(k)-Grammatik).

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte