= Datum der Prüfung
29. September 2021

= Benötigte Lernzeit als Empfehlung
2 Wochen, wenn man die Inhalte schon gut verstanden hatte und in der Vorlesung und Übung regelmäßig mitgelernt hat. Vom Anteil an Aufgaben mit Code würde ich sagen, dass man auch ohne C zu können gut bestehen kann, aber nicht sehr gut. 

= Verwendete Materialien (Bücher, Skripte etc...)
Protokolle, Repetitorium, alles was wie Klausuraufgaben ist. Die Folien und Übungsaufgaben helfen beim Gesamtverständnis, aber es kommen eben immer wieder die gleichen Aufgaben in Compilerbau, die man gut üben kann. Die Klausur ist sehr viel näher an der Vorlesung, als an der Übung. Die Übung hilft aber wiederum mehr die Zusammenhänge zu verstehen.

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Take Home Klausur, die Atmosphäre bei mir Zuhause ist ganz nett.
Es lief kein Zoom Meeting oder sonstige "Überwachung". Man hatte einfach seine Ruhe.

= Prüfungsfragen
Die Klausur war open Book, aber ich fand es war fast gar keine Zeit etwas nachzuschauen. 150min Zeit. 30min für Upload. Allein das Lesen der Aufgabenstellung hat ziemlich lang gedauert.

Aufgabe 1 - Compilerbau Allgemein - 23 Punkte (9+6+8)
a) Finden Sie möglichst viele Fehler im (vermeintlichen) C-Programm auf der folgenden Seite. Klassifizieren Sie die Fehler nach folgenden Kategorien und geben Sie eine kurze Fehlerbeschreibung an:
lex - lexikalischer Fehler
syn - syntaktische Fehler
sem - (statisch) semantische Fehler
log - logische Fehler
Es sind insgesamt 14 Fehler obiger Kategorien im Quelltext enthalten. Dabei werden die Punkte wie folgt verteilt:
* für jeden richtig gefundenen und korrekt eingeordneten Fehler 1 Punkt
* für jeden richtig gefundenen, aber falsch eingeordneten Fehler 1/2 Punkt
* für jeden inkorrekt identifizierten Fehler -1/2 Punkte
* Fehler, die identisch mehrfach auftreten, werden nur einmal gezählt
Die maixmal erreichbare Punktzahl liegt bei 9 Punkten, die minimale bei 0 Punkten. Das Programm soll einen rekursiven Abstiegsparser für die folgende Grammatik umsetzen:
(1) T -> epsilon
(2) T -> (L,R)
(3) L -> T
(4) R -> T
(5) T -> v
Um Ihnen die Arbeit zu erleichtern, haben wir für Sie die folgende Tabelle mit den FIRST- und FOLLOW-Mengen ausgefüllt.
    FIRST           FOLLOW
T   epsilon v (     $ , )
L   epsilon v (     ,
R   epsilon v (     )

(Wenn mehr als 14 Fehler drin sind, habe ich mich vertippt.)
CODE:
1 extern char* strchr(const char *str, int character);
2 char *const input = "((v,(,v)),)";
3
4 int any(const char *s) { return !!strchr(*input, s); }
5 int eof() { return *input == NULL }
6
7 void err() {
8         printf("error: %c not allowed here\n", input);
9         exit(-1);
10 }
11
12 void eat () {
13         if (eof) {
14                 printf("error: end of input\n);
15                 exit(-2);
16         }
17         input++;
18 }
19 
20 void T() {
21         if (any("(")) {
22                 L();
23                 if (any(",")) eat();
24                 R();
25                 if (any(")") eat();
26                 return;
27         }
28         if (any("v")) eat(); return;
29         if (any("),")) return;
30         else err();
31 }
32
33 void L() {
34        if (any("(v)")) T();
35        else err();
36 }
37
38 void R() {
39         if (any("(v,")) T();
40         else err();
41 }
42 
43 int main() {
44         T();
45         if eof() printf("ok\n");
46         else err("no further input expected\n");
47 }

b) Welche Ausgabe (auf stdout) erzeugt das folgende (fehlerfreie) C-Programm?
CODE:
1 #include <stdio.h>
2
3 int a(int i) {
4         return ++i;
5 }
6
7 int b(int* i) {
8         return (*i)++;
9 }
10
11 int* c(int* i) {
12        ++(*i);
13        return o;
14 }
15
16 int d(int* i) {
17        return *(i++);
18 }
19
20 int e(int i) {
21       static int s = 1;
22       return s+=++1;
23 }
24 
25 #define E(X) printf("%i ", X)
26 #define D(X) E(X); E(X)
27
28 int main() {
29        int x[6] = {6};
30
31        D( a(x[0]));
32        D( b(x+1) );
33        D(*c(x+2) );
34        D( d(x+3) );
35        D( e(x[4]));
36        D( x[0]+x[1]+x[2]+x[3]+x[4]+x[5] );
37
38        return 0;
39 }

c) Welche der folgenden Aussagen sind korrekt?
i) Die Sprache über Sigmar = {a,b} mit gleicher Anzahl von a und b ist regulär.
ii) Alle regulären Sprachen haben eine LR(0)-Grammatik
iii) Deterministische Zustandsmaschinen mit Kellerspeicher können bei entsprechender Programmierung jede kontextfreie Sprache erkennen.
iv) Nichtdeterministische Zustandsmaschinen mit Kellerspeicher können bei entsprechender Programmierung jede kontextfreie Sprache erkennen.

d) Beim Aufbau der LL(1)-Tabelle ergibt sich ein Mehrfacheintrag. Was bedeutet das?
i) Die Grammatik ist nicht in LL(1).
ii) Die Grammatik ist mehrdeutig.
iii) Es existiert für diese Grammatik kein Parser mit rekursivem Abstieg.
iv) Es existiert für diese Grammatik kein tabellengestützter LL(1)-Parser.

e) Wieviele Worte kann eine LL(o)-Sprache maximal enthalten?
i) keines
ii) genau eines
iii) genau zwei
iv) abzählbar unendlich viele

f) Nennen Sie das kleinste k, für das die folgende Grammatik in LL(k) ist.
(1) S -> sushi
(2) S -> sashimi
(3) S -> yakitori
(4) S -> teriyaki
(5) S -> sukiyaki
(6) S -> tonkatsu


Aufgabe 2 - Reguläre Ausdrücke - 26 Punkte (4+9+13)
a) Gegeben ist die Beschreibung eines Identifikators einer fiktiven Institutuion. Der identifikator besteht aus vier verschiedenen Teilen, die durch Schrägstriche voneinander getrennt sind, wobei die Teile 3 und 4 jeweils optional sind.
Auch wenn einer dieser Teile fehlt, bleiben die jeweiligen Schrägstriche erhalten.
Bei allen vorkommenden Buchstaben handelt es sich ausschließlich um Kleinbuchstaben.
*Den ersten Teil bildet der sogenannte Zwei-Buchstaben-Sprachcode, z.B. de für deutsch, wobei Sprache mit zwei weiteren Buchstaben, die mit einem Bindestrich abgetrennnt sind, zur Verfeinerung angehangen werden können, wie etwa en-us oder en-uk.
*Der zweite Teil besteht aus einer zweistelligen Zahl.
*Der dritte Teil ist eine Zeichenkette beliebiger Länge, die mit einem Buchstaben beginnt und danach Buchstaben, Ziffern und Unterstriche enthalten kann.
*Der vierte Teil enthält eine hierarschiche Klassifizierungsnummer, die aus mindestens zwei Hierarchiestufen besteht. Hierarchiestufen bestehen aus jeweils zwei Ziffern und werden durch Punkte voneinander getrennt.
Bestimmen Sie basierend auf der Beschreibung für die folgenden Zeichenketten, ob es sich jeweils um einen gültigen Identifikator handelt oder nicht:
i) en/12/a1_3/13.12
ii) de/73/aafg23rwef/
iii) en/as/a1_3/13.12
iv) se/12/asdfa/
v) de/73/aafgrwef
vi) se/12//asdfa
vii) en-uk/01/01.02.02
viii) en-uk/01//01.02.02

b) Schreiben Sie einen regulären Ausdruck, für den zuvor beschriebenen Identifikator auf.

c) Konstruieren Sie einen DFA für die Sprache aller Strings über dem Alphabet Sigmar = {a,b} mit gerade Anzahl von a und ungerader Anzahl von b.


Aufgabe 2 - LL(k)-Syntaxanalyse - 32 Punkte (6+4+10+12)
a) Formen Sie die folgende Grammatik in eine LL(1)-Grammatik um und berechnen Sie zur Probe für jedes Metasymbol die FIRST- und FOLLOW-Menge.
(1) S -> aXab
(2) S -> Y
(3) X -> bSa
(4) X -> epsilon
(5) Y -> Sc

b) Erstellen Sie aus der Grammatik der vorigen Aufgabe eine LL(1)-Syntaxanalysetabelle, indem Sie die folgende Tabelle ausfüllen. Es reicht, wenn sie nur die rechten Seiten der Regeln eintragen.

c) Analysieren Sie mit Hilfe der von Ihnen erstellen Syntaxanalysetabelle das Wort abaabcaabc.

d) Bei welchen der folgenden Grammatiken handelt es sich um LL(1)-Grammatiken? Begründen Sie Ihre Antwort mit Hilfe der FIRST- und FOLLOW-Mengen.
(1) S -> aXY
(2) X -> bY
(3) X -> cY
(4) X -> e
(5) Y -> XY
(6) Y -> d
(7) Y -> S

(1) S -> XYX
(2) X -> epsilon
(3) X -> a
(4) X -> b
(5) Y -> c
(6) Y -> d
(7) Y -> eXe

(1) S -> XYZ
(2) X -> Yc
(3) X -> a
(4) Y -> epsilon
(5) Y -> c
(6) Z -> epsilon
(7) Z -> b


Aufgabe 4 - LR(k)-Syntaxanalyse - 32 Punkte (4+28)
a)
i) Sie haben die Aufgabe unter Nutzung von Bison einen Parser für eine vorgegebene Sprache zu schreiben. In der Sprachgrammatik finden Sie folgendes Konstrukt; erwarten Sie irgendwelche Probleme? Falls ja, welche?
<stat> -> if (<cond>) <stat>
       -> if (<cond>) <stat> else <stat>
ii) Erwarten Sie (unter den gleichen Bedinungen wie zuvor) hier Probleme? Falls ja, welche?
<expr> -> <expr> + <expr>
       -> <expr> - <expr>
       -> <expr> * <expr>
       -> <expr> / <expr>
       -> num

iii) Erwarten Sie (unter den gleichen Bedinungen wie zuvor) hier Probleme? Falls ja, welche?
<expr> -> <expr> + <expr>
       -> <expr> - <expr>
<term> -> <term> * <num>
       -> <term> / <num>
       -> <num>

iv) Erwarten Sie (unter den gleichen Bedinungen wie zuvor) hier Probleme? Falls ja, welche?
<expr>  -> <term> <erest>
<erest> -> + <term> <erest>
        -> - <term> <erest>
        -> epsilon
<term>  -> <num> <trest>
<trest> -> * <num> <trest>
        -> / <num> <trest>
        -> epsilon

b) Gegeben sei folgende Grammatik:
(1) S -> xAx
(2) S -> yBx
(3) S -> yAy
(4) S -> xBy
(5) A -> z
(6) B -> z
i) Erstellen Sie den dazugehörigen LR(1)-Zustandsübergangsgraphen.
ii) Erstellen Sie daraus eine LR(1)-Syntaxanalysetabelle.
iii) Analysieren Sie mithilfe der LR(1)-Syntaxanalysetabelle das Wort xzx.
iv) Ist die Grammatik vom Typ LR(1), LALR(1), SLR(1), LR(o)? Geben Sie eine ausreichende Begründung an.
v) Ist die Sprache vom Typ LR(1), LALR(1), SLR(1), LR(o)? Geben Sie eine ausreichende Begründung an.


Aufgabe 5 - Semantische Bearbeitung - 25 Punkte (8+8+4+5)
In der Programmiersprache C kann der Typ float[5][10] als Array von 5 Arrays von 10 Fließkommazahlen verstanden weren. Um während der Übersetzung einen entsprechenden Typausdruck zu konstruieren nehmen Sie an, dass Ihnen eine Funktion array zur Verfügung steht. Diese nimmt zwei Parameter entgegen, eine Zahl (= Dimension des Arrays) und einen Typ (=Basistyp des Arrays). Der zu float[5][10] passende, zusammengesetzte Typausdruck ist also array(5, array(10, float)). Die in der folgenden Tabelle dargestellte Attributgrammatik ist in der Lage, derartige Typausdrücke zu konstrieren.

Produktion         Semantische Regel
T -> BC            T.t=C.t
                   C.b=B.t
B -> int           B.t=integer
B -> float         B.t=float
C -> '['num']'C1   C.t=array(num.val, C1.t)
                   C1.b=C.b
C -> epsilon       C.t=C.b

a) Konstruieren Sie den von der Attributgrammatik generierten Attribut-Parse-Baum (auch als kommentierter oder bewerteter Parse-Baum bzw. Syntaxbaum bezeichnet).

b) Anhand des Typs eines Bezeichners kann der für ihn zur Laufzeit benötigte Speicherplatz festgestellt werden. Wir gehen davon aus, dass der Speicher aus Böcken zusammenhängender Bytes besteht, wobei ein Byte die kleinste adressierbare Speichereinheit darstellt. Die Breite eines Typs hängt von der Anzahl der Speichereinheiten ab, die für "Objekte" des Typs benötigt werden. Die in der foldenden Tabelle dargestellte Attributgrammatik ergänzt die obige Attributgrammatik um weitere semantische Regeln, so dass neben dem eigentlichen Typausdruck auch die Breite des durch Ausdruck konstruierten Typs (in Bytes) berechnet wird.
Ergänzen Sie den in Teilaufgabe a) konstruierten Attribut-Parse-Baum um die neuen Attribute, deren Werte durch die ergänzten semantischen Regeln berechnet werden.

Produktion         Semantische Regel
T -> BC            T.t=C.t
                   C.b=B.t
                   T.width=C.width
                   C.w=B.width
B -> int           B.t=integer
                   B.width=4
B -> float         B.t=float
                   B.width=4
C -> '['num']'C1   C.t=array(num.val, C1.t)
                   C1.b=C.b
                   C.width=num.val x C1.width
                   C1.w=C.w
C -> epsilon       C.t=C.b
                   C.width=C.w

c) Welche Breite haben gemäß der in Teilaufgabe b) eingeführten Attributgrammatik die elementaren Typen integer und float? Welche Breite hat der zu float[5][10] passende, zusammengesetzte Typausdruck?

d) Entwerfen Sie eine zu der in Teilaufgabe b) eingeführten Attributgrammatik semantisch äquivalente Attributgrammatik, welche zur Berechnung der Breites eines konstruierten Typausdrucks mit weniger semantischen Regeln auskommt.



= Note (Optional)
2.0 Nach der Einsicht (vorher schlechter, es wurden beim korrigieren mehrere richtige Antworten als falsch gewertet. Lohnt sich also immer hinzugehen). Die Aufgaben waren was man erwartet. Zeitlich fand ich es ziemlich viel. Mir wurde bei der Einsicht gesagt, dass ich bei Fehlern besser nicht neu begonnen hätte und Folgefehler gekriegt hätte. Dass man es eben besser einfach dazuschreibt, dass es nicht ganz stimmt. So hab ich viel Zeit vertödelt und nicht alle Aufgaben bearbeiten können.

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Sehr fair, keine bösen Überraschungen. Zeitlich etwas stressig, wie viele andere Take Home Klausuren auch. Vermutlich damit man eben doch gelernt haben muss und nicht in der Klausur anfängt alles nachzuschlagen. Prof. Kehrer war auch bei der Einsicht sehr nett und hat noch geholfen mehr Punkte rauszuholen.


Dir hat dieses Protokoll beim lernen geholfen? Super! Dann like und subscribe und schreib doch bitte selbst Protokolle zu deinen Klausuren! :)