TU Wien:Übersetzerbau VU (Ertl, Krall)

Aus VoWi
Zur Navigation springen Zur Suche springen
Ähnlich benannte LVAs (Materialien):

Daten[Bearbeiten | Quelltext bearbeiten]

Vortragende M. Anton Ertl (Übungsteil), Andreas Krall (Vorlesungsteil)
ECTS 6
Alias Compilers (en)
Letzte Abhaltung 2024S
Mattermost uebersetzerbau • Register • Mattermost-Infos
Links tiss:185A48 , Homepage
Zuordnungen
Bachelorstudium Informatik Modul Übersetzerbau (Breite Wahl)
Bachelorstudium Wirtschaftsinformatik Modul SPF/INT - Schwerpunkt Informationstechnologie (Gebundenes Wahlfach)
Bachelorstudium Software & Information Engineering Modul Übersetzerbau (Gebundenes Wahlfach)
Bachelorstudium Technische Informatik Modul Übersetzerbau (Gebundenes Wahlfach)


Inhalt[Bearbeiten | Quelltext bearbeiten]

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

Benötigte Vorkenntnisse[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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.

Insgesamt gibt es 120 Punkte auf die Übung und man muss min. 60 Punkte haben um positiv zu sein. Die Punkte sind so auf die Beispiele eingeteilt:

  1. asma (10 Punkte)
  2. asmb (10 Punkte)
  3. scanner (10 Punkte)
  4. parser (10 Punkte)
  5. ag (20 Punkte)
  6. codea (20 Punkte)
  7. codeb (20 Punkte)
  8. gesamt (20 Punkte)

UNBEDINGT die ersten 5 Bsps (asma, asmb, scanner, parser und ag) so bald und gut wie möglich machen! Ab dem 3. Beispiel (scanner) bauen die Beipiele aufeinander auf und man braucht immer einen funktionierenden Code des vorhergehenden Bsps um das nächste Beipiel zu implementieren. Ab dem 5. Bsp (ag) steigt der zeitliche Aufwand (vor allem wenn wenig C, Assembler und Compiler Erfahrung da ist) auf wesentlich mehr als das doppelte an und mit jedem verpassten Beispiel muss bei verpasster Deadline sowieso erstmal das zuvor verpasste Beispiel implementiert werden, was ultra frustrierend ist, weil man es trotzdem machen muss um durchzukommen, aber dann viel weniger oder gar keine Punkte mehr dafür bekommt. Wenn man also alles bis zum ag-Bsp gut macht und dann seine 60 Punkte zusammen hat, braucht man bei den restlichen Beipielen (codea, codeb und gesamt) nicht verzweifeln wenn man dann compilierbaren AMD64 Assembler Code auf stdout schreiben muss, während man versucht die bfe syntax und iburg zu dazahn.

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

Abgabegespräch[Bearbeiten | Quelltext 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.

SS24: AG beim Ertl super gechillt. Hab vorher voll Stress gehabt, weil ich nur knapp positiv war auf die Übung und mein codea und vor allem mein codeb Beispiel wegen anderem Unistress nicht so gut geworden sind, wie ich es gerne gehabt hätte. Aber er hat sich einfach meine beste Abgabe rausgesucht (asmb) und hat mir dann nur Fragen zu diesem einen Beispiel gestellt, was ich natürlich problemlos erklären konnte.

Prüfung[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Tipps[Bearbeiten | Quelltext bearbeiten]

Übungsteil[Bearbeiten | Quelltext 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.
    • : Es hat sich 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.
  • 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.
  • Für die Assembler Beispiele hilft es manchmal mit Compiler Explorer rumzuspielen um zu sehen wie GCC compiliert.
  • 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. (Tipp: 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.
  • Alle in der LVA verwendeten Tools können nach der Eingabe der richtigen Flags auch C++ Code generieren. Ich wünsche mir jetzt im Nachhinein, ich hätte die Beispiele mit C++ gemacht, dann müsste ich nicht mühsam selbst mehrere Datenstrukturen schreiben (z. B. Listen), sondern könnte die generischen Implementierungen aus der Standardbibliothek verwenden. Die anderen C++ Features (z. B. Methoden) können bestimmt auch nett sein. Ich würde nur vorher im Tuwel nachfragen, ob C++ in jenem Jahr erlaubt ist. Im 2023S war es möglich.

Vorlesungsteil/Prüfung[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext 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.

Abgerufen von „https://vowi.fsinf.at/index.php?title=TU_Wien:Übersetzerbau_VU_(Ertl,_Krall)&oldid=189030“