Übung Kellerautomaten

---

Aufgabe 1

Gegeben ist die Sprache L = {aⁿbⁿ | n > 0}

1. Geben Sie eine Grammatik für diese Sprache an.
2. Geben Sie ein Syntaxdiagramm zu dieser Grammatik an.
3. Entwickeln Sie den Graphen für einen zugehörigen Kellerautomaten mit Angabe der Überführungsfunktion. Testen Sie diesen Kellerautomaten mit dem Simulationsprogramm.
4. Schreiben Sie ein eigenes gut strukturiertes Java-Programm mit eigener Kellerverwaltung (z. B. als String) für diesen Automaten.

---

Aufgabe 2

Führen Sie eine "vorausschauende" Syntaxanalyse des Wortes "((()())())" nach der angegebenen Grammatik G₂ im Kapitel Algorithmische Umsetzung von Kellerautomaten durch, indem jeweils das Restwort und der Kellerinhalt zeilenweise angegeben wird.

---

Aufgabe 3

Entwickeln Sie für die "vorausschauende" Syntaxanalyse mit der Grammatik

G = (N,T,P,S)
V = {S}
V = {( , ) , a ... z}
P = {S -> (S)S | a ... z | nichts}

ein Demonstrationsprogramm.

---

Aufgabe 4

Entwerfen Sie einen Kellerautomaten (Zustandsgraph und Übergangsfunktion) der folgende formale Sprache erkennt und testen Sie ihn mithilfe des Simulationsprogramms: Wörter der Form IIII-IIII mit gleich viel Strichen links und rechts vom Trennzeichen.

---

Aufgabe 5

Gegeben ist eine Grammatik für die Sprache der vereinfachten arithmetischen Ausdrücke.

G = (N,T,P,S)
N = {A,T,F}
T = {a,+,*,(,)}
P = {( A -> A + T | T),
     ( T -> T * F | F),
     ( F -> ( A ) | a)}

1. Erzeugen Sie einige vereinfachte arithmetische Ausdrücke aus dem Startsymbol A.
2. Zeichnen Sie die Syntaxbäume für die Ausdrücke
   • (a+a)*a
   • a+a*a
   • a+aa
   • (a+(a*a+a)*a)
   • (a+(a*a+a*a))
3. Begründen Sie, weshalb man mit dieser Grammatik durch Vorausschau (look ahead) über eine feste Zahl von Zeichen nicht die richtige anzuwendende Regel fnden kann.
4. Schreiben Sie einen Rekursiv-Descent-Parser, der Worte auf die gegebene Grammatik hin überprüft. (Achtung: Die Produktionen sind vorher noch abzuändern. Begründen Sie, weshalb.)
5. Geben Sie Ausdrücke für eine Grammatik an, mit der man eine Eingabefolge durch Vorausschau analysieren kann. Entwickeln Sie für diese Grammatik eine Parsingtabelle und schreiben Sie ein entsprechendes Programm zur Wortanalyse (sehr schwierig und eigentlich zu weit ...).

---

Aufgabe 6

(E)chte (Z)weiseitige (V)erzweigungen werden durch das folgende Syntaxdiagramm beschrieben:

Im Vorfeld wurden von einem Scanner die Token i, t und e für die Worte if, then und else gesetzt.

1. Erzeugen Sie einige EZV's entsprechend dem Syntaxdiagramm.
2. Entwickeln Sie einen Kellerautomaten und testen Sie diesen in einem Prolog- und einem Java-Programm
3. Geben Sie eine zugehörige Grammatik an.
4. Erweitern Sie diese Grammatik, damit neben den EZV's auch einseitige Verzweigungen (if .. then) zugelassen werden. Welche Probleme könnten dabei auftreten?