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

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

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

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

Literatur Bearbeiten