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. |
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.) |
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:
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.) |
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?
#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".
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.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
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.) |
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.
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.) |