• 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.
• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

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

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 gå), 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:

• gå 2
• skjut 2
• skjut 2,3,4
• gå 2; skjut 3,4; gå 3; skjut 4,5,6
• ge upp
• börja om

Några felaktiga kommandorader:

• gå
• gå 2,3
• gå 2 skjut 3
• gå 2, skjut 3

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.

Uppgift 2: Faser (5 p)

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

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)

#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)

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;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

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

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)

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.