Kompilatorer och interpretatorer: Lösningar till tentamen 2020-10-27

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 bakgrundssorl från en restaurang eller liknande. Här nedan kommer lösningsförslagen till uppgifterna.

Uppgift 1 (5 p)

Vi ska göra ett gissa-spel. Spelaren ska tänka på ett tal, och datorn gissar vilket tal det är. Ett körexempel, med användarens inmatning understruken:
Tänk på ett tal och tryck ENTER.

Är det 7?
nej
Är det 7?
nej
Är det 7?
va?
Svara ja eller nej!
Är det 7?
sluta
Svara ja eller nej!
Är det 7?
nej
Är det 7?
ja
Jag vann!
Datorn gissar alltså hela tiden på talet 7, tills användaren ger upp och svarar "ja"!

Vi skriver spelet i form av ett C-program, men det blev tyvärr inte helt korrekt, och när vi försöker bygga och köra det får vi de angivna fel- och varningsmeddelandena. I vilka av kompilatorns faser, eller vid andra tidpunkter, upptäcks vart och ett av de olika felen och varningarna?

(Man kan behöva åtgärda en del av felen för att komma vidare och få de andra felen.)

Programmet Meddelanden Svar
#include <stdio.h>

int question(void) {
    char svar[10];
    while (true) {
        gets(svar);
        if (strcmp(svar, "ja") == 0)
            return 1; @
        else if (strcmp(svar, nej) == 0)
            return 0;
        else {
            printf("Svara ja eller nej!\n");
            return;
        }
    }
}

int Main(void) {
    printf("Tänk på ett tal\n");
    printf("och tryck ENTER.\n");
    while (getchar() != "\n")
        ;
    do {
        printf("Är det 7?\n");
    } while (question() != 1e);
    printf("Jag vann!\n")
} /* main




'true' undeclared

implicit declaration of 'strcmp'
stray '@' in program
'nej' undeclared



'return' with no value




undefined reference to 'main'


comparison between pointer and integer



exponent has no digits
expected ';' before '}' token
unterminated comment




semantisk analys

semantisk analys
scanner
semantisk analys



semantisk analys




länkaren


semantisk analys



scanner
parser
scanner

Uppgift 2 (5 p)

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

Översätt ovanstående programavsnitt till två av följande tre typer av mellankod. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

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

Ett (abstrakt) syntaxträd

b) postfixkod för en stackmaskin

        rvalue a
        rvalue b
        -
        rvalue c
        rvalue d
        *
        rvalue e
        *
        <
        gofalse ELSE-START
label WHILE-START:
        rvalue a
        rvalue b
        <
        gofalse AFTER-WHILE
        lvalue c
        rvalue d
        rvalue e
        *
        rvalue f
        +
        =
        lvalue d
        rvalue e
        rvalue f
        *
        rvalue g
        *
        =
        jump WHILE-START
label AFTER-WHILE:
        goto AFTER-IF
label ELSE-START:
        lvalue a
        rvalue b
        =
label AFTER-IF:

c) treadresskod

        temp1 = a - b
        temp2 = c * d
        temp3 = temp2 * e
        if temp1 >= temp3 goto ELSE-START
label WHILE-START:
        if a >= b goto AFTER-WHILE
        temp4 = d * e
        c = temp4 + f
        temp5 = e * f
        d = temp5 * g
        goto WHILE-START
label AFTER-WHILE:
        goto AFTER-IF
label ELSE-START:
        a = b
label AFTER-IF:

Uppgift 3 (5 p)

I uppgiften ovan finns en while-loop med villkoret a < b, men ingen av variablerna a och b ändras i loopen. Om villkoret är sant från början, får man alltså en oändlig loop.

Förklara hur detta påverkar var och en av faserna i kompilatorn!

Scannern påverkas inte alls. Scannern arbetar med enskilda tokens i källprogrammet, och det har inget med oändliga loopar att göra.

Parsern påverkas inte alls. Parsern jämför källprogrammet med källspråkets grammatik, och grammatiken säger (normalt) inget om värden på loopvillkor och andra uttryck.

Den semantiska analysen påverkas förmodligen inte alls. Den semantiska analysfasen arbetar med vad programmet betyder, och det har mycket att göra med datatyper, till exempel vilken jämförelseoperator man egentligen använder i loopvillkoret. Man kan möjligen tänka sig ett språk där man låter variablers konstans (om de ändras eller inte) vara en del av datatypen, men det gäller normalt sådant som const-deklarationer i C och C++, och inte en analys som kan avgöra om ett loopvillkor ändras.

Mellankodsgeneratorn påverkas inte alls. Den gör en ganska enkel översättning av källprogrammet till mellanformatet, och genererar mellankod som motsvarar loopen.

Den maskinoberoende optimeraren kan analysera hur variabler ändras, och det är i den här fasen kompilatorn kan upptäcka att villkoret alltid är sant, och att loopen blir oändlig. I så fall kan hela resten av programmet optimeras bort! Alternativt kan optimeraren upptäcka att villkoret alltid är falskt, och då kan loopen optimeras bort.

Kodgeneratorn genererar målkod baserat på resultatet från den maskinoberoende optimeringen. Om delar av programmet optimerats bort, kommer ingen kod att genereras för dem.

Den maskinberoende optimeraren gör ganska enkla förbättringar av den genererade målkoden. Eventuella optimeringar som innebär att delar av källprogrammet försvinner och inte har någon motsvarighet i målprogrammet är redan gjorda, så denna fas påverkas inte, mer än att den förstås slipper arbeta med dessa bortoptimerade delar.

Uppgift 4 (2 p)

a) Vad är ett basic block?

En följd av instruktioner, till exempel i treadresskod, där det inte sker några hopp vare sig in i eller ut ur blocket, med undantag för att hopp kan ske till den första instruktionen i blocket, och att den sista instruktionen kan vara ett (villkorligt eller ovillkorligt) hopp.

b) Definitionen av basic block innehåller en del begränsningar av vilka hopp som är tillåtna. Varför finns dessa begränsningar?

För att underlätta för optimeraren. Man vet att alla instruktionerna utförs, i den ordning de står, så det är mycket enklare att analysera vilka värden variablerna har, än om hopp kan ske hur som helst.

Uppgift 5 (7 p)

a) En av terminalerna som behövs för att man ska kunna skriva en grammatik för språket är ord. Ett ord är en följd av stora eller små bokstäver. Skriv ett reguljärt uttryck som beskriver hur ett ord får se ut.

[A-Za-z]+

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

"=", radslut och nyckelorden candidate, vote, alias och result

c) Skriv en scanner som kan dela upp inmatningen i tokens. Du får själv välja om du ska använda Flex eller skriva den för hand i C, C++ eller ett liknande språk. Scannern ska bestå av en funktion som returnerar en token-kod. Du kan anta att token-koderna finns definierade i form av makron, ungefär som Bison gör när man har en Bison-grammatik med %token-deklarationer.

Här är en Flex-fil (election.l):

%{
    #include "election.tab.h"
%}

%%

[\t ] { /* Ignorera whitespace utom radslut */ }
\n { return END_OF_LINE; }
"candidate"  { return CANDIDATE; }
"alias" { return ALIAS; }
"vote" { return VOTE; }
"result" { return RESULT; }
[a-zA-Z]+ { return WORD; }
"=" { return EQUALS; }
. { fprintf(stderr, "[Ignorerar felaktigt tecken: '%c']\n", *yytext); }

%%

Uppgift 6 (5 p)

Skriv en grammatik för språket. Startsymbolen ska vara inmatning, som representerar en fullständig inmatning enligt scenariot ovan.
inmatning -> kommandon resultatkommando
kommandon -> kommando kommandon | tomt
kommando -> kandidatkommando | aliaskommando | rostningskommando
flera-ord -> ord flera-ord | ord
kandidatkommando -> candidate flera-ord radslut
aliaskommando -> alias ord = flera-ord radslut
rostningskommando -> vote flera-ord radslut
resultatkommando -> result radslut

tomt markerar en tom produktion.

Uppgift 7 (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 inmatningen, enligt din grammatik i uppgiften ovan:

candidate Kim Jong Un
vote Kim Jong Un
result

Ett (konkret) parse-träd

Uppgift 8 (8 p)

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

Grammatiken i uppgift 6 har en FIRST()-konflikt, så vi behöver först vänsterfaktorisera:

flera-ord -> ord flera-ord | ord

blir i stället:

flera-ord -> ord noll-eller-flera-ord | ord
noll-eller-flera-ord -> ord noll-eller-flera-ord | ord

En nedladdningsbar komplett fil finns här: election-parser.c

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

void inmatning(void) {
    kommandon(); resultatkommando();
}


void kommandon(void) {
    if (lookahead == CANDIDATE || lookahead == ALIAS || lookahead == VOTE) {
        kommando(); kommandon();
    }
    else {
        /* Tomt */
    }
}

void kommando(void) {
    if (lookahead == CANDIDATE) {
        kandidatkommando();
    }
    else if (lookahead == ALIAS) {
        aliaskommando();
    }
    else if (lookahead == VOTE) {
        rostningskommando();
    }
    else {
        error("Det här kan inte hända");
    }
}

void flera_ord(void) {
    match(WORD); noll_eller_flera_ord();
}

void noll_eller_flera_ord(void) {
    if (lookahead == WORD) {
        match(WORD); noll_eller_flera_ord();
    }
    else {
        /* Tomt */
    }
}

void kandidatkommando(void) {
    match(CANDIDATE); flera_ord(); match(END_OF_LINE);
}

void aliaskommando(void) {
    match(ALIAS); match(WORD); match(EQUALS); flera_ord(); match(END_OF_LINE);
}

void rostningskommando(void) {
    match(VOTE); flera_ord(); match(END_OF_LINE);
}

void resultatkommando(void) {
    match(RESULT); match(END_OF_LINE);
}

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

int main() {
    printf("Mata in ett kommando. Avsluta med EOF.\n");
    parse();
}


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 26 oktober 2020