Kompilatorer och interpretatorer
för Dataingenjörsprogrammet m fl
måndag 23 oktober 2017
Gäller som tentamen för:
DT125G Kompilatorer och interpretatorer, provkod 0100
DT3030 Datateknik C, Kompilatorer och interpretatorer, provkod 0100
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 51.
För godkänt betyg krävs totalt minst 30 poäng, varav minst 15 poäng på uppgift 8. |
Resultat: | Meddelas på kursens hemsida eller via e-post senast måndag 13 november 2017. |
Å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
#include <stdlib.h> #include <stdio.h> int a, b, c; void f(int d) { int a; int* p; a = 1; b = 2; c = 3; p = malloc(sizeof(int)); *p = d; if (d < 1) f(d + 1); printf("Här!\n"); } int main(void) { int a; int* p; a = 4; b = 5; c = 6; p = malloc(sizeof(int)); *p = 8; f(0); }
När programexekveringen för första gången kommer fram till raden med utskriften "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.
I minnet kommer det då att finnas ett antal heltalsvariabler och andra lagringsutrymmen för heltal, som innehåller olika tal. Rita upp en skiss över dessa variabler och lagringsutrymmen, med innehåll, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.a = 1; if (b < a - b - c * d) { while (i * 2 > j * 3) { if (i % 4 == 5) i = i + 6; b = 7; } a = 8; }
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) Vi använder referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.
b) Vilka av dataobjekten kommer att tas bort?
c) Antag att vi i stället använder skräpsamling med mark-and-sweep. Vilka av dataobjekten kommer att tas bort av skräpsamlaren?
Inmatningsspråket består av något vi kan kalla "köp", som består av nyckelordet start, följt av noll eller flera varurader, följt av nyckelordet klart. En varurad består av ett tal (eventuellt med en decimaldel, som då avskiljs med decimalkomma), följt av en enhet (till exempel liter) som kan utelämnas, följt av en textsträng som anger vilken vara man köpt. Exempel på en komplett inmatning av ett köp:
start 1 liter "mjölk" 2,3 kg "ekologiska morötter" 1 "apelsin" 19 "Coca-Cola 33 cl" klart
b) (2p) Vilka andra terminaler, förutom textsträng, behövs för att man ska kunna skriva en grammatik för köpen?
start 1 "apelsin" 2 "äpple" klart
Påstående | Sant | Falskt |
---|---|---|
Den första fasen i kompilatorn är den lexikaliska analysatorn, även kallad scanner. | ||
Scannern gör om en sekvens av tokens till en sekvens av tecken. | ||
Den andra fasen i kompilatorn är den syntaktiska analysatorn, även kallad parser. | ||
I de flesta vanliga programmeringsspråk tolkas de tre tecknen 123 som ett heltal, vilket är en typ av token. För heltalet 123 är lexemet de tre tecknen 1, 2 och 3. | ||
För heltalet 123 är det lexikaliska värdet talet 123. | ||
Parsern analyserar programmet enligt källspråkets grammatik. | ||
Utdata från parsern är ofta ett syntaxträd, men det är inte säkert att man faktiskt bygger upp trädet, med pekare i minnet eller på annat sätt. | ||
Semantisk analys analyserar programmets betydelse, dvs om det stämmer med källspråkets grammatik. | ||
Det är den semantiska analysatorn som avgör vad additionen i deluttrycket x+y egentligen innebär, till exempel om det är addition av heltal eller om det är sammanslagning av strängar. | ||
Det är den semantiska analysen som lägger in symboler i symboltabellen. | ||
Mellankodsgeneratorn genererar mellankod ("intermediärkod"). Mellankoden skickas vidare till nästa fas som textrader, till exempel t2 = x + t1, och så körs scannern på nytt för att läsa in dem, men de är så enkla att parsern inte behövs. | ||
Maskinoberoende kodoptimering gör programmet mindre och snabbare (eller en av dessa). Det kan hända att det optimerade programmet blir större än utan optimering, till exempel med looputrullning. | ||
Kodgeneratorn genererar målkoden, som till exempel kan bestå av maskininstruktioner för en fysisk processor. |
Påstående | Sant | Falskt |
---|---|---|
Målkoden kan vara i form av text, till exempel assemblerinstruktioner som ADD R1, R2. | ||
Den maskinberoende optimeraren gör optimeringar som bara kan göras på målkodsnivå, till exempel sammanslagning av assemblerinstruktioner. | ||
Om scannern är implementerad i form av en funktion som heter scan, och parsern är implementerad i form av en funktion som heter parse, kommer funktionen scan alltid att anropas före funktionen parse. | ||
Den semantiska analysen resulterar i mellankod, som den maskinoberoende kodoptimeraren sen omvandlar till ett syntaxträd. | ||
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan omvandla 1+2 till 3. | ||
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan ibland omvandla en loop till ett konstant värde. | ||
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan omvandla en länkad lista till en hashtabell. |