• 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 (12 p)

Fig. 1. Wumpus.

Fig. 2. Wumpusens son.

I spelet Son of Wumpus går man runt mellan olika rum i en grotta och jagar ett litet och ganska ofarligt monster. Eftersom monstret är så litet och ofarligt, behöver man inte se sig för så noga i grottan, utan man anger i förväg vilka rum man ska besöka, och i vilka rum man vill skjuta på monstret. (Man hoppas alltså att monstret råkar vara i något av de rummen.) Det man gör är att man skriver ett litet program, som börjar med begin och slutat med end, och som räknar upp vilka rum man ska besöka och var man vill skjuta. Ett exempel:

• begin 2 3 4 5 skjut 4 3 end

Här är några andra exempel på program som man kan ange:

• begin 2 3 4 end
• begin skjut skjut skjut end
• begin 8 9 10 11 12 skjut 13 skjut 14 skjut end
• begin end

a) (1p) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för kommandosprå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 2: Faser (6 p)

• begin 8 9 12 skjut 13 skjut 14 skjut end
• begin 8 9 10 11 12 skjut 19 skjut 20 skjut end

b) (2p) Man kan dela upp den kodoptimering som kompilatorn gör i två olika faser: maskinoberoende respektive maskinberoende optimering. Ge ett exempel på en optimering som bäst görs i den maskinoberoende optimeringsfasen, och förklara varför den skulle vara svårare att göra i den andra, maskinberoende optimeringsfasen.

c) (2p) Ge ett exempel på en optimering som bäst görs i den maskinberoende optimeringsfasen, och förklara varför den skulle vara svårare att göra i den andra, maskinoberoende optimeringsfasen.

Uppgift 3: Mellankod (5 p)

if (x > y)
    x = y;
else
    y = x;
while (x > y − z − t) {
    x = x * y - z;
    y = x - y - z;
    z = x - y * z;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

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

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.

Uppgift 5: Typkontroll (5 p)

Exempel på ett program i språket:

int i;
float f;

i = 17;
i + i;		// Resultat: heltalet 34
i + 3;		// Resultat: heltalet 20

f = 7.0;
f + f;		// Resultat: flyttalet 14.0
f + 3.0;	// Resultat: flyttalet 10.0

f = 17;		// typfel: f ska innehålla ett flyttal
f = i + 47;	// typfel: f ska innehålla ett flyttal
3.0 + 17;	// typfel: flyttal + heltal ej tillåtet
f + i;		// typfel: flyttal + heltal ej tillåtet
f + 47;		// typfel: flyttal + heltal ej tillåtet

program -> deklarationer satser
deklarationer -> deklarationer deklaration | empty
satser -> satser sats | empty
deklaration -> typ id ";"
typ -> "int" | "float"
sats -> uttryck ";" | id "=" uttryck ";"
uttryck -> id | heltalskonstant | flyttalskonstant | uttryck "+" uttryck

Uppgift 6: Några termer (10 p)

1. call by value
2. DAG
3. heap
4. konservativ skräpsamling
5. parseträd (ibland kallad "konkret syntaxträd")
6. registerallokering
7. reguljärt uttryck
8. syntaxträd (ibland kallad "abstrakt syntaxträd")
9. tvetydig grammatik
10. Yacc