Fachkonzept - Grammatik
Ein Beispiel
Als Beispiel betrachten wir die vereinfachten E-Mail-Adressen aus einem der letzten Abschnitte.
| Grammatik - in Langform | Grammatik - in Kurzform |
|---|---|
emailadresse -> user @ domain user -> name domain -> subdomains topleveldomain subdomains -> name . subdomains -> name . subdomains topleveldomain -> name name -> buchstabe name -> buchstabe name buchstabe -> b |
E -> U@D U -> N D -> ST S -> N. S -> N.S T -> N N -> B N -> BN B -> b |
Die Grammatik legt genau fest, wie eine (vereinfachte) E-Mail-Adresse gebildet werden kann. Dabei wird das Bildungsgesetz mit Hilfe von Regeln beschrieben, die als Ersetzungsregeln benutzt werden. Im Folgenden soll dieser Ansatz, eine Sprache mit Ersetzungsregeln festzulegen, genauer beschrieben werden.
Bestandteile einer Grammatik
Wir präzisieren zunächst die Bestandteile einer Grammatik.
- einer endlichen nichtleeren Menge T von Terminalsymbolen (Alphabet der betreffenden Sprache)
- einer endlichen nichtleeren Menge N von Nichtterminalsymbolen (Hilfsymbole)
- einer endlichen Menge P von Produktionen (Ersetzungsregeln)
- einem Startsymbol S ∈ N (zum Starten einer Ableitung)
G = (T, N, P, S).
Im Zentrum stehen dabei die sogenannten Produktionen.
Eine Produktion hat die Gestalt u -> v.
Die linke Seite u und die rechte Seite v sind dabei Wörter über dem Alphabet V = T ∪ N
sämtlicher Symbole.
Die linke Seite u muss mindestens ein Nichtterminalsymbol aus N enthalten.
Beispiel 1:
E -> U@D U -> N D -> ST S -> N. S -> N.S T -> N N -> B N -> BN B -> b
Hier gilt:
- Terminalsymbole: {b, @, .}
- Nichtterminalsymbole: {E, U, D, S, T, N}
- Produktionen: {E -> U@D, U -> bU, ..., B -> b}
- Startsymbol: E
Beachte, dass das Startsymbol oft durch die linke Seite der ersten aufgelisteten Regel implizit festgelegt wird.
Beispiel 2:
E -> bU@D U -> bU U -> λ D -> bS S -> bS S -> .bS .bS -> .bT T -> bT T -> λ
Hier gilt:
- Terminalsymbole: {b, @, .}
- Nichtterminalsymbole: {E, U, D, S, T}
- Produktionen: {E -> U@D, U -> bU, ..., T -> λ}
- Startsymbol: E
Dieses Beispiel zeigt, dass eine Produktion das leere Wort λ als rechte Seite einer Produktion haben kann. Es zeigt auch, dass auf der linken Seite einer Produktion komplexere Wörter stehen können.
Worterzeugung mit Ableitungen
Produktionen einer Grammatik dienen zur Worterzeugung.
Eine Ableitung beginnt immer mit dem Startsymbol. Sie endet, wenn alle Nichtterminalsymbole ersetzt sind. Ein Ableitungsschritt besteht darin, ein Teilwort innerhalb eines Worts mit Hilfe einer passenden Produktion zu ersetzen. Produktionen sind demnach Ersetzungsregeln.
Beispiel 1 (s.o.):
E -> U@D U -> N D -> ST S -> N. S -> N.S T -> N N -> B N -> BN B -> b
Ableitung des Worts bb@b.bbb.bb mit den Produktionen:
E -> # mit der Regel E -> U@D U@D -> # mit der Regel U -> N N@D -> # mit der Regel N -> BN BN@D -> # mit der Regel B -> b bN@D -> # mit der Regel N -> B bB@D -> # mit der Regel B -> b bb@D -> # mit der Regel D -> ST bb@ST -> # mit der Regel S -> N.S bb@N.ST -> # mit der Regel S -> N. bb@N.N.T -> # mit der Regel N -> B bb@B.N.T -> # mit der Regel B -> b bb@b.N.T -> # mit der Regel N -> BN bb@b.BN.T -> # mit der Regel N -> BN bb@b.BBN.T -> # mit der Regel N -> B bb@b.BBB.T -> # mit der Regel B -> b bb@b.bBB.T -> # mit der Regel B -> b bb@b.bbB.T -> # mit der Regel B -> b bb@b.bbb.T -> # mit der Regel T -> N bb@b.bbb.N -> # mit der Regel N -> BN bb@b.bbb.BN -> # mit der Regel B -> b bb@b.bbb.bN -> # mit der Regel N -> B bb@b.bbb.bB -> # mit der Regel B -> b bb@b.bbb.bb
Beispiel 2 (s.o.):
E -> bU@D U -> bU U -> λ D -> bS S -> bS S -> .bS .bS -> .bT T -> bT T -> λ
Ableitung des Worts bb@b.bbb.bb mit den Produktionen:
E -> # mit der Regel E -> U@D U@D -> # mit der Regel U -> bU bU@D -> # mit der Regel U -> bU bbU@D -> # mit der Regel U -> λ bb@D -> # mit der Regel D -> bS bb@bS -> # mit der Regel S -> .bS bb@b.bS -> # mit der Regel S -> bS bb@b.bbS -> # mit der Regel S -> bS bb@b.bbbS -> # mit der Regel S -> .bS bb@b.bbb.bS -> # mit der Regel .bS -> .bT bb@b.bbb.bT -> # mit der Regel T -> bT bb@b.bbb.bbT -> # mit der Regel T -> λ bb@b.bbb.bb
Beachte, dass es auch verschiedene Ableitungen zu einem Wort geben kann.
Sprachfestlegung mit einer Grammatik
Eine Grammatik legt eine Sprache fest.
Die von einer Grammatik G=(T, N, P, S) erzeugte Sprache L(G) ist die Menge aller Wörter über dem Alphabet T, die vom Startsymbol S mit Hilfe der Produktionen aus P abgeleitet werden können.
Beachte, dass verschiedene Grammatiken dieselbe Sprache erzeugen können. So erzeugen die Grammatiken aus Beispiel 1 (s.o.) und Beispiel 2 (s.o.) dieselbe Sprache (der stark vereinfachten E-Mail-Adressen).
