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