Übungen

Aufgabe 1: ipigisi

Gegeben sind die folgenden Produktionen.

S -> iAi
A -> siAis
A -> piBis
B -> siBis
B -> g

(a) Welche der folgenden Wörter können mit den Produktionen abgeleitet werden?

ipigisi, isipisigisi, isipisigisisisi

(b) Welche Sprache wird durch die angegebene Grammatik festgelegt?

(c) Entwickle auch Syntaxdiagramme, die den Produktionen entsprechen.

Aufgabe 2: Rechenausdrücke

Im Abschnitt Einstieg - Rechenausdrücke wird der Aufbau von Rechenausdrücken mit Hilfe von Syntaxdiagrammen beschrieben.

(a) Entwickle eine Grammatik, die den Syntaxdiagrammen entspricht.

(b) Teste die Grammatik mit JFlap.

(c) Schreibe die Grammatik als EBNF-Beschreibung.

Aufgabe 3: FEN

Die Forsyth-Edwards-Notation (kurz FEN) wird benutzt, um Schach-Spielzustände zu beschreiben. In der freien Enzyklopädie Wikipedia findet man die folgende Grammatik von FEN in EBNF:

FEN := Position " " Spieler " " Rochade " " en-passant " " Halbzüge " " Zugnummer
Position := Reihe "/" Reihe "/" Reihe "/" Reihe "/" Reihe "/" Reihe "/" Reihe "/" Reihe
Reihe := { Figur | Leerfelder }+
Figur :=  "p" | "r" | "n" | "b" | "q" | "k" | "P" | "R" | "N" | "B" | "Q" | "K"
Leerfelder := "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8"
Spieler := "w" | "b"
Rochade := "K" ["Q"] ["k"] ["q"] | "Q" ["k"] ["q"] | "k" ["q"] | "q" | "-"
en-passant := "-" | ( ("a"|"b"|"c"|"d"|"e"|"f"|"g"|"h") ("3"|"6") )
Halbzüge := positiveGanzeZahl
Zugnummer := positiveGanzeZahl

Die folgende Zeichenkette soll betrachtet werden:

8/1p1kpQ2/2np4/1p2b1BP/2q2p2/8/5PP1/5RK1 w - - 1 30

(a) Erkläre mit Hilfe der Grammatik, dass diese Zeichenkette einen Schach-Spielzustand in FEN korrekt beschreibt.

(b) Welche Bedeutung hat die vorgegebene Zeichenkette? Legen die Grammatikregeln auch die Bedeutung der benutzten Symbole fest?

Aufgabe 4: Postanschriften

Entwickle eine Grammatik in Backus-Naur-Form für Postanschriften. Beachte die folgenden Aspekte:

• Eine Postanschrift besteht aus einem Personenteil, gefolgt von einer Straße, gefolgt von der Stadt.
• Der Personenteil besteht aus einem Titelteil und einem Namensteil, gefolgt von einem Zeilenende.
• Der Titelteil besteht aus einem Titel oder ist leer.
• Der Vornamenteil besteht aus einem Vornamen oder einem Initial, auf den ein Punkt folgt.
• Der Namensteil besteht aus einem Vornamensteil, einem Nachnamen oder aus einem Vornamensteil und wiederum aus einem Namensteil.
• Eine Straße besteht aus einem Straßenname, gefolgt von einer Hausnummer, gefolgt von einem Zeilenende.
• Eine Stadt besteht aus einer Postleitzahl, gefolgt von einem Stadtname, gefolgt von einem Zeilenende.

Eine Lösung findest du in der freien Enzyklopädie Wikipedia unter dem Stichwort Backus-Naur-Form.