Örebro universitet
Institutionen för naturvetenskap och teknik
Thomas Padron-McCarthy
(thomas.padron-mccarthy@oru.se)
Tentamen i
Kompilatorer och interpretatorer
onsdag 24 augusti 2022
Gäller som tentamen för:
DT135G Kompilatorer och interpretatorer, provkod A001
Hjälpmedel:
|
Ordbok för översättning.
|
Poängkrav:
|
Maximal poäng är 40.
För godkänt betyg krävs totalt minst 22 poäng.
|
Resultat:
|
Meddelas senast 15 arbetsdagar efter tentamensdatum.
|
Återlämning av tentor:
|
Elektroniskt via webbportalen Studenttjänster.
|
Examinator och jourhavande:
|
Thomas Padron-McCarthy, telefon 070 - 73 47 013.
|
-
Skriv tydligt och klart.
Lösningar som inte går att läsa kan naturligtvis inte ge några poäng.
Oklara och tvetydiga formuleringar kommer att misstolkas.
-
Skriv den personliga tentamenskoden på varje inlämnat blad.
Skriv inte namn eller personnummer på bladen.
-
Skriv bara på en sida av papperet.
Använd inte röd skrift.
-
Antaganden utöver de som står i uppgifterna måste anges.
Gjorda antaganden får inte förändra den givna uppgiften.
-
Skriv gärna förklaringar om hur du tänkt.
Även ett svar som är fel kan ge poäng,
om det finns med en förklaring som visar att huvudtankarna var rätt.
LYCKA TILL!
Formelsamling
1. Eliminering av vänsterrekursion
En vänsterrekursiv grammatik kan skrivas om så att den inte är vänsterrekursiv.
Antag att en regel (eller, korrektare uttryckt, två produktioner)
i grammatiken ser ut så här:
A -> A x | y
A är en icke-terminal,
men x och y står för godtyckliga konstruktioner
som består av terminaler och icke-terminaler.
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
2. Vänsterfaktorisering
Antag att grammatiken innehåller denna regel (två produktioner):
A -> x y | x z
A är en icke-terminal,
men x, y och z står för godtyckliga konstruktioner
som består av terminaler och icke-terminaler.
Skriv om till dessa tre produktioner:
A -> x R
R -> y | z
Uppgift 1 (10 p)
En kompilators arbete brukar delas in i ett antal faser.
Ange vilka det är, och förklara kort vad varje fas gör.
Vad är in- och utdata från respektive fas?
Uppgift 2 (7 p)
Det här är ett programavsnitt i ett C-liknande språk:
if (a == b) {
c = d;
while (e != f) {
g = h;
i = j;
}
k = l;
}
else {
m = n + o + p * q * r;
s = t;
}
|
Översätt ovanstående programavsnitt till
två av följande tre typer av mellankod.
(Skulle du svara på alla tre, räknas den med högst poäng bort.)
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
c) treadresskod
Observera: Två av typerna, inte alla tre!
Scenario till uppgift 3-6
Ett företag som vi kan kalla Brun utvecklar och tillverkar produkter inom hemelektronik,
bland annat elektriska tandborstar.
Här är en äldre modell från 1937:
(Foto av användaren Gazebo, Wikipedia. Licens: Creative Commons Attribution-Share Alike 4.0 International)
De mer avancerade modellerna av Bruns eltandborstar använder Bluetooth och en mobilapp
för att ansluta till en central databas, där vi lagrar data om
tandborstar och tandborstningar:
-
Varje tandborste har ett unikt serienummer.
-
Varje tandborstning
gjordes med en viss tandborste,
den skedde ett visst datum med en viss starttid,
den hade en längd (mätt i sekunder).
För att underlätta arbetet med databasen skapar vi ett särskilt inmatningsspråk
för att mata in data om tandborstar och tandborstningar.
Här är ett exempel på en inmatning:
start;
borste 28938;
borste 28939;
borstning 28939 2022-08-23 08:55 120;
borste 30000;
borstning 28939 2022-08-24 08:55 120;
borstning 30000 2022-08-24 08:55 120;
klart;
|
Inmatningen ovan säger att det finns tre olika tandborstar,
och de har serienumren 28938, 28939 och 30000.
Tandborsten med serienummer 28939 har använts två gånger,
och
tandborsten med serienummer 30000 har använts en gång.
Hela inmatningen ska inledas med ett start-kommando
och avslutas med ett klart-kommando,
och mellan dessa kan man skriva två typer av kommandon, i godtycklig ordning:
-
Tandborstkommandon, som består av ordet borste
följt av ett serienummer (till exempel 28938)
och ett semikolon.
-
Tandborstningskommandon, som består av ordet borstning
följt av serienumret på en tandborste,
ett datum på formatet ÅÅÅÅ-MM-DD,
ett klockslag på formatet HH:MM,
en tid i sekunder,
och sist ett semikolon.
Inmatningen kan skrivas på fritt format. Exempelvis är nedanstående inmatning
syntaktiskt ekvivalent med den i exemplet ovan.
start ; borste 28938 ; borste 28939 ; borstning 28939
2022-08-23 08:55
120 ; borste 30000 ; borstning
28939 2022-08-24 08:55 120 ; borstning
30000 2022-08-24 08:55 120 ; klart ;
|
Uppgift 3 (5 p)
a)
Vilka terminaler behövs
för att man ska kunna skriva en grammatik för språket i scenariot?
b)
En del av terminalerna har inte fixa lexem, utan kan se olika ut.
Skriv, för varje sådan terminal,
ett reguljärt uttryck som beskriver hur den får se ut!
Uppgift 4 (5 p)
Skriv en grammatik för språket.
Startsymbolen ska vara inmatning,
som representerar en komplett inmatning enligt scenariot ovan.
Uppgift 5 (5 p)
Ett parse-träd (ibland kallat "konkret syntaxträd")
innehåller noder för alla icke-terminaler.
Rita upp parse-trädet för den här inmatningen,
enligt din grammatik i uppgiften ovan:
start;
borste 1;
borste 2;
borste 3;
klart;
|
Uppgift 6 (8 p)
Skriv en prediktiv recursive-descent-parser för språket
i ett språk som åtminstone liknar C, C++, C# eller Java.
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,
som returnerar typen på nästa token,
och en funktion som heter error,
som man kan anropa när något gått fel
och som skriver ut ett felmeddelande och avslutar programmet.