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. |
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?
Exempel på uttryck som grammatiken ska klara:
Följande terminaler kan användas i grammatikreglerna: +, -, *, /, (, ), sin, cos och number. En terminal av typen number är ett reellt tal.
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.
Om du svarar ja: Ange det reguljära uttrycket.
Om nej: Förklara varför det inte går.
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!
Översätt ovanstående programavsnitt tillif (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
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.
b) Referensräkning har problem med en viss sorts datastrukturer. Förklara med ett exempel.