Kompilatorer och interpretatorer: Lösningar till tentamen 2022-01-13

Uppgift 1 (11 p)

a) Skriv upp vad faserna heter, och numrera dem i deras logiska ordning.

Svar:

1. Lexikalisk analys ("scanner")
2. Syntaktisk analys ("parser")
3. Semantisk analys
4. Mellankodsgenerering
5. Maskinoberoende optimering
6. Kodgenerator
7. Maskinberoende optimering

b) Vilken fas hör var och en av termerna nedan ihop med? Det kan hända att en del passar in på mer än en fas. Det kan hända att en del inte passar in på någon fas alls.

Skriv fasens nummer enligt ditt svar på a-delen vid varje term, och lämna in det här bladet tillsammans med dina övriga svar!

Svar:

aktiveringspost: ingen, men 6 kan vara ett acceptabelt svar
aktuell token: 2, kanske också 1
anropskonventioner: ingen, men 6 kan vara ett acceptabelt svar
anropsstack: ingen, men 6 kan vara ett acceptabelt svar
basic block: 5
Bison: 2
copy propagation: 5
dataflödesanalys: 5
dekorerat parse-träd: 3
dynamisk länkning: ingen
eliminering av svansrekursion: 5
eliminering av vänsterrekursion: 2
FIRST()-konflikt: 2
flödesgraf: 5
Flex: 1
gemensamma deluttryck: 5
grammatik: 2
heap: ingen
icke-terminal: 2
instruktionsval: 6
kontextfri grammatik: 2
Lex: 1
lexem: 1
lexikaliskt värde: 1
LL(1): 2
lookahead: 2, men 1 kan också vara ett acceptabelt svar
loop unrolling: 5
LR(1): 2
operatorprioritet: 2
operatorassociativitet: 2
parse-träd: 2
produktion: 2
reduce-reduce-konflikt: 2
registerallokering: 6
shift-reduce-konflikt: 2
skräpsamling: ingen
startsymbol: 2
statiska data: ingen
statisk länkning: ingen
syntaxträd: 2, 4
terminal: 2, men 1 kan också vara ett acceptabelt svar
token: 1
treadresskod: 4, 5
tvetydig grammatik: 2
typkontroll: 3
typsystem: 3
vänsterrekursion: 2
Yacc: 2

Poängberäkning: 1 poäng för a-uppgiften, 10 poäng för b-uppgiften. På b-uppgiften finns 48 termer, och man får 1/4 poäng per korrekt associerad term, men de första åtta korrekta räknas inte. 1+(48-8)*1/4 = 11. Decimaler i slutpoängen på uppgiften trunkeras.

Uppgift 2 (8 p)

a = 1; b = 2; if (c < d * e + f * g * h) { j = 3; while (j < k) { j = j + 4 * m; k = 5; } k = 6; }

Ö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!)

Svar:

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

Svar:

        lvalue a
        push 1
        =
        lvalue b
        push 2
        =
        rvalue c
        rvalue d
        rvalue e
        *
        rvalue f
        rvalue g
        *
        rvalue h
        *
        +
        <
        gofalse AFTER-IF
        lvalue j
        push 3
        =
label WHILE-START:
        rvalue j
        rvalue k
        <
        gofalse AFTER-WHILE
        lvalue j
        rvalue j
        push 4
        rvalue m
        *
        +
        =
        lvalue k
        push 5
        =
        jump WHILE-START
label AFTER-WHILE:
        lvalue k
        push 6
        =
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

Svar:

        a = 1
        b = 2
        temp1 = d * e
        temp2 = f * g
        temp3 = temp2 * h
        temp4 = temp1 + temp3
        if (c ≥ temp4) goto AFTER-IF
        j = 3
label WHILE-START:
        if (j ≥ k) goto AFTER-WHILE
        temp5 = 4 * m
        j = j + temp5
        k = 5
        goto WHILE-START
label AFTER-WHILE:
        k = 6
label AFTER-IF:

Vi kan också numrera instruktionerna och översätta programlägesetiketterna ("labels" på engelska), så ser det likadant ut som exemplet från föreläsningarna:

(1)     a = 1
(2)     b = 2
(3)     temp1 = d * e
(4)     temp2 = f * g
(5)     temp3 = temp2 * h
(6)     temp4 = temp1 + temp3
(7)     if (c ≥ temp4) goto 15
(8)     j = 3
(9)     if (j ≥ k) goto 14
(10)    temp5 = 4 * m
(11)    j = j + temp5
(12)    k = 5
(13)    goto 9
(14)    k = 6
(15)    ....

Uppgift 3 (4 p)

Svar:

{ } : , heltal sträng

b) (2p) En del av terminalerna har inte fixa lexem, utan kan se olika ut. Skriv, för varje sådan terminal, ett reguljärt uttryck som beskriver hur den får se ut!

Svar:

heltal: [0-9]+
sträng: \"[^"]*\"

En kommentar:

• En del har inte gjort en sträng-token där citationstecknen (") ingår, så att en komplett sträng bildar en token, utan i stället har de gjort citationstecknet som en egen token, och sen ska allt mellan två citationstecken-tokens bilda en sträng. Det är väl inte helt omöjligt att göra så, men det blir både konstigt och krångligt. Vad händer till exempel med blanktecken och radbrytningar, som scannern normalt ska kunna kasta bort?

Uppgift 4 (5 p)

Svar:

objekt -> { valfri-par-lista }
valfri-par-lista -> par-lista | ingenting
par-lista -> par , par-lista | par
par -> sträng : värde
värde -> sträng | heltal | objekt

Kommentarer:

• 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.
• Tänk på namngivning och struktur även i en grammatik! Exempelvis är det förvirrande för läsaren, och därför olämpligt, om en icke-terminal som heter namn-värde-par inte skulle beskriva ett namn-värde-par, utan i stället en hel lista med ett eller flera namn-värde-par. Eller om icke-terminalen objekt inte har en produktion med högerledet { lista }, utan i stället { lista, och där slut-fiskmåsklammern för objektet ingår i listan lista. En lista skulle då alltså inte vara en lista, utan en lista plus en obalanserad klammer.

Uppgift 5 (4 p)

{ "namn" : "Örebro", "befolkning" : 126009 }

Svar:

Uppgift 6 (8 p)

Svar:

I grammatiken som vi skrivit ovan finns en FIRST()-konflikt, som först måste elimineras. Vi får en ny grammatik som beskriver samma språk:

objekt -> { valfri-par-lista }
valfri-par-lista -> par-lista | ingenting
par-lista -> par par-liste-rest
par-liste-rest -> , par-lista | ingenting
par -> sträng : värde
värde -> string | heltal | objekt

Ladda ner: mini-json-parser.c, plus en hjälpfil i form av en Lex-scannerspecifikation, mini-json.l, och en Bison-version av grammatiken, mini-json.y. Det finns också en Makefile för att bygga parsern.

Token-typer: BEGIN_OBJECT, END_OBJECT, COLON, COMMA, NUMBER, STRING

int lookahead;

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

void object(void) {
    match(BEGIN_OBJECT); optional_pair_list(); match(END_OBJECT);
}

void optional_pair_list(void) {
    if (lookahead == STRING) {
        pair_list();
    }
    else {
        /* Empty */
    }
}

void pair_list(void) {
    pair(); pair_list_rest();
}

void pair_list_rest(void) {
    if (lookahead == COMMA) {
        match(COMMA); pair_list();
    }
    else {
        /* Empty */
    }
}

void pair(void) {
    match(STRING); match(COLON); value();
}

void value(void) {
    if (lookahead == STRING) {
        match(STRING);
    }
    else if (lookahead == NUMBER) {
        match(NUMBER);
    }
    else {
        object();
    }
}

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

int main() {
    printf("Enter a Mini-JSON object!\n");
    parse();
}