Direkt zum Inhalt

Lexikon der Mathematik: LR(k)-Grammatik

kontextfreie Grammatik, die deterministische Bottom-up-Analyse gestattet.

Die Bezeichnung ist zu lesen als: Verarbeitung der Eingabe von links nach rechts mit Erzeugung einer Rechtsableitung unter Vorausschau bis zu k Zeichen.

LR(k)-Grammatiken gestatten die eindeutige Auswahl der als nächstes durchzuführenden Aktion (Shift-Schritt bzw. Reduktionsschritt) eines Bottom-Up-Parsers anhand des bereits analysierten Teils der Eingabe sowie der nächsten k Eingabezeichen.

LR(k)-Grammatiken sind durch folgende Eigenschaft charakterisiert: Wenn für zwei Regeln [Z, v] und [Z′, v′] sowie Satzformen w1, \({w}_{1}^{\prime}\) und Wörter w2, \({w}_{2}^{\prime}\) Ableitungen der Form S ⇒* w1Zw2w1vw2 und \(S\Rightarrow * \,{w}_{1}^{\prime}Z^{\prime} {w}_{2}^{\prime}\Rightarrow {w}_{1}^{\prime}v^{\prime} {w}_{2}^{\prime}\) existieren, wobei \({w}_{1}v={w}_{1}^{\prime}v^{\prime} \) ist und die k-Präfixe von w2 und \({w}_{2}^{\prime}\) übereinstimmen, so ist [Z, v] = [Z′, v′].

Die Information über den bereits gelesenen Teil der Eingabe (wv) liefert der die Analyse steuernder LR(0)-Analysator. In seiner verfeinerten Version (d. h. unter Einbeziehung der Vorausschaumengen in die Items) liefert er genügend Information, um für jede LR(k)-Grammatik zusammen mit den folgenden k Eingabezeichen die eindeutige Aktionsauswahl zu gestatten.

Beim LALR(k)-Verfahren (look-ahead-LR(k)-Verfahren) wird als Information über den bereits analysierten Teil lediglich der Zustand des nicht verfeinerten LR(0)-Analysators verwendet (d.h., Zustände, die sich nur in den Vorausschaumengen unterscheiden, werden nicht unterschieden). Auf diese Weise können zwar nicht mehr alle LR(k)-Sprachen deterministisch analysiert werden, der für den LR(0)-Analysator notwendige Speicherplatz ist aber deutlich geringer. Außerdem überdeckt das LALR(k)-Verfahren alle in der Praxis verwendeten programmiersprachlichen Konstruktionen.

Beim SLR(k)-Verfahren (simple LR(k)) wird die durchzuführende Aktion unabhängig vom Zustand des LR(0)-Analysators gewählt. Es gibt allerdings einige praxisrelevante Sprachkonstruktionen (z. B. Zuweisungen einiger Programmiersprachen), für die das SLR(k)-Verfahren keine eindeutige Aktionsauswahl trifft. Zu jeder LR(k)-Grammatik existiert eine äquivalente LR(1)-Grammatik.

Jede LL(k)-Grammatik ist LR(k). Verbreitete Werkzeuge zur Generierung von Bottom-Up-Parsern unterstützen in der Regel LALR(1)-Grammatiken und decken damit so gut wie alle praktisch relevanten Anwendungen ab.

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

Partnervideos