• Det finns nio uppgifter på tentan. Välj ut och besvara (högst) åtta av dessa.
• 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.
• Lös bara en uppgift per blad. 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.

Uppgift 1: Grammatiker (5p)

hälsning -> god tidsspecifikation
tidsspecifikation -> morgon
tidsspecifikation -> middag
tidsspecifikation -> kväll
tidsspecifikation -> god

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

• lexikalisk analys ("scanner")
• syntaktisk analys ("parser")
• semantisk analys
• mellankodsgenerering
• optimering
• kodgenerering

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)

%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:

• Hej!
• Hej, %s!
• Hej, %10s!
• Hej, %-10s!
• Hej, %-10.7s!
• Hej, %.7s!
• Hej, %s, du är %d år gammal och har %10.2f kronor.

• Hej, %!
• Hej, %10.-7s!
• Hej, %-.7s!
• Antal: %5.2d!

Uppgift 4: Parsning (5 p)

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)

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;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 7: Optimering (5 p)

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)

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

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