Prof. Dr. R. Laue                                                                                                                                  WS9899
                                Informatik III
                                Übungsblatt 7
                                Abgabe: 11.1.99 in der Vorlesung

URL:         /axel/informatik3_ws9899_blatt7.html
Dieses  Übungsblatt ist alleine zu bearbeiten.
 

Aufgabe 19 (10 + 3 + 2 + 2 Punkte)
In Aufgabe 16 wurde  für den Taschenrechner ein lex/yacc Programm geschrieben. Nun soll die Syntax erweitert werden, damit Variablen funktionieren:
<eingabe>      a=5;
<ausgabe>     5
<eingabe>       a*2;
<ausgabe>      10
Die Arbeit soll zwischen lex und yacc geteilt werden. lex soll das Token Variable liefern und den aktuellen Wert zurück geben. Dazu muß lex eine Verwaltung der Variablennamen vornehmen, d.h. beim ersten mal Platz für Name und Wert schaffen. 10 Punkte für das neue lex/yacc Programm. 3 Punkte für die neue Grammatik. 2+2  Punkte für die Behandlung folgender Fragen: welche Datenstruktur ist zu wählen, wenn die Verwaltung der Variablen zeitkritisch ist und auch bei einer großen Anzahl von Variablen funktionieren soll. Wie funktioniert die Fehlerbehandlung, d.h. was passiert wenn eine Variable angesprochen wird, die noch nicht definiert wurde.

Aufgabe 20 (11 Punkte)
In der Aufgabe 10 wurde eine Grammatik für den Taschenrechner vorgestellt. Dabei wurde durch geschickte Vorgehensweise erreicht, daß Punkt vor Strich ausgerechnet wird. Betrachten Sie den Taschenrechner, der folgende
Operationen kann: Plus, Minus, Multiplikation, Division
- Geben Sie eine linksrekursionfreie Grammatik an (2 Punkte)
- Geben Sie die Parsertafel bei Top Down Syntaxanalyse für diese Grammatik an (5 Punkte)
- Erstellen Sie unter Angabe des Kellers einen Syntaxbaum für
                3 + (2 * 7) + 34; 3;                                              ( 4 Punkte)

Aufgabe 21 (2 + 6 + 2 + 6 Punkte)
Betrachten Sie folgende Grammatik Regeln:

(1) E --> E sub E sup E
(2) E --> E sub E
(3) E --> E sup E
(4) E --> { E }
(5) E --> c

c ist dabei ein einzelnes Token. Dies ist Teil der Grammatik des Programms EQN, das früher unter UNIX zur Textverarbeitung verwendet wurde.

- Welche Konflikte erwarten Sie nach liebevollem Betrachten der Grammatik Regeln.
- Konstruieren Sie die kanonischen LR(0) Item Mengen
- Bei welchen Item Mengen treten Konflikte auf, wie werden sie sinnvoll gelöst?
- Stellen Sie die SLR Parsertafel auf.