Kompilatorer och interpretatorer
för Dataingenjörsprogrammet m fl
lördag 7 november 2009
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 lördag 28 november 2009. |
Återlämning av tentor: | Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-73 47 013. |
Här är ett exempel på hur en fil med en sådan träningsdagbok ska kunna se ut:
typ löpning; typ motionscykling; 2009-10-19 löpning; typ styrketräning ; 2009-10-19 styrketräning; 2009-10-20 löpning 43:12.2; 2009-10-21 löpning 1:44:00.62 ; 2009-10-21 styrketräning 1:00:00 ; 2009-10-22 motionscykling 1:09:22.1; slut;
Som synes ska filen kunna skrivas på fritt format, vilket betyder att blanktecken och radslut inte spelar någon roll, annat än för att skilja orden från varandra.
Man kan skriva in vilka sporter man ägnar sig åt med "satser" som börjar med nyckelordet typ. Man kan skriva in träningspass med "satser" som börjar med ett datum, följt av namnet på en sport (som tidigare måste ha deklarerats med en typ-sats), eventuellt följt av en tid. Dessutom finns en slut-sats som markerar slutet på träningsdagboken. Alla satser avslutas med semikolon.
Det finns alltså ett "träningsdagboks-språk" som beskriver hur träningsdagboken ser ut, och ett program som ska kunna läsa och förstå träningsdagboken måste kunna läsa och förstå det språket.
a) (2p) Vilka övriga tokentyper ingår i träningsdagboks-språket?
b) (1p) Ett exempel på hur ett datum kan se ut är 2009-10-19. Datum ska bestå av årtal med fyra siffror, ett bindestreck, månad med två siffror, ännu ett bindestreck, och till sist datum med två siffror. Skriv ett reguljärt uttryck som beskriver tokentypen datum.
c) (2p) Den träningstid som man kan ange för en träning kan bestå av timmar, minuter, sekunder och decimaldelar av en sekund, som till exempel 1:09:22.1 och 117:00:09.6293845. Minuterna och sekunderna måste vara med, men timmarna och sekunddecimalerna kan uteslutas, som till exempel 09:22.17, 1:09:22 och 0:09. Skriv ett reguljärt uttryck som beskriver tokentypen tid.
b) (2p) Om grammatiken från a-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.)
Här är en kort träningsdagbok:
typ vila; 2009-10-19 vila 24:00:00; 2009-10-20 fika 1:00:00; slut;
Rita upp ett parse-träd för denna träningsdagbok, med din grammatik från (b-)uppgiften ovan.
Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.
Ett programs adressrymd kan delas upp i fyra delar: programkod och konstanter, statiska data, heap och stack. Rita upp hur stacken, heapen och statiska data ser ut när programkörningen kommer till kommentaren "Här!".#include <stdlib.h> #include <stdio.h> int x = 1; int apa(int a, int b) { int* p = malloc(sizeof(int)); *p = a; x = a; if (a <= 2) { /* Här! */ return 3; } else { return apa(a - 4, b); } } void svamp(int a, int y) { int z; z = 5; z = apa(6, x); } int main(void) { int a; int y; a = 7; y = 8; svamp(a, y); a = 9; return 0; }
Översätt ovanstående programavsnitt till var och en av följande tre typer av mellankod.i = 0; j = 10; n = 0; while (i < j) { if (i % 2 == 0) i = i + 2; else j = j - 1; n = (j - i - 1) / 2; }
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
a) Skriv en grammatikregel för while-satsen i C.
b) Välj en form av mellankod (bland dem från uppgift 6 ovan), och tala om vilken du valde. Skriv sedan en syntax-styrd definition eller ett syntaxstyrt översättningsschema (och tala om vilken du valde) för översättning av while-satsen till mellankod.
a) Kompilatorn har ju faser som "scanning", "parsning" och så vidare. Varför finns det ingen fas i kompilatorn som heter "skräpsamling"? Skräpsamling är ju ett ändå ganska viktigt begrepp i modern programmering, och man vill slippa krångla med manuella free och delete.
b) Jag tycker att man borde sluta med kompilatorer och bara använda interpretatorer, för interpretatorer måste ju vara mycket snabbare. En kompilator översätter ju först källkoden, innan den kan köras, medan en interpretator börjar köra programmet direkt!
c) Bison säger att jag har en massa "shift/reduce-konflikter" här i min grammatik. Vad är det för nåt? Vad beror det på? Är det farligt?