Zum Inhalt springen

Formale Grammatik

Aus FLBK-Wiki
(Weitergeleitet von Grammatik)

Eine Grammatik beschreibt eine Sprache durch Regeln, mit denen sich ihre Wörter erzeugen lassen. So ist auch die Syntax von Programmiersprachen festgelegt.

Definition

Eine formale Grammatik ist ein 4-Tupel [math]\displaystyle{ G = (N; T; P; S) }[/math]. Ein Tupel ist eine geordnete Zusammenstellung: Jeder der vier Bestandteile hat seinen festen Platz. Die Bestandteile stehen in runden Klammern und werden durch Semikolons getrennt:

  • [math]\displaystyle{ N }[/math] ist die endliche Menge der Nichtterminale. Sie sind Platzhalter für Strukturen, die noch durch Regeln ersetzt werden.
  • [math]\displaystyle{ T }[/math] ist die endliche Menge der Terminale. Das sind die Zeichen, aus denen die Wörter der Sprache bestehen, also das Alphabet der erzeugten Sprache. Kein Zeichen ist zugleich Nichtterminal und Terminal: [math]\displaystyle{ N \cap T = \emptyset }[/math].
  • [math]\displaystyle{ P }[/math] ist eine endliche Menge von Regeln (Produktionen) der Form [math]\displaystyle{ \alpha \to \beta }[/math]. Links steht eine Folge aus Nichtterminalen und Terminalen, die mindestens ein Nichtterminal enthält. Rechts steht eine beliebige, auch leere Folge aus Nichtterminalen und Terminalen.
  • [math]\displaystyle{ S \in N }[/math] ist das Startsymbol.

Die Reihenfolge der Bestandteile im Tupel ist eine Vereinbarung, manche Quellen schreiben [math]\displaystyle{ (N; T; S; P) }[/math].

Meist gelten diese Schreibweisen: Nichtterminale sind Großbuchstaben, Terminale sind Kleinbuchstaben, Ziffern oder Sonderzeichen. Ist nichts anderes angegeben, ist [math]\displaystyle{ S }[/math] das Startsymbol. Verbindlich ist diese Übereinkunft nicht: In den Beispielen dieses Wikis zum Kaffeeautomaten sind die Großbuchstaben [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math] Terminale. Steht in jeder Regel links genau ein Zeichen, lassen sich die Nichtterminale an den linken Seiten der Regeln ablesen, alle übrigen Zeichen sind Terminale. Stehen links mehrere Zeichen, müssen [math]\displaystyle{ N }[/math] und [math]\displaystyle{ T }[/math] angegeben sein.

Regeln mit derselben linken Seite lassen sich mit dem Strich [math]\displaystyle{ \mid }[/math] zusammenfassen: [math]\displaystyle{ \alpha \to \beta_1 \mid \beta_2 }[/math] steht für die beiden Regeln [math]\displaystyle{ \alpha \to \beta_1 }[/math] und [math]\displaystyle{ \alpha \to \beta_2 }[/math]. Die Form der Regeln bestimmt den Typ einer Grammatik, siehe Chomsky-Hierarchie.

Ableitung

Eine Ableitung erzeugt ein Wort aus dem Startsymbol. Ein Ableitungsschritt ersetzt in einer Zeichenfolge die linke Seite einer Regel durch ihre rechte Seite und wird [math]\displaystyle{ \Rightarrow }[/math] geschrieben. Zu einer Regel [math]\displaystyle{ \alpha \to \beta }[/math] gehört also der Schritt [math]\displaystyle{ u\alpha v \Rightarrow u\beta v }[/math]. Dabei sind [math]\displaystyle{ u }[/math] und [math]\displaystyle{ v }[/math] beliebige Zeichenfolgen aus Nichtterminalen und Terminalen, die unverändert stehen bleiben. Die Menge all dieser Zeichenfolgen wird [math]\displaystyle{ (N \cup T)^* }[/math] geschrieben, auch die leere Zeichenfolge gehört dazu.

[math]\displaystyle{ \Rightarrow^* }[/math] steht für null oder mehr Ableitungsschritte. Die Ableitung beginnt beim Startsymbol und ist fertig, wenn nur noch Terminale übrig sind. Ein Wort ist ableitbar, wenn es eine solche Ableitung gibt.

Erzeugte Sprache

Die von [math]\displaystyle{ G }[/math] erzeugte Sprache enthält alle Wörter aus Terminalen, die sich aus dem Startsymbol ableiten lassen:

[math]\displaystyle{ L(G) = \{w \in T^* \mid S \Rightarrow^* w\} }[/math]

Gelesen wird die Formel so: [math]\displaystyle{ L(G) }[/math] ist die Menge aller Wörter [math]\displaystyle{ w }[/math] über [math]\displaystyle{ T }[/math], für die gilt, dass [math]\displaystyle{ w }[/math] aus [math]\displaystyle{ S }[/math] ableitbar ist (zur Schreibweise siehe Mengenschreibweise). [math]\displaystyle{ T^* }[/math] ist die Menge aller Wörter über [math]\displaystyle{ T }[/math] einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math]. Zeichenfolgen mit Nichtterminalen gehören nicht zu [math]\displaystyle{ L(G) }[/math]. Zwei Grammatiken sind gleichwertig, wenn sie dieselbe Sprache erzeugen.

Um zu zeigen, dass ein Wort zu [math]\displaystyle{ L(G) }[/math] gehört, genügt eine Ableitung. Um zu zeigen, dass ein Wort nicht dazugehört, braucht es eine Eigenschaft, die alle ableitbaren Wörter haben und die dem Wort fehlt.

Beispiele

Satzbau beschreiben

Der Artikel Syntax beschreibt den Satzbau englischer Sätze mit Regeln. Als Grammatik gelesen sind [math]\displaystyle{ \text{Satz} }[/math], [math]\displaystyle{ \text{Subjekt} }[/math], [math]\displaystyle{ \text{Prädikat} }[/math] und [math]\displaystyle{ \text{Objekt} }[/math] die Nichtterminale, [math]\displaystyle{ \text{Satz} }[/math] ist das Startsymbol. Die Terminale sind die englischen Wörter und Wortgruppen wie „soccer players“. Die Regeln lauten:

[math]\displaystyle{ \text{Satz} \to \text{Subjekt Prädikat Objekt} }[/math]
[math]\displaystyle{ \text{Subjekt} \to \text{She} \mid \text{He} }[/math]
[math]\displaystyle{ \text{Prädikat} \to \text{loves} \mid \text{kicked} \mid \text{likes} }[/math]
[math]\displaystyle{ \text{Objekt} \to \text{soccer players} \mid \text{swimming} \mid \text{the ball} }[/math]

Das Subjekt hat 2 Möglichkeiten, das Prädikat 3 und das Objekt 3. Die Sprache enthält deshalb [math]\displaystyle{ 2 \cdot 3 \cdot 3 = 18 }[/math] Sätze. Die Grammatik prüft nur die Form, nicht die Bedeutung: Jede Kombination ist ein gültiger Satz.

Der Satz „She likes soccer players“ entsteht in vier Schritten:

Schritt Zeichenfolge angewendete Regel
0 [math]\displaystyle{ \text{Satz} }[/math] Startsymbol
1 [math]\displaystyle{ \text{Subjekt Prädikat Objekt} }[/math] [math]\displaystyle{ \text{Satz} \to \text{Subjekt Prädikat Objekt} }[/math]
2 [math]\displaystyle{ \text{She Prädikat Objekt} }[/math] [math]\displaystyle{ \text{Subjekt} \to \text{She} }[/math]
3 [math]\displaystyle{ \text{She likes Objekt} }[/math] [math]\displaystyle{ \text{Prädikat} \to \text{likes} }[/math]
4 [math]\displaystyle{ \text{She likes soccer players} }[/math] [math]\displaystyle{ \text{Objekt} \to \text{soccer players} }[/math]

Nach Schritt 4 stehen nur noch Terminale da. Die Ableitung ist fertig.

Grammatik als 4-Tupel angeben

Gegeben sind die Regeln einer Grammatik:

[math]\displaystyle{ S \to 0S1 \mid 01 }[/math]

Gesucht ist die Grammatik als 4-Tupel [math]\displaystyle{ G = (N; T; P; S) }[/math].

  1. Nichtterminale: Links vom Pfeil steht nur [math]\displaystyle{ S }[/math], also gilt [math]\displaystyle{ N = \{S\} }[/math].
  2. Terminale: Alle übrigen Zeichen der Regeln sind Terminale, also gilt [math]\displaystyle{ T = \{0; 1\} }[/math].
  3. Regeln: Der Strich trennt zwei Alternativen. Die Regelmenge enthält deshalb zwei Regeln: [math]\displaystyle{ P = \{S \to 0S1; S \to 01\} }[/math].
  4. Startsymbol: Es ist nichts anderes angegeben, also ist [math]\displaystyle{ S }[/math] das Startsymbol.

Damit lautet die Grammatik [math]\displaystyle{ G = (\{S\}; \{0; 1\}; P; S) }[/math].

Wort ableiten

Die Grammatik aus dem vorigen Beispiel hat das Startsymbol [math]\displaystyle{ S }[/math], die Terminale [math]\displaystyle{ 0 }[/math] und [math]\displaystyle{ 1 }[/math] und diese Regeln:

[math]\displaystyle{ S \to 0S1 \mid 01 }[/math]

Das Wort [math]\displaystyle{ 000111 }[/math] wird so abgeleitet:

[math]\displaystyle{ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000111 }[/math]
  • Schritt 1: Die Regel [math]\displaystyle{ S \to 0S1 }[/math] ersetzt [math]\displaystyle{ S }[/math] durch [math]\displaystyle{ 0S1 }[/math].
  • Schritt 2: Dieselbe Regel ersetzt das [math]\displaystyle{ S }[/math] in der Mitte erneut. Es entsteht [math]\displaystyle{ 00S11 }[/math].
  • Schritt 3: Die Regel [math]\displaystyle{ S \to 01 }[/math] ersetzt das [math]\displaystyle{ S }[/math] durch [math]\displaystyle{ 01 }[/math]. Es bleiben nur Terminale übrig.

Damit gilt [math]\displaystyle{ S \Rightarrow^* 000111 }[/math] und [math]\displaystyle{ 000111 \in L(G) }[/math].

Erzeugte Sprache bestimmen

Gesucht ist [math]\displaystyle{ L(G) }[/math] für die Grammatik aus dem Beispiel Wort ableiten mit den Regeln [math]\displaystyle{ S \to 0S1 }[/math] und [math]\displaystyle{ S \to 01 }[/math].

Jede Ableitung beginnt mit [math]\displaystyle{ S }[/math]. Jeder Schritt mit [math]\displaystyle{ S \to 0S1 }[/math] setzt links vom [math]\displaystyle{ S }[/math] eine [math]\displaystyle{ 0 }[/math] und rechts eine [math]\displaystyle{ 1 }[/math]. Nach [math]\displaystyle{ n - 1 }[/math] solchen Schritten steht [math]\displaystyle{ 0^{n-1} S 1^{n-1} }[/math] da. Die Schreibweise mit Exponent ist eine Wortpotenz: Der Exponent gibt an, wie oft das Zeichen hintereinander steht. Die Regel [math]\displaystyle{ S \to 01 }[/math] ersetzt dann [math]\displaystyle{ S }[/math] durch [math]\displaystyle{ 01 }[/math] und beendet die Ableitung. Nur diese Regel entfernt das [math]\displaystyle{ S }[/math]. Das Ergebnis ist [math]\displaystyle{ 0^n 1^n }[/math].

Die kürzesten Wörter sind [math]\displaystyle{ 01 }[/math], [math]\displaystyle{ 0011 }[/math] und [math]\displaystyle{ 000111 }[/math]. Es gilt:

[math]\displaystyle{ L(G) = \{0^n 1^n \mid n \geq 1\} }[/math]

Die Sprache enthält alle Wörter, die aus gleich vielen Nullen und Einsen bestehen und in denen alle Nullen vor den Einsen stehen. Das leere Wort gehört nicht dazu, weil jede Ableitung mit [math]\displaystyle{ S \to 01 }[/math] endet.

Nicht ableitbares Wort begründen

Für die Grammatik mit den Regeln [math]\displaystyle{ S \to 0S1 }[/math] und [math]\displaystyle{ S \to 01 }[/math] soll geprüft werden, ob [math]\displaystyle{ 001 }[/math] und [math]\displaystyle{ 0101 }[/math] zu [math]\displaystyle{ L(G) }[/math] gehören.

  • [math]\displaystyle{ 001 }[/math]: Jede der beiden Regeln erzeugt genau eine [math]\displaystyle{ 0 }[/math] und genau eine [math]\displaystyle{ 1 }[/math]. Jedes ableitbare Wort enthält deshalb gleich viele Nullen und Einsen. Das Wort [math]\displaystyle{ 001 }[/math] enthält zwei Nullen, aber nur eine Eins. Es ist nicht ableitbar: [math]\displaystyle{ 001 \notin L(G) }[/math].
  • [math]\displaystyle{ 0101 }[/math]: Das Wort enthält zwar gleich viele Nullen und Einsen. Die Regel [math]\displaystyle{ S \to 0S1 }[/math] setzt aber die [math]\displaystyle{ 0 }[/math] vor das [math]\displaystyle{ S }[/math] und die [math]\displaystyle{ 1 }[/math] dahinter, und die Regel [math]\displaystyle{ S \to 01 }[/math] ersetzt das [math]\displaystyle{ S }[/math] durch [math]\displaystyle{ 01 }[/math]. In jedem ableitbaren Wort stehen deshalb alle Nullen vor allen Einsen. In [math]\displaystyle{ 0101 }[/math] folgt auf eine [math]\displaystyle{ 1 }[/math] noch eine [math]\displaystyle{ 0 }[/math]. Es ist nicht ableitbar: [math]\displaystyle{ 0101 \notin L(G) }[/math].

Ausprobieren einzelner Ableitungen reicht für eine solche Begründung nicht aus, denn es müssten alle Ableitungen betrachtet werden. Die Begründung nennt deshalb eine Eigenschaft aller ableitbaren Wörter, die dem geprüften Wort fehlt.

Grammatik gegen eine Beschreibung prüfen

Eine Grammatik soll genau die Wörter erzeugen, die aus mindestens einer [math]\displaystyle{ 0 }[/math] und einer abschließenden [math]\displaystyle{ 1 }[/math] bestehen: [math]\displaystyle{ 01 }[/math], [math]\displaystyle{ 001 }[/math], [math]\displaystyle{ 0001 }[/math] und so weiter. Vorgeschlagen wird:

[math]\displaystyle{ S \to 0S \mid 1 }[/math]

Schritt 1: Gewünschte Wörter ableiten. Das Wort [math]\displaystyle{ 001 }[/math] ist ableitbar:

[math]\displaystyle{ S \Rightarrow 0S \Rightarrow 00S \Rightarrow 001 }[/math]

Schritt 2: Nach unpassenden Wörtern suchen. Geprüft werden die kürzesten Ableitungen und Ableitungen, die eine Regel mehrfach anwenden. Hier genügt schon die kürzeste: Sie wendet sofort die Regel [math]\displaystyle{ S \to 1 }[/math] an und erzeugt das Wort [math]\displaystyle{ 1 }[/math]. Dieses Wort enthält keine [math]\displaystyle{ 0 }[/math] und passt nicht zur Beschreibung. Die Grammatik erzeugt also ein Wort zu viel. Nicht jeder Fehler zeigt sich so früh: Manche unpassenden Wörter entstehen erst, wenn eine Regel, die sich wiederholen lässt, mehrfach angewendet wird.

Schritt 3: Grammatik korrigieren. Die erste [math]\displaystyle{ 0 }[/math] muss erzwungen werden. Das Startsymbol erzeugt deshalb zuerst eine [math]\displaystyle{ 0 }[/math] und übergibt dann an ein zweites Nichtterminal [math]\displaystyle{ A }[/math]. [math]\displaystyle{ A }[/math] hängt weitere Nullen an oder schließt mit [math]\displaystyle{ 1 }[/math] ab:

[math]\displaystyle{ S \to 0A }[/math]
[math]\displaystyle{ A \to 0A \mid 1 }[/math]

Schritt 4: Erneut prüfen. Jede Ableitung beginnt jetzt mit [math]\displaystyle{ S \Rightarrow 0A }[/math], jedes ableitbare Wort beginnt also mit einer [math]\displaystyle{ 0 }[/math]. Das Wort [math]\displaystyle{ 1 }[/math] ist nicht mehr ableitbar, [math]\displaystyle{ 001 }[/math] weiterhin:

[math]\displaystyle{ S \Rightarrow 0A \Rightarrow 00A \Rightarrow 001 }[/math]

Eine Grammatik passt nur dann zu einer Beschreibung, wenn beides gilt: Jedes beschriebene Wort ist ableitbar, und jedes ableitbare Wort passt zur Beschreibung.