Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Allgemeines

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();
           return d;
       }
        //...  
   }

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…“. Wurde dann gefragt ob der Lexer denn Vorausschau hat. Nach Nachdenken dann das ganze bejaht und „ID TKASSGN…“ draus gemacht. Dann noch schnell die Namenstabelle erklaert und auf Nachfrage bestaetigt, dass auch Konstantenliterale in der Namenstabelle landen.

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, die man aus der Sprachdefinition erstellen und dem Parser mitgeben muss.

B: Mal doch mal den AST fuer [1].

S: Gemalt.

B: Gut. Was passiert jetzt noch so mit diesem AST?

S: Deklarationspruefung, um festzustellen, welche Symbole zu welchem Bezeichner gehoeren.

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, mit tatsaechlich ermitteltem Typ vergleichen, Fehler bei Missmatch.

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, Arbeit ist dann vorbei.

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? Jeden Bezeichner besuchen. Typueberpruefung? Prototypen durchreichen. (P haette hier gerne explizit erwaehnt gehabt, dass man bei c schon mehr ueber den erwarteten Typ weiss, da man a und b besucht hat.)

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? Was ist denn eine gute Zwischensprache?

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? Was ist das hier denn?

S: Graham & Glanville. Erkennbar an der Prefixnotation.

B: Wie funktioniert das?

S: Baum in preorder durchlaufen, um Prefixdarstellung zu haben. Dann Shift-Reduce, aehnlich wie beim Parsen. Als Seiteneffekt wird der Maschinencode bei Reduzierungsanwendung erzeugt.

B: Ist so eine Grammatik immer eindeutig?

S: Nein, hochgradig mehrdeutig. Deswegen versucht man nach dem Prinzip des maximalen Verschlingens immer so viel wie moeglich zu reduzieren.

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, dass das die falsche Antwort war, hab aber in der Besprechung vergessen, nachzufragen.

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, die versuchen erst mit 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, da immer nur ein Stackplatz pro Register zum Spillen benoetigt wird, man also bei weniger Registern auch weniger Spillplaetze auf dem Stack benoetigt. Nuetzlich bspw. fuer eingebettete Systeme)