Kompilatorer och interpretatorer: Lösningar till tentamen 2018-10-29

Observera att detta är förslag på lösningar. Det kan finnas andra lösningar som också är korrekta. Det kan hända att en del av lösningarna är mer omfattande än vad som krävs för full poäng på uppgiften, eller att de bara hänvisar till var man kan läsa svaren. Dessutom har det inträffat i världshistorien att lärare skrivit fel i lösningsförslagen. Jag har förstås aldrig gjort det, men andra. Är det verkligen någon som läser såna här inledande texter? Jag vet inte. Det kan vara så. Rabarber rabarber rabarber. Det har jag hört att statisterna får säga på filminspelningar när det ska vara bakgrundsorl från en restaurang eller liknande. Här nedan kommer lösningsförslagen till uppgifterna.

Uppgift 1 (10 p)

En kompilators arbete brukar delas in i ett antal faser. Ange vilka det är, och förklara kort vad varje fas gör. Vad är in- och utdata från respektive fas?

Se också boken eller föreläsningsanteckningarna, särskilt den här figuren, med tillägget att den maskinberoende optimeringen ger som utdata målkod i målspråket, men mindre och snabbare jämfört med den kod som är utdata från kodgeneratorn.

Uppgift 2 (8 p)

Det här är ett programavsnitt i ett C-liknande språk:
    if (a < b) {
        while (c > d) {
            b = a + 1;
            a = c * (b + c);
            a = a + 1;
            d = c * (b + c);
        }
        b = a + 1;
    }
    c = a + 1;

a) Översätt ovanstående programavsnitt till antingen ett abstrakt syntaxträd (genom att rita upp trädet) eller postfixkod för en stackmaskin. (Inte båda!)

Abstrakt syntaxträd:

Ett (abstrakt) syntaxträd

En kommentar:

Postfixkod för en stackmaskin:

        rvalue a
        rvalue b
        <
        gofalse AFTER-IF
label WHILE-START:
        rvalue c
        rvalue d
        >
        gofalse AFTER-WHILE
        lvalue b
        rvalue a
        push 1
        +
        =
        lvalue a
        rvalue c
        rvalue b
        rvalue c
        +
        *
        =
        lvalue a
        rvalue a
        push 1
        +
        =
        lvalue d
        rvalue c
        rvalue b
        rvalue c
        +
        *
        =
        jump WHILE-START
label AFTER-WHILE:
        lvalue b
        rvalue a
        push 1
        +
        =
label AFTER-IF:
        lvalue c
        rvalue a
        push 1
        +
        =

En kommentar:

b) Översätt programavsnittet till treadresskod. Identifiera vilka basic blocks som finns, och rita upp flödesgrafen. (Flödesgrafen, med treadresskoden i, räcker som svar.)

Treadresskoden:

        if a >= b goto AFTER-IF
label WHILE-START:
        if c <= d goto AFTER-WHILE
        b = a + 1
        temp1 = b + c
        a = c * temp1
        a = a + 1
        temp2 = b + c
        d = c * temp2
        goto WHILE-START
label AFTER-WHILE:
        b = a + 1
label AFTER-IF:
        c = a + 1

En kommentar:

Vi kan också numrera instruktionerna och översätta programlägesetiketterna, så ser det likadant ut som exemplet från föreläsningarna:

(1)     if a >= b goto 11
(2)     if c <= d goto 10
(3)     b = a + 1
(4)     temp1 = b + c
(5)     a = c * temp1
(6)     a = a + 1
(7)     temp2 = b + c
(8)     d = c * temp2
(9)     goto 2
(10)    b = a + 1
(11)    c = a + 1

Flödesgrafen:

En flödesgraf

c) Visa någon optimering som går att göra inom ett av dessa basic blocks.

Det tredje blocket, (3)-(9):

(3)     b = a + 1
(4)     temp1 = b + c
(5)     a = c * temp1
(6)     a = a + 1
(7)     temp2 = b + c
(8)     d = c * temp2
(9)     goto 2
Här finns ett gemensamt deluttryck b + c (men inte a + 1). Genom copy propagation och eliminering av temp2 fås:

(3)     b = a + 1
(4)     temp1 = b + c
(5)     a = c * temp1
(6)     a = a + 1
(8)     d = c * temp1
(9)     goto 2

Scenario till uppgift 3-6

Pumpa

Snart är det Halloween, och barnen går en "godisrunda", där de går runt till grannarna och frågar "bus eller godis". För att dokumentera sina aktiviteter behöver de ett särskilt Halloween-språk, där en inmatning kan se ut så här:

började godisrundan;
godis: tre karameller;
bus: gjorde ruskiga ljud;
godis: ett kilo choklad;
godis: en morot;
bus: eldade upp grannens bil;
gick hem;

Inmatningen beskriver en godisrunda. Den börjar med började godisrundan; och slutar med gick hem;. Däremellan anger man noll eller flera noteringar om bus eller godis. En sådan notering börjar med antingen bus eller godis, ett kolon (:), ett eller flera ord som anger vad man gjorde, och ett semikolon (;).

Inmatningen ska kunna skrivas på fritt format, som de flesta vanliga programmeringsspråk, till exempel så här:


började godisrundan ; godis : tre karameller ; bus
: gjorde ruskiga
   ljud ; godis : ett kilo choklad
; godis
: en morot ; bus : eldade upp
grannens bil ; gick hem ;

Uppgift 3 (3 p)

a) (1p) En av terminalerna, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för halloween-språket är ord. Det är helt enkelt en eller flera små bokstäver, a till z. (Vi nöjer oss alltså med det engelska alfabetet.) Skriv ett reguljärt uttryck som beskriver hur ett ord får se ut.

Svar: [a-z]+

b) (2p) Vilka andra terminaler, förutom ord, behövs för att man ska kunna skriva en grammatik för språket?

Svar: började, godisrundan, bus, godis, gick, hem, kolon, semikolon

Uppgift 4 (4 p)

Skriv en grammatik för halloween-språket. Startsymbolen ska vara godisrunda, som representerar en inmatning enligt scenariot ovan.

Svar:

godisrunda -> började godisrundan semikolon busellergodislista gick hem semikolon
busellergodislista -> busellergodis busellergodislista | ingenting
busellergodis -> bus kolon ordlista semikolon | godis kolon ordlista semikolon
ordlista -> ord ordlista | ord

ingenting (ε) står för en tom produktion, och brukar oftast skrivas med en liten "e"-symbol, som tyvärr inte verkar fungera överallt i HTML.

Uppgift 5 (3 p)

Ett parse-träd (ibland kallat "konkret syntaxträd") innehåller noder för alla icke-terminaler. Rita upp parse-trädet för den här godisrundan, enligt din grammatik i uppgiften ovan:

började godisrundan;
godis: ett tuggummi;
gick hem;

Svar:

Ett parse-träd (konkret syntaxträd)

Uppgift 6 (8 p)

Skriv en prediktiv recursive-descent-parser för halloween-språket, i ett språk som åtminstone liknar C, C++, C# eller Java. 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 finns en funktion som heter scan, som returnerar typen på nästa token, och en funktion som heter error, som man kan anropa när något gått fel och som skriver ut ett felmeddelande och avslutar programmet.

Svar:

Grammatiken i uppgift 5 har en FIRST-konflikt, så först måste vi vänsterfaktorisera:

godisrunda -> började godisrundan semikolon busellergodislista gick hem semikolon
busellergodislista -> busellergodis busellergodislista | ingenting
busellergodis -> bus kolon ordlista semikolon | godis kolon ordlista semikolon
ordlista -> ord flerord
flerord -> ordlista | ingenting

Eller så här:

godisrunda -> började godisrundan semikolon busellergodislista gick hem semikolon
busellergodislista -> busellergodis busellergodislista | ingenting
busellergodis -> bus kolon ordlista semikolon | godis kolon ordlista semikolon
ordlista -> ord flerord
flerord -> ord flerord | ingenting

Ladda ner: halloweenparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation halloween.l, och en Bison-version av grammatiken halloween.y

void match(int expected) {
    if (lookahead != expected)
        error();
    else
        lookahead = scan();
}

void godisrunda(void) {
    match(BORJADE); match(GODISRUNDAN); match(SEMIKOLON); busellergodislista(); match(GICK); match(HEM); match(SEMIKOLON);
}

void busellergodislista(void) {
    if (lookahead == BUS || lookahead == GODIS) {
        busellergodis(); busellergodislista();
    }
    else {
        /* empty */
    }
}

void busellergodis(void) {
    if (lookahead == BUS) {
        match(BUS); match(KOLON); ordlista(); match(SEMIKOLON);
    }
    else if (lookahead == GODIS) {
        match(GODIS); match(KOLON); ordlista(); match(SEMIKOLON);
    }
    else {
        error();
    }
}

void ordlista(void) {
    match(ORD); ordlisterest();
}

void ordlisterest(void) {
    if (lookahead == ORD) {
        match(ORD); ordlisterest();
    }
    else {
        /* empty */
    }
}

void parse() {
    lookahead = scan();
    godisrunda();
    printf("Ok.\n");
}


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 1 november 2018