0 Daumen
706 Aufrufe

Frage:

LL(1)- und LR(1)-Grammatiken

Beurteilen Sie für die folgenden zwei Grammatiken, ob es sich um eine LL(1)-Grammatik handelt und begründen Sie Ihr Urteil.

Grammatik G1:
S →aA | bBA
A →aA | dC
B →cB | bB | AC

C →ε


Grammatik G2:
S →dBA
A →aAb | DD

B →AC | b
C →Ac

D→ε


Ich komme bei dieser Aufgabe leider nicht weiter, wie löse ich das am besten?

Avatar von

1 Antwort

0 Daumen

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community