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





Tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

lördag 8 december 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 43.
För godkänt betyg (3 respektive G) krävs 21 poäng.
Resultat: Meddelas på kursens hemsida eller via e-post senast lördag 29 december 2007.
Visning och frågestund: Tisdag 8 januari 2008 kl 15:00-15: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!

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

En Wumpus
Fig. 1. Wumpus.
                  
En liten 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:

Programmet innebär att man i tur och ordning går till rum nummer 2, 3, 4 och 5, sen stannar man i rum nummer 5 och skjuter, och sen går man tillbaka till först rum nummer 4 och sen nummer 3.

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

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)

a) (2p) I uppgiften ovan kan man bara gå mellan rum som ligger intill varandra, så följande program är felaktiga: Bör den kontrollen ligga i kompilatorn? I så fall, i vilken fas? Motivera svaret!

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)

Det här är ett programavsnitt i C:
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;
}
Ö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 4: Syntaxstyrd översättning (5 p)

a) Skriv en grammatikregel för while-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.

Uppgift 5: Typkontroll (5 p)

Ett enkelt programmeringsspråk innehåller två datatyper: heltal och flyttal. Man kan deklarera variabler, och man kan addera två värden av samma typ, men man får inte blanda tal av olika typ.

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
Här är en grammatik för språket:
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
Visa hur kompilatorn kan hantera typinformation, i en syntaxstyrd översättning och i symboltabellen, så att den upptäcker typfelen i exemplet ovan.

Uppgift 6: Några termer (10 p)

Förklara kort vad följande begrepp från kompilatortekniken innebär. Ge gärna exempel.
  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