Eine Grammatik aus Produktionen

Eine vereinfachte Darstellung der Ersetzungsregeln

Syntaxdiagramme legen Ersetzungsregeln fest. Diese Ersetzungsregeln lassen sich - wie im letzten Abschnitt gezeigt - textuell darstellen. Für viele eher theoretische Fragestellungen benutzt man eine elementarere Darstellung der Ersetzungsregeln. Die folgende Übersicht zeigt diese vereinfachte Version von Ersetzungsregeln.

Syntaxdiagramm	Ersetzungsregeln (elementar)
Emailadresse:	(1) Emailadresse -> User @ Domain
User:	(2) User -> Name
Domain:	(3) Domain -> Subdomains Topleveldomain
Subdomains:	(4) Subdomains -> Name . (5) Subdomains -> Name . Subdomains
Topleveldomain:	(6) Topleveldomain -> Name
Name:	(7) Name -> Buchstabe (8) Name -> Buchstabe Name
Buchstabe:	(9) Buchstabe -> b

Die Ersetzungsregeln sind hier zusätzlich durchnummeriert. Beachte, dass zur Beschreibung von Syntaxdiagrammen mit Verzeigungen mehrere Ersetzungsregeln benutzt werden. Beachte auch, dass iterierte Wege mit Hilfe rekursiver Ersetzungsregeln beschrieben werden.

Die Ableitung einer E-Mail-Adresse kann man jetzt wie folgt mit Ersetzungsvorgängen beschreiben.

Emailadresse ->                                                # (1)
User @ Domain ->                                               # (2)
Name @ Domain ->                                               # (8)
Buchstabe Name @ Domain ->                                     # (9)
b Name @ Domain ->                                             # (7)
b Buchstabe @ Domain ->                                        # (9)
b b @ Domain ->                                                # (3)
b b @ Subdomains Topleveldomain ->                             # (5)
b b @ Name . Subdomains Topleveldomain ->                      # (7)
b b @ Buchstabe . Subdomains Topleveldomain ->                 # (9)
b b @ b . Subdomains Topleveldomain ->                         # (4)
b b @ b . Name . Topleveldomain ->                             # (8)
b b @ b . Buchstabe Name . Topleveldomain ->                   # (9)
b b @ b . b Name . Topleveldomain ->                           # (8)
b b @ b . b Buchstabe Name . Topleveldomain ->                 # (9)
b b @ b . b b Name . Topleveldomain ->                         # (7)
b b @ b . b b Buchstabe . Topleveldomain ->                    # (9)
b b @ b . b b b . Topleveldomain ->                            # (6)
b b @ b . b b b . Name ->                                      # (8)
b b @ b . b b b . Buchstabe Name ->                            # (9)
b b @ b . b b b . b Name ->                                    # (7)
b b @ b . b b b . b Buchstabe ->                               # (9)
b b @ b . b b b . b b

Aufgabe 1

(a) Entwickle analog eine Ableitung zur Zeichenkette bb@bbb.bb.

(b) Warum kann man keine Ableitung zur Zeichenkette bbb@bbb erzeugen?