Übersetzerbau 1

30.01.2015

• Grundlagen des Übersetzerbaus
• 30 Minuten
• Prüfer: Prof. Dr. Michael Philippsen
• Beisitz: Marius Kamp M. Sc.
• Papier und Stift bereitgestellt
• Ein Blatt mit ausgedrucktem Java Code vorbereitet

Vorgabe Java Code:

interface Filter {
 
	public boolean apply(int i);
 
}
 
public class A {
 
	public boolean fu(int i) {
 
		final int y = i;
 
		/* 1 */
		Filter f = (int i) -> i == y ;
 
		doSomething(f);
 
	}
 
	public fu2(int x, int y) {
		/* 2 */
		int[] a = bar2(x,y);
	}
 
	public boolean bar(Object x, int y) {
		/* 3 */
		return (x != null) && (y < 0)
	}
 
}

(P) Was macht ein Parser allg. mit dem folgendem Code? Sie können beim Interface anfangen.

(S) Erklärt dass Lexer bei lexikalischer Analyse aus Input Token erzeugt.

(P) Welche Tokelfolge würde erzeugt werden?

(S) TK_INTERFACE TK_IDENTIFIER TK_{ etc. TK_PUBLIC TK_BOOLEAN

(P) Was dann?

(S) Parser erzeugt aus Folge von Token mit Hilfe von Grammatik einen AST. (Prüfer hat hier nach Stichwort Grammatik gefragt und wie ein Parser aussieht. → Kurz erklärt dass Parser einen Stack hat und evtl Lookahead um zu entscheiden welche Produktion der Grammatik er anwendet.)

(P) Wie sieht AST bei aus?

(S) Im ersten Moment dachte ich dass es eine Zuweisung ist, dann aber korrigiert dass es eine Arraydeklaration und Initialisierung (mittels Funktion) ist. (Wichtig, auch identifier, typen und dimensionen des arrays. Hier angemerkt dass Spanne der einzigen Dimension die existiert noch nicht bekannt ist.) Ast sieht dann etwa so aus:

                  vardecl 
                 /  |     \
                id type    \
                /   |  \     init
               a   int dims    \
                          \    func_call
                           1     /     \
                               id      args
                                |      /  \
                                bar2  x    y

(P) Erzeuge Zwischencode für

(S) Okay, ich verwende cut Semantik für schnellere Auswertung und invertiere Bedigungen um direkt zu Ergebnis springen zu können:

ifeq x null goto f
ifle y 0 goto false
t: return true
f: return false

(P) Der Code ist Java 8. Java 8 hat jetzt Lambdaausdrücke. Siehe. Wie kann man das in den Compiler einbauen?

(S) Erstmal Tokens erweitern. Annahme dass nur → nicht als Token deklariert, muss also hinzugefügt werden.

  Dann noch in Grammatik einbauen.
  
  

(P) Wie?

(S) Produktionen erweitern, von Expression

    expr :=
         ...
       | ...
       | TK( var_decl_list TK) TK_PFEIL block TK_SEMIKOLON

(P) Wie bilde ich das jetzt in AST ab?

(S) Erste Idee: Verwendung von Funktion. Geht aber nicht da die Funktion keinen Namen hat. Auch nicht weil das ja eine Expression ist und man sie übergeben kann / will. Ausserdem hat Lambda keinen (anfangs bekannten) Rückgabewert. Also nicht einfach abbildbar. Dann (wieder durch Hilfe) drauf gekommen dass man den Rückgabetyp bestimmen kann (weil es ja der Variablen f zugewiesen wird.). Da man jetzt weiss dass es vom Typ Filter is kann man die Signaturen (Rückgabewert + Parameter) mit dem des Interfaces Filter vergleichen und schauen ob man das verwenden kann. Ums besser zu erklären wurde ich darauf hingewiesen doch am besten mal konkret aufzuschreiben wie meine Transformation aussieht:

class Filter$1 implements Filter {
 
	public boolean apply(int i) {
		return i == y;
	}
 
}

(P) Was is jetzt mit y, das gibts da ja gar nicht?

(S) Stimmt. Ist aber final, kann sich also nicht ändern. Wie bei Transformation von inneren Klassen kann man ein neues Attribut in der neuen Klasse anlegen und dann y im Konstruktor übergeben (Auch hier brauchte ich einen kleine Anstoss):

class Filter$1 implements Filter {
 
	private int y;
 
	public Filter$1(int y) {
		this.y = y;
	}
 
	public boolean apply(int i) {
		return i == y;
	}
 
}

Nach der Besprechung wurde ich gefragt wie ich mich einschätze. Ich habe dann gesagt nicht besonders gut weil ich bei einigen Sachen schon Hilfe gebraucht habe. Prüfer merkt dann an dass es sehr gut war, da es ihm darum geht dass Probleme erkannt werden und dann eine Lösung Schritt für Schritt erarbeitet werden kann. V.a. weil die Frage mit dem Lambdaausdruck als sehr schwer eingestuft wurde. Insgesamt geht es also sehr ums Verständnis. Deshalb empfehle ich v.a. die praktischen Beispiele gut durchzumachen und v.a. ein Verständnis für die Probleme zu bekommen, also warum besteht das Problem eigentlich? Dann ist die Lösung meistens auch einfacher zu finden. In der Prüfung selbst sehr nette und angenehme Atmosphäre.