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





Tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

tisdag 6 november 2007 kl 08:00 - 12:00

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 40.
För godkänt betyg (3 respektive G) krävs 20 poäng.
Resultat: Meddelas på kursens hemsida eller via e-post senast måndag 19 november 2007.
Visning och frågestund: Måndag 19 november 2007 kl 12:00-12:30 i mitt rum (T2220).
Efter visningen kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-7347013.



LYCKA TILL!

Observera: Det finns sju uppgifter på tentan, men alla ska inte lösas. Svara på uppgift 1 och (högst) fem av de övriga sex uppgifterna. (Skulle du svara på alla sex, räknas den med högst poäng bort.)

Uppgift 1: Språk, grammatiker och parsning (15 p)

En Wumpus
Fig. 1. Wumpus.

I spelet Hunt the Wumpus går man runt mellan olika rum i en grotta och jagar ett farligt monster. I den variant som beskrivs här kan man ge kommandon för att gå mellan olika rum (kommandot ), för att skjuta på wumpusen (kommandot skjut), för att ge upp (kommandot ge upp), och för att börja om (kommandot börja om). Till skjut-kommandot anger man en lista med rum, som man skjuter mot. Man kan ge flera kommandon på en gång genom att skriva semikolon mellan dem.

Här är några exempel på kommandorader som man kan ge:

Några felaktiga kommandorader:

a) (2p) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för kommandospråket.

b) (5p) Skriv grammatiken. Använd terminalerna från a-uppgiften. Startsymbolen ska beskriva en kommandorad, som alltså kan innehålla flera kommandon.

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) (6p) 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.

Observera: Det finns sju uppgifter på tentan, men alla ska inte lösas. Svara på uppgift 1 och (högst) fem av de övriga sex uppgifterna. (Skulle du svara på alla sex, räknas den med högst poäng bort.)

Uppgift 2: Faser (5 p)

En kompilators arbete brukar delas in i sex eller sju faser. Ange vilka det är, och förklara kort vad varje fas gör. Vad är in- och utdata från respektive fas?

Uppgift 3: Scanning och reguljära uttryck (5 p)

a) (3p) Skriv reguljära uttryck för de olika tokentyperna i uppgiften ovan.

b) (2p) Vad är det för skillnad på ett lexem och ett lexikaliskt värde, och vad har dessa med scanning att göra?

Uppgift 4: Run-time-omgivning, aktiveringsposter (5 p)

Betrakta följande C-program:

#include <stdlib.h>
#include <stdio.h>

int x = 1;
int y = 2;

void f(int a) {
    int b;
    b = x;
    a = 3;
    // Här!
}

void g(int a, int b) {
    int c;
    c = a;
    x = 4;
    int* p = malloc(sizeof(int));
    *p = b;
    f(x);
}

int main(void) {
    int x;
    x = 5;
    y = 6;
    g(7, x);
    return 0;
}

Funktionen main anropar funktionen g, som i sin tur anropar funktionen f. När programexekveringen i funktionen f kommer fram till raden med kommentaren "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.

I minnet kommer det då att finnas ett antal lagringsutrymmen för heltal, som innehåller olika heltalsvärden. Rita upp en skiss över dessa variabler, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".

Uppgift 5: Mellankod (5 p)

Det här är ett programavsnitt i C:
x = 1;
y = 2;
while (x > y) {
    if (x < a) {
        x = x − a − 2;
        y = y + a * 3;
    }
    else
        x = x − 1;
    y = y + 1;
}
Översätt ovanstående programavsnitt till två 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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

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

Här är en grammatikregel för if-satsen i ett språk:

sats -> if ( uttryck ) then sats1 else sats2 endif

Skapa en syntaxstyrd definition, med produktioner och semantiska regler, för översättning av for-satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod.

Uppgift 7: Optimering (5 p)

a) Vad är treadresskod? Visa med exempel.

b) Vad är ett basic block? Visa med exempel.

c) Flera olika typer av optimeringar kan göras på koden inuti ett enskilt basic block. Vilka? Beskriv dem, och använd treadresskod för att ge exempel på hur de fungerar.

Observera: Det finns sju uppgifter på tentan, men alla ska inte lösas. Svara på uppgift 1 och (högst) fem av de övriga sex uppgifterna. (Skulle du svara på alla sex, räknas den med högst poäng bort.)