Direkt zum Inhalt

Lexikon der Mathematik: Item bezüglich LR(fr)

Regel einer kontextfreien Grammatik mit (üblicherweise durch einen Punkt markierten) Zerlegung der rechten Regelseite.

Aus der Regel [A, aBc] können also die Items [A, aBc], [A, a.Bc], [A, aB.c] sowie [A, aBc.] gebildet werden. Für das kanonische LR(k)-Verfahren (LR(k)-Grammatik) wird außerdem eine Menge J von k-elementigen Terminalzeichenreihen, die sog. Vorausschaumenge, aufgenommen (dann notiert z. B. als [A, a.Bc; J]). Dann heißt der Teil vor dem Semikolon Kern des Items.

Items charakterisieren Situationen im Verlauf der Bottom-up-Analyse. Dabei beschreibt der Teil vor dem Punkt auf der rechten Regelseite die Situation an der Spitze des Analysekellers. Der zweite Teil der rechten Seite beschreibt eine im noch nicht gelesenen Teil der Eingabe erwartete Satzform, die, falls vorgefunden, zu einem Reduktionsschritt mit der dem Item zugrundeliegenden Grammatikregel führen würde. Die Vorausschaumenge J spezifiziert, daß ein solcher Reduktionsschritt nur dann sinnvoll (d. h. einer erfolgreichen Reduktion der Eingabe zum Startsymbol dienlich) ist, wenn die auf die erkannte rechte Regelseite folgenden k Eingabezeichen in J enthalten sind.

Schreiben Sie uns!

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

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.