Normalformen von CFG

Nächste Seite: Top-Down-Parser (von Hand) Aufwärts: Syntakt. Analyse (4. 12.) Vorherige Seite: Syntakt. Analyse (4. 12.)

Normalformen von CFG

Erreichbare und produktive Variablen

Id: reduziert.tex,v 1.2 2003/12/03 11:51:10 joe Exp

Für eine CFG heißt die Variable

erreichbar, falls $\exists u,v\in (\Sigma\cup V)^* : S \to_R^* u A v$
produktiv, falls $\exists w\in \Sigma^* : A \to_R^* w$

Aufgabe: wie kann man entscheiden, ob diese Eigenschaften zutreffen (ohne alle Ableitungen aufzuzählen)?

Vergleiche mit gleichen Begriffen für Zustände von endlichen Automaten.

Reduzierte Grammatiken

Def: Die Grammatik heißt reduziert,

wenn alle Variablen erreichbar und produktiv sind.

Satz: zu jeder CFG gibt es eine reduzierte CGF mit $ L(G)=L(G')$ .

Beweis: lösche in zuerst alle nicht produktiven Variablen,

dann alle (im Rest) nicht erreichbaren Variablen

(jeweils mit allen Regeln, in denen sie vorkommen)

Aufgabe: warum gerade diese Reihenfolge?

Nullierbare Variablen

Id: null.tex,v 1.2 2003/12/03 11:51:10 joe Exp

Def: Eine Variable heißt nullierbar, falls $A \to_R^* \epsilon$ .

Die Menge der nullierbaren Variablen von

ist die kleinste Menge $N \subseteq V$ mit:

wenn $(A \to \epsilon) \in R$ , dann $A \in N$
wenn $(A \to x) \in R$ und $x \in N^*$ , dann $A \in N$

Bemerkung: der erste Fall ist tatsächlich im zweiten enthalten.

Def: eine Regel $A \to r$ heißt nullierbar, falls $r\to_R^* \epsilon$ .

Epsilon-freie Grammatiken

Id: epsfree.tex,v 1.2 2003/12/03 11:51:10 joe Exp

Def: eine CFG heißt epsilon-frei, falls $\forall (A \to r)\in R: r \neq \epsilon$ .

Bemerkung: wenn epsilon-frei, dann $\epsilon \notin L(G)$ .

Satz: Für jede CFG existiert eine epsilon-freie CGF mit $L(G') = L(G) \setminus \{\epsilon\}$ .

Beweis: Wende auf alle rechten Regelseiten die Substitution

$A \to$ ( wenn nullierbar, dann $\{A, \epsilon\}$ , sonst $\{A\}$ )

an, und lösche dann alle Epsilon-Regeln.

Aufgabe: Konstruiere für mit $R = \{ S \to \epsilon \mid aSb \mid SS \}$ .

Kettenregeln

Id: kette.tex,v 1.2 2003/12/03 11:51:10 joe Exp

Eine Regel $(l \to r)$ mit $\vert r\vert=1$ heißt Kettenregel.

Der Ketten-Abschluß von ist die kleinste Menge mit

$R \subseteq R'$
falls $(A \to B) \in R$ und $(B \to r)\in R'$ , dann $(A \to r)\in R'$ .

Aufgaben: Wieviele Regeln kann man maximal hinzufügen?

Satz: Zu jeder CFG existiert eine CFG ohne Kettenregeln mit $ L(G)=L(G')$ .

Beweis: $G'=(\Sigma,V,S,R'$ ohne Kettenregeln.

Aufgabe: falls epsilon-frei, dann auch .

Kreise und kreisfreie Grammatiken

Id: kreis.tex,v 1.1 2003/12/03 11:51:10 joe Exp

Def: eine Kreis-Ableitung ist von der Form $A \to_R^+ A$ für eine Variable .

Satz: für jede CFG gibt es eine kreisfreie CFG mit $ L(G)=L(G')$ .

Idee: epsilon-frei: $ G_1$ , kettenfrei: $ G_2$ , ist kreisfrei.

Aufgaben:

Anwenden auf $S \to \epsilon \mid SS \mid aSb$
Behauptung beweisen, dabei beachten:
wie wird $\epsilon \in L(G)$ behandelt?
Wie kann man entscheiden, ob gegebenes kreisfrei ist (ohne alle Ableitungen aufzuzählen)?

Nächste Seite: Top-Down-Parser (von Hand) Aufwärts: Syntakt. Analyse (4. 12.) Vorherige Seite: Syntakt. Analyse (4. 12.)

Johannes Waldmann 2004-01-28