Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » ueb1-2025_03_10

  • Datum: 10.03.2025, 10:40
  • Pruefer: Philippsen und Tobias
  • Ergebnis: 1,7

Die Fragen hat zum grossteil Tobias gestellt, Philippsen hat nur ab und zu eine eingeworfen

F: Welche 3 Schritte macht den so ein Compiler?

Codebeispiel (so aehnlich) 

func foo( i : int ) : int
	...
end

func bar() : int
	...
end

func main() : int

	var k : int;
	
	k := bar().foo().foo();
	
	writeInt(k);

	return 0;
end

F: Was muesste man nun im Compiler anpassen?

A:

  • '.' Token im Lexer
  • Grammatik anpassen

[legt e2 Grammatik hin]

F: Dann machen Sie mal

A:

  • Neue alternative bei factor: call '.' call

F: Sicher?

A: Nein, wir wollen ja mehrere calls hintereinander unterstuezen → call ('.' call)*

F: Warum steht hinten ein call, koennte man das nicht anders machen mit factor?

A: Nein, dann koennte auch foo().ab[0]() valide sein, was nicht gewollt ist

F: So, und was muessen wir sonst noch anpassen?

A:

  • AST Node Klasse erzeugen
  • AbstractVisitor anpassen
  • Namecheck und Typecheck anpassen, ggf. sogar verschrenken
  • Code emitter anpassen, dass dieser das richtig macht

F: Geht das auch anders?

A: Ja, Baumtransformation, Syntax Sugar abbauen → Call mit Parameter

F: Kann es dabei zu Problemen kommen?

A: Ja, wenn das laden des Funktionsnamen Seiteneffekte haben kann [war nicht das, was sie hoehren wollten, stimmte aber]

Codebeispiel (so aehnlich) 

var arr : int[10][20];
var val : int;

func bar() : int
	...
end

func foo( x : int, y : int)
	if arr[x][y] == bar() and bar() == 0 then
		arr[x][y] := 5;
	end
end

[AST zu foo gegeben]

F: Was macht der Compiler nun damit?

A: Zwischencode generieren

F: Dann machen sie mal

A:

  • if … → true-Label und false-Label aufsetzen
  • … and … → neues true label, damit linke Seite auswerten, am true label mit alten labels rechte Seite auswerten
  • Indexberechnung fuer array: x + y * 20
  • … == … → jump if equal mit true label / false label
  • array-Zugriff wieder x + y * 20, dahin einen store

F: Wie kommt der Compiler darauf, an der einen Stelle ein Load und an der anderen ein Store zu machen bei den Arrayzugriffen?

A: Beim Store macht das die StoreNode selbst, also ohne visit [war scheinbar nicht ganz das, was sie hoehren wollten, aber funktioniert]

[gibt ein Blatt mit dem dazugehoerigen Zwischencode]

F: Und was machen wir jetzt damit?

A: Variablenzuweisung & Codegenerierung, ggf. Gemeinsam

Instruktionssatz 

r = mov r
r = mov m
r = r op r
r = *(r)
r = *(r + r)
r = *(r + r * 20)
r = *($e + r + r)

F: Wie koennten wir das damit machen?

A: Hier komplizierte Instruktionen → keine einfachen Verfahren sinnvoll (z.B. getref), sondern z.B. Dynamische Programmierung, Sethi-Ullmann, Graham / Glanville

F: Dann machen Sie das doch mal fuer [Zwischencode von val == arr[x][y]] mit Dynamischer Programmierung

… [Habe mich relativ schlecht angestellt und einiges an Hilfe gebraucht, hatte Probleme mit den komplizierteren Befehlen, ACHTUNG: Call hat Seiteneffekte! Auswertungsreihenfolge beachten]

F: Ok, und wie machen wir daraus jetzt Code?

A: Von oben nach unten in der gewaehlten Auswertungsreihenfolge durchlaufen, und von den Blaettern aus dann die Instruktionen erzeugen

F: Dann machen sie mal

…

[Zeit fast um, nur noch eine kurze Frage]

F: Wenn unser Instruktionssatz bestimmte Instruktionen hat, die nur mit bestimmten Registern arbeiten, welche Verfahren gibt es dann, die damit umgehen koennen?

A: z.B. Graphenfaerben, „kann fast alles“

F: Und wie genau?

A:

  • Interferenzgraphen ueber Lebensspannen bilden
  • Vollvermaschtes Netz aller Register daneben
  • Nun Variablen, die in bestimmten Registern stehen muessen, mit allen anderen Registern verbinden, sodass nur noch diese Farbe(n) uebrig bleiben

F: Ok, [Irgendwie Ueberleitung zu den mov-Kanten] Wie machen wir das?

A:

  • Wir koennen zwei Knoten u.u. verschmelzen, wenn die urspruengliche Instruktion a = mov b ist, dann sparen wir uns das mov, und a und b landen im gleichen Register
  • Koennen wir machen, wenn der Grad des neuen Knotens < R ist, oder weniger als R Nachbarn einen Grad von groesser R haben, oder [dritte Option ist mir nicht eingefallen]

F: Ja, aber was muessen wir vorher noch beachten?

A: Keine normale Kanten zwischen den Knoten

Ergebnis: Trotz groesserer Schwierigkeiten bei der dynamischen Programmierung (war aber auch ein schweres Beispiel) eine sehr gute Note