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








Omtentamen i

Kompilatorer och interpretatorer

för Dataingenjörsprogrammet

torsdag 5 juni 2003 kl 14:00 - 19:00








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.



LYCKA TILL!


Uppgift 1: Faser (6 p)

En kompilators arbete brukar delas in i sex faser. Ange vilka det är, och förklara kort vad varje fas gör. Vad är in- och utdata från respektive fas?

Uppgift 2: Kontextfri grammatik (10 p)

Skriv en grammatik för enkla beräkningar på mängder av heltal. Den ska kunna hantera mängdliteraler, variabler, och de tre operatorerna snitt (skrivs som intersection), union (skrivs som union) och differens (skrivs som -). Operatorerna union och differens har samma prioritet. Snitt har högst prioritet. Alla operatorerna är vänsterassociativa. Uttryck ska kunna grupperas med parenteser.

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: integer, comma, left_bracket, right_bracket, identifier, intersection, union, minus, left_parenthesis, right_parenthesis.

Uppgift 3: Top-down-parsning (17 p)

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

a) Ge exempel på en tvetydig grammatik, dvs en som kan ge upphov till flera olika parse-träd för samma tokensekvens.

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

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

b) postfixkod för en stackmaskin

c) treadresskod

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

Ge en grammatikregel för en if-sats i ett högnivåspråk.

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)

a) Vad är ett basic block?

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)

Förklara hur skräpsamlingsmetoden mark and sweep fungerar. Visa med exempel.

Uppgift 9: Lexikalisk analys (3 p)

Skriv ett reguljärt uttryck (engelska: regular expression) som matchar ett amerikanskt personnamn. Sådana namn består av ett förnamn, en initial med en punkt, och ett efternamn, till exempel George W. Bush, Richard M. Nixon och John F. Kennedy. Andra tillåtna namn är Foo B. Fum, Zwz X. Wnnnn och A B. C. Exempel på namn som inte ska tillåtas är a b. c och Bill Clinton.