Kompilatorer och interpretatorer: Lösningar till tentamen 2011-10-31

Uppgift 1: Grunder om kompilatorer (6 p)

debugger, editor, länkning

b) (1p)

En modul eller del av kompilatorn som bearbetar programmet som ska kompileras. Den tar en representation av (hela) programmet som indata, bearbetar den på något sätt, och ger en annan representation av programmet som utdata.

c) (0.5 p)

symboltabellen

d) (0.5p)

• lexikalisk analys ("scanner")
• syntaktisk analys ("parser")
• semantisk analys
• mellankodsgenerering
• maskinoberoende optimering
• kodgenerering
• maskinberoende optimering

Se 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: Mellankod (6 p)

b) postfixkod för en stackmaskin

Inga poängavdrag om man optimerat lite i förväg genom att slå ihop label 1 och 3.

        rvalue a
        rvalue b
        <
        gofalse 1
        lvalue c
        rvalue d
        rvalue e
        /
        rvalue f
        /
        =
        goto 2
label 1:
label 3:
        rvalue g
        rvalue h
        >
        gofalse 4
        lvalue i
        rvalue j
        =
        lvalue k
        rvalue l
        rvalue m
        rvalue n
        /
        /
        =
        goto 3
label 4:
        lvalue o
        push 17
        =
label 2:

c) treadresskod

Inga poängavdrag om man optimerat lite i förväg genom att slå ihop label 1 och 3.
Man kan också använda temporärvariabler för varje deluttryck, så att exempelvis "c = temp1 / f" nedan i stället blir "temp2 = temp1 / f; c = temp2".

        if (a >= b) goto 1
        temp1 = d / e
        c = temp1 / f
        goto 2
label 1:
label 3:
        if (g <= h) goto 4
        i = j
        temp2 = m / n
        k = l / temp2
        goto 3
label 4:
        o = 17
label 2:

Uppgift 3: En oändlig loop (2p)

Normalt ingenting. Optimering, som att upptäcka att kodavsnitt aldrig kan köras, görs efter mellankodsgenereringen. Det är just för att underlätta optimeringen som man överhuvudtaget genererar mellankod.

b) Vad innebär detta för kompileringen i övrigt? Dvs, beskriv om andra delar av kompilatorn på något sätt hanterar att loopen är oändlig.

(Den maskinoberoende) optimeringen kan upptäcka att kodavsnitt är "döda", vilket här betyder att de omöjligen kan komma att köras. Då kan optimeraren ta bort den koden, så när kodgeneratorn genererar målkod kommer den inte med. Alltså är den inte med i det färdiga, kompilerade programmet. Därför skulle optimeraren kunna ta bort o = 17. Däremot kan optimerarn inte generera kod som hoppar vidare ur loopen, för den får inte ändra programmets beteende annat än när det gäller prestanda. (Ett undantag är om ett C-program uppvisar odefinierat beteende. Då får optimeraren göra vad som helst.)

Uppgift 4: Grammatiker (4 p)

Nyckelorden avlyssnat, plats och slut, =, samt tidpunkt, decimaltal och platsnamn.

b) (3p) Skriv en grammatik för språket. Använd terminalerna från deluppgift a. Om grammatiken inte lämpar sig för implementation i form av en prediktiv recursive-descent-parser, ska du också transformera den så den passar.

Grammatik (där *tomt* står för en tom följd av terminaler och icke-terminaler):

inmatning -> kommandon slut
kommandon -> kommando kommandon | *tomt*
kommando -> avlyssning | platsdefinition
avlyssning -> avlyssnat tidpunkt decimaltal decimaltal | avlyssnat tidpunkt platsnamn
platsdefinition -> plats platsnamn = decimaltal decimaltal

• avlyssning -> avlyssnat tidpunkt decimaltal decimaltal
• avlyssning -> avlyssnat tidpunkt platsnamn

inmatning -> kommandon slut
kommandon -> kommando kommandon | *tomt*
kommando -> avlyssning | platsdefinition
avlyssning -> avlyssnat tidpunkt platsangivelse
platsangivelse -> decimaltal decimaltal | platsnamn
platsdefinition -> plats platsnamn = decimaltal decimaltal

Uppgift 5: Parsning (6 p)

#include <stdlib.h>
#include <stdio.h>

int lookahead;

enum Tokentyp { AVLYSSNAT, PLATS, SLUT, LIKAMED, TIDPUNKT, DECIMALTAL, PLATSNAMN };

/* Dummy */

int input[] = {
    AVLYSSNAT, TIDPUNKT, DECIMALTAL, DECIMALTAL,
    PLATS, PLATSNAMN, LIKAMED, DECIMALTAL, DECIMALTAL,
    AVLYSSNAT, TIDPUNKT, PLATSNAMN,
    PLATS, PLATSNAMN, LIKAMED, DECIMALTAL, DECIMALTAL,
    PLATS, PLATSNAMN, LIKAMED, DECIMALTAL, DECIMALTAL,
    PLATS, PLATSNAMN, LIKAMED, DECIMALTAL, DECIMALTAL,
    AVLYSSNAT, TIDPUNKT, PLATSNAMN,
    SLUT,
    -17, -17, -17
};

int inputpos = 0;

int scan() {
    return input[inputpos++];
}

void error() {
  printf("Ledsen error.\n");
  exit(EXIT_FAILURE);
}

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

extern void inmatning(), kommandon(), kommando(), avlyssning(), platsdefinition(), platsangivelse();

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

void inmatning() {
    kommandon(); match(SLUT);
}

void kommandon() {
    if (lookahead == AVLYSSNAT || lookahead == PLATS) {
        kommando(); kommandon();
    }
    else {
        /* Tom produktion. Gör ingenting. */
    }
}

void kommando() {
    if (lookahead == AVLYSSNAT)
        avlyssning();
    else
        platsdefinition();
}

void avlyssning() {
    match(AVLYSSNAT); match(TIDPUNKT); platsangivelse();
}

void platsangivelse() {
    if (lookahead == DECIMALTAL) {
        match(DECIMALTAL); match(DECIMALTAL);
    }
    else {
        match(PLATSNAMN);
    }
}

void platsdefinition() {
    match(PLATS); match(PLATSNAMN); match(LIKAMED); match(DECIMALTAL); match(DECIMALTAL);
}

int main() {
  parse();
  return 0;
}

Uppgift 6: Scanning och reguljära uttryck (1 p)

• [012]?[0-9]:[0-5][0-9]:[0-5][0-9](\.[0-9]+)?
• ([01]?[0-9]|2[0-3]):[0-5][0-9]:[0-5][0-9](\.[0-9]+)?

Uppgift 7: Optimering (5 p)

Det blir följande sex stycken block.

(1) temp1 = b * 17
(2) temp2 = c * 18
(3) a = temp1 + temp2
(4) temp3 = c * 18
(5) if (a > temp3) goto 14

(6) temp4 = c - 1
(7) if (a > temp4) goto 13

(8) temp5 = 1 * d
(9) c = c - temp5
(10) temp6 = b * 17
(11) a = a + temp6
(12) goto 6

(13) goto 16

(14) e = b * 17
(15) f = c * 18

(16) temp7 = b * 17
(17) g = a + temp7

b) Optimera koden med hjälp av de vanliga metoderna för optimering, såväl inom ett enskilt basic block som i flera block. Beskriv inte bara resultatet, utan de olika stegen, gärna med namn.

För att underlätta förklaringarna namnger vi de sex blocken efter deras första rader: B1, B6, B8, B13, B14 och B16.

Vi kan först göra två optimeringar lokalt, dvs genom att bara titta på ett block i taget. I blocket B1 finns det lokala gemensamma deluttrycket c * 18, som vi eliminerar, och den eliminerade variabeln temp3 ersätts med temp2:

(1) temp1 = b * 17
(2) temp2 = c * 18
(3) a = temp1 + temp2
(5) if (a > temp2) goto 14

I blocket B8 finns beräkningen 1 * d, som vi eliminerar, och den eliminerade variabeln temp5 ersätts med d:

(9) c = c - d
(10) temp6 = b * 17
(11) a = a + temp6
(12) goto 6

För att göra fler optimeringar behöver vi studera program- och dataflödet mellan alla blocken, och då underlättar det med en flödesgraf:

Deluttrycken b * 17 och c * 18 förekommer flera gånger, och i inget fall kan b respektive c ha ändrats mellan förekomsterna. Därför kan vi eliminera dem, och ersätta dem med variablerna t1 respektive t2.

Dessutom består blocket B13 enbart av satsen goto 16, och kan inte nås annat än via hopp, så vi kan ta bort det blocket och ersätta goto 13 med goto 16.

Resultat:

(1) temp1 = b * 17
(2) temp2 = c * 18
(3) a = temp1 + temp2
(5) if (a > temp2) goto 14

(6) temp4 = c - 1
(7) if (a > temp4) goto 16

(9) c = c - d
(11) a = a + temp1
(12) goto 6

(14) e = temp1
(15) f = temp2

(17) g = a + temp1