LF(k)-Grammatik

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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


Eine LF(k)-Grammatik ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LF(k)-Parsers bildet. Auf Grund der sehr engen Verwandtschaft werden LF(k)-Grammatiken auch als starke LL(k)-Grammatiken bezeichnet.

Die Bezeichnung LF(k)-Grammatik bedeutet, dass jeder Ableitungsschritt eindeutig durch k Symbole der Eingabe (Lookahead) bestimmt ist. Damit kann die Frage, welches Nichtterminalsymbol mit welcher Regel als Nächstes expandiert werden soll, eindeutig mit Hilfe der nächsten k Symbole der Eingabe beantwortet 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 Grammatiken, die für kein k LF(k)-Grammatiken sind.

Formale Definition LF(k)-Grammatik

[Bearbeiten | Quelltext bearbeiten]

Eine kontextfreie Grammatik ist genau dann eine LF(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:

Die formale Definition einer LF(k)-Grammatik ist bezüglich praktischer Anwendung nur mit großem Aufwand überprüfbar. Daher erfolgt die Prüfung auf LF(k)-Eigenschaft mithilfe eines abgewandelten Ansatzes.

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


Erklärung: Infolge einer Wortableitung wurde das Startsymbol der kontextfreien Grammatik (in eventuell mehreren Schritten) expandiert. Angenommen, im nächsten Schritt soll das Nichtterminalsymbol A ersetzt werden. Dazu stehen aber zwei verschiedene Regeln und zur Verfügung. Ist die in der Gesetzmäßigkeit angegebene Schnittmenge leer, dann kann die Regelauswahl eindeutig getroffen werden.

Für diesen Zweck wird die Funktion benötigt, die die Menge aller A folgenden Symbole berechnet.

Die Prüfung auf LL(1)-Eigenschaft benutzt den gleichen Ansatzpunkt. Eine Verallgemeinerung auf beliebige k ist dabei jedoch nicht möglich. Dieser Unterschied grenzt beide Grammatikformen voneinander ab.

Die Grammatik soll auf ihre LF(k)-Eigenschaft hin untersucht werden. Mit anderen Worten: Für welches k ist G eine LF(k)-Grammatik?

und die Menge der Produktionen ist

Zunächst werden die first- bzw. follow-Mengen der Nichtterminalsymbole bestimmt.

Es folgt der Vergleich der wie oben definierten Mengen für alle Produktionen mit gleichen linken Regelseiten. In diesem Beispiel werden somit die Regeln mit und mit verglichen.

Im Fall des Nichtterminalsymbols S sind schon für die Mengen und disjunkt. Weitere Betrachtungen für größere k können entfallen.

Erst für sind die zu vergleichenden Mengen disjunkt und damit die deterministische Regelauswahl gewährleistet. Die Beispielgrammatik G ist also eine LF(3)-Grammatik.