Kompilatorer och interpretatorer: Tentamen 2024-01-12

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

Tentamen i

Kompilatorer och interpretatorer

fredag 12 januari 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

Uppgift 1 (5 p)

Betrakta följande C-program:

#include <stdlib.h>
#include <stdio.h>

int a = 1, b = 2;

void f(int c) {
    int* p;
    p = malloc(sizeof(int));
    *p = c;
    if (c < 3)
        f(c + 1);
    else
        printf("Här!\n");        
}

void g(int d) {
    int a, e;
    int *p;
    a = 4;
    b = 5;
    e = 6;
    p = malloc(sizeof(int));
    *p = d;
    f(1);
}

int main(void) {
    int a, f;
    a = 7;
    b = 8;
    f = 9;
    g(10);
}

När programexekveringen kommer fram till raden med utskriften "Här!", 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".

Uppgift 2 (5 p)

Vi skriver in C-programmet från uppgiften ovan, men vi råkar göra en del skrivfel. När vi försöker bygga och köra programmet får vi de fel- och varningsmeddelanden som visas nedan. I vilka av kompilatorns faser, eller vid andra tidpunkter, upptäcks vart och ett av de olika felen och varningarna?

(Man kan behöva åtgärda en del av felen för att komma vidare och få de andra felen.)

Programmet	Meddelanden
#include <stdlib.h> #include <stdio.h> int a = 1, b = 2; int f(int c) { int* p; p = c; if (c < 3) f(c + 1); else printf("Här!\n"); } void g(int d) { int a, e; int p; a = 4; b = 5; e = 6; p = malloc(sizeof(int); *p = d; f(); } int main(void) { int a, f; a = 7; b = 8; f = 9; h(10); }	(1) Segmentation fault (core dumped) (2) control reaches end of non-void function (3) expected ")" before ";" token (4) too few arguments to function "f" (5) undefined reference to "h"

Programmet

Meddelanden

#include <stdlib.h>
#include <stdio.h>

int a = 1, b = 2;

int f(int c) {
    int* p;
    *p = c;
    if (c < 3)
        f(c + 1);
    else
        printf("Här!\n");        
}

void g(int d) {
    int a, e;
    int *p;
    a = 4;
    b = 5;
    e = 6;
    p = malloc(sizeof(int);
    *p = d;
    f();
}

int main(void) {
    int a, f;
    a = 7;
    b = 8;
    f = 9;
    h(10);
}








(1) Segmentation fault (core dumped)




(2) control reaches end of non-void function







(3) expected ")" before ";" token

(4) too few arguments to function "f"







(5) undefined reference to "h"

Uppgift 3 (9 p)

Det här är ett programavsnitt i ett C-liknande språk:

a = b;
c = d;
while (e < f + g + h * i + j) {
    k = m + n;
}
if (o < p) {
    q = r;
}
else {
    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 är inte ovanligt med gator och hus, som Granvägen och Brickebergsvägen på den här bilden:

Satellitbild med gator och hus

Vi ska bygga en databas för att lagra data om gator och hus, och därför behöver vi ett särskilt inmatningsspråk. Med kommandona gata, hus och korsning ska man kunna mata in en beskrivning av vilka gator och hus som finns, och hur gatorna hänger ihop med varandra. Här är ett exempel på en inmatning:

gata Granvägen;
hus Granvägen 6A;
hus Granvägen 6B;
gata Brickebergsvägen;
hus Brickebergsvägen 19;
gata Alstavägen;
korsning Granvägen Alstavägen;
gata Barkvägen;
korsning Granvägen Barkvägen;
gata Åstadalsvägen;
gata Stenåsvägen;
korsning Åstadalsvägen Stenåsvägen Brickebergsvägen;
klart;

Här har vi matat in att det finns ett antal gator, var och en med ett namn som Granvägen eller Brickebergsvägen. Namn är alltid ett enda ord utan mellanslag, så namn som Elof Ljunggrens väg är inte tillåtna. Vi har också matat in att det finns ett antal hus, till exempel Granvägen 6A och Granvägen 6B. Dessutom anger vi hur gatorna sitter ihop med varandra i olika vägkorsningar, som att Granvägen och Barkvägen sitter ihop i en korsning. Notera att efter nyckelordet korsning kan det komma fler än två gator, exempelvis för att Åstadalsvägen, Stenåsvägen och Brickebergsvägen sitter ihop med varandra i en korsning. 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.

gata Granvägen ; hus Granvägen 6A ; hus Granvägen 6B ; gata Brickebergsvägen ; hus
Brickebergsvägen 19 ; gata Alstavägen ; korsning Granvägen Alstavägen ; gata Barkvägen ;
korsning Granvägen Barkvägen ; gata Åstadalsvägen ; gata Stenåsvägen ; korsning
Åstadalsvägen Stenåsvägen Brickebergsvägen ; klart ;

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

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

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

gata Vägen;
gata Stigen;
gata Gränden;
korsning Vägen Stigen Gränden;
klart;

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