Kompilatorer och interpretatorer: Lösningar till tentamen 2014-11-03

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.

Uppgift 1 (10 p)

En kompilators arbete brukar delas in i ett antal 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 ("scanner"), som delar upp programmets källkodstext i tokens
  2. Syntaktisk analys ("parser"), som analyserar programmet (i form av tokens) enligt källspråkets grammatik
  3. Semantisk analys, som analyserar programmets betydelse, främst med avseende på datatyper ovh typkorrekthet (typkontroll)
  4. Generering av mellankod ("intermediärkod")
  5. Maskinoberoende kodoptimering, som gör programmet (i form av mellankod) mindre och snabbare (eller en av dessa)
  6. Kodgenerator som genererar målkoden
  7. Maskinberoende kodoptimering, som gör optimeringar som bara kan göras på målkodsnivå, till exempel sammanslagning av assemblerinstruktioner
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 (3 p)

När vi "bygger" (dvs kompilerar och länkar) och till sist (efter att ha rättat kompileringsfelen) provkör följande C-program, får vi de angivna fel- och varningsmeddelandena. I vilken av kompilatorns faser (eller på annan plats) upptäcks vart och ett av dessa fel och varningar?

Uppgift 3 (7 p)

Det här är ett programavsnitt i ett C-liknande språk:
    if (a < b)
        c = a;
    else
        c = b;
    while (a < b) {
        a = a * 2 + 3 * d;
        b = b - d - 1;
    }
Översätt ovanstående programavsnitt till var och en av följande tre typer av mellankod.

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

Ett (abstrakt) syntaxträd

b) postfixkod för en stackmaskin

        rvalue a
        rvalue b
        lt
        gofalse 1
        lvalue c
        rvalue a
        assign
        goto 2
label 1:
        lvalue c
        rvalue b
        assign
label 2:
label 3:
        rvalue a
        rvalue b
        lt
        gofalse 4
        lvalue a
        rvalue a
        push 2
        *
        push 3
        rvalue d
        *
        +
        assign
        lvalue b
        rvalue b
        rvalue d
        -
        push 1
        -
        assign
        goto 3
label 4:

c) treadresskod

        if (a ≥ b) goto 1
        c = a
        goto 2
label 1:
        c = b
label 2:
label 3:
        if a ≥ b goto 4
        t1 = a * 2
        t2 = 3 * d
        t3 = t1 + t2
        a = t3
        t4 = b - d
        t5 = t4 - 1
        b = t5
        goto 3
label 4:

Man kan redan här optimera bort (eller snarare låta bli att generera) temporärvariabler i tilldelningar, så att exempelvis de två instruktionerna "t3 = t1 + t2" och "a = t3" ovan i stället blir "a = t1 + t2".

Uppgift 4 (5 p)

Här är ett C-program. Ett programs adressrymd kan delas upp i fyra delar: programkod och konstanter, statiska data, heap och stack. Rita upp hur stacken (med aktiveringsposter), heapen och statiska data ser ut när programkörningen kommer till utskriften av "Här!".

Minnet med stack, heap och statiska data

Scenario till de övriga uppgifterna

En struct i C är ett dataobjekt som innehåller ett eller flera andra dataobjekt. Structar kallas också för poster. Vi ska skriva den del av en C-kompilator som läser (förenklade) struct-deklarationer, Här är ett exempel på en struct som innehåller tre dataobjekt, nämligen ett heltal och två flyttal:

struct Punkt {
    int nummer;
    float x, y;
};
I de förenklade struct-deklarationer som vårt program ska klara finns bara de två datatyperna int och float.

Här är ett annat exempel på en struct-deklaration, som visar att C-kod kan skrivas på fritt format, dvs att man kan stoppa in extra mellanslag och radbrytningstecken:

struct Banan { float pris;
      float             vikt;
int
banannummer;
    float pos1, pos2, pos3,     pos3b; };

Uppgift 5 (3 p)

a) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för struct-deklarationer.

Vänsterklammer ({), högerklammer (}), kommatecken (,), semikolon (;), namn/identifierare, samt nyckelorden struct, int och float.

b) Ange reguljära uttryck för de terminaler som inte har ett fast utseende.

namn/identifierare: [A-Za-z_][A-Za-z_0-9]*

Uppgift 6 (4 p)

Skriv en grammatik för struct-deklarationer. Startsymbolen ska vara deklaration, som representerar en enda struct-deklaration enligt scenariot ovan.

deklaration -> struct namn { medlemmar } ;
medlemmar -> medlem medlemmar | medlem
medlem -> datatyp variabler ;
datatyp -> int | float
variabler -> namn , variabler | namn

Egentligen kan en struct vara helt tom i C, men för att uppgift 8 ska bli roligare har jag gjort grammatiken så att en struct måste ha minst en medlemsvariabel.

Uppgift 7 (3 p)

Rita upp parse-trädet (även kallat konkret syntaxträd) för nedanstående inmatning, enligt grammatiken i uppgiften ovan:
struct Vara {
    int nummer;
    float pris, vikt;
};

Ett parse-träd

Uppgift 8 (7 p)

Skriv en prediktiv recursive-descent-parser för struct-deklarationer, 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, och att den returnerar typen på nästa token.

Det finns FIRST()-konflikter i produktionerna för medlemmar och i produktionerna för variabler, så grammatiken måste först skrivas om med hjälp av två vänsterfaktoriseringar:

deklaration -> struct namn { medlemmar } ;
medlemmar -> medlem fler-medlemmar
fler-medlemmar -> medlemmar | ingenting
medlem -> datatyp variabler ;
datatyp -> int | float
variabler -> namn fler-variabler
fler-variabler -> , variabler | ingenting

ingenting står för en tom produktion.

Ladda ner: structparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation struct.l

#include <stdlib.h>
#include <stdio.h>
#include "struct.tab.h" // Bara för att få tokenkoderna
// Från Bison: %token STRUCT INT FLOAT NAMN

extern int yylex(void);

int lookahead;

int scan(void) {
    return yylex();
}

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 deklaration(void),
    medlemmar(void),
    fler_medlemmar(void),
    medlem(void),
    datatyp(void),
    variabler(void),
    fler_variabler(void);

void deklaration(void) {
    match(STRUCT); match(NAMN); match('{'); medlemmar(); match('}'); match(';');
}

void medlemmar(void) {
    medlem(); fler_medlemmar();
}

void fler_medlemmar(void) {
    if (lookahead == INT || lookahead == FLOAT)
        medlemmar();
    else
        ; /* Ingenting */
}

void medlem(void) {
    datatyp(); variabler(); match(';');
}

void datatyp(void) {
    if (lookahead == INT)
        match(INT);
    else if (lookahead == FLOAT)
        match(FLOAT);
    else
        error();
}

void variabler(void) {
    match(NAMN); fler_variabler();
}

void fler_variabler(void) {
    if (lookahead == ',') {
        match(','); variabler();
    }
    else {
        /* Ingenting */
    }
}

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

int main() {
    printf("Mata in kommandon. Avsluta med KLART-kommandot och EOF.\n");
    parse();
}

// Behövs för Lex
int yywrap(void) {
    return 1;
}


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 20 oktober 2014