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.
Dabei steht DPDA für die deterministischen Kellerautomaten. Diese können genau die deterministisch kontextfreien Sprachen erkennen.
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.
Dabei steht DPDA für die deterministischen Kellerautomaten. Diese können genau die deterministisch kontextfreien Sprachen erkennen.