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 -> b b
name -> buchstabe
name -> buchstabe name
buchstabe -> b
E -> U@D
U -> N
D -> ST
S -> N.
S -> N.S
T -> bb
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.

Eine Grammatik besteht aus den folgenden Komponenten:
  • 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)
Hierfür schreibt man auch kurz: 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 -> bb
N -> B
N -> BN
B -> b

Hier gilt:

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 -> .bb

Hier gilt:

Dieses Beispiel zeigt, dass eine Produktion das leere Wort λ als rechte Seite einer Produktion haben kann. Auf der linken Seite einer Produktion steht oft nur ein Nichtterminalsymbol. Allerdings sind hier auch kompliziertere Wörter erlaubt.

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.): Ableitung des Worts bb@b.bbb.bb

E ->             # mit der Regel E -> bU@D
bU@D ->          # mit der Regel U -> N
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 -> bb
bb@b.bbb.bb

Beispiel 2 (s.o.) : Ableitung des Worts bb@b.bbb.bb

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 -> .bb
bb@b.bbb.bb

Beachte, dass es oft verschiedene Ableitungen zu einem Wort gibt.

Sprachfestlegung mit einer Grammatik

Eine Grammatik legt eine Sprache fest.

Eine Grammatik G = (T, N, P, S) erzeugt eine Sprache L(G) über dem Alphabet T. L(G) ist dabei die Menge der Wörter über T, die vom Startsymbol S mit Hilfe der Produktionen aus P abgeleitet werden können. Man nennt L(G) die von G erzeugte Sprache.

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). Diese Sprache wird ebenfalls durch folgende Grammatik erzeugt.

E -> bU
U -> bU
U -> @S
S -> bB
B -> bB
B -> .S
B -> .T
T -> bZ
Z -> b
X

Fehler melden

X

Suche