Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Allgemeines (Übersicht)
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
— | pruefungen:hauptstudium:ls2:ueb1-2017-02-20 [21.02.2017 16:23] (aktuell) – angelegt volschaf | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== Allgemeines ====== | ||
+ | B: Beisitzer (Kamp) | ||
+ | P: Prüfer (Philippsen) | ||
+ | |||
+ | S: Student | ||
+ | |||
+ | Zeit: 30min (Voll ausgenutzt) | ||
+ | |||
+ | ====== Analyse ====== | ||
+ | int foo(int a, int b) | ||
+ | { | ||
+ | int d;//[2] | ||
+ | int c; | ||
+ | // ... | ||
+ | c := 2 - a * b /*...*/; //[1] | ||
+ | if(a > b > c) //[3] | ||
+ | { | ||
+ | int d; //[2] | ||
+ | d := bar(); | ||
+ | | ||
+ | } | ||
+ | // | ||
+ | } | ||
+ | B: Hier ist ein Stueck Code. Was macht der Compiler damit? | ||
+ | |||
+ | S: Lexer liest Zeichen ein, erzeugt Tokenstrom bedeutungstragender Elemente, wirft Whitespace und Kommentare weg. | ||
+ | |||
+ | B: Mal doch mal den Tokenstrom fuer [1] auf. | ||
+ | |||
+ | S: Hatte zuerst "ID TKCOL TKEQ..." | ||
+ | |||
+ | B: Gut, was passiert danach? | ||
+ | |||
+ | S: Parser erstellt aus Tokenstrom Baumstruktur. | ||
+ | |||
+ | B: Und woher weiss der Parser, welche Knoten er einfuegen muss? | ||
+ | |||
+ | S: Durch die Grammatikregeln, | ||
+ | |||
+ | B: Mal doch mal den AST fuer [1]. | ||
+ | |||
+ | S: Gemalt. | ||
+ | |||
+ | B: Gut. Was passiert jetzt noch so mit diesem AST? | ||
+ | |||
+ | S: Deklarationspruefung, | ||
+ | |||
+ | B: Wie ist das denn bei [2]? Wir haben da jetzt ja 2 d. | ||
+ | |||
+ | S: Die liegen in unterschiedlichen Sichtbarkeitsbloecken. Verwendung von Symboltabelle erklaert. Erwaehnt, dass man sie beispielsweise als verkettete Hastabellen implementieren kann oder durch Durchfaedeln des Stacks implementieren kann. | ||
+ | |||
+ | P: Wieso sollte man den Stack per Hand durchfaedeln? | ||
+ | |||
+ | S: Aus Effizienzgruenden. (Bin mir nicht wirklich sicher, ob die Antwort korrekt war.) | ||
+ | |||
+ | B: Gut, was kommt denn dann noch? | ||
+ | |||
+ | S: Typpruefung. Wir versehen alle Knoten mit ihrem Typ. | ||
+ | |||
+ | B: Wo kommen diese Typen denn her? | ||
+ | |||
+ | S: Hier bin ich kurz ins Schleudern gekommen, beim Versuch zu klaeren, woher die Typen an den Blaettern kommen. | ||
+ | |||
+ | P: Wie ist das denn bei Konstanten? Kann die der Lexer schon erkennen? | ||
+ | |||
+ | S : Ja, kennt er beim Erstellen des Namenstabelleneintrags. (Nach einigem Nachdenken) | ||
+ | |||
+ | P: Und jetzt steht hier im Blatt ja ein a. Kann das auch schon der Lexer? | ||
+ | |||
+ | S: Nein. Nach laengerem Rumlavieren sind wir dann da angekommen, dass bei der Deklariertheitspruefung der Typ annotiert wird. Lag glaub ich hauptsaechlich daran, dass ich mich nicht wirklich gut ausgedrueckt hab. | ||
+ | |||
+ | B: Okay, du hast vorhin schonmal Prototypen erwaehnt. Was ist das denn? | ||
+ | |||
+ | S: Kurz erklaert: Erwarteten Typ durchreichen, | ||
+ | |||
+ | B: Wieso macht man das? | ||
+ | |||
+ | S: Man bekommt dadurch bessere Fehlermeldungen. Funktionsaufrufbeispiel gebracht. | ||
+ | |||
+ | ====== Spracherweiterung ====== | ||
+ | B: Wir wollen nun die Sprache erweitern? Und zwar um einen Intervallvergleich wie bei [3]. Was muessen wir denn dafuer tun? | ||
+ | |||
+ | S: Also im Lexer nichts, alle Token sind ja bereits bekannt. | ||
+ | Im Parser muessen wir die Expressionregel anpassen. Dann muessen wir noch neue Klassen fuer die Knoten erzeugen. | ||
+ | |||
+ | P :Wie koennte man das noch machen? | ||
+ | |||
+ | S: Abbilden auf a > b && b > c. | ||
+ | |||
+ | P: Was ist der Vorteil davon? | ||
+ | |||
+ | S: Abbilden auf bekannte Sprachefeatures, | ||
+ | |||
+ | P: Will man das hier also machen? | ||
+ | |||
+ | S: Ja! (Falsche Antwort. Durch Hilfe komme ich drauf, dass das kaputt geht, wenn b Seiteneffekte hat.) | ||
+ | |||
+ | |||
+ | P: Also doch neue Klassen. Was passiert da noch? | ||
+ | |||
+ | S: Schnittstellen von Besucher anpassen. | ||
+ | P fragt fuer die einzelnen Phasen genauer nach: | ||
+ | Deklariertheitspruefung? | ||
+ | Typueberpruefung? | ||
+ | |||
+ | ====== Codegenerierung ====== | ||
+ | B: Gut. Was kommt danach? | ||
+ | |||
+ | S: Transformationen. | ||
+ | |||
+ | B: Lassen wir weg. | ||
+ | |||
+ | S: Codegenerierung. | ||
+ | |||
+ | B: Wie sieht das dann aus fuer [3]? | ||
+ | |||
+ | S: b einmal berechnen, dann die beiden Vergleiche. Kurz den Zwischencode mit entsprechenden | ||
+ | Labels hingemalt. Okay, wenn ich mich jetzt nicht in den Labels vertan hab, sollte das so passen. | ||
+ | |||
+ | B: Jo, das sieht nach Code fuer ein && aus. | ||
+ | |||
+ | S: Fuer || dann entsprechend dual. | ||
+ | |||
+ | B: Jetzt haben wir da ja schon Zwischencode? | ||
+ | |||
+ | S: Uebersetzungsschritte AST - > IR und IR -> ASM sollte leicht sein. | ||
+ | |||
+ | B: Reicht es dann, wenn wir eine leichte Uebersetzung AST -> ASM haben? | ||
+ | |||
+ | S: Nein, Informationen gehen verloren. Wollen wir aber behalten bspw. fuer Optimierungen. | ||
+ | |||
+ | B: Wir haben da ja bestimmte Verfahren zur Zwischencodegenerierung kennengelernt? | ||
+ | |||
+ | S: Graham & Glanville. Erkennbar an der Prefixnotation. | ||
+ | |||
+ | B: Wie funktioniert das? | ||
+ | |||
+ | S: Baum in preorder durchlaufen, | ||
+ | Shift-Reduce, | ||
+ | Reduzierungsanwendung erzeugt. | ||
+ | |||
+ | B: Ist so eine Grammatik immer eindeutig? | ||
+ | |||
+ | S: Nein, hochgradig mehrdeutig. Deswegen versucht man nach dem Prinzip des maximalen | ||
+ | |||
+ | B schaut erwartend. | ||
+ | |||
+ | S: Also bei reduce-reduce die groessere Reduktion waehlen, bei shift-reduce shiften, wenn dadurch groessere Reduktion moeglich. | ||
+ | |||
+ | B: Okay, wie sieht das denn mit Registern aus? | ||
+ | |||
+ | S: Wir nehmen einfach unendlich viele an und machen eine extra Registerzuteilung danach. | ||
+ | |||
+ | P: Muss man bei den Regeln keine Annahmen ueber die Register treffen? Bspw bei float-Befehlen. | ||
+ | |||
+ | S: Ich hatte keine Ahnung und hab vermutet, dass nicht, weil man alles spaeter bei der Registerzuteilung machen kann. Ich vermute mittlerweile, | ||
+ | |||
+ | ====== Registerzuteilung ====== | ||
+ | |||
+ | B: Danach kommt also noch eine Registerzuteilung. Wie macht man das denn? | ||
+ | |||
+ | S: Wir haben in der Vorlesung das Verfahren mittels Graphfaerben kennengelernt. Kurz den Aufbau des Interferenzgraphen erklaert und am Ende gemeint, dass man dann versucht. mit der Anzahl der Register zu faerben Register. | ||
+ | |||
+ | P: Macht man das wirlich immer? Es gibt Uebersetzer, | ||
+ | weniger zu faerben. Wieso? | ||
+ | |||
+ | S: Wenn die Register aufgeteilt sind in caller saved und callee saved, koennte man versuchen, nur caller saved Register zu verwenden, um so Sicherungs- und Wiederherstellungscode in der aufgerufenen Funktion zu vermeiden. | ||
+ | |||
+ | P akzeptiert das, will aber noch auf einen anderen Grund hinaus. Ich komme nicht drauf, die Pruefung ist vorbei. (Der Grund ist weniger Stackverbrauch, |