Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Lexer   (Übersicht)

Beisitzer (Kamp)

Prüfer (Philippsen)

Prüfungsdauer 30min

Lexer

Stück Code gegeben. Was tut ein Compiler damit?

Lexer geht zeichenweise über Code. Kommentare weg. Vorteil: Ist schnell, weil deterministischer endlicher Automat. Konkret an einem Beispiel durchführen: statt `int a =` `TKINT ID TKASSNG` etc.pp. Namenstablle erwähnen, weil da das `a` reinkommt.

Parser

Parser baut anhand von Grammatik Strukturbaum auf.

Langsamer als Lexer, weil Kellerautomat. Lexer trotzdem sinnvoll, weil Parser dadurch einfacher & schneller.

Grammatik erweitern

Codestück enthielt so was wie

  while(foo() && (r = r+1) > 3) {}

Das Besondere ist `(r = r+1)`. Nach Beschreibung der Prüfer liefert das (wie in C) immer den neuen Wert zurück. Das konnte „unsere“ Übungssprache nicht. Frage → Was muss man ändern, um das in den Compiler einzubauen?

Grammatik erweitern, entsprechend auch AST-Knoten mit Aktionen erweitern. Alternativ auch Umformen in vorhandenen Konstrukte möglich & erneut in den Compiler werfen möglich.

Graham & Glanville

Syntaxbaum für `(r = r+1) > 3`

  • in Präfixform bringen
  • Vorgehen ala LR erklären. Begriffe wie shift-reduce, reduce-reduce nennen & erklären

Nachfrage, ob wirklich Graham & Glanville anwendbar, da Seiteneffekt durch Variablenzuweisung. (wusste ich nicht; wurde im Nachhinein aber auch als schwierige und daher nicht so wichtige Frage deklariert)

Registerzuteilung mit Graph färben

Graph gegeben

mit zugehörigem Code (darf man sich jetzt selber einen ausdenken). 2 reale Register zur Verfügung.

Erstmal Begriffe wissen & erklären wie

  • Konfliktgraph (nur symbolische Register, so wie gegeben)
  • Interferenzgraph → Warum kommen da die realen Register rein? (Wusste ich nicht) Antwort wäre gewesen: x86 hat ja z.B. spezielle Register wie esp, da soll/darf kein arithmetisches Ergebnis rein
  • was ist eine Lebensspanne? → Folien
  • im Graphen ist da so eine gestrichelte Kante. Wofür ist die? Move-Kante, Registerverschmelzung

Verfahren selber durchführen

  • Grad < R-Regel nur bei einem Knoten (v5) anwendbar → v5 auf Stack packen
  • Nachbarregel (max. < R Nachbarn mit Grad >= R) auch nicht anwendbar
  • Lösung → spilling, d.h. einen Wert in RAM verschieben. Erklären, dass man beim Laden neues symbolisches Register verwendet & nochmal neuen Graph färbt.

Fazit

  • nicht stressen lassen. Man muss IMHO nicht so schnell alles rauswerfen, wie teils in alten Protokollen geschrieben. Notfalls lieber ein paar Sekunden überlegen und sagen man weiß es nicht. Nur komplett schweigen ist doof.
  • vor allem Folien, besonders die roten Markierungen & Bespiele zu Verfahren durchgehen. Letztere zum Beispiel einfach mal parallel auf einem Blattpapier machen & nachvollziehen. Schwieriger wird es in der Prüfung nicht (im Idealfall muss man die konkreten Schritte dann nicht mal anwenden) Übungen sind praktisch, wenn man einen Teil der Folien mal nicht nachvollziehen kann.
  • mit jemand anderen einfach mal ähnliche Übungsaufgaben durchgehen → man weiß schon, wie man es erklären soll. Kann einem die ein oder andere Verwirrung ersparen ;)