inf-schule | Grammatiken

Fachkonzept

Im Einstieg hast du Syntaxdiagramme in Regeln übersetzt. Hier bekommen die Bausteine ihre Fachbegriffe. Als Beispiel dient die Grammatik für vereinfachte E-Mail-Adressen. Legende: S Emailadresse, U User, D Domain, K Subdomains, L Topleveldomain, M Name, B Buchstabe.

(1) S → U @ D
(2) U → M
(3) D → K L
(4) K → M .
(5) K → M . K
(6) L → M
(7) M → B
(8) M → B M
(9) B → b

Bestandteile einer Grammatik

Eine Grammatik legt durch Regeln fest, wie die Wörter einer formalen Sprache aufgebaut sind. Sie hat vier Bestandteile:

Bestandteil	Bedeutung	Symbol
Nichtterminalsymbole	Symbole, die noch ersetzt werden, meist Großbuchstaben. Im Syntaxdiagramm stehen sie eckig.	`N`
Terminalsymbole	Zeichen, die stehen bleiben. Im Syntaxdiagramm stehen sie rund. Sie bilden das Alphabet der Sprache.	`T`
Produktionsregeln	Ersetzungsregeln „linke Seite → rechte Seite“. Links steht genau ein Nichtterminalsymbol, rechts eine beliebige Folge von Symbolen (auch gar keins).	`P`
Startsymbol	das Nichtterminalsymbol, mit dem jede Ableitung beginnt (meist `S`). Es entspricht dem Startdiagramm.	`S`

Kurz schreibt man eine Grammatik als Tupel (feste Reihenfolge): G = (N, T, P, S)

Beispiel: Die E-Mail-Grammatik

Bestandteil	E-Mail-Grammatik
Nichtterminalsymbole	`N = {S, U, D, K, L, M, B}`
Terminalsymbole	`T = {b, @, .}`
Produktionsregeln	`P = {S → U @ D, U → M, D → K L, K → M ., K → M . K, L → M, M → B, M → B M, B → b}` (9 Regeln)
Startsymbol	`S`

Als Tupel: G = ({S, U, D, K, L, M, B}, {b, @, .}, P, S)

Kurzschreibweisen

Regeln mit derselben linken Seite fasst man mit | zusammen: M → B | B M steht für M → B und M → B M.
ε ist das leere Wort. Die Regel A → ε heißt: A wird durch nichts ersetzt und verschwindet.

Probiere es selbst aus:

Wörter ableiten

Ein Wort entsteht, indem man mit dem Startsymbol beginnt und immer wieder ersetzt.

Ein Ableitungsschritt ⇒ ersetzt genau ein Nichtterminalsymbol mit einer Regel durch deren rechte Seite.

Eine Ableitung ist eine Kette von Ableitungsschritten, die mit dem Startsymbol beginnt.

Jede Zeichenfolge der Kette (auch S am Anfang) heißt Satzform. Steht in der Satzform kein Nichtterminalsymbol mehr, ist die Ableitung zu Ende. Die Satzform ist dann ein Wort der Sprache.

Die erzeugte Sprache L(G) einer Grammatik G ist die Menge aller Wörter, die sich aus dem Startsymbol ableiten lassen.

Beispiel: Ableitung von b@b.b

Die Spalte „Satzform“ enthält alle Satzformen der Ableitung.

Schritt	Satzform	Regel
0	`S`	Startsymbol
1	`U @ D`	`S → U @ D`
2	`M @ D`	`U → M`
3	`B @ D`	`M → B`
4	`b @ D`	`B → b`
5	`b @ K L`	`D → K L`
6	`b @ M . L`	`K → M .`
7	`b @ B . L`	`M → B`
8	`b @ b . L`	`B → b`
9	`b @ b . M`	`L → M`
10	`b @ b . B`	`M → B`
11	`b @ b . b`	`B → b`