LL(k)-Grammatik

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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


Eine LL(k)-Grammatik (im Gegensatz 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.

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

Formale Definition LL(k)-Grammatik[Bearbeiten | Quelltext bearbeiten]

Eine kontextfreie Grammatik ist genau dann eine LL(k)-Grammatik, wenn für alle Linksableitungen der Form

mit und gilt:

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

Anwendung[Bearbeiten | Quelltext bearbeiten]

Aktuelle LL-Parser benutzen meist nur einen Lookahead von 1. Daher kann in den folgenden Ausführungen 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 , für alle Produktionen und mit und gilt: .

Erklärung: Das Startsymbol der kontextfreien Grammatik wurde (in eventuell mehreren Schritten) nach expandiert. Gemäß der Linksableitung wird das Nichtterminalsymbol als Nächstes ersetzt. Dazu gibt es in der kontextfreien Grammatik aber zwei verschiedene Regeln; und . Die Frage, mit welcher Regel expandiert wird, bestimmt sich aus der Berechnung von und . Um die Frage eindeutig beantworten zu können, müssen beide Mengen disjunkt sein.

Im Allgemeinen hängt aber vom Rechtskontext ab (wenn ). Das Ziel ist die Bestimmung von nur aus den Produktionen, d. h. aus und aus den Strings, die einem Vorkommen von folgen können. Für diesen Zweck wird die Funktion definiert, die die Menge aller folgenden Symbole berechnet.

Damit kann die eingangs geforderte Bedingung umformuliert werden:

Eine reduzierte kontextfreie Grammatik ist genau dann eine LL(1)-Grammatik, wenn für alle Nichtterminalsymbole und für alle Produktionen und mit gilt:

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

Die zu einer Produktion berechnete Menge wird als Lookahead-Menge bezeichnet.

Beispiel[Bearbeiten | Quelltext bearbeiten]

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

und die Menge der Produktionen ist:

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

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

Als erstes für die beiden Produktionen und

Als Nächstes für die beiden Produktionen und

Als letztes für die beiden Produktionen und

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

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]