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. |
Exempel på uttryck som grammatiken ska klara:
Följande terminaler kan användas i grammatikreglerna: integer, comma, left_bracket, right_bracket, identifier, intersection, union, minus, left_parenthesis, right_parenthesis.
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.
b) När är tvetydighet ett problem i en grammatik? När är det det inte? Visa med exempel!
Översätt ovanstående programavsnitt tillx = 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
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.
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.