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







Tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet m fl

lördag 30 oktober 2010

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






→ This exam is also available in an English version.

Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 32.
För godkänt betyg (3 respektive G) krävs 16 poäng.
Resultat: Meddelas på kursens hemsida eller via e-post senast lördag 20 november 2010.
Återlämning av tentor: Efter att resultatet meddelats kan tentorna hämtas på universitetets centrala tentamensutlämning.
Examinator: Thomas Padron-McCarthy




LYCKA TILL!

Uppgift 1: Faser (3 p)

När vi kompilerar följande försök till C-program, ger kompilatorn de kursiverade fel- och varningsmeddelandena:
#include <stdio.h>

int main(void) {
    int a;

    printf("Hej!\n );         error: missing terminating " character
    printf("Ange ett tal: ");
    scanf("%d", &a ;          error: expected ')' before ';' token
    printf("Talet var: %d\n", a);

    return "Kalle";           warning: return makes integer from pointer without a cast
}
En kompilators arbete brukar delas in i flera faser. I vilka faser upptäcks de olika felen och varningarna?

Uppgift 2: Scanning och reguljära uttryck (5 p)

a) (2p) Skriv reguljära uttryck ("regexpar") för följande:

b) (2p) Skriv ett reguljärt uttryck för svenska personnummer (som till exempel 631211-1658). Uttrycket ska matcha alla giltiga personnummer. Det är besvärligt att skriva ett reguljärt uttryck som inte också matchar vissa otillåtna personnummer, så det gör inget om ditt svar gör det. Men förklara minst en kontroll som inte görs av ditt reguljära uttryck.

c) (1p) Vad är det för skillnad på en token och ett lexem?

Uppgift 3: Grammatiker (10 p)

Här är tre saker som kan vara problematiska i en grammatik:

a) vänsterrekursion
b) FIRST()-konflikter
c) tvetydighet

Ge för var och en av dessa saker exempel på en grammatik som uppvisar problemet. Förklara också för var och en av dessa grammatiker hur problemet visar sig i praktiken. (Dvs: vad är det som inte fungerar, på grund av det problemet?) Visa också hur man löser problemet.

Uppgift 4: Mellankod (5 p)

x = 1;
y = 2;
z = 3;
while (y == 2) {
    if (z > 4) {
        y = y - 1 - 1;
    }
    else {
        z = z + y * z + z;
        t = t + 2;
    }
}
Ö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!)

b) postfixkod för en stackmaskin

c) treadresskod

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

Uppgift 5: Några termer (9 p)

Förklara kort vad följande begrepp från kompilatortekniken innebär:

a) målspråk
b) målprogram
c) front end
d) Yacc
e) symboltabell
f) shift-reduce-konflikt
g) deterministisk ändlig tillståndsmaskin
h) reserverat ord
i) anropskonventioner (på engelska: call sequence)