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