Kompilatorer och interpretatorer: Lösningar till tentamen 2013-11-04

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.

Uppgift 1 (10 p)

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

  1. Lexikalisk analys analyzer ("scanner"), som delar upp programmets källkodstext i tokens
  2. Syntaktsik analys ("parser"), som analyserar programmet (i form av tokens) enligt källspråkets grammatik
  3. Semantisk analys, som analyserar programmets betydelse, främst med avseende på datatyper ovh typkorrekthet (typkontroll)
  4. Generering av mellankod ("intermediärkod")
  5. Maskinoberoende kodoptimering, som gör programmet (i form av mellankod) mindre och snabbare (eller en av dessa)
  6. Kodgenerator som genererar målkoden
  7. Maskinberoende kodoptimering, som gör optimeringar som bara kan göras på målkodsnivå, till exempel sammanslagning av assemblerinstruktioner
In- och utdata:

Se också boken eller föreläsningsanteckningarna, särskilt den här figurern, 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 (3 p)

Uppgift 3 (7 p)

Det här är ett programavsnitt i ett C-liknande språk:
    b = a;
    while (a < d) {
        c = c * 2 + a;
        a = a - b + 2 * 3;
    }
Översätt ovanstående programavsnitt till var och en av följande tre typer av mellankod.

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

Ett abstrakt syntaxträd

b) postfixkod för en stackmaskin

        lvalue b
        rvalue a
        assign
label 1:
        rvalue a
        rvalue d
        lt
        gofalse 2
        lvalue c
        rvalue c
        push 2
        times
        rvalue a
        plus
        assign
        lvalue a
        rvalue a
        rvalue b
        minus
        push 2
        push 3
        times
        plus
        assign
        jump 1
label 2:

c) treadresskod

        b = a
label 1:        
        if a ≥ d  goto 2
        temp1 = c * 2
        c = temp1 + a
        temp2 = a - b
        temp3 = 2 * 3
        a = temp2 + temp3
        goto 1
label 2:

Man kan också använda temporärvariabler för varje deluttryck, så att exempelvis "c = temp1 + a" ovan i stället blir "temp2 = temp1 + a; c = temp2".

Samma treadresskod men lite annorlunda uppställd:

(1) b = a
(2) if a ≥ d goto 9
(3) temp1 = c * 2
(4) c = temp1 + a
(5) temp2 = a - b
(6) temp3 = 2 * 3
(7) a = temp2 + temp3
(8) goto 2
(9) ....

Uppgift 4 (4 p)

Ange vilka basic blocks som mellankoden från deluppgift c i uppgiften ovan innehåller. Optimera därefter koden med hjälp av de vanliga metoderna för optimering av treadresskod.

Optimeringar i block 3:

(3) temp1 = c * c
(4) c = temp1 + a
(5) temp2 = a - b
(6) temp3 = 2 * 3
(7) a = temp2 + temp3
(8) goto 2
Om addition är snabbare än multiplikation på målmaskinen, kan vi byta ut c * 2 mot c + c. Det kallas reduktion i styrka, dvs att byta ut en operation mot en ekvivalent operation som går snabbare.

Vi kan att beräkna 2 * 3, vilket blir 6, och sedan byta ut instruktion (7) mot a = temp2 + 6. Då kan instruktion (6) och variabeln temp3 tas bort.

Uppgift 5 (3 p)

Jämför mark and sweep med referensräkning. Vilja fördelar och nackdelar har de?

Uppgift 6 (3 p)

a) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för språket.

skapa, skick, kamin, klart, namn, nummer och semikolon (;)

b) Ange reguljära uttryck för de terminaler som inte har ett fast utseende.

namn: [a-z]+
nummer: [0-9]+

Uppgift 7 (4 p)

Skriv en grammatik för språket. Startsymbolen ska vara inmatning, som representerar en hel inmatning som i exemplet ovan i scenariot.

Terminaler skrivs med fetstil, och icke-terminaler kursiverade. *tomt* står för en tom följd av terminaler och icke-terminaler.

inmatning -> kommandolista klart ';'
kommandolista -> kommando kommandolista | *tomt*
kommando -> kaminkommando | skapaskickkommando | skickkommando
kaminkommando -> kamin nummer ';'
skapaskickkommando -> skapa skick namn ';'
skickkommando -> skick nummer namn ';'

Uppgift 8 (3 p)

Rita upp parse-trädet (även kallat konkret syntaxträd) för nedanstående inmatning, enligt grammatiken i uppgiften ovan:
skapa skick skrattretande;
kamin 1;
skick 2 absurd;
klart;

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

Uppgift 9 (2 p)

I uppgiften ovan anger man i inmatningen att kamin 2 har skicket "absurd", Men varken den kaminen eller det skicket har definierats tidigare. Förklara hur det påverkar parsningen!

Inte alls. Om man inte har en ganska underlig grammatik.

(Det finns språk där man måste ta hänsyn till semantisk information vid parsningen. I C++ kan man till exempel skriva int x(y);, vilket är en variabeldefinition om identifieraren y är namnet en variabel, men en funktionsdeklaration om y är namnet på en datatyp. Men i vårt kaminspråk finns det knappast någon anledning att krångla till det så.)

Uppgift 10 (7 p)

Skriv en prediktiv recursive-descent-parser för datorspecifikationssprå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, och att den returnerar typen på nästa token.

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

#include <stdlib.h>
#include <stdio.h>
#include "kaminer.tab.h" // Bara för att få tokenkoderna
// Från Bison: %token SKAPA SKICK KAMIN KLART NAMN NUMMER

extern int yylex(void);

int lookahead;

int scan(void) {
    return yylex();
}

void error() {
    printf("Det har tyvärr uppstått ett fel.\n");
    exit(EXIT_FAILURE);
}

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

void inmatning(void), kommandolista(void), kommando(void), kaminkommando(void), skapaskickkommando(void), skickkommando(void);

void inmatning(void) {
    kommandolista(); match(KLART); match(';');
}

void kommandolista(void) {
    if (lookahead == KAMIN || lookahead == SKAPA || lookahead == SKICK) {
        kommando(); kommandolista();
    }
    else {
        // Tomt
    }
}

void kommando(void) {
    if (lookahead == KAMIN)
        kaminkommando();
    else if (lookahead == SKAPA)
        skapaskickkommando();
    else if (lookahead == SKICK)
        skickkommando();
    else
        error();
}

void kaminkommando(void) {
    match(KAMIN); match(NUMMER); match(';');
}

void skapaskickkommando(void) {
    match(SKAPA); match(SKICK); match(NAMN); match(';');
}

void skickkommando(void) {
    match(SKICK); match(NUMMER); match(NAMN); match(';');
}

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

int main() {
    printf("Mata in kommandon. Avsluta med KLART-kommandot och EOF.\n");
    parse();
}

// Behövs för Lex
int yywrap(void) {
    return 1;
}


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 23 november 2013