• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara 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. Gjorda antaganden får inte förändra den givna uppgiften.

Uppgift 1: Kontextfri grammatik (5 p)

Exempel på sökfraser:

• bil
  Jag vill hitta information om bilar.
• bil or traktor
  Jag vill hitta information som handlar om bilar eller om traktorer.
• bil and not traktor
  Jag söker efter webbsidor som innehåller ordet bil, men inte innehåller ordet traktor.
• bio and pirater and Örebro or teater and (Gnesta or Ånge)
  Jag vill antingen se en piratfilm i Örebro, eller så vill jag gå på teater i Gnesta eller Ånge.

Uppgift 2: Top-down-parsning (15 p)

S -> a X | a Y
X -> X b | b
Y -> c Y | d

a) Ange tio olika strängar som ingår i det språk som beskrivs av grammatiken ovan.

b) Grammatiken lämpar sig inte för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser). Ange vilka problem det är, vad i grammatiken som orsakar problemen, och vad som händer i parsern.

c) Använd de transformationer som tagits upp i kursen för att omvandla grammatiken till en grammatik som beskriver samma språk, men som enkelt kan implementeras i en prediktiv recursive-descent-parser. Ange de generella transformationsregler som du använder, och visa vad resultatet blir för den här grammatiken.

d) 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 3: Lexikalisk analys (3 p)

a) Ange det uttrycket.

b) Ange en grammatik som inte kan ersättas med ett reguljärt uttryck, och förklara varför det inte går!

Uppgift 4: Mellankodsgenerering (9 p)

while (i < x + y) {
  if (x > 0) {
    y = y - 1;
  }
  else {
    a = b * c + d * e;
    d = e;
    f = h - i - j;
  }
}

a) ett abstrakt syntaxträd

b) postfixnotation

c) treadresskod

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

Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av while-satsen till stackmaskinkod. Antag att översättningsschemat ska implementeras i bottom-up-parsningmiljö med en stack, som i Yacc och Bison. Utgå från din grammatikregel ovan, som dock kanske måste modifieras. Förklara införda attribut och eventuella funktioner och instruktioner som används. Ange alla dina antaganden.

Uppgift 6: Typkontroll (7 p)

Exempel:

variable s : string;
variable i : number;

i = 17;
i + i;		// Resultat: talet 34
i + 3;		// Resultat: talet 20

s = "foo";
s + s;		// Resultat: strängen "foofoo"
s + "hej";	// Resultat: strängen "foohej"

s = 17;		// typfel: s ska innehålla en sträng
s = i + 47;	// typfel: s ska innehålla en sträng
"foo" + 17;	// typfel: sträng + tal ej tillåtet
s + i;		// typfel: sträng + tal ej tillåtet
s + 47;		// typfel: sträng + tal ej tillåtet

P -> Ds Ss
Ds -> Ds D | empty
Ss -> Ss S | empty
D -> "variable" id ":" T ";"
T -> "string" | "number"
S -> E ";" | id "=" E ";"
E -> id | string-constant | number-constant | E "+" E

Uppgift 7: Aktiveringsposter (4 p)

• 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. Gjorda antaganden får inte förändra den givna uppgiften.

Uppgift 1: Faser (6 p)

Uppgift 2: Kontextfri grammatik (10 p)

Exempel på uttryck som grammatiken ska klara:

• [ 1, 2, 7 ]
  Mängden som innehåller elementen 1, 2 och 7.
• x
  Vad det nu är för mängd som råkar finnas i variabeln x.
• [ 1, 2, 7 ] union [ 3, 7, 9 ]
  Unionen av de två mängderna [ 1, 2, 7 ] och [ 3, 7, 9 ]. Resultatet blir [ 1, 2, 3, 7, 9 ].
• ( [ 1, 2 ] union [ 2, 5 ] ) intersection [ 2, 7 ]
  Snittet mellan å ena sidan unionen av de två mängderna [ 1, 2 ] och [ 2, 5 ], och å andra sidan mängden [ 2, 7 ], Resultatet blir [ 2 ].
• x union y - z intersection [ 622, 117 ] intersection t

• x y
• [ 1, 2
• [ 1 2 ]
• [ 1, 2, ]
• [ 1, 2 ] union intersection x
• [ 1, 2, [ 3 ] ]

Följande terminaler kan användas i grammatikreglerna: integer, comma, left_bracket, right_bracket, identifier, intersection, union, minus, left_parenthesis, right_parenthesis.

Uppgift 3: Top-down-parsning (17 p)

S -> a X | a Y
X -> X b | c Z
Y -> a | d
Z -> e Z | f

a) Rita upp parse-trädet för strängen aceeef.

b) Ange tio andra strängar som ingår i det språk som beskrivs av grammatiken ovan.

c) Grammatiken lämpar sig inte för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser). Ange vilka problem det är, vad i grammatiken som orsakar problemen, och vad som händer i parsern.

d) Använd de transformationer som tagits upp i kursen för att omvandla grammatiken till en grammatik som beskriver samma språk, men som enkelt kan implementeras i en prediktiv recursive-descent-parser. Ange de generella transformationsregler som du använder, och visa vad resultatet blir för den här grammatiken.

e) 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 4: Tvetydighet (5 p)

b) När är tvetydighet ett problem i en grammatik? När är det det inte? Visa med exempel!

Uppgift 5: Mellankodsgenerering (9 p)

x = 0;
while (x < 10) {
  y = y + 2;
  while (y < 3 + 2 * x) {
    z = z + x + y;
    y = y + 1;
  }
  x = x + 1;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

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

Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av if-satsen till stackmaskinkod. Antag att översättningsschemat ska implementeras i bottom-up-parsningmiljö med en stack, som i Yacc och Bison. Utgå från din grammatikregel ovan, som dock kanske måste modifieras. Förklara införda attribut och eventuella funktioner och instruktioner som används. Ange alla dina antaganden.

Uppgift 7: Optimering (8 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.

c) Ofta vill man felsöka program med en symbolisk debugger, som till exempel kan stega fram programmet en rad i taget och visa innehållet i variabler. Vilka problem kan det innebära att felsöka ett optimerat program i en symbolisk debugger? Förklara hur de problemen uppstår.

Uppgift 8: Skräpsamling (5 p)

Uppgift 9: Lexikalisk analys (3 p)

• 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: Faser (7 p)

a) Ange vilka det är, och förklara kort vad varje fas gör. Vad har varje fas för in- och utdata?

b) En viktig del av en kompilator är felhantering. Kompilatorn ska upptäcka, och rapportera, de fel som smugit sig in i källprogrammet. Vilka typer av fel kan upptäckas, och i vilken fas upptäcks varje typ av fel?

Uppgift 2: Kontextfri grammatik (10 p)

Exempel på uttryck som grammatiken ska klara:

• 2 + 7.5 * 3
  Resultat: 24.5
• (2 + 7.5) * 3
  Resultat: 28.5
• 2 * sin(3.14 / 2)
  Resultat: 2.0
• (1 + 2) * cos(1.5 - 3 * 0.5)
  Resultat: 3
• sin(0.9) * sin(0.9) + cos(0.9) * cos(0.9)
  Resultat: 1

• 7.3 4.2
• * 2.0
• sin(1)cos(0)

Följande terminaler kan användas i grammatikreglerna: +, -, *, /, (, ), sin, cos och number. En terminal av typen number är ett reellt tal.

Uppgift 3: Top-down-parsning (16 p)

S -> a X
X -> Y | Z
Y -> b Y b | a
Z -> Z c | c

a) Rita upp parse-trädet för strängen acc.

b) Rita upp parse-trädet för strängen abbbabbb.

c) Det finns minst ett problem med grammatiken som gör att den inte lämpar sig för implementation av en prediktiv recursive-descent-parser (engelska: predictive recursive-descent parser). Ange vilket eller vilka problem det är, vad i grammatiken som orsakar problemen, och vad som händer i parsern.

d) Använd de transformationer som tagits upp i kursen för att omvandla grammatiken till en grammatik som beskriver samma språk, men som enkelt kan implementeras i en prediktiv recursive-descent-parser. Ange de generella transformationsregler som du använder, och visa vad resultatet blir för den här grammatiken.

e) 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 4: Lexikalisk analys (4 p)

Om du svarar ja: Ange det reguljära uttrycket.
Om nej: Förklara varför det inte går.

Uppgift 5: Tvetydighet (5 p)

b) Ge exempel på en tvetydig grammatik.

c) När är tvetydighet ett problem i en grammatik? När är det det inte? Visa med exempel!

Uppgift 6: Mellankodsgenerering (10 p)

if (x - 3 > y + z) {
  x = x - y - 1;
  y = 3 - 2 * z;
}
else {
  x = z;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 7: Syntaxstyrd översättning (6 p)

Statement -> for identifier = Expression to Expression do Statement

Statement och Expression är icke-terminaler. for, identifier, =, to och do är terminaler.

Exempel: Satsen

for i = 2 to 5 do Writeln(i)

ger utskriften

2
3
4
5

Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av for-satsen till treadresskod. Antag att översättningsschemat ska implementeras i bottom-up-parsningmiljö med en stack, som i Yacc och Bison. Utgå från grammatikregeln. Förklara införda attribut och eventuella funktioner och instruktioner som används. Ange alla dina antaganden.

Uppgift 8: Skräpsamling (5 p)

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

Uppgift 9: Några termer (7 p)

• front end (engelska: front end)
• pass (engelska: pass)
• parser-generator (engelska: parser generator)
• symboltabell (engelska: symbol table)
• strukturekvivalens (engelska: structural equivalence), som är motsatsen till namnekvivalens (engelska: name equivalence)
• anropskonventioner (engelska: call sequence)
• literal (engelska: literal)

• 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: Kontextfri grammatik (6 p)

Skriv en grammatik för kommandospråket. Grammatiken ska hantera ett enda kommando, med ett eller flera mål. Det är inget krav att grammatiken ska lämpa sig för någon viss typ av parsning, men den ska vara entydig.

Exempel på kommandon som grammatiken ska klara:

• move 1, 17
• move 9, 19; 11, 19; 12, 20

• move
• move 9
• move 9, 19, 11

Uppgift 2: Parse-träd (3 p)

• move 1, 17
• move 9, 19; 11, 19

Uppgift 3: Top-down-parsning (13 p)

Om den grammatik du gjorde i uppgift 1 inte lämpar sig för implementation av en prediktiv recursive-descent-parser, så gör först om den till en grammatik som beskriver samma språk, men som enkelt kan implementeras i en prediktiv recursive-descent-parser. Beskriv vad du gör, och varför.

Uppgift 4: Lexikalisk analys (3 p)

Om du svarar ja: Ange det reguljära uttrycket.
Om nej: Förklara varför det inte går.

Uppgift 5: Mellankodsgenerering (10 p)

i = 1;
j = 0;
while (i > j) {
  if (i < 10)
    i = i + 1;
  else
    j = 10 - i - j;
}

a) ett abstrakt syntaxträd (rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod

Uppgift 6: Semantik (3 p)

Uppgift 7: Kontextfri grammatik, igen (6 p)

switch (i - j - k) {
  case 1: i = i + 2; break;
  case 2: i = i + 3; break;
  case 3: i = 19; break;
  case k + 7: i = 19; break;
  default: i = 19; break;
}

Du kan använda dig av den här regeln för en case-gren:

Branch -> case Expression : Statement break ;

Uppgift 8: Exekvering av syntaxträd (10 p)

Använd ett språk som åtminstone liknar C, Java eller Pascal, och skriv funktionen execute_switch, som exekverar switch-satsen. Den ska ta en pekare till en trädnod som argument.

Det finns redan en funktion, execute, som tar en pekare till en trädnod som argument. Den kan användas för att beräkna uttryck och utföra satser (utom, tyvärr, just switch-satsen).

Trädnoderna är av typen TreeNode. Du kan anta att trädnoderna har ett typfält som heter type, och som bland annat kan ha värdena SWITCH, CASE och DEFAULT. Noderna har pekare till de underliggande subträden i en array som heter args. Om pekaren p pekar på en trädnod, kan man nå det vänstra subträdet under den noden med uttrycket p->args[0].

• 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: Faser (6 p)

a) den lexikaliska analysen ("scannern")

b) den syntaktiska analysen ("parsern")

c) den semantiska analysen

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

S -> X Y Z
X -> a | b
Y -> Z | c
Z -> d

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

b) (3p) Vilka strängar, förutom bdd, 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!

f) (2p) Skulle man kunna beskriva samma språk med ett annat reguljärt uttryck?
Om ja: Ange ett sådant alternativt reguljärt uttryck.
Om nej: Förklara varför man inte kan det.

Uppgift 3: Grammatiktransformationer (8 p)

b) (2p) Visa med ett exempel hur man kan eliminera, dvs ta bort, vänsterrekursion från en grammatik.

c) (1p) Hur påverkas det språk som grammatiken beskriver av att man tar bort vänsterrekursionen från den grammatiken?

d) (2p) I vilka sammanhang behöver man ta bort vänsterrekursion? Varför behöver man göra det?

e) (2p) Man kan ha semantiska aktioner instoppade i grammatiken. Förklara, med exempel, hur man hanterar dessa vid eliminering av vänsterrekursion.

Uppgift 4: Parsning (10 p)

Det reguljära uttrycket a*b[cd] beskriver ett språk som består av strängar som:

• Börjar med noll, ett eller flera a
• Sen kommer ett b
• Sen kommer antingen ett c eller ett d

b) (7p) 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: Mellankodsgenerering (10 p)

  if (x < 7 + y) {
    x = 9 - x - y;
  }
  else {
    while (x > 10) {
      z = x + 1;
      x = 2 * x * (y - 1);
    }
  }

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

b) (3p) postfixkod för en stackmaskin

c) (4p) treadresskod

Uppgift 6: Aktiveringsposter (4 p)

Uppgift 7: Typkontroll (10 p)

Ett exempel, där vi först deklarerar de tre variablerna f, i och s:

f : flyttal;
i : heltal;
s : sträng;

i = 17;
i + i;		// Resultat: heltalet 34
i + 3;		// Resultat: heltalet 20
2 + 5;		// Resultat: heltalet 7
14;		// Resultat: heltalet 14

f = 3.14;
f + f;		// Resultat: flyttalet 6.28
2.1 + f;	// Resultat: flyttalet 5.24

f = 17;		// typfel: f ska innehålla ett flyttal
f = "hej";	// typfel: f ska innehålla ett flyttal
3.5 + 12;	// typfel: flyttal + heltal ej tillåtet
i + 0.5;	// typfel: heltal + flyttal ej tillåtet
"hej" + "hopp"  // typfel: sträng + sträng ej tillåtet

S -> Deklarationslista Satslista
Deklarationslista -> Deklarationslista Deklaration | empty
Satslista -> Satslista Sats | empty
Deklaration -> id ":" Typ ";"
Typ -> "flyttal" | "heltal" | "sträng"
Sats -> Uttryck ";" | id "=" Uttryck ";"
Uttryck -> Konstant | id | Uttryck "+" Uttryck
Konstant -> heltalskonstant | flytalskonstant | strängkonstant

• 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: Faser (3 p)

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

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)

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;

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)

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

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 6: Skräpsamling (6 p)

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

c) Hur kan man lösa det problemet?

Med vissa rättelser.

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

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?

• 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?

• 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: Grammatiker (5p)

S -> a T | a U
T -> b c
U -> c d

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

I ett annat språk ska man kunna skriva godtyckligt många förekomster av strängen a b c. Med "godtyckligt många" menas noll, en eller flera. Exempel på strängar som ska accepteras:

• den tomma strängen
• abc
• abcabcabcabc

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.

(d) (1p)

Skriv ett reguljärt uttryck som beskriver språket i deluppgift a.

Uppgift 2: Kompilatorer (5 p)

Uppgift 3: Parsning (5 p)

Gör eventuella transformationer av grammatiken i deluppgift 1 a 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 4: Syntaxstyrd översättning (5 p)

Skriv en grammatikregel för while-satsen i C.

b)

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

Uppgift 5: Mellankod (5 p)

if (a - b - c > d + e + f) {
  g = 100;
  h = 200;
}
else {
  while (i < 20) {
    i = i + 1;
  }
  j = 300;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 6: Run-time-omgivningar (5 p)

a) Antag att vi använder skräpsamlingsmetoden "mark and sweep". Vilka av objekten kommer att markeras i markeringsfasen?

b) Vilka av objekten kommer att tas bort i sopfasen?

c) Antag att vi i stället använder referensräkning. Kan situationen som visas på bilden uppstå? (Vi antar att vi inte är mitt i en uppstädning.)

d) Vi använder fortfarande referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.

e) Vi använder fortfarande referensräkning. Vi sätter de båda pekarna som pekar ut ur rotmängden (dvs i dataobjekt 2 och 3) till NULL. Beskriv vad som händer.

• 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: Grammatiker (5p)

S -> a T | b U
T -> b c U e
U -> c d

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

I ett annat språk ska man kunna skriva godtyckligt många förekomster av strängen a a, följt av strängen bc. Med "godtyckligt många" menas noll, en eller flera. Exempel på strängar som ska accepteras:

• b c
• a a b c
• a a a a a a a a b c

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.

(d) (1p)

Skriv ett reguljärt uttryck som beskriver språket i deluppgift a.

Uppgift 2: Kompilatorer (5 p)

a) Vilka andra faser finns det, och i vilken ordning kommer de?

b) I en nyare upplaga av "drakboken" har man delat in optimeringsfasen i två olika faser: maskinoberoende optimering och maskinberoende optimering. Varför har man gjort den uppdelningen?

Uppgift 3: Parsning (5 p)

Gör eventuella transformationer av grammatiken i deluppgift 1 a 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 4: Syntaxstyrd översättning (5 p)

Skriv en grammatikregel för if-satsen i C.

b)

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

Uppgift 5: Mellankod (5 p)

while (a + (b + c) < a + b + c) {
  if (i > j) {
    a = 200;
  }
  else {
    c = b * c + a * j;
    j = j + 1;
  }
  a = j + 1;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 6: Run-time-omgivningar (5 p)

a) Antag att vi använder skräpsamlingsmetoden "mark and sweep". Vilka av objekten kommer att markeras i markeringsfasen?

b) Vilka av objekten kommer att tas bort i sopfasen?

c) Antag att vi i stället använder referensräkning. Kan situationen som visas på bilden uppstå? (Vi antar att vi inte är mitt i en uppstädning.) Motivera svaret.

d) Vi använder fortfarande referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.

e) Nu använder vi mark and sweep. Vi sätter de tre pekarna som pekar ut ur rotmängden från dataobjekt 1 och 2 till NULL. Beskriv vad som händer vid nästa skräpsamling.