LL(k)-Grammatik

LL(k)-Grammatik

Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus.


Eine LL(k)-Grammatik (im Kontrast zu LF(k)-Grammatik auch schwache LL(k)-Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LL(k)-Parsers bildet.

Eine kontextfreie Grammatik heißt LL(k)-Grammatik für eine natürliche Zahl k, wenn jeder Ableitungsschritt eindeutig durch die nächsten k Symbole der Eingabe (Lookahead) bestimmt ist. Das bedeutet, die Frage, welches Nichtterminalsymbol mit welcher Regel als nächstes expandiert werden soll, kann eindeutig mit Hilfe der nächsten k Symbole der Eingabe bestimmt werden.

Generell gilt, je größer k gewählt wird, umso mächtiger wird die Sprachklasse, wobei die Ausdrucksstärke von kontextfreien Grammatiken nie erreicht wird. Damit gibt es kontextfreie Sprachen, die für kein k von einer LL(k)-Grammatik erzeugt werden.

\mathcal L(\mathrm{LL}(1)) \subsetneq \mathcal L(\mathrm{LL}(2)) \subsetneq \dots \subsetneq \mathcal L(\mathrm{LL}(k)) \subsetneq \mathcal L(\mathrm{LR}(1)) = \mathcal L(\mathrm{DPDA})

Dabei steht DPDA für die deterministischen Kellerautomaten. Diese können genau die deterministisch kontextfreien Sprachen erkennen.

Inhaltsverzeichnis

Formale Definition LL(k)-Grammatik

Eine kontextfreie Grammatik G = (N,Σ,P,S) ist genau dann eine LL(k)-Grammatik, wenn für alle Linksableitungen der Form

S\Rightarrow^*_l wA\gamma\Rightarrow_l
  \left\{ \begin{array}{l}
            w\alpha\gamma \Rightarrow^*_l wx \\
            w\beta\gamma \Rightarrow^*_l wy
          \end{array} \right.

mit \quad (w,x,y \in \Sigma^*; \alpha,\beta,\gamma \in (N \cup \Sigma)^*; A \in N) und \mathit{first}_k(x)=\mathit{first}_k(y)^{\,} gilt: \alpha=\beta^{\,}

Für die in der Definition benutzte Funktion zur Bestimmung der FIRST-Mengen gilt:

a\in\Sigma^*;|a|\le k \mathit{first}_k\left(a\right)=\{a\}
a\in\Sigma^*;|a|>k \mathit{first}_k(a)=\{v \in \Sigma^ * \mid a=vw; |v|=k\}
A \in (N\cup\Sigma)^* \backslash \Sigma^* \mathit{first}_k(A)=\{v \in \Sigma^ * \mid A \Rightarrow^* w;w \in \Sigma^ *; \mathit{first}_k(w)=\{v\}\}

Anwendung

Aktuelle LL-Parser benutzen meist nur einen Lookahead von 1. Daher kann in den folgenden Ausführungen k = 1 gesetzt werden.

Bei der praktischen Anwendung ist nur mit großem Aufwand überprüfbar, ob die vorliegende Grammatik die Definition einer LL(k)-Grammatik erfüllt. Es wird stattdessen ein abgewandelter Ansatz benutzt.

Eine kontextfreie Grammatik ist genau dann eine LL(k)-Grammatik, wenn für alle Nichtterminalsymbole A, für alle Produktionen A \to \beta und A \to \gamma mit \beta \ne \gamma und S \Rightarrow^*_l wA\alpha gilt: first_k(\beta\alpha) \cap first_k(\gamma\alpha) = \emptyset.  (w \in \Sigma^*; \alpha,\beta,\gamma \in (N \cup \Sigma)^*; A \in N)

Erklärung: Das Startsymbol der kontextfreien Grammatik S wurde (in eventuell mehreren Schritten) nach wA^{\,}\alpha expandiert. Gemäß der Linksableitung wird das Nichtterminalsymbol A als nächstes ersetzt. Dazu gibt es in der kontextfreien Grammatik aber zwei verschiedene Regeln; A \to \beta und A \to \gamma. Die Frage, mit welcher Regel A expandiert wird, bestimmt sich aus der Berechnung von first_k\left(\beta\alpha\right) und first_k\left(\gamma\alpha\right). Um die Frage eindeutig beantworten zu können, müssen beide Mengen disjunkt sein.

Im Allgemeinen hängt first_k\left(\beta\alpha\right) aber vom Rechtskontext α ab (wenn \beta \Rightarrow^* \epsilon). Das Ziel ist die Bestimmung von first_k\left(\beta\alpha\right) nur aus den Produktionen, d. h. aus β und aus den Strings, die einem Vorkommen von A folgen können. Für diesen Zweck wird die Funktion follow_k\left(A\right) definiert, die die Menge aller A folgenden Symbole berechnet.

\forall\beta \in (N \cup \Sigma)^*: follow_k(\beta)=\{w \in \Sigma^* \mid \exists \alpha\gamma \in (N \cup \Sigma)^* \mbox{ mit } S \Rightarrow^*_l \alpha\beta\gamma \mbox{ und } w \in first_k(\gamma)\}

Damit kann die eingangs geforderte Bedingung umformuliert werden:

Eine reduzierte kontextfreie Grammatik ist genau dann eine LL(1)-Grammatik, wenn für alle Nichtterminalsymbole A und für alle Produktionen A \to \beta und A \to \gamma mit \beta \ne \gamma gilt: first_1(\{\beta\}follow_1(A)) \cap first_1(\{\gamma\}follow_1(A))=\emptyset.

Achtung: Dieser Satz kann auf Fälle k > 1 nicht angewandt werden.

Die zu einer Produktion A \to \beta berechnete Menge la(A,\beta)=first_1\left(\{\beta\}follow_1(A)\right) wird als Lookahead-Menge bezeichnet.

Beispiel

Für die folgende Grammatik G wird geprüft, ob sie eine LL(1)-Grammatik ist. Dazu müssen die Lookahead-Mengen aller Produktionen mit gleichen linken Regelseiten disjunkt sein.

G=\left(\{E,E',T,T',F\},\{\epsilon,a,(,),+,*\},P,E\right) und die Menge der Produktionen ist:
E \to TE'
E' \to +TE'
E' \to \epsilon
T \to FT'
T' \to *FT'
T' \to \epsilon
F \to (E)
F \to a

Zunächst werden die first- bzw. follow-Mengen der Nichtterminalsymbole bestimmt, da diese für die Berechnung der Lookahead-Mengen nötig sind.

E E' T T' F
first1 \left\{(,a\right\} \left\{+,\epsilon\right\} \left\{(,a\right\} \left\{*,\epsilon\right\} \left\{(,a\right\}
follow1 \left\{)\right\} \left\{\epsilon,)\right\} \left\{+,\epsilon,)\right\} \left\{+,\epsilon,)\right\} \left\{*,+,\epsilon,)\right\}

Es folgt der Vergleich der Lookahead-Mengen für alle Produktionen mit gleichen linken Regelseiten.

Als erstes für die beiden Produktionen E' \to +TE' und E' \to \epsilon

la(E',+TE') \cap la(E',\epsilon)=first_1(\{+TE'\}follow_1(E')) \cap first_1(\{\epsilon\}follow_1(E'))=\{+\} \cap \{\epsilon,)\}=\emptyset

Als nächstes für die beiden Produktionen T' \to *FT' und T' \to \epsilon

la(T',*FT') \cap la(T',\epsilon)=first_1(\{*FT'\}follow_1(T')) \cap first_1(\{\epsilon\}follow_1(T'))=\{*\} \cap \{+,\epsilon,)\}=\emptyset

Als letztes für die beiden Produktionen F \to (E) und F \to a

la(F,(E)) \cap la(F,a)=first_1(\{(E)\}follow_1(F)) \cap first_1(\{a\}follow_1(F))=\{(\} \cap \{a\}=\emptyset

Da alle betrachteten Schnittmengen leer sind, handelt es sich bei der Grammatik G um eine LL(1)-Grammatik.

Siehe auch

Literatur


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Grammatik (Begriffsklärung) — Grammatik (griechisch γραμματική, von γράμμα „der Buchstabe“) bezeichnet: Grammatik, einen Teil der Sprachwissenschaft formale Grammatik, ein mathematisches Modell in der theoretischen Informatik Grammatik (artes liberales), ein Gebiet der… …   Deutsch Wikipedia

  • Grammatik (Band) — Grammatik ist eine polnische Hip Hop Gruppe aus Warschau. Sie wurde 1997 gegründet, ihr Stil ist betont ruhig, als Samples nutzen sie bevorzugt Fragmente klassischer Musik. Bekannt wurde sie im Jahr 2000 mit der EP EP+ und dem Album Światła… …   Deutsch Wikipedia

  • Grammatik — Grammatik, 1) bei den Griechen u. Römern die Anweisung in den Wissenschaften (Grammăta), s. Grammatiker; 2) der Inbegriff u. die wissenschaftliche Darstellung der Regeln, wonach eine Sprache gesprochen u. geschrieben wird. Die Allgemeine G.… …   Pierer's Universal-Lexikon

  • Grammatik — Sf std. (11. Jh.), mhd. gramatic(a), ahd. grammatih Entlehnung. Entlehnt aus l. (ars) grammatica Sprachlehre , dieses aus gr. grammatikḗ (téchnē), zu gr. grámma n. Geschriebenes, Buchstabe , einer Ableitung von gr. gráphein einritzen, schreiben …   Etymologisches Wörterbuch der deutschen sprache

  • Grammatik von heute — [Network (Rating 5600 9600)] Auch: • Grammatik für heute …   Deutsch Wörterbuch

  • Grammatik für heute — [Network (Rating 5600 9600)] Auch: • Grammatik von heute …   Deutsch Wörterbuch

  • Grammátik — (griech., Sprachlehre) ist die Gesamtheit der Regeln über die Laute (s. Lautlehre) und Formen (s. Flexion) einer Sprache und über die Aneinanderreihung der Wörter zu Sätzen (s. Syntax). Grammatiker war bei den alten Griechen soviel wie Philolog,… …   Meyers Großes Konversations-Lexikon

  • Grammátik — (grch.), Sprachlehre, die Darstellung des vorhandenen Materials einer Sprache, ihres Baues und der Gesetze ihrer Entwicklung und Veränderung. Die wissenschaftliche G. zerfällt gewöhnlich in 1) Lautlehre, 2) Stammbildungslehre, 3) Wortbildungs… …   Kleines Konversations-Lexikon

  • Grammatik — Grammatik, griech., Sprachlehre, die systematische Zusammenstellung der Regeln, nach welchen eine Sprache gebaut ist; die allgem. G. behandelt diejenigen Hauptformen, welche auf den allg. Gesetzen des menschl. Vorstellens beruhend, sich in allen… …   Herders Conversations-Lexikon

  • Grammatik — (Teil der Sprachwissenschaft, der sich mit den sprachlichen Formen und ihrer Funktion beschäftigt; auch Bezeichnung für ein Lehrbuch der Sprachlehre): Das Wort (mhd. grammatic‹a›, ahd. gram‹m›atik) ist entlehnt aus lat. (ars) grammatica… …   Das Herkunftswörterbuch

  • Grammatik — [Network (Rating 5600 9600)] …   Deutsch Wörterbuch

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”