Örebro universitet
Institutionen för naturvetenskap och teknik
Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se)






Tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet m fl

måndag 3 november 2014

Gäller som tentamen för:
DT3030 Datateknik C, Kompilatorer och interpretatorer, provkod 0100



Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 42.
För godkänt betyg krävs totalt minst 24 poäng, varav minst 8 poäng på uppgift 1.
Resultat: Meddelas på kursens hemsida eller via e-post senast måndag 24 november 2014.
Återlämning av tentor: Efter att resultatet meddelats kan tentorna hämtas på universitetets centrala tentamensutlämning.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070 - 73 47 013.




LYCKA TILL!

Formelsamling

1. Eliminering av vänsterrekursion

En vänsterrekursiv grammatik kan skrivas om så att den inte är vänsterrekursiv. Antag att en regel (eller, korrektare uttryckt, två produktioner), i grammatiken ser ut så här:
A -> A x | y
A är en icke-terminal, men x och y står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.

Regeln ersätts av följande två regler (eller, korrektare uttryckt, tre produktioner), som beskriver samma språk men som inte är vänsterrekursiva:

A -> y R
R -> x R | empty

2. Vänsterfaktorisering

Antag att grammatiken innehåller denna regel (två produktioner):
A -> x y | x z
A är en icke-terminal, men x, y och z står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.

Skriv om till dessa tre produktioner:

A -> x R
R -> y | z

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?

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?

Program Fel och varningar
#include <math.h>

int main(void) {
    int ena = 1, andra = 2 * ena, tredje = 3andra;
    double x = sqrt(ena)  sqrt(andra);
    double y, z;

    x = x * y;
    printf("Hej, världen! x = %f\n", x);

    return "Ok!";
}



invalid suffix "andra" on integer constant
expected ',' or ';' before 'sqrt'
unused variable 'z'

'y' is used uninitialized in this function
missing declaration of function 'printf'

return makes integer from pointer without a cast

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

b) postfixkod för en stackmaskin

c) treadresskod

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!".
#include <stdlib.h>
#include <stdio.h>

int a = 1, b = 2;

int f(int a) {
    int b = 3;
    printf("Här!\n");
    return a;
}

int g(int c) {
    int b = 4;
    int *d = malloc(sizeof(int));
    *d = c;
    if (c > 5)
        b = b * g(c - 1);
    else
        b = f(c);
    return b;
}

int main(void) {
    int b = 6;
    b = g(7);
    printf("b = %d\n", b);
    return 0;
}

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.

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

Uppgift 6 (4 p)

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

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;
};

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.