Örebro universitet
Institutionen för teknik
Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se)





Tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

måndag 3 november 2008 kl 08:00 - 12:00

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







Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 40.
För godkänt betyg (3 respektive G) krävs 20 poäng.
Resultat: Meddelas på kursens hemsida eller via e-post senast måndag 24 november 2008.
Visning och frågestund: Tisdag 25 november 2008 kl 15:00-15:30 i mitt rum (T2220).
Efter visningen kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-73 47 013.



LYCKA TILL!

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

I en enkel databashanterare kan man skapa tabeller med kolumner, som kan innehålla heltal och strängar. Man kan skapar och ta bort tabellerna med kommandona create table och drop table. Man kan också stoppa in data i tabellerna med kommandot insert into.

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);
Databashanteraren implementerar alltså en ganska liten delmängd av det vanliga databasspråket SQL. Mer om SQL-dialekten: Här är några exempel på SQL-kommandon som databashanteraren inte förstår:
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)

Här är ett C-program. (Radnumren ingår inte i programmet, utan är bara med som referens.)
    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   }
När man försöker kompilera och köra programmet, får man följande fyra felmeddelanden:
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'
En kompilator indelas i flera faser. I vilken fas (eller någonannanstans) har vart och ett av de fyra felen upptäckts?

Uppgift 3: Mellankod (10 p)

Det här är ett programavsnitt i C:
i = 1;
j = 17;
while (i < j) {
    m = (i + j - 1) / 2;
    i = i + j;
    j = i + j;
    if (i > x)
        x = j;
}
Översätt ovanstående programavsnitt till var och en 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, i form av en flödesgraf ("flow graph") med treadresskoden indelad i basic blocks

Uppgift 4: Optimering (5 p)

Visa vilka optimeringar som en kodoptimerare gör på flödesgrafen i uppgiften ovan. Förklara också vad som händer. Tala gärna om vad de olika optimeringarna heter.

Uppgift 5: Några termer (6 p)

Förklara kort vad följande begrepp från kompilatortekniken innebär. Ge gärna exempel.

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