Kompilatorer och interpretatorer: Lösningar till tentamen 2015-10-26

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 figuren, 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 (7 p)

Det här är ett programavsnitt i ett C-liknande språk:
    x = 0;
    while (x < y) {
        while (y < z) {
            y = y + z + 1;
        }
        z = 2;
    }
Ö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

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 x
        push 0
        assign
label 1:
        rvalue x
        rvalue y
        lt
        gofalse 2
label 3:
        rvalue y
        rvalue z
        lt
        gofalse 4
        lvalue y
        rvalue y
        rvalue z
        plus
        push 1
        plus
        assign
        goto 3
label 4:
        lvalue z
        push 2
        assign
        goto 1
label 2:

c) treadresskod

        x = 0
label 1:
        if (x ≥ y) goto 2
label 3:
        if (y ≥ z) goto 4
        temp1 = y + z
        temp2 = temp1 + 1
        y = temp2
        goto 3
label 4:
        z = 2
        goto 1
label 2:

En kommentar: Man kan redan här optimera bort (eller snarare låta bli att generera) temporärvariabler i tilldelningar, så de två instruktionerna "temp2 = temp1 + 1" och "y = temp2" ovan i stället blir "y = temp1 + 1"

Uppgift 3 (2 p)

Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för släktträdsinmatningsspråket i scenariot.

Namn, punkt (.), utropstecken (!) samt nyckelorden är, barn, till och Klart.

Uppgift 4 (4 p)

Skriv en grammatik för släktträdsinmatningar. Startsymbolen ska vara släktträd, som representerar ett enda släktträd enligt scenariot ovan.

släktträd -> lista Klart utropstecken
lista -> föräldraskap | lista föräldraskap
föräldraskap -> namn är barn till namn punkt

Uppgift 5 (3 p)

Rita upp parse-trädet (även kallat konkret syntaxträd) för det här exemplet från scenariot, enligt din grammatik i uppgiften ovan:
Klas är barn till Sven. Sven är barn till Svea. Klart!

Ett parse-träd

Uppgift 6 (2 p)

Apropå exemplen från scenariot, så nog ser väl det här exemplet väldigt underligt ut?
Nisse är barn till Nisse. Nisse är barn till Nisse. Nisse är barn till Nisse. Klart!
Nisse är barn till sig själv, flera gånger om!

Förklara hur det påverkar parsningen!

Svar: Inte alls. I grammatiken står det bara om tokentypen namn, inget om vilka namn det är. Namn som namn! Analysen av hur släktträdet hänger ihop kommer senare, inte i parsningsfasen.

Uppgift 7 (7 p)

Skriv en prediktiv recursive-descent-parser för släktträdsspecifikationer, 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 en vänsterrekursion i produktionen lista -> lista föräldraskap, så grammatiken måste först skrivas om för att eliminera den vänsterrekursionen:

släktträd -> lista Klart utropstecken
lista -> föräldraskap fler-föräldraskap
fler-föräldraskap -> föräldraskap fler-föräldraskap | ingenting
föräldraskap -> namn är barn till namn punkt

ingenting står för en tom produktion.

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

#include <stdlib.h>
#include <stdio.h>
#include "slakttrad.tab.h" // Bara för att få tokenkoderna
// Från Bison: %token NAMN AR BARN TILL PUNKT KLART UTROPSTECKEN

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 slakttrad(void),
    lista(void),
    fler_foraldraskap(void),
    foraldraskap(void);

void slakttrad(void) {
    lista(); match(KLART); match(UTROPSTECKEN);
}

void lista(void) {
    foraldraskap(); fler_foraldraskap();
}

void fler_foraldraskap(void) {
    if (lookahead == NAMN) {
        foraldraskap(); fler_foraldraskap();
    }
    else {
        /* Ingenting */
    }
}

void foraldraskap(void) {
    match(NAMN); match(AR); match(BARN); match(TILL); match(NAMN); match(PUNKT);
}

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

int main() {
    printf("Mata in ett släktträd. Avsluta med \"Klart!\" och EOF.\n");
    parse();
}

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


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 29 oktober 2015