Kompilatorer och interpretatorer
för Dataingenjörsprogrammet m fl
måndag 29 oktober 2018
Gäller som tentamen för:
DT125G Kompilatorer och interpretatorer, provkod 0100
DT3030 Datateknik C, Kompilatorer och interpretatorer, provkod 0100
→ This exam is also available in an English version.
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 36.
För godkänt betyg krävs totalt minst 18 poäng. |
Resultat: | Meddelas på kursens hemsida eller via e-post senast måndag 19 november 2018. |
Återlämning av tentor: | Elektroniskt via Studentforum. |
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
if (a < b) { while (c > d) { b = a + 1; a = c * (b + c); a = a + 1; d = c * (b + c); } b = a + 1; } c = a + 1;
a) Översätt ovanstående programavsnitt till antingen ett abstrakt syntaxträd (genom att rita upp trädet) eller postfixkod för en stackmaskin. (Inte båda!)
b) Översätt programavsnittet till treadresskod. Identifiera vilka basic blocks som finns, och rita upp flödesgrafen. (Flödesgrafen, med treadresskoden i, räcker som svar.)
c) Visa någon optimering som går att göra inom ett av dessa basic blocks.
Snart är det Halloween, och barnen går en "godisrunda", där de går runt till grannarna och frågar "bus eller godis". För att dokumentera sina aktiviteter behöver de ett särskilt Halloween-språk, där en inmatning kan se ut så här:
började godisrundan; godis: tre karameller; bus: gjorde ruskiga ljud; godis: ett kilo choklad; godis: en morot; bus: eldade upp grannens bil; gick hem;
Inmatningen beskriver en godisrunda. Den börjar med började godisrundan; och slutar med gick hem;. Däremellan anger man noll eller flera noteringar om bus eller godis. En sådan notering börjar med antingen bus eller godis, ett kolon (:), ett eller flera ord som anger vad man gjorde, och ett semikolon (;).
Inmatningen ska kunna skrivas på fritt format, som de flesta vanliga programmeringsspråk, till exempel så här:
började godisrundan ; godis : tre karameller ; bus : gjorde ruskiga ljud ; godis : ett kilo choklad ; godis : en morot ; bus : eldade upp grannens bil ; gick hem ;
b) (2p) Vilka andra terminaler, förutom ord, behövs för att man ska kunna skriva en grammatik för språket?
började godisrundan; godis: ett tuggummi; gick hem;