Eine Grammatik gehört genau dann zur Klasse LL(1), wenn für zwei unterschiedliche Produktionen A → α und A → β folgende Bedingungen gelten:
1. FIRST(α) und FIRST(β) sind disjunkt, dh. sie haben keine gemeinsamen Elemente.
2. Wenn λ ∈ FIRST(α) gilt, dann sind FIRST(β) und FOLLOW(A) disjunkt. Wenn λ ∈ FIRST(β) gilt, dann sind FIRST(α) und FOLLOW(A) disjunkt.
Am Beispiel für S in G1 gibt es zwei zu betrachtende Produktionen:
S -> aA
S -> bBA
Um die erste Bedingung zu erfüllen, muss die Schnittmenge aus FIRST(aA) und FIRST(bBA) leer sein.
FIRST(aA) = {a}
FIRST(bBA) = {b}
Da die beiden Mengen keine gemeinsame Schnittmenge haben, ist Bedingung Nr. 1 erfüllt.
Die zweite Bedingung ist nur zu überprüfen, falls in einer der beiden FIRST-Mengen das Leere Wort auftaucht. Hier nicht der Fall, kann also übersprungen werden.
Damit ist jede Produktion S in G1 also LL(1)-tauglich. Damit man die gesamte Grammatik LL(1) nennen darf, müssen noch die anderen Produktionen neben S (A, B, C) überprüft werden.
Wichtig:
Falls es wie bei C nur eine Produktion gibt, ist diese automatisch LL(1)-tauglich.
Spoiler: G1 ist eine LL(1)-Grammatik.
