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

Kompilatorer och interpretatorer

torsdag 16 januari 2025

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.
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 (3 p)

Vad är skillnaden mellan ett språk, en grammatik och en parser? Hur hänger de ihop?

Uppgift 2 (4 p)

Här är en grammatik. Den har terminalerna a, b, c, d och e, och icke-terminalerna S, T och U. Startsymbolen är S.

S -> a T | a b U
T -> T c | d
U -> e

Det finns två problem med denna grammatik som gör den olämplig för användning med en LL(1)-parser, som är den typ av prediktiv top-down-parser med en tokens lookahead som vi har sett till exempel i 2.9-programmet. Förklara problemen! Visa gärna var i parserns programkod det blir fel.

Uppgift 3 (3 p)

Även om en LL(1)-parser har problem med grammatiken i uppgiften ovan, finns det andra typer av parsers som klarar den. Visa hur en bottom-up-parser med en stack parsar inmatningen a b e.

Uppgift 4 (9 p)

Det här är ett programavsnitt i ett C-liknande språk: 
if (a < b) {
    c = d;
    e = f;
    if (g + h > i + j * k + l) {
        m = n / o / p;
    }
    else {
        q = r;
    }
    s = t * u + v * w * x;
}

Ö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 övriga uppgifter

Det finns studenter som låter ChatGPT skriva sina inlämningsuppgifter i stället för att göra dem själva. De lär sig förstås inte så mycket, men de kanske blir klara med labbarna och får betyg och studiemedel.

Tyvärr, ur de studenternas synvinkel, börjar lärarna lära sig att känna igen AI-genererade texter. De texterna har en speciell stil. Till exempel är de nästan alltid rättstavade och grammatiskt korrekta, men meningsbyggnaden kan kännas konstlad eller ovanlig.

Därför behöver de här studenterna ett program som hjälper dem att lura lärarna att deras AI-genererade text egentligen är skriven av studenterna själva! Programmet ska byta ut rättstavade ord mot olika felstavningar, och det ska byta ut fraser (som består av flera ord) mot andra sätt att uttrycka samma sak.

Det vi ska göra här är att skapa ett särskilt inmatningsspråk för att ange vilka utbyten som programmet ska göra. Inmatningsspråket ska innehålla kommandona byt och byt fras, och här är ett exempel på en inmatning: 

byt statistik : statestik;
byt krasch : crash krash crasch;
byt fras statistik kan vara ett kraftfullt verktyg : statistik är bra;
byt bransch : branch;
byt millennium : milennium millenium milenium;
byt fras avslöjade snabbt dess begränsningar : funkade inte bra;
klart;

Här har vi bland annat angett att ordet statistik ska bytas mot felstavningen statestik, och att ordet krasch ska bytas mot vilken som helst av felstavningarna crash, krash och crasch. Frasen statistik kan vara ett kraftfullt verktyg ska bytas till statistik är bra. Hela inmatningen ska avslutas med ett klart-kommando, enligt ovan.

Inmatningen kan skrivas på fritt format. Exempelvis är nedanstående inmatning syntaktiskt ekvivalent med den i exemplet ovan. 

byt statistik : statestik ; byt krasch : crash krash crasch ; byt fras
statistik kan vara ett kraftfullt verktyg : statistik är bra ; byt

                                        bransch

 : branch ; byt millennium : milennium millenium milenium ; byt
fras avslöjade snabbt dess begränsningar : funkade inte bra ; klart ;

Uppgift 5 (4 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 6 (5 p)

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

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

byt sant : sannt ;
byt fras en annan faktor : och sen ;
klart ;

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