Kompilatorer och interpretatorer: Lösningar till tentamen 2021-01-13

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

a) Två av terminalerna som behövs för att man ska kunna skriva en grammatik för språket är heltal och personnummer. Ett heltal är ett positivt heltal skrivet med vanliga decimala siffror 0-9. Ett personnummer skrivs med tio siffror på det vanliga formatet. Skriv reguljära uttryck som beskriver hur heltal och personnummer får se ut.

Svar:

heltal: [0-9]+
personnummer: [0-9][0-9][0-1][0-9][0-3][0-9]-[0-9][0-9][0-9][0-9]

b) Vilka andra terminaler, förutom heltal och personnummer behövs för att man ska kunna skriva en grammatik för språket?

Svar:

Nyckelorden person, prioritet, vaccinerat, lista, alla, vaccinerade, ovaccinerade och avsluta, samt radslut

Uppgift 2 (4 p)

Skriv en scanner som kan dela upp inmatningen i tokens. Du får själv välja om du ska använda Flex eller skriva den för hand i C, C++ eller ett liknande språk. Scannern ska bestå av en funktion som returnerar en token-kod. Du kan anta att token-koderna finns definierade i form av makron eller enum-konstanter, ungefär som Bison gör när man har en Bison-grammatik med %token-deklarationer.

Svar (filen vaccinering.l):

%{
    #include "vaccinering.tab.h"
%}

%%

[\t ] { /* Ignorera whitespace */ }
\n { return RADSLUT; }
"person" { return PERSON; }
"prioritet" { return PRIORITET; }
"vaccinerat" { return VACCINERAT; }
"lista" { return LISTA; }
"alla" { return ALLA; }
"vaccinerade" { return VACCINERADE; }
"ovaccinerade" { return OVACCINERADE; }
"avsluta" { return AVSLUTA; }
[0-9][0-9][0-1][0-9][0-3][0-9]-[0-9][0-9][0-9][0-9] { return PERSONNUMMER; }
[0-9]+ { /* printf("[HELTAL: '%s']", yytext); */ return HELTAL; }
. { fprintf(stderr, "[Ignorerar felaktigt tecken: '%c']\n", *yytext); }

%%

Uppgift 3 (5 p)

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

Svar:

inmatning -> kommandolista avslutakommando
kommandolista -> kommando kommandolista | tomt
kommando -> personkommando | prioritetskommando | vaccineratkommando | listakommando
personkommando -> person personlista radslut
prioritetskommando -> prioritet heltal personlista radslut
vaccineratkommando -> vaccinerat personlista radslut
listakommando -> lista alla radslut | lista vaccinerade radslut | lista ovaccinerade radslut
avslutakommando -> avsluta radslut
personlista -> personnummer personlista | personnummer

tomt markerar en tom produktion.

Grammatiken finns också som en fil för Yacc/Bison: vaccinering.y

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

person 650402-7266 720515-4524
vaccinerat 871031-1922
avsluta

Svar:

Ett (konkret) parse-träd

Uppgift 5 (3 p)

Vaccinationsprogrammet i scenariot har en inmatning i form av ett särskilt språk, och på det viset liknar det en kompilator. Vi har ju en scanner och en parser. Skulle det vara rimligt att också ha en semantisk fas? Om nej, varför inte? Om ja, vad skulle den i så fall göra?

Svar:

En semantisk fas är inte särskilt användbar här. Semantik handlar om betydelse, vad olika konstruktioner i språket betyder, och därför arbetar den med datatyper, för att till exempel (i många språk) skilja på vad + betyder i en konstruktion som 3 + 3 respektive "3" + "3". (I det ena fallet är det heltalsaddition, i det andra strängkonkatenering.) I inmatningen har vi något som skulle kunna kallas datatyper, nämligen heltal och personnummer, men dels gör man inga beräkningar eller andra operationer med dem, och dels står de på olika syntaktiska platser, så det blir aldrig någon tvekan om vad som är vad.

Å andra sidan kan det finnas problem kvar i inmatningen efter att den syntaktiska analysen är gjord. Enligt grammatiken går det utmärkt att mata in samma personnummer flera gånger med person-kommandon, man kan både vaccinera och ge prioriteter till personer som inte finns inmatade, Man kan mata in personnummer som ingen person har, och (beroende på hur duktig man var när man skrev scannern) helt felaktiga personnummer. Kontrollen av sådant kan man se som en semantisk fas.

Uppgift 6 (2 p)

En annan viktig del av en kompilator brukar vara symboltabellen. Om man tänker sig att vi bygger klart vaccinationsprogrammet, så det fungerar med utskrifter och allt, behöver programmet hålla reda på inmatade personnummer. Tabellen med personnumren kan motsvara symboltabellen. Vilka likheter och skillnader finns mellan den här personnummertabellen och en normal symboltabell i en kompilator?

Svar:

Symboltabellen i en riktig kompilator innehåller också information om datatyper och variabelns "scope". Variabeln x kanske är en heltalsvariabel, som är lokal i funktionen f. Någon sådan information finns inte om personnumren. I språk med typade variabler använder den semantiska fasen symboltabellen för att hitta datatypen på variabler, så kompilatorn kan avgöra vad + i ett uttryck som x + y innebär. I vaccineringsspråket har vi inga variabler alls.

Däremot behöver man, precis som med en riktig symboltabell, kunna lagra nya personnummer, hitta existerande personnummer, och även associera information med dem (personernas prioritet, ifall de blivit vaccinerade, och i så fall när).

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. Du kan anta att token-koderna finns definierade i form av makron eller enum-konstanter.

Om grammatiken från uppgift 3 ovan inte lämpar sig för en prediktiv recursive-descent-parser, måste den först göras om.

Svar:

Grammatiken lämpar sig inte för att implementeras i en prediktiv recursive-descent-parser eftersom den innehåller FIRST()-konflikter. För att få bort dem transformerar vi grammatiken genom att vänsterfaktorisera listakommando och personlista. De här produktionerna:

listakommando -> lista alla radslut | lista vaccinerade radslut | lista ovaccinerade radslut

görs om till:

listakommando -> lista lista-argument
lista-argument -> alla radslut | vaccinerade radslut | ovaccinerade radslut

De här produktionerna:

personlista -> personnummer personlista | personnummer

görs om till:

personlista -> personnummer flerpersoner
flerpersoner -> personlista | tomt

Resultat:

inmatning -> kommandolista avslutakommando
kommandolista -> kommando kommandolista | tomt
kommando -> personkommando | prioritetskommando | vaccineratkommando | listakommando
personkommando -> person personlista radslut
prioritetskommando -> prioritet heltal personlista radslut
vaccineratkommando -> vaccinerat personlista radslut
listakommando -> lista lista-argument
lista-argument -> alla radslut | vaccinerade radslut | ovaccinerade radslut
avslutakommando -> avsluta radslut
personlista -> personnummer flerpersoner
flerpersoner -> personlista | tomt

Därefter skriver vi parsern. En nedladdningsbar komplett fil finns här: vaccineringsparser.c

void match(int expected) {
    if (lookahead != expected)
        error();
    else
        lookahead = scan();
}

void inmatning(void);
void kommandolista(void);
void kommando(void);
void personkommando(void);
void prioritetskommando(void);
void vaccineratkommando(void);
void listakommando(void);
void lista_argument(void);
void avslutakommando(void);
void personlista(void);
void flerpersoner(void);

void inmatning(void) {
    kommandolista(); avslutakommando();
}

void kommandolista(void) {
    if (lookahead == PERSON || lookahead == PRIORITET || lookahead == VACCINERAT || lookahead == LISTA) {
        kommando(); kommandolista();
    }
    else {
        /* Ingenting */
    }
}

void kommando(void) {
    if (lookahead == PERSON) {
        personkommando();
    }
    else if (lookahead == PRIORITET) {
        prioritetskommando();
    }
    else if (lookahead == VACCINERAT) {
        vaccineratkommando();
    }
    else if (lookahead == LISTA) {
        listakommando();
    }
    else {
        error();
    }
}

void personkommando(void) {
    match(PERSON); personlista(); match(RADSLUT);
}

void prioritetskommando(void) {
    match(PRIORITET); match(HELTAL); personlista(); match(RADSLUT);
}

void vaccineratkommando(void) {
    match(VACCINERAT); personlista(); match(RADSLUT);
}

void listakommando(void) {
    match(LISTA); lista_argument();
}

void lista_argument(void) {
    if (lookahead == ALLA) {
        match(ALLA); match(RADSLUT);
    }
    else if (lookahead == VACCINERADE) {
        match(VACCINERADE); match(RADSLUT);
    }
    else if (lookahead == OVACCINERADE) {
        match(OVACCINERADE); match(RADSLUT);
    }
    else {
        error();
    }
}

void avslutakommando(void) {
    match(AVSLUTA); match(RADSLUT);
}

void personlista(void) {
    match(PERSONNUMMER); flerpersoner();
}

void flerpersoner(void) {
    if (lookahead == PERSONNUMMER) {
        personlista();
    }
    else {
        /* Ingenting */
    }
}

void parse() {
    lookahead = scan();
    inmatning();
    printf("Ok.\n");
}

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 22 januari 2021