Lexikon der Mathematik: LL(k)-Grammatik
kontextfreie Grammatik, die deterministische Top-Down-Analyse gestattet.
Die Bezeichnung ist zu lesen als Verarbeitung der Eingabe von links nach rechts mit Erzeugung einer Linksableitung bei Vorausschau um k Zeichen.
Die LL(k)-Eigenschaft ist wie folgt charakterisiert: Falls es für zwei verschiedene Regeln [X1, w1] und [X2, w2] der Grammatik, die Linksableitungen \(S\,\,{\Rightarrow }^{* }\,\,u{X}_{1}{v}_{1}\Rightarrow u{w}_{1}{v}_{1}\,\,{\Rightarrow }^{* }\,\,u{w}_{1}^{{\prime}}\) und \(S\,\,{\Rightarrow }^{* }\,\,u{X}_{2}{v}_{2}\Rightarrow u{w}_{2}{v}_{2}\,\,{\Rightarrow }^{* }\,\,u{w}_{2}^{{\prime}}\) gibt (\({w}_{1}^{{\prime}}\) und \({w}_{2}^{{\prime}}\) sind Wörter über dem Alphabet der Sprache), so ist der k-Präfix von \({w}_{1}^{{\prime}}\) verschieden vom k-Präfix von w2. Die Auswahl einer Grammatik-Regel kann also stets eindeutig anhand der ersten k Zeichen der daraus (oder darauffolgend) abzuleitenden Eingabe sowie anhand des bereits analysierten Textes (u) getroffen werden.
LL(k)-Grammatiken sind stets auch LR(k)-Grammatiken. Als Wert für k ist vor allem 1 gebräuchlich.
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.