Kompilatorer och interpretatorer: Lösningar till tentamen 2012-11-05

Observera att detta är förslag på lösningar. Det kan finnas andra lösningar som också är korrekta, och 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.

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")
  2. Syntaktsik analys ("parser")
  3. Semantisk analys
  4. Generering av mellankod ("intermediärkod")
  5. Maskinoberoende kodoptimering
  6. Kodgenerator
  7. Maskinberoende kodoptimering
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 (6 p)

Det här är ett programavsnitt i ett C-liknande språk:

    a = b;
    c = 17;
    while (x < 19) {
        x = x + b - c - 1;
        if (c > 0)
            c = c - 1;
        r = r + 2 * b;
    }

Översätt ovanstående programavsnitt till två 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 a
        rvalue b
        assign
        lvalue c
        push 17
        assign
label 1:
        rvalue x
        push 19
        lt
        gofalse 2
        lvalue x
        rvalue x
        rvalue b
        plus
        rvalue c
        minus
        push 1
        minus
        assign
        rvalue c
        push 0
        le
        gofalse 3
        lvalue c
        rvalue c
        push 1
        minus
        assign
label 3:
        lvalue r
        rvalue r
        push 2
        rvalue b
        times
        plus
        assign
        jump 1
label 2:

c) treadresskod

        a = b
        c = 17
label 1:        
        if (x >= 19) goto 2
        temp1 = x + b
        temp2 = temp1 - c
        x = temp2 - 1
        if (c <= 0) goto 3
        c = c - 1
label 3:
        temp3 = 2 * b;
        r = r + temp3
        goto 1
label 2:

Man kan också använda temporärvariabler för varje deluttryck, så att exempelvis "x = temp2 - 1" ovan i stället blir "temp3 = temp2 - 1; x = temp3".

Uppgift 3 (10 p)

Vi vill skapa ett språk för att kunna hantera anslag och anslagstavlor. Här är en grammatik för språket. Terminaler skrivs med fetstil, och icke-terminaler kursiverade. *tomt* står för en tom följd av terminaler och icke-terminaler.

kommandolista -> kommando kommandolista | *tomt*
kommando -> anslagskommando | anslagstavlekommando | placeringskommando
anslagskommando -> skapa anslag heltal rubrik innehåll
rubrik -> textsträng
innehåll -> textsträng
anslagstavlekommando -> skapa anslagstavla heltal
placeringskommando -> sätt upp anslag heltal  anslagstavla heltal

Här är också en Flex-fil som beskriver hur terminalerna i språket ser ut:

%{
    #include "anslag.tab.h"
%}
%%
[\n\t ] { /* Ignorera whitespace */ }
skapa { return skapa; }
anslag { return anslag; }
anslagstavla { return anslagstavla; }
sätt { return sätt; }
upp { return upp; }
på { return ; }
[0-9]+ { return heltal; }
\"[^"]*\" { return textsträng; }
. { fprintf(stderr, "Ignorerar felaktigt tecken: '%c'\n", *yytext); }
%%

a) Icke-terminalen kommando beskriver de kommandon som man kan ge. Ange fem olika kommandon som ingår i det språk som beskrivs av grammatiken ovan. Variera dem så att de inte är alltför lika.

skapa anslag 13 "Säljes" "En båt"
skapa anslag 13 "Köpes" "En väldigt fin liten båt som jag kan segla med"
skapa anslagstavla 14
sätt upp anslag 13 på anslagstavla 14
sätt upp anslag 14 på anslagstavla 17

b) Ange fem olika kommandon som inte ingår i det språk som beskrivs av grammatiken ovan, men som man kanske skulle kunna tro gjorde det om man inte var så bra på grammatiker och Flex.

kommando kommandolista
skapa anslag heltal rubrik innehåll
sätt upp anslag heltal på anslagstavla heltal
*tomt*
skapa anslagstavla [0-9]+

c) Den här grammatiken lämpar sig inte för implementation av en prediktiv recursive-descent-parser. Ange vilket eller vilka problem som finns, vad i grammatiken som orsakar problemen, och vad som händer i parsern.

Vi har en FIRST()-konflikt eftersom både anslagskommando och anslagstavlekommando börjar med terminalen skapa. Om vi ska parsa ett kommando och hittar terminalen skapa i inmatningen, vet vi därför inte om det som kommer är ett anslagskommando eller ett anslagstavlekommando. Proceduren kommando i parsern skulle se ut så här:

void kommando() {
    if (lookahead == SÄTT)
        placeringskommando();
    else if (lookahead == SKAPA)
        // Ja, vad? Ska vi anropa anslagskommando eller anslagstavlekommando?

d) Använd de transformationer som tagits upp i kursen för att omvandla grammatiken till en grammatik som beskriver samma språk, men som enkelt kan implementeras i en prediktiv recursive-descent-parser. Ange vilka transformationer du gör, och visa vad resultatet blir för den här grammatiken.

Väsnterfaktorisering ger:

kommandolista -> kommando kommandolista | *tomt*
kommando -> skapa skapelse | placeringskommando
skapelse -> anslagsskapelse | anslagstavleskapelse
anslagsskapelse -> anslag heltal rubrik innehåll
rubrik -> textsträng
innehåll -> textsträng
anslagstavleskapelse -> anslagstavla heltal
placeringskommando -> sätt upp anslag heltal  anslagstavla heltal

e) Skriv den prediktiva recursive-descent-parsern i ett språk som åtminstone liknar C, Java eller Pascal. 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 och provkör: anslagsparser.c

int lookahead;

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 kommandolista(void) {
    if (lookahead == SKAPA || lookahead == SATT) {
        kommando(); kommandolista();
    }
    else {
        // Tomt
    }
}

void kommando(void) {
    if (lookahead == SKAPA) {
        match(SKAPA); skapelse();
    }
    else if (lookahead == SATT) {
        placeringskommando();
    }
    else {
        error();
    }
}

void skapelse(void) {
    if (lookahead == ANSLAG) {
        anslagsskapelse();
    }
    else if (lookahead == ANSLAGSTAVLA) {
        anslagstavleskapelse();
    }
    else {
        error();
    }
}

void anslagsskapelse(void) {
    match(ANSLAG); match(HELTAL); rubrik(); innehall();
}

void rubrik(void) {
    match(TEXTSTRANG);
}

void innehall(void) {
    match(TEXTSTRANG);
}

void anslagstavleskapelse(void) {
    match(ANSLAGSTAVLA); match(HELTAL);
}

void placeringskommando(void) {
    match(SATT); match(UPP); match(ANSLAG); match(HELTAL); match(PA); match(ANSLAGSTAVLA); match(HELTAL);
}

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

Uppgift 4 (4 p)

Adressrymden

Uppgift 5 (5 p)

a)
Dataobjekt nummer 1, 2, 4 och 5 kommer att markeras.
De objekt som markerats kommer att behållas.
De objekt som inte markerats kommer att förstöras, och det minne de tar upp kan återanvändas till annat.

b)
Rotmängden är utgångspunkten för vad som är nåbart från programmet. Dataobjekt som finns i rotmängden, eller som kan nås via pekare i ett eller flera steg från objekt i rotmängden, är nåbara, och eftersom de är nåbara kan det hända att vi kommer att använda dem i framtiden, så de ska inte förstöras. Ej nåbara objekt kan inte nås, och kommer därför inte att användas, så de kan förstöras.

c)
Objekt 1: 2
Objekt 2: 1
Objekt 3: 1
Objekt 4: 2
Objekt 5: 2
Objekt 6: 1
Objekt 7: 1
Objekt 8: 1


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 6 november 2012