Kontextfreie Grammatiken

Kontextfreie Sprachen

$$Id: cf.tex,v 1.3 2003/11/24 14:18:43 joe Exp $$

Def (Wdhlg): $G$ ist kontextfrei (Typ-2), falls $\forall (l,r) \in R(G): l \in V$.

geeignet zur Beschreibung von Sprachen mit hierarchischer Struktur.

Anweisung -> Bezeichner = Ausdruck
    | if Ausdruck then Anweisung else Anweisung
Ausdruck -> Bezeichner | Literal
    | Ausdruck Operator Ausdruck

Bsp: korrekt geklammerte Ausdrücke: $G = ( \{ a,b\}, \{S\}, S, \{ S \to aSbS, S \to \epsilon )$.

Bsp: Palindrome: $G = ( \{ a,b\}, \{S\}, S, \{ S \to aSa, S \to bSb, S \to \epsilon )$.

Bsp: alle Wörter $w$ über $\Sigma=\{a,b\}$ mit $\vert w\vert _a = \vert w\vert _b$

...und ähnlich Aufgaben, siehe demnächst autotool.

Ableitungsbäume für CF-Sprachen

$$Id: baum.tex,v 1.3 2003/12/03 11:51:10 joe Exp $$

Def: ein geordneter Baum $T$ mit Markierung $m: T \to \Sigma\cup\{\epsilon\}\cup V$ ist Ableitungsbaum für eine CF-Grammatik $G$, wenn:

• für jeden inneren Knoten $k$ von $T$ gilt $m(k) \in V$
• für jedes Blatt $b$ von $T$ gilt $m(b) \in\Sigma \cup \{\epsilon\}$
• für die Wurzel $w$ von $T$ gilt $m(w)=S(G)$ (Startsymbol)
• für jeden inneren Knoten $k$ von $T$ mit Kindern $k_1, k_2, \ldots, k_n$ gilt $(m(k), m(k_1) m(k_2) \ldots m(k_n)) \in R(G)$ (d. h. jedes $m(k_i) \in V \cup\Sigma$)
• für jeden inneren Knoten $k$ von $T$ mit einzigem Kind $k_1 = \epsilon$ gilt $(m(k), \epsilon)\in R(G)$.

Ableitungsbäume (II)

Def: der Rand eines geordneten, markierten Baumes $(T,m)$ ist die Folge aller Blatt-Markierungen (von links nach rechts).

Beachte: die Blatt-Markierungen sind $\in \{\epsilon\} \cup \Sigma$, d. h. Terminalwörter der Länge 0 oder 1.

Für Blätter: $\operatorname{rand}(b)=m(b)$, für innere Knoten: $\operatorname{rand}(k)=\operatorname{rand}(k_1) \operatorname{rand}(k_2)\ldots \operatorname{rand}(k_n)$

Satz: $w \in L(G) \iff$ existiert Ableitungsbaum $(T,m)$ für $G$ mit $\operatorname{rand}(T,m)=w$.

Eindeutigkeit

$$Id: eindeut.tex,v 1.1 2003/11/24 13:19:24 joe Exp $$

Def: $G$ heißt eindeutig, falls $\forall w \in L(G)$ genau ein Ableitungsbaum $(T,m)$ existiert.

Bsp: ist $\{ S \to aSb \vert SS \vert \epsilon \}$ eindeutig?

(beachte: mehrere Ableitungen $S \to_R^* w$ sind erlaubt, und wg. Kontextfreiheit auch gar nicht zu vermeiden.)

Eindeutigkeit (II)

(äquiv. Definition ohne Bäume)

Def: ein Schritt (Regel-Anwendung) $u = x l z \to x r z = v$ heißt Links-Schritt, geschrieben $u \to_L v$, falls $x \in \Sigma^*$

(d. h. $l$ ist die am weitesten links stehende Variable).

Eine Links-Ableitung ist eine Folge von Links-Schritten.

Satz: $G$ ist eindeutig $\iff$ jedes $w$ besitzt genau eine Links-Ableitung.

Beweis: betrachte Pre-Order-Durchquerung des Abl.-Baums.

Dangling else

$$Id: else.tex,v 1.1 2003/11/24 13:19:24 joe Exp $$

In vielen Programmiersprachen ist definiert:

Anweisung -> ... 
   |  if Ausdruck then Anweisung
   |  if Ausdruck then Anweisung else Anweisung

Modell: $\{ S \to e \vert t S \vert t S e S \}$.

Diese Regelmenge führt zu einer mehrdeutigen Grammatik.

Aufgabe: finden Sie eine eindeutige Grammatik mit den ,,richtigen `` Ableitungsbäumen.

Arithmetische Ausdrücke

$$Id: arith.tex,v 1.2 2003/11/24 14:18:43 joe Exp $$

Arithmetische Ausdrücke kann man so definieren:

Ausdruck -> Zahl
    | Ausdruck + Ausdruck
    | Ausdruck - Ausdruck
    | Ausdruck * Ausdruck
    | Ausdruck / Ausdruck

Das ist mehrdeutig.

Aufgabe: machen Sie das so eindeutig, daß die aus der Grundschule bekannten Ableitungsbäume entstehen.