Kompilatorer och interpretatorer
för Dataingenjörsprogrammet m fl
måndag 26 oktober 2015
Gäller som tentamen för:
DT3030 Datateknik C, Kompilatorer och interpretatorer, provkod 0100
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 35.
För godkänt betyg krävs totalt minst 20 poäng, varav minst 8 poäng på uppgift 1. |
Resultat: | Meddelas på kursens hemsida eller via e-post senast måndag 16 november 2015. |
Återlämning av tentor: | Efter att resultatet meddelats kan tentorna hämtas på universitetets centrala tentamensutlämning. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070 - 73 47 013. |
A är en icke-terminal, men x och y står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.A -> A x | y
Regeln ersätts av följande två regler (eller, korrektare uttryckt, tre produktioner), som beskriver samma språk men som inte är vänsterrekursiva:
A -> y R R -> x R | empty
A är en icke-terminal, men x, y och z står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.A -> x y | x z
Skriv om till dessa tre produktioner:
A -> x R R -> y | z
x = 0; while (x < y) { while (y < z) { y = y + z + 1; } z = 2; }Översätt ovanstående programavsnitt till var och en av följande tre typer av mellankod.
a) ett syntaxträd, även kallat abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Anna är förälder till Bertil. Bertil är förälder till Cecilia och David. Cecilia är förälder till Elin och Filip.
Vi vill kunna specificera släktträdet genom att ange alla kopplingarna, dvs vem som är barn till vem, så här:
Bertil är barn till Anna. Cecilia är barn till Bertil. David är barn till Bertil. Elin är barn till Cecilia. Filip är barn till Cecilia. Klart!Man anger alltså ett antal kopplingar med är barn till. Varje koppling avslutas med punkt. Allra sist kommer ordet Klart och ett utropstecken.
Här är ytterligare tre exempel på hur inmatningen kan se ut:
Klas är barn till Sven. Klart!
Klas är barn till Sven. Sven är barn till Svea. Klart!
Nisse är barn till Nisse. Nisse är barn till Nisse. Nisse är barn till Nisse. Klart!
Man ska kunna stoppa in blanktecken och radslut var som helst, utom inuti orden.
De här inmatningarna är inte tillåtna:
Klas är barn till Sven.
Elin och Filip är barn till Cecilia. Klart!
Klas är barn till Sven. Sven är barn till Svea. Klart!
Nisse är barn till Nisse. Nisse är barn till Nisse. Nisse är barn till Nisse. Klart!Nisse är barn till sig själv, flera gånger om!
Förklara hur det påverkar parsningen!