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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 48. För betyget 3 krävs 24 poäng. För betyget 4 krävs 32 poäng. För betyget 5 krävs 40 poäng.
Resultat och lösningar:	Meddelas på kursens hemsida senast tisdag 1 april 2003.
Visning:	Onsdag 2 april 2003 kl 12:00-13:00 i T2220. Därefter kan tentor hämtas på expeditionen.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-7347013.

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 68. För betyget 3 krävs 34 poäng. För betyget 4 krävs 45 poäng. För betyget 5 krävs 57 poäng.
Resultat:	Meddelas på kursens hemsida senast torsdag 12 juni 2003.
Visning och frågestund:	Torsdag 12 juni 2003 kl 12:00-13:00 i T2220. Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-7347013.

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 70. För betyget 3 krävs 35 poäng. För betyget 4 krävs 46 poäng. För betyget 5 krävs 58 poäng.
Resultat:	Meddelas på kursens hemsida senast tisdag 30 mars 2004.
Visning och frågestund:	Tisdag 30 mars 2004 kl 12:00-13:30 i T2220. Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-7347013.

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 54. För betyget 3 krävs 27 poäng. För betyget 4 krävs 36 poäng. För betyget 5 krävs 45 poäng.
Resultat:	Meddelas på kursens hemsida senast måndag 8 november 2004.
Visning och frågestund:	Meddelas senare. Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-7347013.

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

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

• 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

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

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

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

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

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

Uppgift 1: Grammatiker (5p)

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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

Uppgift 7: Optimering (5 p)

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?

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

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

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

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

Uppgift 1: Grammatiker (5p)

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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

Uppgift 7: Optimering (5 p)

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?

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 30. För betyget 3 krävs 15 poäng.
Resultat:	Meddelas på kursens hemsida senast måndag 29 januari 2007.
Visning och frågestund:	Tisdag 30 januari 2007 kl 15:00-15:30 i T2220. Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande:	Thomas Padron-McCarthy, tel: Mellankod (5 p)efon 070-7347013.

• 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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 30. För betyget 3 krävs 15 poäng.
Resultat:	Meddelas på kursens hemsida senast måndag 10 september 2007.
Visning och frågestund:	Tisdag 11 september 2007 kl 12:00-12:30 i mitt rum (T2220). Därefter kan tentorna hämtas på expeditionen.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-7347013.

• 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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 40. För godkänt betyg (3 respektive G) krävs 20 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast måndag 19 november 2007.
Visning och frågestund:	Måndag 19 november 2007 kl 12:00-12:30 i mitt rum (T2220). Efter visningen kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-7347013.

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

Observera: 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. (Skulle du svara på alla sex, räknas den med högst poäng bort.)

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.

Observera: 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. (Skulle du svara på alla sex, räknas den med högst poäng bort.)

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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

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

Observera: 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. (Skulle du svara på alla sex, räknas den med högst poäng bort.)

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 43. För godkänt betyg (3 respektive G) krävs 21 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast lördag 29 december 2007.
Visning och frågestund:	Tisdag 8 januari 2008 kl 15:00-15:30 i mitt rum (T2220). Efter visningen kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-7347013.

• 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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

Uppgift 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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 40. För godkänt betyg (3 respektive G) krävs 20 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast måndag 24 november 2008.
Visning och frågestund:	Tisdag 25 november 2008 kl 15:00-15:30 i mitt rum (T2220). Efter visningen kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-73 47 013.

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 36. För godkänt betyg (3 respektive G) krävs 18 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast lördag 10 januari 2009.
Återlämning av tentor:	Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-73 47 013.

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 40. För godkänt betyg (3 respektive G) krävs 20 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast lördag 28 november 2009.
Återlämning av tentor:	Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-73 47 013.

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 40. För godkänt betyg (3 respektive G) krävs 20 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast lördag 28 november 2009.
Återlämning av tentor:	Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-73 47 013.

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 37. För godkänt betyg (3 respektive G) krävs 18 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast lördag 9 januari 2010.
Återlämning av tentor:	Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-73 47 013.

• 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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

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

Aids:	No aids.
Score requirements:	Maximum score is 32. To pass (3 or G), at least 16 points are required.
Results:	Announced on the course website or by e-mail by Saturday November 20, 2010.
Return of the exams:	After the result has been announced, exams can be collected from the university's central "tentamensutlämning".
Examiner:	Thomas Padron-McCarthy

• 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

Note: There are three sub-tasks in the task above. Select and answer (at most) two of them. (If you answer all three, the one with the most points will be discarded.)

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 32. För godkänt betyg (3 respektive G) krävs 16 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast lördag 20 november 2010.
Återlämning av tentor:	Efter att resultatet meddelats kan tentorna hämtas på universitetets centrala tentamensutlämning.
Examinator:	Thomas Padron-McCarthy

• 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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 30. För godkänt betyg (3 respektive G) krävs 15 poäng.
Resultat:	Meddelas på kursens hemsida eller via e-post senast måndag 5 september 2011.
Återlämning av tentor:	Efter att resultatet meddelats kan tentorna hämtas på universitetets centrala tentamensutlämning.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070 - 73 47 013.

• 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

Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.)

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