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

• Det finns sju uppgifter på tentan, men alla ska inte lösas. Svara på uppgift 1 och (högst) fem av de övriga sex uppgifterna.
• 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: Språk, grammatiker och parsning (15 p)

Fig. 1. Wumpus.

I spelet Hunt the Wumpus går man runt mellan olika rum i en grotta och jagar ett farligt monster. I den variant som beskrivs här kan man ge kommandon för att gå mellan olika rum (kommandot gå), för att skjuta på wumpusen (kommandot skjut), för att ge upp (kommandot ge upp), och för att börja om (kommandot börja om). Till skjut-kommandot anger man en lista med rum, som man skjuter mot. Man kan ge flera kommandon på en gång genom att skriva semikolon mellan dem.

Här är några exempel på kommandorader som man kan ge:

• gå 2
• skjut 2
• skjut 2,3,4
• gå 2; skjut 3,4; gå 3; skjut 4,5,6
• ge upp
• börja om

Några felaktiga kommandorader:

• gå
• gå 2,3
• gå 2 skjut 3
• gå 2, skjut 3

a) (2p) 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 beskriva en kommandorad, som alltså kan innehålla flera kommandon.

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

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

b) (2p) Vad är det för skillnad på ett lexem och ett lexikaliskt värde, och vad har dessa med scanning att göra?

Uppgift 4: Run-time-omgivning, aktiveringsposter (5 p)

#include <stdlib.h>
#include <stdio.h>

int x = 1;
int y = 2;

void f(int a) {
    int b;
    b = x;
    a = 3;
    // Här!
}

void g(int a, int b) {
    int c;
    c = a;
    x = 4;
    int* p = malloc(sizeof(int));
    *p = b;
    f(x);
}

int main(void) {
    int x;
    x = 5;
    y = 6;
    g(7, x);
    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 olika heltalsvä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 5: Mellankod (5 p)

x = 1;
y = 2;
while (x > y) {
    if (x < a) {
        x = x − a − 2;
        y = y + a * 3;
    }
    else
        x = x − 1;
    y = y + 1;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

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

sats -> if ( uttryck ) then sats1 else sats2 endif

Skapa en syntaxstyrd definition, med produktioner och semantiska regler, 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.

Uppgift 7: Optimering (5 p)

b) Vad är ett basic block? Visa med exempel.

c) 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.

• 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: Språk, grammatiker och parsning (12 p)

Fig. 1. Wumpus.

Fig. 2. Wumpusens son.

I spelet Son of Wumpus går man runt mellan olika rum i en grotta och jagar ett litet och ganska ofarligt monster. Eftersom monstret är så litet och ofarligt, behöver man inte se sig för så noga i grottan, utan man anger i förväg vilka rum man ska besöka, och i vilka rum man vill skjuta på monstret. (Man hoppas alltså att monstret råkar vara i något av de rummen.) Det man gör är att man skriver ett litet program, som börjar med begin och slutat med end, och som räknar upp vilka rum man ska besöka och var man vill skjuta. Ett exempel:

• begin 2 3 4 5 skjut 4 3 end

Här är några andra exempel på program som man kan ange:

• begin 2 3 4 end
• begin skjut skjut skjut end
• begin 8 9 10 11 12 skjut 13 skjut 14 skjut end
• begin end

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

b) (4p) Skriv grammatiken. Använd terminalerna från a-uppgiften. Ange vad som är startsymbol. Startsymbolen ska beskriva ett program, 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) (5p) 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 (6 p)

• begin 8 9 12 skjut 13 skjut 14 skjut end
• begin 8 9 10 11 12 skjut 19 skjut 20 skjut end

b) (2p) Man kan dela upp den kodoptimering som kompilatorn gör i två olika faser: maskinoberoende respektive maskinberoende optimering. Ge ett exempel på en optimering som bäst görs i den maskinoberoende optimeringsfasen, och förklara varför den skulle vara svårare att göra i den andra, maskinberoende optimeringsfasen.

c) (2p) Ge ett exempel på en optimering som bäst görs i den maskinberoende optimeringsfasen, och förklara varför den skulle vara svårare att göra i den andra, maskinoberoende optimeringsfasen.

Uppgift 3: Mellankod (5 p)

if (x > y)
    x = y;
else
    y = x;
while (x > y − z − t) {
    x = x * y - z;
    y = x - y - z;
    z = x - y * z;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

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

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

Exempel på ett program i språket:

int i;
float f;

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

f = 7.0;
f + f;		// Resultat: flyttalet 14.0
f + 3.0;	// Resultat: flyttalet 10.0

f = 17;		// typfel: f ska innehålla ett flyttal
f = i + 47;	// typfel: f ska innehålla ett flyttal
3.0 + 17;	// typfel: flyttal + heltal ej tillåtet
f + i;		// typfel: flyttal + heltal ej tillåtet
f + 47;		// typfel: flyttal + heltal ej tillåtet

program -> deklarationer satser
deklarationer -> deklarationer deklaration | empty
satser -> satser sats | empty
deklaration -> typ id ";"
typ -> "int" | "float"
sats -> uttryck ";" | id "=" uttryck ";"
uttryck -> id | heltalskonstant | flyttalskonstant | uttryck "+" uttryck

Uppgift 6: Några termer (10 p)

1. call by value
2. DAG
3. heap
4. konservativ skräpsamling
5. parseträd (ibland kallad "konkret syntaxträd")
6. registerallokering
7. reguljärt uttryck
8. syntaxträd (ibland kallad "abstrakt syntaxträd")
9. tvetydig grammatik
10. Yacc

• 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: Språk, grammatiker och parsning (15 p)

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

• Det finns inget kommando (som select) för att söka i databasen.
• En tabell kan ha en eller flera kolumner, som kan vara av typen integer eller string.
• En kolumn kan anges som primärnyckel (primary key) eller som unik (unique), men inte båda.

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)

    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   }

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'

Uppgift 3: Mellankod (10 p)

i = 1;
j = 17;
while (i < j) {
    m = (i + j - 1) / 2;
    i = i + j;
    j = i + j;
    if (i > x)
        x = j;
}

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)

Uppgift 5: Några termer (6 p)

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

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

#include <stdlib.h>
#include <stdio.h>

int a = 1;
int b = 2;
int c = 3;

void smurf(int x, int y);
void drutt(int x, int y, int z);

void smurf(int x, int y) {
    int c;
    c = a;
    x = 4;
    // Här!
    drutt(x, y - 5, 6);
}

void drutt(int x, int y, int z) {
    int c;
    int* p = malloc(sizeof(int));
    *p = 7;
    b = 8;
    c = 9;
    x = 10;
    y = 11;
    z = 12;
    smurf(a, x);
}

int main(void) {
    int b;
    a = 13;
    b = 14;
    drutt(a, b, c);
    c = 15;
    return 0;
}

b) Vad kommer att hända när programmet fortsatt att köra en stund? Varför?

Uppgift 2: Språk, grammatiker och parsning (12 p)

punkt a = 6, 7;
punkt d = 6, 9;
punkt b = 8, 14;
kör till a;
kör till b;
punkt tjohej = 3, 3;
kör till d;
kör till tjohej;

a) (1p) Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för det här lilla programmeringsspråket.

b) (4p) Skriv grammatiken. Använd terminalerna från a-uppgiften. Ange vad som är startsymbol. Startsymbolen ska beskriva ett program, 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) (5p) 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 3: Faser (6 p)

Uppgift 4: Mellankod (7 p)

while (true) {
    y = y - z - w * 2;
    if (z > w)
        z = y;
    else {
        z = -y;
        a = a * b - c * d;
    }
}

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

b) postfixkod för en stackmaskin

c) treadresskod

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

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. (Tala också om vilket du valde.)

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

Scenario till (en del av) uppgifterna

Här är ett exempel på hur en fil med en sådan träningsdagbok ska kunna se ut:

typ löpning; typ motionscykling; 2009-10-19 löpning; typ styrketräning ; 2009-10-19 styrketräning; 2009-10-20 löpning 43:12.2; 2009-10-21 löpning 1:44:00.62 ; 2009-10-21 styrketräning 1:00:00 ; 2009-10-22 motionscykling 1:09:22.1; slut;

Som synes ska filen kunna skrivas på fritt format, vilket betyder att blanktecken och radslut inte spelar någon roll, annat än för att skilja orden från varandra.

Man kan skriva in vilka sporter man ägnar sig åt med "satser" som börjar med nyckelordet typ. Man kan skriva in träningspass med "satser" som börjar med ett datum, följt av namnet på en sport (som tidigare måste ha deklarerats med en typ-sats), eventuellt följt av en tid. Dessutom finns en slut-sats som markerar slutet på träningsdagboken. Alla satser avslutas med semikolon.

Det finns alltså ett "träningsdagboks-språk" som beskriver hur träningsdagboken ser ut, och ett program som ska kunna läsa och förstå träningsdagboken måste kunna läsa och förstå det språket.

Uppgift 1 (5 p)

a) (2p) Vilka övriga tokentyper ingår i träningsdagboks-språket?

b) (1p) Ett exempel på hur ett datum kan se ut är 2009-10-19. Datum ska bestå av årtal med fyra siffror, ett bindestreck, månad med två siffror, ännu ett bindestreck, och till sist datum med två siffror. Skriv ett reguljärt uttryck som beskriver tokentypen datum.

c) (2p) Den träningstid som man kan ange för en träning kan bestå av timmar, minuter, sekunder och decimaldelar av en sekund, som till exempel 1:09:22.1 och 117:00:09.6293845. Minuterna och sekunderna måste vara med, men timmarna och sekunddecimalerna kan uteslutas, som till exempel 09:22.17, 1:09:22 och 0:09. Skriv ett reguljärt uttryck som beskriver tokentypen tid.

Uppgift 2 (5 p)

b) (2p) Om grammatiken från a-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.)

Uppgift 3 (3 p)

Här är en kort träningsdagbok:

typ vila; 2009-10-19 vila 24:00:00; 2009-10-20 fika 1:00:00; slut;

Rita upp ett parse-träd för denna träningsdagbok, med din grammatik från (b-)uppgiften ovan.

Uppgift 4 (5 p)

Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 5 (4 p)

#include <stdlib.h>
#include <stdio.h>

int x = 1;

int apa(int a, int b) {
    int* p = malloc(sizeof(int));
    *p = a;
    x = a;
    if (a <= 2) {
        /* Här! */
        return 3;
    }
    else {
        return apa(a - 4, b);
    }
}

void svamp(int a, int y) {
    int z;
    z = 5;
    z = apa(6, x);
}

int main(void) {
    int a;
    int y;
    a = 7;
    y = 8;
    svamp(a, y);
    a = 9;
    return 0;
}

Uppgift 6 (7 p)

i = 0;
j = 10;
n = 0;
while (i < j) {
    if (i % 2 == 0)
         i = i + 2;
    else
         j = j - 1;
    n = (j - i - 1) / 2;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 7 (5 p)

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

b) Välj en form av mellankod (bland dem från uppgift 6 ovan), och tala om vilken du valde. Skriv sedan en syntax-styrd definition eller ett syntaxstyrt översättningsschema (och tala om vilken du valde) för översättning av while-satsen till mellankod.

Uppgift 8 (6 p)

a) Kompilatorn har ju faser som "scanning", "parsning" och så vidare. Varför finns det ingen fas i kompilatorn som heter "skräpsamling"? Skräpsamling är ju ett ändå ganska viktigt begrepp i modern programmering, och man vill slippa krångla med manuella free och delete.

b) Jag tycker att man borde sluta med kompilatorer och bara använda interpretatorer, för interpretatorer måste ju vara mycket snabbare. En kompilator översätter ju först källkoden, innan den kan köras, medan en interpretator börjar köra programmet direkt!

c) Bison säger att jag har en massa "shift/reduce-konflikter" här i min grammatik. Vad är det för nåt? Vad beror det på? Är det farligt?

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

Scenario till (en del av) uppgifterna

Här är ett exempel på hur en fil med en sådan träningsdagbok ska kunna se ut:

typ löpning; typ motionscykling; 2009-10-19 löpning; typ styrketräning ; 2009-10-19 styrketräning; 2009-10-20 löpning 43:12.2; 2009-10-21 löpning 1:44:00.62 ; 2009-10-21 styrketräning 1:00:00 ; 2009-10-22 motionscykling 1:09:22.1; slut;

Som synes ska filen kunna skrivas på fritt format, vilket betyder att blanktecken och radslut inte spelar någon roll, annat än för att skilja orden från varandra.

Man kan skriva in vilka sporter man ägnar sig åt med "satser" som börjar med nyckelordet typ. Man kan skriva in träningspass med "satser" som börjar med ett datum, följt av namnet på en sport (som tidigare måste ha deklarerats med en typ-sats), eventuellt följt av en tid. Dessutom finns en slut-sats som markerar slutet på träningsdagboken. Alla satser avslutas med semikolon.

Det finns alltså ett "träningsdagboks-språk" som beskriver hur träningsdagboken ser ut, och ett program som ska kunna läsa och förstå träningsdagboken måste kunna läsa och förstå det språket.

Uppgift 1 (5 p)

a) (2p) Vilka övriga tokentyper ingår i träningsdagboks-språket?

b) (1p) Ett exempel på hur ett datum kan se ut är 2009-10-19. Datum ska bestå av årtal med fyra siffror, ett bindestreck, månad med två siffror, ännu ett bindestreck, och till sist datum med två siffror. Skriv ett reguljärt uttryck som beskriver tokentypen datum.

c) (2p) Den träningstid som man kan ange för en träning kan bestå av timmar, minuter, sekunder och decimaldelar av en sekund, som till exempel 1:09:22.1 och 117:00:09.6293845. Minuterna och sekunderna måste vara med, men timmarna och sekunddecimalerna kan uteslutas, som till exempel 09:22.17, 1:09:22 och 0:09. Skriv ett reguljärt uttryck som beskriver tokentypen tid.

Uppgift 2 (5 p)

b) (2p) Om grammatiken från a-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.)

Uppgift 3 (3 p)

Här är en kort träningsdagbok:

typ vila; 2009-10-19 vila 24:00:00; 2009-10-20 fika 1:00:00; slut;

Rita upp ett parse-träd för denna träningsdagbok, med din grammatik från (b-)uppgiften ovan.

Uppgift 4 (5 p)

Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 5 (4 p)

#include <stdlib.h>
#include <stdio.h>

int x = 1;

int apa(int a, int b) {
    int* p = malloc(sizeof(int));
    *p = a;
    x = a;
    if (a <= 2) {
        /* Här! */
        return 3;
    }
    else {
        return apa(a - 4, b);
    }
}

void svamp(int a, int y) {
    int z;
    z = 5;
    z = apa(6, x);
}

int main(void) {
    int a;
    int y;
    a = 7;
    y = 8;
    svamp(a, y);
    a = 9;
    return 0;
}

Uppgift 6 (7 p)

i = 0;
j = 10;
n = 0;
while (i < j) {
    if (i % 2 == 0)
         i = i + 2;
    else
         j = j - 1;
    n = (j - i - 1) / 2;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 7 (5 p)

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

b) Välj en form av mellankod (bland dem från uppgift 6 ovan), och tala om vilken du valde. Skriv sedan en syntax-styrd definition eller ett syntaxstyrt översättningsschema (och tala om vilken du valde) för översättning av while-satsen till mellankod.

Uppgift 8 (6 p)

a) Kompilatorn har ju faser som "scanning", "parsning" och så vidare. Varför finns det ingen fas i kompilatorn som heter "skräpsamling"? Skräpsamling är ju ett ändå ganska viktigt begrepp i modern programmering, och man vill slippa krångla med manuella free och delete.

b) Jag tycker att man borde sluta med kompilatorer och bara använda interpretatorer, för interpretatorer måste ju vara mycket snabbare. En kompilator översätter ju först källkoden, innan den kan köras, medan en interpretator börjar köra programmet direkt!

c) Bison säger att jag har en massa "shift/reduce-konflikter" här i min grammatik. Vad är det för nåt? Vad beror det på? Är det farligt?

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

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

• teckenlösa heltal (alltså heltal som inte är negativa)
• heltal (som även kan vara negativa)
• identifierare, som kan innehålla siffror och bokstäver, men måste börja på en bokstav

b) (2p) Vad är det för skillnad på ett lexem och ett lexikaliskt värde, och vad har dessa med scanning att göra?

Uppgift 3: Grammatiker och top-down-parsning (15 p)

S -> a X | b | X Y
X -> X c | e
Y -> d 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 4: Mellankod (5 p)

x = 1;
while (y < 2) {
    if (z > 3) {
        t = t - x - y / (1 - z - y);
    }
    else {
        x = 1;
        y = 2;
        z = 3;
    }
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 5: Några termer (7 p)

a) aktiveringspost
b) basic block
c) copy propagation
d) fas (engelska: phase)
e) pass (engelska: pass)
f) registerallokering
g) rotmängd (engelska: root set)

• Write clearly. Solutions that can not be read can obviously not give any points. Unclear and ambiguous wording will be misinterpreted.
• Enter the personal exam code on each sheet submitted. Do not write your name on the sheets.
• Write only on one side of the paper. Do not use red letters.
• Assumptions beyond those in the given problems must be stated.
• You are allowed to explain your solutions. Even an incorrect answer may give some points, if the key ideas were right.

Task 1: Phases (3 p)

#include <stdio.h>

int main(void) {
    int a;

    printf("Hi!\n );            error: missing terminating " character
    printf("Give a number: ");
    scanf("%d", &a ;            error: expected ')' before ';' token
    printf("The number was: %d\n", a);

    return "Charles";           warning: return makes integer from pointer without a cast
}

Task 2: Scanning and Regular Expression (5 p)

• a year with four digits (that is, from year 1000 to year 9999)
• clothes sizes (which can be XS, S, M, L and XL)

b) (2p) Write a regular expression for the Swedish personal identity number (for example 631211-1658). Your expression should match all valid such numbers. It is difficult to write a regular expression that does not also match certain incorrect numbers, so your solution is allowed to do that. But state at least one check that is not made by your regular expression.

c) (1p) What is the difference between a token and a lexeme?

Task 3: Grammars (10 p)

a) left recursion
b) FIRST() conflicts
c) ambiguity

For each of these problems, provide an example of a grammar that exhibits the problem. Also explain, for each of the grammars, how the problem manifests itself in practice. (That is: what is it that does not work, because of the problem?) Also explain how to solve the problem.

Task 4: Intermediate Code (5 p)

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

a) an abstract syntax tree (by drawing the tree!)

b) postfix code for a stack machine

c) three-address code

Task 5: Some Terms(9 p)

a) target language
b) target program
c) front end
d) Yacc
e) symbol table
f) shift-reduce conflict
g) deterministic finite state machine
h) reserved word (or "keyword")
i) call sequence

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

#include <stdio.h>

int main(void) {
    int a;

    printf("Hej!\n );         error: missing terminating " character
    printf("Ange ett tal: ");
    scanf("%d", &a ;          error: expected ')' before ';' token
    printf("Talet var: %d\n", a);

    return "Kalle";           warning: return makes integer from pointer without a cast
}

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

• årtal med fyra siffror (dvs från år 1000 till år 9999)
• klädstorlekar (som kan vara XS, S, M, L och XL)

b) (2p) Skriv ett reguljärt uttryck för svenska personnummer (som till exempel 631211-1658). Uttrycket ska matcha alla giltiga personnummer. Det är besvärligt att skriva ett reguljärt uttryck som inte också matchar vissa otillåtna personnummer, så det gör inget om ditt svar gör det. Men förklara minst en kontroll som inte görs av ditt reguljära uttryck.

c) (1p) Vad är det för skillnad på en token och ett lexem?

Uppgift 3: Grammatiker (10 p)

a) vänsterrekursion
b) FIRST()-konflikter
c) tvetydighet

Ge för var och en av dessa saker exempel på en grammatik som uppvisar problemet. Förklara också för var och en av dessa grammatiker hur problemet visar sig i praktiken. (Dvs: vad är det som inte fungerar, på grund av det problemet?) Visa också hur man löser problemet.

Uppgift 4: Mellankod (5 p)

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

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 5: Några termer (9 p)

a) målspråk
b) målprogram
c) front end
d) Yacc
e) symboltabell
f) shift-reduce-konflikt
g) deterministisk ändlig tillståndsmaskin
h) reserverat ord
i) anropskonventioner (på engelska: call sequence)

• 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: Pass och faser (6 p)

b) Vilka faser brukar man tala om? Skriv inte bara vad de heter, utan beskriv (mycket) kort vad de gör.

c) När vi "bygger" (dvs kompilerar och länkar) följande försök till C-program, får vi de tre kursiverade fel- och varningsmeddelandena. I vilka faser upptäcks dessa fel och varningar?

#include <stdio.h>

int main(void) {
    int a;
    int 2a;                     error: invalid suffix "a" on integer constant

    printf("Hej!\n");
    printg("Ange ett tal: ");   warning: implicit declaration of function 'printg'
                                error: undefined reference to `printg'
    scanf("%d", &a);
    printf("Talet = %d\n", a);

    return 0;
}

Uppgift 2: Mellankod (6 p)

a = 1;
b = a - b - c * d;
while (i * 2 > j * 3) {
    if (i % 2 == 0)
         i = i + 2;
    b = i;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Scenario till (en del av) uppgifterna

Man använder nyckelordet ort för att lägga in en tätort, till exempel så här: ort Örebro

Man använder nyckelordet väg för att lägga in en väg, till exempel så här för att ange att det finns en väg mellan Örebro och Karlskoga: väg Örebro Karlskoga

Man använder nyckelordet rutt (och nyckelordet framme) för att lägga in en rutt, till exempel så här för att lägga in en rutt från Örebro till Karlstad: rutt Örebro Karlskoga Kristinehamn Karlstad framme

Man använder nyckelordet slut för att ange slutet på hela inmatningen.

Här är ett komplett exempel:

ort Örebro ort Karlstad ort Karlskoga ort Kristinehamn ort Arboga ort Kungsör ort Oslo väg Örebro Karlskoga väg Karlskoga Kristinehamn väg Kristinehamn Karlstad rutt Örebro Karlskoga Kristinehamn Karlstad framme väg Örebro Arboga väg Arboga Kungsör rutt Örebro Arboga Kungsör framme slut

Kommandona ska kunna skrivas på fritt format, vilket betyder att blanktecken och radslut inte spelar någon roll, annat än för att skilja orden från varandra.

Vi antar att ortnamn alltid består av ett enda ord.

Uppgift 3: Grammatiker (5 p)

b) (4p) Skriv en grammatik för språket. Använd terminalerna från deluppgift a. Om grammatiken inte lämpar sig för implementation i form av en prediktiv recursive-descent-parser, ska du också transformera den så den passar.

Uppgift 4: Träd (3 p)

Här är ett kortare exempel på inmatning till kartdatabasen:

ort Örebro ort Karlstad väg Örebro Karlskoga slut

Rita upp ett parse-träd för denna inmatning, med din grammatik från uppgiften ovan.

Uppgift 5: Parsning (6 p)

Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 6: Några termer (4 p)

1. Aktiveringspost ("activation record")
2. Döda data ("dead data")
3. Död kod ("dead code")
4. Referensräkning ("reference counting")

Med vissa korrigeringar 2011-10-31.

• 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: Grunder om kompilatorer (6 p)

1. debugger
2. editor
3. kodgenerering
4. lexikalisk analys ("scanner")
5. länkning
6. maskinberoende optimering
7. maskinoberoende optimering
8. mellankodsgenerering
9. semantisk analys
10. symboltabellen
11. syntaktisk analys ("parser")

a) (1 p) Det blev fel i listan ovan. Vilka av de uppräknade modulerna ingår inte i kompilatorn?

b) (1p) En del av de uppräknade modulerna brukar kallas "faser". Vad menas med en fas?

c) (0.5 p) En av modulerna ingår i kompilatorn, men är inte en fas. Vilken?

d) (0.5p) I listan ovan är modulerna ordnade i bokstavsordning. Lista faserna i rätt ordning.

e) (3p) 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. Beskriv alla fasernas indata och utdata.

Uppgift 2: Mellankod (6 p)

if (a < b) {
    c = d / e / f;
}
else {
    while (g > h) {
        i = j;
        k = l / (m / n);
    }
    o = 17;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 3: En oändlig loop (2p)

a) Vad innebär detta för mellankodsgenereringen i uppgiften ovan? Förklara också varför!

b) Vad innebär detta för kompileringen i övrigt? Dvs, beskriv om andra delar av kompilatorn på något sätt hanterar att loopen är oändlig.

Scenario till resten av uppgifterna

Vi konstruerar ett enkelt språk för att ange var och när vi avlyssnat. Man använder nyckelordet avlyssnat för att ange en avlyssning, med tid och plats. Platser kan anges med koordinater, men man kan också namnge platser med nyckelordet plats. Man använder nyckelordet slut för att ange slutet på hela inmatningen.

Här är ett komplett exempel:

avlyssnat 9:10:22.103 59.274120 15.2066 plats Örebro = 59.274120 15.2066 avlyssnat 15:07:28.210 Örebro plats Örebro-universitet = 59.254320 15.24625 plats Brickeberg = 59.2465 15.2415 plats Tripoli = 32.902222 13.185833 avlyssnat 16:01:01 Tripoli slut

Kommandona ska kunna skrivas på fritt format, vilket betyder att blanktecken och radslut inte spelar någon roll, annat än för att skilja orden från varandra.

Vi antar att platsnamn alltid består av ett enda ord.

Uppgift 4: Grammatiker (4 p)

b) (3p) Skriv en grammatik för språket. Använd terminalerna från deluppgift a. Om grammatiken inte lämpar sig för implementation i form av en prediktiv recursive-descent-parser, ska du också transformera den så den passar.

Uppgift 5: Parsning (6 p)

Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 6: Scanning och reguljära uttryck (1 p)

Uppgift 7: Optimering (5 p)

(1) temp1 = b * 17
(2) temp2 = c * 18
(3) a = temp1 + temp2
(4) temp3 = c * 18
(5) if (a > temp3) goto 14
(6) temp4 = c - 1
(7) if (a > temp4) goto 13
(8) temp5 = 1 * d
(9) c = c - temp5
(10) temp6 = b * 17
(11) a = a + temp6
(12) goto 6
(13) goto 16
(14) e = b * 17
(15) f = c * 18
(16) temp7 = b * 17
(17) g = a + temp7

a) Dela in koden i basic blocks.

b) Optimera koden med hjälp av de vanliga metoderna för optimering, såväl inom ett enskilt basic block som i flera block. Beskriv inte bara resultatet, utan de olika stegen, gärna med namn.

• 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: Grunder om kompilatorer (6 p)

1. debugger
2. editor
3. kodgenerering
4. lexikalisk analys ("scanner")
5. länkning
6. maskinberoende optimering
7. maskinoberoende optimering
8. mellankodsgenerering
9. semantisk analys
10. symboltabellen
11. syntaktisk analys ("parser")

a) (1 p) Det blev fel i listan ovan. Vilka av de uppräknade modulerna ingår inte i kompilatorn?

a) (1p) En del av de uppräknade modulerna brukar kallas "faser". Vad menas med en fas?

a) (0.5 p) En av modulerna ingår i kompilatorn, men är inte en fas. Vilken?

c) (0.5p) I listan ovan är modulerna ordnade i bokstavsordning. Lista faserna i rätt ordning.

d) (3p) 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. Beskriv alla fasernas indata och utdata.

Uppgift 2: Mellankod (6 p)

if (a < b) {
    c = d / e / f;
}
else {
    while (g > h) {
        i = j;
        k = l / (m / n);
    }
    o = 17;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 3: En oändlig loop (2p)

a) Vad innebär detta för mellankodsgenereringen i uppgiften ovan? Förklara också varför!

b) Vad innebär detta för kompileringen i övrigt? Dvs, beskriv om andra delar av kompilatorn på något sätt hanterar att loopen är oändlig.

Scenario till resten av uppgifterna

Vi konstruerar ett enkelt språk för att ange var och när vi avlyssnat. Man använder nyckelordet avlyssnat för att ange en avlyssning, med tid och plats. Platser kan anges med koordinater, men man kan också namnge platser med nyckelordet plats. Man använder nyckelordet slut för att ange slutet på hela inmatningen.

Här är ett komplett exempel:

avlyssnat 9:10:22.103 59.274120 15.2066 plats Örebro = 59.274120 15.2066 avlyssnat 15:07:28.210 Örebro plats Örebro-universitet = 59.254320 15.24625 plats Brickeberg = 59.2465 15.2415 plats Tripoli = 32.902222 13.185833 avlyssnat 16:01:01 Tripoli slut

Kommandona ska kunna skrivas på fritt format, vilket betyder att blanktecken och radslut inte spelar någon roll, annat än för att skilja orden från varandra.

Vi antar att platsnamn alltid består av ett enda ord.

Uppgift 4: Grammatiker (4 p)

b) (3p) Skriv en grammatik för språket. Använd terminalerna från deluppgift a. Om grammatiken inte lämpar sig för implementation i form av en prediktiv recursive-descent-parser, ska du också transformera den så den passar.

Uppgift 5: Parsning (6 p)

Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 6: Scanning och reguljära uttryck (1 p)

Uppgift 7: Optimering (5 p)

(1) temp1 = b * 17
(2) temp2 = c * 18
(3) a = temp1 + temp2
(4) temp3 = c * 18
(5) if (a > temp3) goto 14
(6) temp4 = c - 1
(7) if (a > temp4) goto 13
(8) temp5 = 1 * d
(9) c = c - temp5
(10) temp6 = b * 17
(11) a = a + temp6
(12) goto 6
(13) goto 16
(14) e = b * 17
(15) f = c * 18
(16) temp7 = b * 17
(17) g = a + temp7

a) Dela in koden i basic blocks.

b) Optimera koden med hjälp av de vanliga metoderna för optimering, såväl inom ett enskilt basic block som i flera block. Beskriv inte bara resultatet, utan de olika stegen, gärna med namn.