Kompilatorer och interpretatorer: Tentamen 2022-03-17

Örebro universitet
Institutionen för naturvetenskap och teknik
Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se)

Tentamen i

Kompilatorer och interpretatorer

torsdag 17 mars 2022

Gäller som tentamen för:
DT501A Kompilatorer och interpretatorer för civilingenjörer, provkod A001

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 40. För godkänt betyg krävs totalt minst 22 poäng.
Resultat:	Meddelas senast torsdag 7 april 2022.
Å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.
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:

r = 1;
s = r * s - r * t - 2;
while (s < 3) {
    s = s + 1;
    if (s > 0)
        t = t + 1;
    else
        t = t - 1;
    r = r * t;
}
u = 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

För att underlätta för lokalvården på universitetet har vi skapat en databas över alla papperskorgar och när de tömts. Det databasen innehåller är följande:

Papperskorgar. Varje papperskorg har ett unikt nummer och en volym, mätt i liter.
Lokaler. Varje lokal har ett unikt namn, till exempel T120.
Papperskorgarnas placering. Varje papperskorg är placerad i en lokal.
Tömningsrundor. Varje tömningsrunda sker ett visst datum, och den omfattar ett antal papperskorgar som man tömde.

Lokalvårdarna vägrar att lära sig SQL, så för att mata in data om papperskorgarna och tömningsrundorna ska vi skapa ett särskilt inmatningsspråk. Här är ett exempel på en inmatning:

{
    lokal T120;
    papperskorg 1 10 T120;
    lokal T122;
    papperskorg 2 20 T122;
    tömningsrunda 2022-03-16 1 2;
    papperskorg 3 20 T122;
    tömningsrunda 2022-03-16 3;
    tömningsrunda 2022-03-17 1 2 3;
}

Inmatningen ovan säger att vi har lokalerna T120 och T122. I T120 har vi papperskorg nummer 1 som rymmer 10 liter, och i T122 har vi papperskorg 2 och 3, som rymmer 20 liter vardera. 2022-03-16 gjorde vi två tömningsrundor: en där vi tömde papperskorg nummer 1 och 2, och en där vi bara tömde papperskorg nummer 3. 2022-03-17 gjorde vi en tömningsrunda, och då tömde vi alla tre papperskorgarna 1, 2 och 3.

Hela inmatningen ska alltså stå inom fiskmåsklamrar { och }, och innanför dem kan man skriva tre typer av kommandon, i godtycklig ordning:

Lokalkommandon, som består av ordet lokal, följt av ett namn (till exempel T120).
Papperskorgskommandon, som består av ordet papperskorg, följt av papperskorgens nummer (ett heltal), papperskorgens volym (också ett heltal), och namnet på den lokal som papperskorgen står i.
Tömningsrundekommandon, som består av ordet tömningsrunda, följt av ett datum på formatet ÅÅÅÅ-MM-DD, följt av en lista med numren på de papperskorgar som tömdes.

Alla kommandon avslutas med semikolon.

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:

{ lokal T120; tömningsrunda 2022-03-16 1 2; }

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.