TU Wien:Übersetzerbau VU (Ertl, Krall)

Aus VoWi
Wechseln zu: Navigation, Suche

Daten[Bearbeiten]

Inhalt[Bearbeiten]

Ein Compiler für eine (einfache) Programmiersprache wird erstellt – unter Zuhilfenahme diverser Hilfsmittel/Codegeneratoren wie lex, yacc, ox, …

Benötigte Vorkenntnisse[Bearbeiten]

Es ist sehr hilfreich, schon einmal unter *NIX programmiert zu haben (ls, mkdir, … bis gcc, Makefile, …), da die Übung hauptsächlich auf den Servern des Instituts stattfindet. Inhalte der Theoretischen Informatik sind auch nützlich (Grammatiken, Endliche Automaten), da sowohl dein Übersetzer als auch die Übersetzergenerierenden Programme intern solche Mechnismen verwenden. Es hilft auch, schon einmal (IA_32-/AMD64-)Assembler programmiert zu haben. Wenn nicht, deckt aber die von der LVA zur Verfügung gestellte ASM Einführung alles Nötige gut ab.

LVAs:

Ablauf[Bearbeiten]

Programmieraufgaben mit Deadline. Wenn man das Abgabesystem und Testsystem einmal durchschaut hat, ist es ziemlich genial, da vor der Abgabe leicht festgestellt werden kann, wie gut das Programm schon ist. Dazu schreibt man sich entweder selber Testfälle oder besorgt sich Testfälle von andern Leuten (z.B. im Informatik-Forum).

  • Die ersten 4 Abgaben (ASMA, ASMB, Scanner, Parser) sind wöchentlich, danach sind pro Abgabe 2 Wochen Zeit.
  • Es gibt in den beiden Wochen nach der Abgabe jeweils noch "Nachabgaben", wo noch 70% bzw. 30% der Punkte erreicht werden können.

Vom Abgabegespräch (das trivial ist, wenn die Beispiele selbst gemacht wurden) abgesehen, gibt es während der LVA fast keinen direkten Kontakt zum Betreuungsteam. Prof. Ertl liest aber im Informatikforum mit und beantwortet dort alle Fragen sehr schnell.

Die Übungsnote fließt zu 2/3 in die Gesamtnote ein, die Prüfungsnote (Stoff von 3 Vorlesung) zu 1/3.

Vortrag[Bearbeiten]

Der Vortrag wurde (im SS2016) wöchentlich abgehalten. Der Vortragende erklärt die Themenbereiche langsam und ausführlich und hält sich, sofern keine Fragen aus dem Publikum kommen, sehr stark an die Folien. Für die Übung und Prüfung reichen jedoch auch die Folien und das Skriptum aus. Ein Grundverständnis (vor allem für Grammatiken und Automaten) ist jedoch dann trotzdem notwendig.

Einmal gab es einen Gastvortrag zum Thema "Übersetzerbau in der Praxis", wo mehrere Leute erzählten wie sie Übersetzerbau in Projekten einsetzen. War sehr zu empfehlen!

Der Vortrag ist eher kurz gehalten und deckt nicht alles ab, was für die Übungsbeispiele notwendig ist. Ziel ist eher einen groben Überblick bzw. Einstieg in die Thematik zu geben. Die Details muss man sich dann selbst erarbeiten.

Übung[Bearbeiten]

Die Übung besteht aus 8 Beispielen die selbstständig gelöst werden müssen. Nach den ersten beiden Beispiele, welche zum Aufwärmen sind, bauen die restlichen Beispiele aufeinander auf. Am Ende soll so ein kompletter Compiler entstehen.

Als Unterstützung gibt es auf der Lehrveranstaltungshomepage einige wenige Beispiele, welche die Technologien (flex, bison, ox, bfe/iburg) nutzen, die man auch bei der Übung verwenden soll. Man ist jedoch meistens auf viel Selbststudium angewiesen und sollte daher mit den einzelnen Beispielen möglichst früh anfangen. Die verwendeten Tools sind Jahrzehnte alt, manche davon sind auch eher experimentell und nicht verbreitet. Wer es gewohnt ist, mit Hilfe von Google und Stack Overflow zu programmieren, wird sich auf jeden Fall umstellen müssen.

Alle Teilaufgaben sollten zu Beginn der LVA auf der Homepage bereit stehen!

Abgabegespräch[Bearbeiten]

Bevor man die Prüfung macht, sollte man das Abgabegespräch direkt beim Ertl absolvieren (es geht auch nach der Prüfung, es muss aber absolviert werden). Nichts wovor man Angst haben müsste, es geht im Allgemeinen darum herauszufinden ob die Beispiele selbständig gelöst wurden. Punkteabzüge gibt es normal nicht. Der Ablauf ist durchschnittlich: Nach der ausgiebigen Gesichtskontrolle holt sich Ertl die Abgaben, schaut sich das letzte brauchbare Bsp an (gesamt > codeb > codea > ag - Assembler und Parser/Scanner Bsp werden eigentlich nicht speziell besprochen). Danach wird eine spezielle Codestelle herausgesucht die man Zeile für Zeile erklären soll (Allgemeine Erklärungen ala wie funktioniert der Compiler im Ganzen gibt es anscheinend kaum). Vielleicht gibt es dann noch Fragen über den Grund einer möglichen Mangelhaften Abgabe (wenn man zB nicht alle Punkte hat) und das war's. Gesamtdauer ca. 5-15 min.

Prüfung[Bearbeiten]

Es gibt eine mündliche Prüfung. Kralls Prüfungsstil in Übersetzerbau ähnelt dem in OOP, siehe auch TU_Wien:Objektorientierte_Programmierung_VL_(Puntigam)#Abgabegespräch & Prüfung.

Bei der Prüfung sind üblicherweise drei Prüflinge anwesend, die in drei Fragerunden jeweils ein Themengebiet ausführlich erläutern müssen. Die Fragen sind im Prinzip Überschriften aus dem Skriptum, etwa "Registerbelegung", "LR-Analyse", "LL-Analyse" (typische Prüfungsfragen) etc. und großteils die, die auch auf der LVA-Website stehen. Man kann dann alles dazu erzählen, was einem einfällt. Dabei sollte man durchaus auch detaillierte Antworten geben, also nicht nur das WAS, sondern auch das WIE erklären. Pseudocode auswendig lernen ist nicht notwendig, aber verbal sollte man den Ablauf der Algorithmen schon erklären können (z.B. "Wie werden die Action- und Goto-Tabellen aufgebaut? Wozu benötigt man diese? Wie ist der Ablauf des Algorithmus?"). Wer das Skriptum aber verstanden hat, muss sich nicht vor der Prüfung fürchten. In jeder der drei Fragerunden kann man ein Plus, Ringerl oder Minus bekommen. Aus diesen drei Bewertungen setzt sich dann die Note auf den mündlichen Teil zusammen. Üblicherweise fragt Krall nach, wenn man etwas nicht erwähnt hat, bewertet aber human und man muss nicht jedes Detail aufzählen können. Krall ist bei der Prüfung sehr freundlich und auch bemüht, nicht so gut vorbereiteten Studenten zu helfen, die Prüfung trotzdem zu schaffen.

Das Skriptum bzw. an sich die Prüfung hat ein paar Kapitel mehr als das, was in der Übung behandelt wird, z.B. ein Kapitel über objektorientierte Sprachen. Man sollte nicht glauben, dass nur das gefragt werden würde, was mit der Übersetzerbauübung zu tun hatte - sondern (meiner Erfahrung nach) eher umgekehrt. Also am Besten das ganze Skriptum lernen.

Die Zeugnisse werden nach der Prüfung sofort ausgestellt.

Literatur[Bearbeiten]

  • Skriptum
  • lex & yacc, 2nd Edition (O'Reilly Media): Gutes Buch um lex & yacc zu verstehen.

Tipps[Bearbeiten]

Übungsteil[Bearbeiten]

  • Das Testskript zu benutzen.
    • Unter Umständen kann es auch sehr praktisch sein, wenn man das Testskript kopiert und modifiziert (es ist ein bash-Script... einfach mit einem Editor öffnen!). So kannst du etwa erreichen, dass dein modifiziertes Skript nur noch deine Testfälle überprüft, was die Übersichtlichkeit erhöht.
    • testub10: Es hat sich im SS10 als äußerst praktisch erwiesen ein gemeinsames Repository für Testfälle anzulegen. Die Sammlung enthält neben Testfälle noch zusätzlich Skripte zum Entwickeln der einzelnen Beispiele. (hat auch im SS16 sehr gut funktioniert)
  • Es empfiehlt sich, trotz Zeitdruck, den Code möglichst überschaubar zu halten, da die Teilaufgaben (ab Aufgabe scanner) aufeinander basieren. Man kann z.B. in Ox die @autosyn und @autoinh Methoden nutzen um den Code möglichst übersichtlich zu halten.
  • Die ersten Beispiele sind zwar einfach, bringen aber auch Punkte, allerdings noch nicht genug für eine positive Note.
  • Es hilft bei den späteren Beispielen sehr, sich zuerst genau zu überlegen wie sich die Aufgaben mit den verwendeten Tools gut lösen lassen, anstatt gleich loszucoden. Oft gibt es eine sehr einfache und elegante Lösung.
  • Es lohnt sich wirklich, die ersten vier Beispiele so früh wie möglich in Angriff zu nehmen. Damit bleibt für die schwierigen Beispiele (attributierte Grammatik, Codeerzeugung und Gesamtbeispiel) mehr Zeit, und die kann man wirklich brauchen.
  • Sich nicht von der Kürze der ersten Beispiele täuschen lassen, ab der attributierten Grammatik steigt der Aufwand extrem.
  • Torero ist "leichter" Overkill für das AG-Beispiel und bringt nur eine unnötig komplexe/komplizierte attributierte Grammatik.
  • Austausch mit Kollegen hilft gerade hier oft enorm viel (Informatikforum!).
  • Falls man zu den Minimalisten gehört und nach erreichen der Minimalpunktezahl aufgehört hat sich weiter mit dem Code zu beschäftigen, sollte man sich vor dem Abgabegespräch sehr gut seinen Code nochmals ansehen und komplett durchdenken. Sonst kann es schonmal vorkommen, dass behauptet wird, jemand anderes habe das Beispiel gemacht. (Tip: Scope, Datenstrukturen, globale Variablen)
  • Hat man noch keine Erfahrung mit C Programmierung unter *NIX Systemen sollte man dies zu Beginn des Semesters nachzuholen versuchen. Für die ersten 4 Beispiele benötigt man kaum C Kenntnisse, aber ab dem Attributierter Grammatik dafür um so mehr. Die LVA ist durchaus schaffbar ohne C Vorkenntnisse (Habe ein Gut ohne jemals zuvor C programmiert zu haben), aber man sollte dann die ersten Beispiele so schnell wie möglich fertig bekommen um dann genug Zeit für die restlichen zu haben. Die Zeit wird man als C Neuling brauchen.
  • Um Zeit zu sparen empfiehlt es sich, sich Lösungen der Vorjahre zu besorgen/anzusehen. Zwar ist die Sprache jedes mal anders, aber es hat mir trotzdem sehr geholfen, das Zusammenspiel der Komponenten bzw. den grundsätzlichen Aufbau zu sehen.
  • Die Bonuspunkte sind nicht wirklich notwendig, hier wirklich kein Risiko eingehen.
  • Wenn man die Bonuspunkte trotzdem will: es reicht hier das Augenmerk auf die Befehlsauswahl zu legen (z.B. Summe mit lea,...) und die Anleitung von Ertl zu befolgen. Irgendwelche fortgeschrittenen Sachen (Registerbelegung, Manipulation an der Zwischendarstellung,...) bringt gar nichts.
  • Beim Gesamtbeispiel nicht davor zurückschrecken BFE anzupassen, um für Funktionsaufrufe Code auch Preorder generieren zu können. BFE ist nur ein (kurzes) AWK Skript, das ist echt kein Problem.

Vorlesungsteil/Prüfung[Bearbeiten]

  • Bei Unklarheiten bzw. Interesse in der VO: Fragen stellen. Krall beantwortet diese sehr ausführlich.
  • Oft ist es nicht so einfach ein Verfahren verbal verständlich zu erläutern. Es ist daher hilfreich wenn man sich beim Lernen gleich überlegt wie man die einzelnen Kapitel erklären würde.
  • Man sollte zu jedem Thema (= Überschrift im Skriptum) zirka 2-3 Minuten reden können. Wenn das halbwegs flüssig hinüberkommt sind nachträgliche Fragen des Prüfers eher selten.
  • Datei:TU Wien-Übersetzerbau VU (Ertl, Krall) - Erklärung LR(k) Analyse.pdf hilft ungemein für das Verständnis der Bottom-Up Analyse
  • Kommentierte Musterlösungen aus Übersetzerbau (alt) sind ebenfalls hilfreich

Zeitaufwand[Bearbeiten]

Die ersten vier Aufgaben sind relativ kurz und lassen sich binnen weniger Stunden lösen wenn die entsprechenden Vorkenntnisse vorhanden sind. Ohne Vorkenntnisse in der Programmierung einer Übersetzungsmaschine ist ein beträchtlicher Zeitaufwand einzuplanen.

Ab der 5. Aufgabe (-->AG) macht der Aufwand allerdings einen großen Sprung und man sollte für jede der folgenden Aufgaben mehrere Tage Zeit einplanen.

Die Prüfungsvorbereitung sollte nicht allzu viel Zeit verschlucken, nachdem das Skriptum wenig Stoff enthält. Die Bedienung der in der Übung verwendeten Tools wird nicht abgefragt. Pseudocode muss nicht auswendig gelernt werden, aber man sollte verstehen wie die Algorithmen (z.B. die LR-Analyse) arbeiten. Die Fragen sind meist die Überschriften aus dem Skriptum, daher sollte man sich überlegen was man zu den Thematiken erzählen würde. Sind Vorkenntnisse und Interesse einigermaßen vorhanden, dann reichen (für die mündliche Prüfung) etwa 2 Tage um das Skriptum 1-2 Mal zu lesen.

Ähnliche und verwandte LVAs[Bearbeiten]

Verbesserungsvorschläge / Kritik[Bearbeiten]

Die LVA ist zwar gut gealtert aber schon ein wenig in die Jahre gekommen. Die Tools sind ein wenig seltsam zu bedienen und man merkt ihnen ihren Jahrzehnte alten Ursprung an. Die gelehrten Inhalte sind aber sicher immer noch brauchbar, insofern ist die LVA definitiv empfehlenswert, für alle, die sich für das Thema interessieren. Eine Überarbeitung und Umstellung auf modernere Tools wäre aber trotzdem wünschenswert.