Kompilatorer och interpretatorer: Tentamen 2024-03-15

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

Tentamen i

Kompilatorer och interpretatorer

fredag 15 mars 2024

Gäller som tentamen för:
DT501A Kompilatorer och interpretatorer för civilingenjörer, 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 24 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 svaren på svenska eller engelska.
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

Scenario till uppgifterna

James Bond, spionen som är känd från en serie dokumentärfilmer, behöver hjälp i sitt arbete. Även om en del av hans arbetsdag går åt till biljakter, eldstrider, kasinospel och liknande, är den huvudsakliga uppgiften för en spion just att spionera, dvs samla information.

Nu ska James på ett farligt uppdrag. Varje år i maj är det en stor militärparad på Röda Torget i Moskva. Här är en bild från paraden 2016, då man bland annat visade upp den nya ryska stridsvagnen T-14 Armata:

Paraden 2016

Snart är det dags igen för en parad, och James har i uppdrag att gömma sig på Röda Torget, se vilka typer av stridsvagnar som rullar förbi, och räkna hur många exemplar det är. Eftersom han befinner sig mitt i Moskva är uppdraget mycket farligt, och han kan när som helst bli upptäckt. Därför behöver han ett enkelt språk så han kan mata in vilka vagnar han ser. Här är ett exempel på inmatning:

typ "T-14";
observation "T-14";
typ "T-34";
observation "T-14";
observation "T-34" "T-34" "T-14";
undo;
observation "T-34" "T-34" "T-34";
hjälp;

Inmatningen består av dessa typer av kommandon:

Kommandot typ, följt av en textsträng och ett semikolon, som anger en ny typ av stridsvagn.
Kommandot observation, följt av en eller flera textsträngar och ett semikolon. Det kommandot anger vilka vagnar James just sett.
Kommandot undo, som kan användas för att ångra föregående kommando.
Kommandot klart, som betyder att paraden är slut, och att James kan åka hem. Det avslutar inmatningen.
Kommandot hjälp, som betyder att James blivit upptäckt och måste fly, och som också avslutar inmatningen.

Inmatningen kan skrivas på fritt format, så radslut och blanktecken har ingen betydelse utom inuti strängar.

Uppgift 1 (3 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 2 (5 p)

Skriv en grammatik för språket. Startsymbolen ska vara inmatning, som representerar en komplett inmatning enligt scenariot ovan.

Uppgift 3 (4 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:

typ "T-54";
observation "T-54" "T-54";
klart;

Uppgift 4 (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.

Uppgift 5 (12 p)

a) Man brukar dela upp en kompilators arbete i flera faser. Vilka är dessa faser? Förklara också kort vad varje fas gör, och vad som är inmatning och utmatning från varje fas.

b) Programmet som vi skapade för att underlätta för James Bond är inte precis en kompilator. En del av faserna i svaret till a-uppgiften ovan är relevanta för det programmet, dvs kommer förmodligen att finnas med i programmet och fungera ungefär likadant som i en kompilator. Vilka faser är det?

c) Motivera varför de faser som inte är relevanta i James Bonds program inte kommer att vara med i det programmet.

Uppgift 6 (6 p)

Förutom att James Bond är spion extraknäcker han också som programmerare, och när han kommer hem från Moskva skriver han det här programavsnittet i ett C-liknande språk:

    x = 1;
    y = 2;
    while (x != y) {
        x = x + 1;
        if (x == y)
            x = x - y;
    }
    z = x + y;

Översätt ovanstående programavsnitt till två av följande tre sätt att representera programmet. (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!

Uppgift 7 (2 p)

James Bond är kanske en bättre spion än han är programmerare, för vi ser att while-loopen i programavsnittet i uppgiften ovan aldrig kommer att avslutas. Är det något som en kompilator skulle kunna upptäcka, och i så fall i vilken fas (eller annat tillfälle)?