Kompilatorer och interpretatorer: Lösningar till tentamen 2017-10-23

Uppgift 1 (5 p)

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

int a, b, c;

void f(int d) {
    int a;
    int* p;

    a = 1;
    b = 2;
    c = 3;
    p = malloc(sizeof(int));
    *p = d;

    if (d < 1)
        f(d + 1);

    printf("Här!\n");
}

int main(void) {
    int a;
    int* p;

    a = 4;
    b = 5;
    c = 6;
    p = malloc(sizeof(int));
    *p = 8;
    f(0);
}

När programexekveringen för första gången kommer fram till raden med utskriften "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.

I minnet kommer det då att finnas ett antal heltalsvariabler och andra lagringsutrymmen för heltal, som innehåller olika tal. Rita upp en skiss över dessa variabler och lagringsutrymmen, med innehåll, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".

Aktiveringsposterna innehåller plats för lokala variabler och funktionens parametrar.

Den globala variabeln a (med C-terminologi har den "lagringsklassen extern") får startvärdet noll, eftersom statiska data i C initieras till noll. (Vanliga lokala variabler, med C-terminologi "lagringsklassen auto"), har odefinierat startvärde i C.)

Uppgift 2 (5 p)

a = 1;
if (b < a - b - c * d) {
    while (i * 2 > j * 3) {
        if (i % 4 == 5)
             i = i + 6;
        b = 7;
    }
    a = 8;
}

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

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

        lvalue a
        push 1
        =
        rvalue b
        rvalue a
        rvalue b
        -
        rvalue c
        rvalue d
        *
        -
        lt
        gofalse ELSE-START-1
label WHILE-START:
        rvalue i
        push 2
        *
        rvalue j
        push 3
        *
        gt
        gofalse AFTER-WHILE
        rvalue i
        push 4
        %
        push 5
        eq
        gofalse ELSE-START-2
        lvalue i
        rvalue i
        push 6
        +
        =
        goto AFTER-IF-2
label ELSE-START-2:
label AFTER-IF-2:
        lvalue b
        push 7
        =
        goto WHILE-START
label AFTER-WHILE:
        lvalue a
        push 8
        =
        goto AFTER-IF-1
label ELSE-START-1:
label AFTER-IF-1:

Två kommentar:

• Jag har använt mallen för en if-sats med else-gren. Om man har en särskild mall för if-satser utan else-gren, kan man ta bort ELSE-START-1 och ELSE-START-2, och hoppa direkt till AFTER-IF-1 respektive AFTER-IF-2.
• 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

        a = 1
        temp1 = a - b
        temp2 = c * d
        temp3 = temp1 - temp2
        if (b >= temp3) goto ELSE-START-1
label WHILE-START:
        temp4 = i * 2
        temp5 = j * 3
        if (temp4 <= temp5) goto AFTER-WHILE
        temp6 = i % 4
        if (temp6 != 5) goto ELSE-START-2
        i = i + 6
label ELSE-START-2:
label AFTER-IF-2:
        b = 7
        goto WHILE-START
label AFTER-WHILE:
        a = 8
        goto AFTER-IF-1
label ELSE-START-1:
label AFTER-IF-1:

Två kommentar:

• Precis som i b-delen har jag använt mallen för en if-sats med else-gren. Om man har en särskild mall för if-satser utan else-gren, kan man ta bort ELSE-START-1 och ELSE-START-2, och hoppa direkt till AFTER-IF-1 respektive AFTER-IF-2.
• Beroende på hur smart mellankodsgeneratorn är, kan man behöva fler temporärvariabler, och i stället för "i = i + 6" kan det behövas de två instruktionerna "temp7 = i + 6" och "i = temp7".

Uppgift 3 (3 p)

a) Vi använder referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.

1: 0, 2: 0, 3: 2, 4: 0, 5: 0, 6: 0, 7: 1, 8: 3, 9: 4, 10: 1, 11: 2, 12: 1, 13: 1, 14: 1, 15: 0, 16: 0

b) Vilka av dataobjekten kommer att tas bort?

15 och 16

c) Antag att vi i stället använder skräpsamling med mark-and-sweep. Vilka av dataobjekten kommer att tas bort av skräpsamlaren?

10, 13, 14, 15 och 16

Uppgift 4 (3 p)

Här är tre varianter. Den första hanterar bara engelska bokstäver (A-Z), den andra hanterar även svenska ÅÄÖ, och den tredje fungerar förmodligen inte (men det kan bero på vilket regexp-bibliotek och vilka språkinställningar man har).

\"[-A-Za-z0-9 ]*\"

\"[-A-ZÅÄÖa-zåäö0-9 ]*\"

\"[-A-Öa-ö0-9 ]*\"

Kommentar: I Flex måste citationstecknen skrivas som \" ovan, men i en del andra sammanhang kan man utelämna bakåtstrecken.

b) (2p) Vilka andra terminaler, förutom textsträng, behövs för att man ska kunna skriva en grammatik för köpen?

Nyckelorden start och klart, samt enhet och tal.

Uppgift 5 (4 p)

köp -> start varurader klart
varurader -> varurad varurader | ingenting
varurad -> tal valfri_enhet sträng
valfri_enhet -> enhet | ingenting

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.

Uppgift 6 (3 p)

start
1 "apelsin"
2 "äpple"
klart

Uppgift 7 (8 p)

Ladda ner: kopparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation kop.l, och en Bison-version av grammatiken kop.y

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

void kop(void) {
    match(start); varurader(); match(klart);
}

void varurader(void) {
    if (lookahead == tal) {
        varurad(); varurader();
    }
    else {
        /* empty */
    }
}

void varurad(void) {
    match(tal); valfri_enhet(); match(strang);
}

void valfri_enhet(void) {
    if (lookahead == enhet) {
        match(enhet);
    }
    else {
        /* empty */
    }        
}

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

Uppgift 8 (20 p)