Örebro universitet
Institutionen för teknik
Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se)




Tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

lördag 20 december 2008

Gäller som tentamen för:
DT3004 Datateknik C, Kompilatorer och interpretatorer, provkod 0100
TDK104 Kompilatorer och interpretatorer, provkod 0100







Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 36.
För godkänt betyg (3 respektive G) krävs 18 poäng.
Resultat: Meddelas på kursens hemsida eller via e-post senast lördag 10 januari 2009.
Återlämning av tentor: Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-73 47 013.



LYCKA TILL!

Uppgift 1 (6 p)

Betrakta nedanstående C-program:
#include <stdlib.h>
#include <stdio.h>

int a = 1;
int b = 2;
int c = 3;

void smurf(int x, int y);
void drutt(int x, int y, int z);

void smurf(int x, int y) {
    int c;
    c = a;
    x = 4;
    // Här!
    drutt(x, y - 5, 6);
}

void drutt(int x, int y, int z) {
    int c;
    int* p = malloc(sizeof(int));
    *p = 7;
    b = 8;
    c = 9;
    x = 10;
    y = 11;
    z = 12;
    smurf(a, x);
}

int main(void) {
    int b;
    a = 13;
    b = 14;
    drutt(a, b, c);
    c = 15;
    return 0;
}
a) Ett programs adressrymd kan delas upp i fyra delar: programkod och konstanter, statiska data, heap och stack. Rita upp hur stacken, heapen och statiska data ser ut första gången programkörningen kommer till kommentaren "Här!".

b) Vad kommer att hända när programmet fortsatt att köra en stund? Varför?

Uppgift 2: Språk, grammatiker och parsning (12 p)

I ett bilspel kan man dels definiera punkter, som punkterna a, d, b och tjohej i exemplet nedan, och dels ge kommandon för att köra bilen till de olika punkterna. Kommandona avslutas med semikolon. En följd av noll, ett eller flera kommandon bildar ett program. Här är ett exempel på hur ett program kan se ut:
punkt a = 6, 7;
punkt d = 6, 9;
punkt b = 8, 14;
kör till a;
kör till b;
punkt tjohej = 3, 3;
kör till d;
kör till tjohej;

a) (1p) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för det här lilla programmeringsspråket.

b) (4p) Skriv grammatiken. Använd terminalerna från a-uppgiften. Ange vad som är startsymbol. Startsymbolen ska beskriva ett program, enligt ovan.

c) (2p) Om grammatiken från b-uppgiften inte lämpar sig för implementation i form av en prediktiv recursive-descent-parser, så transformera den så den passar. (Om den redan är lämplig, behöver du inte göra om den, utan du får 2 poäng på den här deluppgiften i alla fall.)

d) (5p) Skriv den prediktiva recursive-descent-parsern i ett språk som åtminstone liknar C, Java eller Pascal. Du behöver inte skriva exakt korrekt programkod, men det ska framgå vilka procedurer som finns, hur de anropar varandra, och vilka jämförelser med tokentyper som görs. Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 3: Faser (6 p)

Vilka faser innehåller en typisk kompilator? Vad gör de? Visa också hur in- och utdata från varje fas kan se ut!

Uppgift 4: Mellankod (7 p)

Det här är ett programavsnitt i ett C-liknande språk:
while (true) {
    y = y - z - w * 2;
    if (z > w)
        z = y;
    else {
        z = -y;
        a = a * b - c * d;
    }
}
Översätt ovanstående programavsnitt till var och en (inte två av dem!) av följande tre typer av mellankod.

a) ett abstrakt syntaxträd (genom att rita upp trädet!)

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 5: Syntaxstyrd översättning (5 p)

a) Skriv en grammatikregel för for-satsen i C.

b) Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av while-satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod. (Tala också om vilket du valde.)