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

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. Dessutom har det inträffat i världshistorien att lärare skrivit fel i lösningsförslagen. Jag har förstås aldrig gjort det, men andra. Är det verkligen någon som läser såna här inledande texter? Jag vet inte. Det kan vara så. Rabarber rabarber rabarber. Det har jag hört att statisterna får säga på filminspelningar när det ska vara bakgrundsorl från en restaurang eller liknande. Här nedan kommer lösningsförslagen till uppgifterna.

Uppgift 1 (5 p)

Betrakta följande C-program:

#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".

Programmets adressrymd vid utskriften med printf

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)

Det här är ett programavsnitt i ett C-liknande språk:
a = 1;
if (b < a - b - c * d) {
    while (i * 2 > j * 3) {
        if (i % 4 == 5)
             i = i + 6;
        b = 7;
    }
    a = 8;
}
Ö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

En kommentar:

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:

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:

Uppgift 3 (3 p)

Antag att minnet innehåller dessa sexton dataobjekt. Pilarna är pekare, och kryss betyder NULL-pekare. De inringade objekten, nummer 1-6, utgör rotmängden.

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)

a) (1p) En av terminalerna, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för köpen är textsträng. En textsträng inleds och avslutas med ett citationstecken ("), och den kan innehålla bokstäver, siffror, bindestreck och mellanslag. Skriv ett reguljärt uttryck som beskriver hur en textsträng får se ut.

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)

Skriv en grammatik för ett köp. Startsymbolen ska vara köp, som representerar en inmatning enligt scenariot ovan.

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)

Ett parse-träd (ibland kallat "konkret syntaxträd") innehåller noder för alla icke-terminaler. Rita upp parse-trädet för det här köpet, enligt din grammatik i uppgiften ovan:

start
1 "apelsin"
2 "äpple"
klart

Ett parse-träd

Uppgift 7 (8 p)

Skriv en prediktiv recursive-descent-parser för köp, 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, som returnerar typen på nästa token, och en funktion som heter error, som man kan anropa när något gått fel och som skriver ut ett felmeddelande och avslutar programmet.

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)

Ange för varje påstående om det är sant eller falskt! Lämna in sidorna med den här uppgiften tillsammans med resten av svaren. Fel svar ger inte minuspoäng.

Påstående Sant Falskt
Den första fasen i kompilatorn är den lexikaliska analysatorn, även kallad scanner. X  
Scannern gör om en sekvens av tokens till en sekvens av tecken.   X
Den andra fasen i kompilatorn är den syntaktiska analysatorn, även kallad parser. X  
I de flesta vanliga programmeringsspråk tolkas de tre tecknen 123 som ett heltal, vilket är en typ av token. För heltalet 123 är lexemet de tre tecknen 1, 2 och 3. X  
För heltalet 123 är det lexikaliska värdet talet 123. X  
Parsern analyserar programmet enligt källspråkets grammatik. X  
Utdata från parsern är ofta ett syntaxträd, men det är inte säkert att man faktiskt bygger upp trädet, med pekare i minnet eller på annat sätt. X  
Semantisk analys analyserar programmets betydelse, dvs om det stämmer med källspråkets grammatik.   X
Det är den semantiska analysatorn som avgör vad additionen i deluttrycket x+y egentligen innebär, till exempel om det är addition av heltal eller om det är sammanslagning av strängar. X  
Det är den semantiska analysen som lägger in symboler i symboltabellen.   X
Mellankodsgeneratorn genererar mellankod ("intermediärkod"). Mellankoden skickas vidare till nästa fas som textrader, till exempel t2 = x + t1, och så körs scannern på nytt för att läsa in dem, men de är så enkla att parsern inte behövs.   X
Maskinoberoende kodoptimering gör programmet mindre och snabbare (eller en av dessa). Det kan hända att det optimerade programmet blir större än utan optimering, till exempel med looputrullning. X  
Kodgeneratorn genererar målkoden, som till exempel kan bestå av maskininstruktioner för en fysisk processor. X  
Målkoden kan vara i form av text, till exempel assemblerinstruktioner som ADD R1, R2. X  
Den maskinberoende optimeraren gör optimeringar som bara kan göras på målkodsnivå, till exempel sammanslagning av assemblerinstruktioner. X  
Om scannern är implementerad i form av en funktion som heter scan, och parsern är implementerad i form av en funktion som heter parse, kommer funktionen scan alltid att anropas före funktionen parse.   X
Den semantiska analysen resulterar i mellankod, som den maskinoberoende kodoptimeraren sen omvandlar till ett syntaxträd.   X
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan omvandla 1+2 till 3. X  
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan ibland omvandla en loop till ett konstant värde. X  
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan omvandla en länkad lista till en hashtabell.   X


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 25 oktober 2017