Örebro universitet
Institutionen för teknik
Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se)








Ordinarie tentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

tisdag 16 mars 2004 kl 08:00 - 13:00 i L0001








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.



LYCKA TILL!

Uppgift 1: Faser (7 p)

En kompilators arbete brukar delas in i sex faser.

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)

Skriv en grammatik för aritmetiska och trigonometriska beräkningar på reella tal. Förutom de fyra räknesätten (addition, subtraktion, multiplikation och division), som skrivs med de vanliga symbolerna, ska språket innehålla de trigonometriska funktionerna sinus (sin) och cosinus (cos). Man ska kunna använda parenteser för att ändra beräkningsordningen.

Exempel på uttryck som grammatiken ska klara:

Exempel på otillåtna uttryck: Grammatiken ska klara det angivna språket, och operatorernas prioritet och associativitet ska bli rätt. Detta ska göras med hjälp av själva grammatiken, och inte med specialkonstruktioner från Yacc. Det är inget krav att grammatiken ska lämpa sig för någon viss typ av parsning.

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)

I följande grammatik är S, X, Y och Z icketerminaler. a, b och c är terminaler. S är startsymbol.
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)

Går grammatiken i uppgiften ovan att beskriva med ett reguljärt uttryck (engelska: regular expression)?

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

Uppgift 5: Tvetydighet (5 p)

a) Vad innebär det att en grammatik är tvetydig?

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;
}
Översätt ovanstående programavsnitt till

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

b) postfixkod för en stackmaskin

c) treadresskod

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

Det här är en grammatikregel för en for-loop i ett programmeringsspråk:

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)

a) Förklara hur referensräkning (engelska: reference counting) fungerar. Visa med exempel.

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

Uppgift 9: Några termer (7 p)

Förklara kort vad följande begrepp från kompilatortekniken innebär: