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. |
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:
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.
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.
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.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
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.) |
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.
Exempel på ett program i språket:
Här är en grammatik för 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
Visa hur kompilatorn kan hantera typinformation, i en syntaxstyrd översättning och i symboltabellen, så att den upptäcker typfelen i exemplet ovan.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