Observera att detta är förslag på lösningar.
Det kan finnas andra lösningar som också är korrekta.
Det kan hända att en del av lösningarna är mer omfattande än vad som krävs för full poäng på uppgiften,
eller att de bara hänvisar till var man kan läsa svaren.
Dessutom har det inträffat i världshistorien att lärare skrivit fel i lösningsförslagen.
Jag har förstås aldrig gjort det, men andra.
Är det verkligen någon som läser såna här inledande texter?
Jag vet inte. Det kan vara så. Rabarber rabarber rabarber.
Det har jag hört att statisterna får säga på filminspelningar
när det ska vara bakgrundssorl från en restaurang eller liknande.
Här nedan kommer lösningsförslagen till uppgifterna.
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?
Svar:
...
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!
Svar:
...
Uppgift 3 (5 p)
a)
Vilka terminaler behövs
för att man ska kunna skriva en grammatik för språket i scenariot?
Svar:
STARTKLAMMER SLUTKLAMMER SEMIKOLON LOKAL PAPPERSKORG TOMNINGSRUNDA NAMN DATUM HELTAL
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!
Svar:
NAMN: [A-Za-z][A-Za-z0-9]*
DATUM: [12][0-9][0-9][0-9]-[0-1][0-9]-[0-3][0-9]
HELTAL: [0-9]+
Uppgift 4 (5 p)
Skriv en grammatik för språket.
Startsymbolen ska vara inmatning,
som representerar en komplett inmatning enligt scenariot ovan.
Svar:
inmatning -> STARTKLAMMER kommandon SLUTKLAMMER
kommandon -> kommandon kommando | ingenting
kommando -> lokalkommando | papperskorgskommando | tomningsrundekommando
lokalkommando -> LOKAL NAMN SEMIKOLON
papperskorgskommando -> PAPPERSKORG HELTAL HELTAL NAMN SEMIKOLON
tomningsrundekommando -> TOMNINGSRUNDA DATUM papperskorgslista SEMIKOLON
papperskorgslista -> papperskorgslista HELTAL | ingenting
ingenting står för en tom produktion,
och brukar oftast skrivas med en liten "e"-symbol (ε)
som tyvärr inte verkar fungera överallt i HTML.
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; }
|
Svar:
...
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.
Svar:
...
Thomas Padron-McCarthy
(thomas.padron-mccarthy@oru.se)
28 mars 2022