Kompilatorer och interpretatorer
för Dataingenjörsprogrammet m fl
lördag 19 december 2009
Gäller som tentamen för:
DT3004 Datateknik C, Kompilatorer och interpretatorer, provkod 0100
TDK104 Kompilatorer och interpretatorer, provkod 0100
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 37.
För godkänt betyg (3 respektive G) krävs 18 poäng. |
Resultat: | Meddelas på kursens hemsida eller via e-post senast lördag 9 januari 2010. |
Återlämning av tentor: | Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-73 47 013. |
b) (2p) Vad är det för skillnad på ett lexem och ett lexikaliskt värde, och vad har dessa med scanning att göra?
S -> a X | b | X Y X -> X c | e Y -> d Y | d
a) Ange tio olika strängar som ingår i det språk som beskrivs av grammatiken ovan.
b) 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.
c) 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.
d) 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.
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.x = 1; while (y < 2) { if (z > 3) { t = t - x - y / (1 - z - y); } else { x = 1; y = 2; z = 3; } }
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.) |
a) aktiveringspost
b) basic block
c) copy propagation
d) fas (engelska: phase)
e) pass (engelska: pass)
f) registerallokering
g) rotmängd (engelska: root set)