LL(k)-Grammatik

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.

${\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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.