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








Ordinarie tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

måndag 16 oktober 2006 kl 08:00 - 13:00 i L001








Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 40.
För betyget 3 krävs 20 poäng.
För betyget 4 krävs 27 poäng.
För betyget 5 krävs 34 poäng.
Resultat: Meddelas på kursens hemsida senast måndag 6 november 2006.
Visning och frågestund: Måndag 13 november 2006 kl 12:00-12:30 i T2220.
Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-7347013.



LYCKA TILL!

Observera: Det finns nio uppgifter på tentan. Välj ut och besvara (högst) åtta av dessa. (Skulle du svara på alla nio, räknas den med högst poäng bort.)

Uppgift 1: Grammatiker (5p)

Ett språk innehåller terminalerna god, morgon, middag och kväll. Grammatiken för språket innehåller icke-terminalerna hälsning och tidsspecifikation, och följande produktioner:
hälsning -> god tidsspecifikation
tidsspecifikation -> morgon
tidsspecifikation -> middag
tidsspecifikation -> kväll
tidsspecifikation -> god
Startsymbolen är hälsning.

(a) (2p)

Ange vilket språk grammatiken beskriver, genom att räkna upp alla strängar (dvs sekvenser av terminaler) som kan uttryckas i språket.

Visa hur du fick fram svaret.

(b) (2p)

I ett annat språk ska man kunna skriva godtyckligt många hälsningar (som beskrivs av hälsning i grammatiken för det förra språket) efter varandra, åtskilda med semikolon. Med "godtyckligt många" menas noll, en eller flera.

Skriv en grammatik för detta språk. Glöm inte att ange vad som är startsymbol. Grammatiken ska vara entydig.

(c) (1p)

I deluppgiften ovan stod det att grammatiken skulle vara entydig. Det är motsatsen till att grammatiken är tvetydig. Förklara med exempel vad som menas med att en grammatik är entydig respektive tvetydig.

Uppgift 2: Kompilatorer (5 p)

En kompilator brukar byggas upp genom att delas in i sex faser: Indata till den första fasen består av källprogrammet i textform (alltså en sekvens av tecken), medan utdata från den sista fasen utgörs av ett målprogram uttryckt i maskinspråk eller assemblerspråk.

Men hur ser de data som skickas mellan faserna ut? Beskriv för var och en av de fem kopplingarna mellan faserna vilka data som överförs.

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

En förenklad version av printf tar formatsträngar som kan innehålla vanlig text, %d-specificerare (som anger heltal), %f-specificerare (som anger flyttal), och %s-specificerare (som anger strängar).

%d-specificerare kan innehålla en fältbredd, som skrivs mellan procenttecknet och d:et. En negativ fältbredd betyder att talet ska vänsterjusteras i fältet.

%f-specificerare kan innehålla en fältbredd på samma sätt som för heltal, men också en punkt följd av en precision (antal decimaler som ska skrivas ut).

%s-specificerare kan innehålla en fältbredd på samma sätt som för heltal, men också en punkt följd av ett största antal tecken som får skrivas ut.

Här är några exempel på tillåtna formatsträngar:

Här är några exempel på formatsträngar som inte är tillåtna: Skriv ett reguljärt uttryck som beskriver hur en formatsträng får se ut. Använd gärna utvidgade reguljära uttryck av samma typ som finns i Lex. Bygg gärna upp uttrycket steg för steg, dvs med namn som står för ett reguljärt uttryck och som sen används i nästa uttryck.

Uppgift 4: Parsning (5 p)

I följande grammatik är S, T, U och V icke-terminaler. a, b, c och d är terminaler. S är startsymbol.
S -> a T | b T U
T -> T U | U
U -> c d | c d d

a)

Gör eventuella transformationer av grammatiken som krävs för att den ska lämpa sig för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser).

b)

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 finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 5: Syntaxstyrd översättning (5 p)

Här är en grammatikregel för for-satsen i C:

sats -> for ( uttryck1 ; uttryck2 ; uttryck3 ) sats1

Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av for-satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod.

Tips: Dessa två loopar kan betraktas som ekvivalenta:

Kom ihåg att dessa

for (i = 0; i < 10; ++i) {
  whatever();
}

i = 0;
while (i < 10) {
  whatever();
  ++i;
}

Uppgift 6: Mellankod (5 p)

r = 0;
s = 100;
while (r < s) {
  if (s > 0)
    s = s - (s - r) / 2;
  else
    s = 0;
}
Ö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 7: Optimering (5 p)

a) Vad är ett basic block?

b) Flera olika typer av optimeringar kan göras på koden inuti ett enskilt basic block. Vilka? Beskriv dem, och använd treadresskod för att ge exempel på hur de fungerar.

Uppgift 8: Aktiveringsposter (5 p)

Betrakta följande C-program:

#include <stdlib.h>

int x;

void g(int x, int y) {
  int* p;
  p = malloc(sizeof(int));
  *p = x;
  // Här!
}

void f(int y, int z) {
  int t;
  t = x;
  x = y;
  g(x, x);
}

int main(void) {
  int y;
  x = 1;
  y = 2;
  f(3, y);
}

Funktionen main anropar funktionen f, som i sin tur anropar funktionen g. När programexekveringen i funktionen g 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 några olika värden. 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 9: Run-time-omgivningar (5 p)

Förklara hur skräpsamlingsmetoden mark and sweep fungerar. Visa med exempel.

Vilka fördelar och nackdelar har den, jämfört med referensräkning?

Observera: Det finns nio uppgifter på tentan. Välj ut och besvara (högst) åtta av dessa. (Skulle du svara på alla nio, räknas den med högst poäng bort.)