• 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.

Scenario till (en del av) uppgifterna

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.

Uppgift 1 (5 p)

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.

Uppgift 2 (5 p)

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.)

Uppgift 3 (3 p)

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.

Uppgift 4 (5 p)

Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 5 (4 p)

#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;
}

Uppgift 6 (7 p)

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

c) treadresskod

Uppgift 7 (5 p)

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.

Uppgift 8 (6 p)

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?