Einstieg

Eine Grammatik für vereinfachte E-Mail-Adressen

Wie schon in den vorherigen Kapiteln soll es im Einstiegsbeispiel um vereinfachte E-Mail-Adressen gehen. Ausgangspunkt sollen die abgebildeten Syntaxdiagramme für diese Adressen sein.

Wie in den Diagrammen zu erkennen ist, soll eine E-Mail-Adresse hier aus verschiedenen Elementen wie User, Domain und Tld aufgebaut sein.

Letztendlich wird durch die Diagramme genau definiert, nach welchen Regeln und aus welchen Terminalzeichen (Buchstaben, Ziffern, Satzzeichen, Sonderzeichen) eine E-Mail-Adresse aufgebaut werden muss.

Im weiteren Verlauf soll eine Grammatik entstehen, die zu diesen Syntaxdiagrammen passt und die selben Regeln formuliert.

Umwandlung der Syntaxdiagramme in eine Grammatik

Syntaxdiagramm Email

Im ersten Diagramm wird der grobe Aufbau der Adressen festgelegt. Es handelt sich hier um die Festlegung einer Sequenz aus dem Nichtterminal User, dem Terminalzeichen @ und dem Nichtterminal Domain.

In einer Grammatik würde das der folgenden Produktionsregel entsprechen:
Email -> User @ Domain
Die Zeile besagt, dass das Nichterminal Email durch die Folge User @ Domain ersetzt werden kann. Eine Produktion ist entsprechend als Ersetzungsregel zu lesen.

Syntaxdiagramm User

Dieses Syntaxdiagramm enthält eine Wiederholung. Ein User darf aus einem oder mehreren (durch Punkte getrennte) Namen bestehen. Die entsprechende Umwandlung in eine Produktion ist etwas komplexer:
User -> Name | Name . User
Hierbei bedeutet der senkrechte Strich ein "oder". Das Nichtterminal User kann also entweder durch das Nichtterminal Name oder durch die Folge Name . User ersetzt werden. Die Wiederholung wird hierbei durch Rekursion erreicht: das Nichtterminal User kann durch eine Folge ersetzt werden, in der User erneut vorkommt.

Syntaxdiagramm Name

Das Syntaxdiagramm Name enthält (in der Wiederholung) zwei alternative Wege: Ziffer und Zeichen. Die Umsetzung geschieht hier durch zwei Regeln:
Name -> Zeichen Name2
Name2 -> EPSILON | Ziffer Name2 | Zeichen Name2
In der ersten Regel wird der Name durch das erste Zeichen und den Rest (Name2) ersetzt. Name2 kann dann eine der drei Alternativen annehmen: nichts (EPSILON), Ziffer Name2 oder Zeichen Name2. Auch hier wird die Wiederholung durch Rekursion erreicht.

Syntaxdiagramm Domain

Das Syntaxdiagramm Domain enthält wieder eine Sequenz und darin eine Wiederholung. Die Umsetzung geschieht hier wieder durch zwei Regeln:
Domain -> Zeichen Zeichen Zusatz . Tld
Zusatz -> Zeichen Zusatz | EPSILON
In der ersten Regel wird die Domain durch die Folge Zeichen Zeichen Zusatz . Tld ersetzt. Zusatz kann dann die Folge Zeichen Zusatz oder nichts (EPSILON) sein.

Syntaxdiagramm Tld, Zeichen und Ziffer

Die Tld kann aus zwei oder drei Zeichen bestehen, entsprechend lautet die Produktionsregel:
Tld -> Zeichen Zeichen | Zeichen Zeichen Zeichen
Die Produktionsregel für Ziffern und Zeichen (beschränkt auf a,b,c,z) ergeben sich dann wie folgt:
Zeichen -> a | b | c | z
Ziffer -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Die Ableitung von Wörtern aus einer Grammatik

Heri siehst du nochmals die gesamte Grammatik für vereinfachte E-Mail-Adressen mit farblicher Hervorhebung der Nichtterminalzeichen in orange und der Terminalzeichen in schwarz. Das Schlüsselwort EPSILON für die leere Ersetzung ist grün markiert.

Um mit dieser Grammatik eine gültige Zeichenfolge zu erzeugen, muss du mit dem Startzeichen Email beginnen und solange Produktionsregeln anwenden, bis nur noch Terminalzeichen vorhanden sind.

Die Ableitung von "a1@cc.ab"

In der folgenden Ableitung ist jeweils die Nummer der Zeile der angewendeten Ersetzungsregel angegeben. Die Ableitung beginnt mit dem Startsymbol Email.

aktueller Ausdruck	angewendete Regel	neuer Ausdruck
Email	(1) Email -> User @ Domain	User @ Domain
User @ Domain	(2) User -> Name	Name @ Domain
Name @ Domain	(3) Name -> Zeichen Name2	Zeichen Name2 @ Domain
Zeichen Name2 @ Domain	(4) Name2 -> Ziffer Name2	Zeichen Ziffer Name2 @ Domain
Zeichen Ziffer Name2 @ Domain	(8) Zeichen -> a	a Ziffer Name2 @ Domain
a Ziffer Name2 @ Domain	(9) Ziffer -> 1	a 1 Name2 @ Domain
a 1 Name2 @ Domain	(4) Name2 -> EPSILON	a 1 @ Domain
a 1 @ Domain	(5) Domain -> Zeichen Zeichen Zusatz . Tld	a 1 @ Zeichen Zeichen Zusatz . Tld
a 1 @ Zeichen Zeichen Zusatz . Tld	(8) Zeichen -> c	a 1 @ c Zeichen Zusatz . Tld
a 1 @ c Zeichen Zusatz . Tld	(8) Zeichen -> c	a 1 @ c c Zusatz . Tld
a 1 @ c c Zusatz . Tld	(8) Zeichen -> EPSILON	a 1 @ c c . Tld
a 1 @ c c . Tld	(7) Tld -> Zeichen Zeichen	a 1 @ c c . Zeichen Zeichen
a 1 @ c c . Zeichen Zeichen	(8) Zeichen -> a	a 1 @ c c . a Zeichen
a 1 @ c c . a Zeichen	(8) Zeichen -> b	a 1 @ c c . a b

Das Wort "a1@cc.ab" konnte abgeleitet werden und gehört somit zur Sprache, die durch die Grammatik definiert wird.