Kompilatorer och interpretatorer: Lösningar till tentamen 2016-10-24

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 (5 p)

När vi kompilerar, länkar och sedan kör följande försök till C-program, får vi de kursiverade fel- och varningsmeddelandena. I vilka faser, eller vid andra tidpunkter, upptäcks vart och ett av de olika felen och varningarna? (Vi kan behöva rätta en del av felen för att komma vidare så att de andra felen upptäcks.)
#include <stdi.h> // fatal error: stdi.h: No such file or directory preprocessorn

int main(void) {
    double d1 = 1.0; // warning: unused variable 'd1' maskinoberoende optimering eller kanske semantisk analys
    int d1 = 2; // error: conflicting types for 'd1' semantisk analys
    double 2; // error: expected identifier or '(' before numeric constant parser
    int i = 17;

    printf(Hej!); // error: 'Hej' undeclared semantisk analys
                  // error: expected ')' before '!' token parser
    printg("%d", i); // undefined reference to `printg' länkning
    printf("%s", i); // Segmentation fault (core dumped) exekvering

    return 0;
}

Uppgift 3 (5 p)

Här är ett C-program. Ett programs adressrymd kan delas upp i fyra delar: programkod och konstanter, statiska data, heap och stack. Rita upp hur stacken (med aktiveringsposter), heapen och statiska data ser ut, med innehåll, när programkörningen kommer till utskriften med printf.
#include <stdlib.h>
#include <stdio.h>

int a = 1, b = 2;

int f(int x, int y) {
    int c;
    int *d;
    a = x;
    c = 3;
    d = malloc(sizeof(int));
    *d = b;
    if (x < 2) {
        return x * f(x + 1, y + 2);
    }
    else {
        printf("Nu!\n");
        return 1;
    }
}

int main(void) {
    int a;
    int *b;
    a = 2;
    b = malloc(sizeof(int));
    *b = 3;
    a = f(0, 4);
    return 0;
}

Programmets adressrymd vid utskriften med prntf

Uppgift 4 (5 p)

Det här är ett programavsnitt i ett C-liknande språk:
    a = 1;
    b = c * 2 + 3 + d;
    if (a < b) {
        while (a + 4 < b * 5 + c) {
            a = a + 6;
        }
    }
    else {
        a = 7;
        b = 8;
    }
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.

a) ett syntaxträd, även kallat abstrakt syntaxträd (genom att rita upp trädet!)

Ett (abstrakt) syntaxträd

En kommentar: Man kan avsluta ";-listorna" med NULL i stället för den sista satsen i listan. Det blir lite mer att rita, men kan vara lite enklare programmeringsmässigt.

b) postfixkod för en stackmaskin

        lvalue a
        push 1
        =
        lvalue b
        rvalue c
        push 2
        *
        push 3
        +
        rvalue d
        +
        =
        rvalue a
        rvalue b
        lt
        gofalse ELSE-START
label WHILE-START:
        rvalue a
        push 4
        +
        rvalue b
        push 5
        *
        rvalue c
        +
        lt
        gofalse AFTER-WHILE
        lvalue a
        rvalue a
        push 6
        +
        =
        goto WHILE-START
label AFTER-WHILE:
        goto AFTER-IF
label ELSE-START:
        lvalue a
        push 7
        =
        lvalue b
        push 8
        =
label AFTER-IF:

En kommentar: Exemplen i kursen har oftast använt numeriska programlägesetiketter ("labels"), men man kan som ovan ha en stackmaskin som förstår mnemoniska namn. Det blir lite lättare att läsa. Har man flera if-satser eller while-loopar måste man förstås generera namn som är olika, till exempel ELSE-START-1, ELSE-START-2 och så vidare.

c) treadresskod

        a = 1
        temp1 = c * 2
        temp2 = temp1 + 3
        temp3 = temp2 + d
        b = temp3
        if a ≥ b goto ELSE-START
label WHILE-START:
        temp4 = a + 4
        temp5 = b * 5
        temp6 = temp5 + c
        if temp4 ≥ temp6 goto AFTER-WHILE
        temp7 = a + 6
        a = temp7
        goto WHILE-START
label AFTER-WHILE:
        goto AFTER-IF
label ELSE-START:
        a = 7
        b = 8
label AFTER-IF:

En kommentar: Man kan redan här optimera bort (eller snarare låta bli att generera) temporärvariabler i tilldelningar, så de två instruktionerna "temp3 = temp2 + d" och "b = temp3" ovan i stället blir "b = temp2 + d".

Scenario till de övriga uppgifterna

Vi ska bygga ett system för att beställa fikabröd från ett bageri, med en klientdel där man kryssar för i rutor, och en serverdel som hanterar beställningarna. När klientdelen skickar en beställning till serverdelen följer kommunikationen ett särskilt protokoll.

En beställning börjar med nyckelordet start och avslutas med nyckelordet klart. Efter nyckelordet start kommer nyckelordet namn följt av en textsträng som anger namnet på kunden. Därefter kan det, men måste inte, komma nyckelordet telefon följt av en textsträng som anger telefonnumret till kunden. Efter detta en eller flera fikabrödsbeställningar, där var och en består av ett tal (som kan innehålla decimaler) och ett av orden kanelbulle, wienerbröd och chokladboll. Blanktecken, som mellanslag och radslut, ska ignoreras, förutom inuti nyckelord, tal och textsträngar.

Här följer två exempel på beställningar:

start
namn "Anna A. Andersson"
telefon "070-73 47 013"
1 kanelbulle
2 wienerbröd
1 kanelbulle
1 chokladboll
3 chokladboll
klart

          start namn
        "Anna A. Andersson" 1
kanelbulle 2      wienerbröd



                 klart

Uppgift 5 (2 p)

Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för fikabeställningarna i scenariot.

Nyckelorden start, klart, namn, telefon, kanelbulle, wienerbröd och chokladboll, samt tal och sträng.

Uppgift 6 (4 p)

Skriv en grammatik för fikabeställningar. Startsymbolen ska vara beställning, som representerar en komplett beställning enligt scenariot ovan.

beställning -> start namndel telefondel lista klart
namndel -> namn sträng
telefondel -> telefon sträng | ingenting
lista -> sak | sak lista
sak -> tal fikatyp
fikatyp -> kanelbulle | wienerbröd | chokladboll

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 7 (3 p)

Rita upp parse-trädet (även kallat konkret syntaxträd) för den här beställningen, enligt din grammatik i uppgiften ovan:

start
namn "Olle"
1 kanelbulle
2 wienerbröd
klart

Ett parse-träd

Uppgift 8 (7 p)

Skriv en prediktiv recursive-descent-parser för fikabeställningar, 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.

Eftersom det finns en FIRST()-konflikt i de två produktionerna lista -> sak | sak lista måste vi vänsterfaktorisera, vilket ger en ny grammatik:

beställning -> start namndel telefondel lista klart
namndel -> namn sträng
telefondel -> telefon sträng | ingenting
lista -> sak flersaker
flersaker -> lista | ingenting
sak -> tal fikatyp
fikatyp -> kanelbulle | wienerbröd | chokladboll

Ladda ner: fikaparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation fika.l.

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

void beställning(void) {
    match(start); namndel(); telefondel(); lista(); match(klart);
}

void namndel(void) {
    match(namn); match(sträng);
}

void telefondel(void) {
    if (lookahead == telefon) {
        match(telefon); match(sträng);
    }
    else {
        /* empty */
    }
}

void lista(void) {
    sak(); flersaker();
}

void flersaker(void) {
    if (lookahead == tal) {
        lista();
    }
    else {
        /* empty */
    }        
}

void sak(void) {
    match(tal); fikatyp();
}

void fikatyp(void) {
    if (lookahead == kanelbulle) {
        match(kanelbulle);
    }
    else if (lookahead == wienerbröd) {
        match(wienerbröd);
    }
    else if (lookahead == chokladboll) {
        match(chokladboll);
    }
    else
        error();
}

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


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 25 oktober 2016