|
|
Fragen Und Antworten
|
Auf dieser Seite werden für alle Fragen im Bezug zur Prüfung beantwortet. Auch Fragen die per E-Mail bei den Dozenten eintreffen werden hier für alle beantwortet.
A: Da ist in der Tat ein kleiner Fehler vorhanden. Die Indizes der Regeln bei den Reduces sind alle eins zu hoch. (Korrigiertes PDF liegt auf dem Skripteserver). Wenn du die Regeln der Grammatik aus Tabelle 3.10 von 0 statt 1 an nummerierst, stimmt die Lösung.
Func → '+' Num [ pstack.push(Num.value) ] Func Func → '-' Num Func [ mstack.push(Num.value) ] //Func steht einmal vor und einmal nach der semantischen Aktion.Zusätzlich: Kann es sein, dass die angegebene Grammatik endlos-rekursiv ist?
A: Die Semantische Aktion wird im ersten Fall, nach dem Erkennen des NT Num ausgeführt und bevor das NT Func erkannt wird. Im zweiten Falle wird die Aktion erst nach dem Erkennen von beiden Symbolen Num und Func ausgeführt. Dies resultiert bei der Ausgabe darin, dass die Zahlen, die Addiert werden in verkehrter Reihenfolge ausgegeben werden und die Zahlen der Subtraktionen in der Reihenfolge ausgegeben werden in der sie auftreten.
Ja diese Grammatik ist endlos Rekursiv, hier ist ein Fehler in der Aufgabenstellung, es fehlt die Regel die Func in Epsilon überführt.
Hier zum ausprobieren noch der ANTLR Code für diesen Parser.
grammar sdg;
@members {
Stack<Integer> pstack = new Stack<Integer>();
Stack<Integer> mstack = new Stack<Integer>();
public void print(Object s) {
System.out.print(s.toString());
}
}
s : e { while(!mstack.isEmpty()) { print(mstack.pop()); }
print("|");
while(!pstack.isEmpty()) { print(pstack.pop()); }
}
;
e : num { pstack.push(new Integer($num.text)); } func
;
func : '+' num {pstack.push(new Integer($num.text));} func
| '-' num func {mstack.push(new Integer($num.text));}
|
;
num : INT;
INT : '0'..'9'+;
A: Dies ist abhängig davon wie das Array im Speicher abgelegt wird. Zeilen-orientiert oder Spalten-orientiert. Im letzten Jahr wurden die Übungen, als auch die Prüfungsfragen für Spalten-orientierte Arrays gestellt (leider nicht explizit angegeben).
In diesem Semester gehen wir von Zeilen-orientierten Arrays aus. Entsprechend der Erklärung in der Vorlesung und den Übungsaufgaben.
Eine Berechnung Zeilen-orientiert ergibt für diesen Fall 120 + 8 * 8 + 3 * 10 * 8 = 424
A: Ja sie sind nötig für eine korrekte Thompson-Konstruktion. Wenn Sie das Beispiel aus Abbildung 2.7 betrachten, sehen Sie, dass vor jedem Terminal ebenfalls ein Epsilon-Übergang steht. In Abbildung 2.6 war dies leider nicht korrekt und ist bereits korrigiert.
A: Die Aussage isoliert betrachtet wäre richtig, falls man die dortige Definition von T nicht für die folgenden Teile weiterziehen würde. Dies wäre jedoch sehr verwirrend. Wir werden diesen Teil überarbeiten, um Klarheit zu schaffen. Bis dahin: Ja, es sollte nicht T sondern N heissen in jener beschreibung. (In aktueller Version korrigiert)
A: Ja, der Unterschied von LR(0) zu SLR(1) besteht lediglich darin, dass die Parse-Tabelle anders aufgebaut wird. Das Parsen wird jedoch gleich abgewickelt.
A: Wir haben die allgemeine Form nicht betrachtet. Dennoch gäbe es diese (Die Zahlen hinter den Nichtterminalen sind Indizes).
Ausgangslage (Grammatik mit Linksrekursion):
A → A1 Y {A.a = g(A1.a, Y.y)}
A → X {A.a = f(X.x)}
Lösung (Linksrekursion entfernt):
A → X {R.i = f(X.x) R {A.a = R.s}}
R → Y {R1.i = g(R.i, Y.y)} R1 {R.s = R1.s}
R → epsilon {R.s = R.i}
A: Die Epsilons haben die übliche Bedeutung: Das leere Wort. Per Konvention müssen diese da stehen (Nicht zu verwechseln mit ANTLR, wo dies nicht der Fall ist). Dies ging im Skript vergessen bei Kapitel 4.6.2. (In aktueller Version korrigiert)
A: Ja, der ANTLR Code wurde ins PDF der Lösung integriert.
A: Ja, dieser ist in Abschnitt 5.2.1 textuell beschrieben. Wenn Sie gerne eine syntaxgerichtete Definition dafür hätten, können Sie die von Tabelle 5.1 betrachten. Dort werden in den semantischen Regeln jeweils neue Knoten erstellt für den Syntaxbaum. Für die Erstellung von DAGs kann dieselbe verwendet werden, jedoch wird dabei nicht immer ein neuer Knoten erstellt. Dies ist nur nötig, falls der Knoten der erstellt würde nicht bereits im Array der existierenden Knoten vorkommt. Bzw. genauer gesagt, falls nicht bereits ein Knoten mit identischer Signatur darin vorkomment. Sollte ein solcher Knoten gefunden werden, wird einfach dieser zurückgegeben.
goto 2; a = b;
a = b; müsste damit ein Anführer sein, richtig? Wie passt das dann mit dem iffalse() im mittleren Block auf Seite 84 zusammen?
A: Richtig. Die korrigierte Version ist auf dem Skripte-Server.
A: Sie müssen ANTLR-Syntax lesen, verstehen und anwenden können. Beispiel: Eine Grammatik ist gegeben. Bestimmen Sie für einen gegebenen Input ob die ANTLR-Grammatik diesen Erkennt und welche Aktionen dafür ausgeführt werden. Sie werden ANTLR-Syntax NICHT selber schreiben müssen.
A: Nein das ist falsch. Der Stoff für die Prüfung ist das Skript CompBSkript.pdf im Ordner HS2010. Dieses basiert zu einem grossen Teil auf den Folien des letzten Jahres, beinhaltet aber auch neue und ergänzende Themen.
A: Ja das wird so sein. Einen guten Überblick über die Themen bieten auch die Übungen. Der Bereich ANTLR wird wie bereits in anderen Fragen erwähnt nur im Bereich Verständnis der Vorgehensweise und Lesen und verstehen von einfachen Beispielen geprüft.
A:
A: Zeile 8 kann man in der Lösung streichen, da sie vermutlich versehentlich reingerutscht ist. Jedenfalls ist sie falsch.
A: Bei der Thompson-Konstruktion sind sich nicht alle Autoren einig, wie viele Epsilon Übergänge wirklich nötig sind. Für die Prüfung gilt folgendes. Folgen mehrere Epsilon Übergänge hintereinander ohne andere Verzweigung, können diese zu einem Einzigen zusammengefasst werden. Aber auch die ausführliche Variante gibt die selben Punkte. Mehrere Übergänge aus dem selben Zustand mit einem Terminal Symbol (Nicht Epsilon) sind nicht korrekt. Hier braucht es zwei aufeinander folgende Epsilon Übergänge.
Beispiel: Im Skript Abbildung 2.9 * operator. Wir werden in der Prüfung auch die vereinfachte Version in der (q0 und q1) zusammengefasst und q4 zum einzigen Endzustand gemacht wird als korrekt bewerten.
|
Fragen Und Antworten |
|