Ö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 9 januari 2006 kl 08:00 - 13:00 i L0003








Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 58.
För betyget 3 krävs 29 poäng.
För betyget 4 krävs 40 poäng.
För betyget 5 krävs 50 poäng.
Resultat: Meddelas på kursens hemsida senast måndag 30 januari 2006.
Visning och frågestund: Onsdag 1 februari 2006 kl 12:00-12:30 i mitt rum (T2220)
Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-7347013.



LYCKA TILL!

Uppgift 1: Faser (3 p)

När följande C-program kompileras med en viss kompilator, får man de fem fel- och varningsmeddelanden som står med kursiv stil i högerspalten.

#include <stdio.h>

int main(void) {
  int i = 17;
  float f = 3.14;
  char c = 'x';
  char* s = "foo;         (1) missing terminating " character

  s = f;                  (2) error: incompatible types in assignment
  printf("f = %f\n", i);  (3) warning: double format, different type arg (arg 2)

  c s;                    (4) error: syntax error before "s"
  return;                 (5) warning: `return' with no value, in function returning non-void
}

Ange för vart och ett av de fem meddelandena i vilken fas i kompilatorn det felet upptäcktes!

Uppgift 2: Grammatiker och parse-träd (11 p)

I följande grammatik är S, A och B icketerminaler. x, y, z och t är terminaler. S är startsymbol.
S -> A | B | x
A -> x | y
B -> B z | t

a) (2p) Rita upp parse-trädet för strängen tzz.

b) (4p) Vilka strängar, förutom tzz, kan genereras av denna grammatik?

c) (1p) Vad innebär det att en grammatik är tvetydig (engelska: "ambiguous")?

d) (2p) Är grammatiken ovan tvetydig? Motivera svaret!

e) (2p) Just den här grammatiken definierar ett språk som också kan beskrivas med ett reguljärt uttryck. Skriv ett reguljärt uttryck som beskriver språket!

Uppgift 3: Språk, grammatiker och parsning (19 p)

Det finns ett spel som går ut på att man ger kommandon till en robot, som rör sig på en spelplan. Man kan beordra roboten att springa till en punkt på spelplanen, eller att hoppa till en punkt. Man kan också beordra den att antingen springa eller hoppa tillbaka till den föregående punkt där den befann sig. Dessutom finns ett startkommando för att starta roboten, och ett stopp-kommando för att stänga av den. Punkter anges med en x- och en y-koordinat, i form av heltal, och roboten startar i origo, dvs punkten med x=0 och y=0.

Som exempel kan följande sekvens av kommandon ge upphov till rörelserna i figuren nedan.

start;
spring till 5, 3;
spring till 9, 3;
hoppa tillbaka;
spring till 4, 6;
hoppa till 1, 6;
spring tillbaka;
spring till 10, 8;
stopp;

Ett diagram över rörelserna

a) (3p) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för kommandospråket.

b) (5p) Skriv grammatiken. Använd terminalerna från a-uppgiften. Startsymbolen ska heta S.

c) (3p) 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 3 poäng på den här deluppgiften i alla fall.)

d) (8p) 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 4: Run-time-omgivning, aktiveringsposter (7 p)

Betrakta följande C-program:

#include <stdlib.h>

int a;
int b;

void f(int c, int d) {
  int e;
  int* p = malloc(sizeof(int));
  e = 13;
  *p = 14;
  // Här!
}

void g(int h) {
  int i;
  int* p = malloc(sizeof(int));
  i = 15;
  *p = 16;
  f(h, 17);
}

int main(void) {
  int k;
  k = 18;
  a = 19;
  b = 20;
  g(k);
  return 0;
}

Funktionen main anropar funktionen g, som i sin tur anropar funktionen f. När programexekveringen i funktionen f kommer fram till raden med kommentaren "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.

I minnet kommer det då att finnas ett antal lagringsutrymmen för heltal, som innehåller talen 13-20. Rita upp en skiss över dessa variabler, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".

Uppgift 5: Mellankodsgenerering (12 p)

if (a + b > c) {
  d = 14;
  while (d < e - f - g) {
    d = d - 1;
  }
}
else {
  a = x + 2 * y - z + t;
  b = x + 3;
  c = x;
  d = 14;
}
Översätt ovanstående programavsnitt till

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 6: Skräpsamling (6 p)

a) Förklara hur referensräkning (engelska: reference counting) fungerar. Visa med exempel.

b) Referensräkning har problem med en viss sorts datastrukturer. Förklara med ett exempel.

c) Hur kan man lösa det problemet?