• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Uppgift 1: Språk, grammatiker och parsning (15 p)

Här är några exempel på SQL-kommandon som den här databashanteraren förstår:

create table Blaha
(foo integer unique,
fum string primary key,
blaj string unique);

drop table Blaha;

create table Apa
(nummer integer,
namn string,
svampkod integer);

insert into Apa values (1, 'Hej', 17);

• Det finns inget kommando (som select) för att söka i databasen.
• En tabell kan ha en eller flera kolumner, som kan vara av typen integer eller string.
• En kolumn kan anges som primärnyckel (primary key) eller som unik (unique), men inte båda.

create table Apa
(nummer integer default 10 not null,
namn char(10),
svampkod integer references Svamp(id));

insert into Apa (nummer, namn) values (17, 'Hej');

select * from Apa;

a) (2p) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för SQL-dialekten.

b) (5p) Skriv grammatiken. Använd terminalerna från a-uppgiften. Ange vad som är startsymbol. Startsymbolen ska beskriva ett SQL-kommando, enligt ovan.

c) (2p) Om grammatiken från b-uppgiften inte lämpar sig för implementation i form av en prediktiv recursive-descent-parser, så transformera den så den passar. (Om den redan är lämplig, behöver du inte göra om den, utan du får 2 poäng på den här deluppgiften i alla fall.)

d) (6p) Skriv den prediktiva recursive-descent-parsern i ett språk som åtminstone liknar C, Java eller Pascal. 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 redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 2: Faser (4 p)

    1   #include <math.h>
    2
    3   int main(void) {
    4       char* s = "hej!;
    5       int i = 18;
    6       double = 7.3;
    7       double e = arcsin(1.13);
    8       e = s;
    9       return 0;
   10   }

faser.c:4: error: missing terminating " character
faser.c:6: error: expected identifier or '(' before '=' token
faser.c:8: error: incompatible types in assignment
faser.c:7: undefined reference to `arcsin'

Uppgift 3: Mellankod (10 p)

i = 1;
j = 17;
while (i < j) {
    m = (i + j - 1) / 2;
    i = i + j;
    j = i + j;
    if (i > x)
        x = j;
}

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

b) postfixkod för en stackmaskin

c) treadresskod, i form av en flödesgraf ("flow graph") med treadresskoden indelad i basic blocks

Uppgift 4: Optimering (5 p)

Uppgift 5: Några termer (6 p)

Tala också om i vilken av kompilatorns faser (eller någonannanstans) som man använder sig av dessa saker.

1. Nyckelhålsoptimering ("peep-hole optimization")
2. Typsystem
3. Strukturekvivalens ("structural equivalence")
4. Aktiveringspost ("activation record")
5. Döda data ("dead data")
6. Onåbara data ("unreachable data")