Kompilatorer och interpretatorer: Lösningar till tentamen 2023-01-11

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

Vi skriver ett C-program som låter användaren mata in två tal, och sen skriver ut talens genomsnitt. Körexempel, med användarens inmatning understruken: 

Ange ett tal: 5
Ange ett tal: 6
Genomsnitt: 5.500000

Programmet, som visas nedan, är tyvärr inte helt korrekt, och när vi försöker bygga och köra det får vi de angivna fel- och varningsmeddelandena. 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 <stdio.h>

ibt main(void) {
    int tal1 tal2;
    printf("Ange ett tal: ");
    scanf("%d", &tal1);
    printf("Ange ett tal: ");
    scanf("%d", &tal1)
    double snitt = 1.0 * (tal1 + tal2) / 2;
    print("Genomsnitt: %f\n", snitt);
}



(1) unknown type name "ibt"
(2) expected "=", "," or ";" before "tal2"



(3) expected ";" before "double"
(4) "tal2" is used uninitialized


(5) undefined reference to "print"

Svar:

(1) semantisk analys (men, pga hur C fungerar, kan även parser vara ett rimligt svar)
(2) parser
(3) parser
(4) maskinoberoende optimering, eller möjligen semantisk analys
(5) länkaren

Uppgift 2 (2 p)

I uppgiften ovan multiplicerar vi summan tal1 + tal2 med konstanten 1.0. Matematiskt sett gör det ju ingen skillnad att multiplicera något med ett. Här gör vi det ändå, och det beror på något som har med kompilatorteknik att göra. Vad? Förklara!

Svar:

Det har att göra med den semantiska analysen, och vilka datatyper som den ger till de olika delarna av programmet. I den semantiska analysen kommer uttrycket (tal1 + tal2) / 2 att analyseras, och vi ser då att tal1 och tal2 är variabler som har datatypen int. Därför bli additionen en heltalsaddition, som också ger ett int-värde som resultat. Därefter delar vi det resultatet med heltalsliteralen 2, som också har datatypen int. Reglerna för språket C (och många andra språk, till exempel Python 2, men inte Python 3) säger att divisionen då är en heltalsdivision, som ger ett int-värde som resultat. Exempelvis blir (5 + 6) / 2 heltalet 5 och inte flyttalet 5.5, som vi vill. Om vi sen lägger det värdet i double-variabeln snitt kommer det att konverteras från int till double, men då är decimalerna redan borta, så variabeln får double-värdet 5.0.

När vi multiplicerar (tal1 + tal2) med flyttalsliteralen 1.0 upptäcker den semantiska analysen att vi multiplicerar ett heltal med ett flyttal. Då kommer först heltalssumman (tal1 + tal2) att konverteras till ett flyttal, och därefter görs flyttalsmultiplikation. Resultatet av 1.0 * (tal1 + tal2), som är ett flyttal, ska divideras med heltalsliteralen 2, som är ett heltal, och då säger reglerna att 2 ska konverteras till ett flyttal, och därefter görs flyttalsdivision. Decimalerna blir kvar.

Uppgift 3 (6 p)

Här är en grammatik. Kursiverade namn är icke-terminaler. Namn i fetstil är terminaler. Startsymbolen är S.

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

a) Grammatiken är inte lämplig för att implementeras med en prediktiv recursive-descent-parser med en token lookahead (en LL(1)-parser). Förklara varför! Vad skulle hända om vi försökte?

Svar:

Grammatiken innehåller vänsterrekursion i produktionen T -> T e. Recursive-descent-parsern skulle hamna i en oändlig rekursion när den försöker parsa icke-terminalen T och hittar terminalen f. Anropet till T() inuti T() sker innan någon token förbrukats: 
void T(void) {
    if (lookahead == 'f') {
        T(); match('e');
    }
    else {
        match('f');
    }
}

b) Visa hur inmatningen a b f e e e parsas av en bottom-up-parser med en stack. Visa vilka skift- och reduce-operationer som utförs, och hur stacken ser ut efter varje operation.

Svar:

1. a skiftas till stacken. Stacken:

a

2. b skiftas till stacken. Stacken:

b
a

3. f skiftas till stacken. Stacken:

f
b
a

4. f reduceras till T enligt produktionen T -> f. Stacken:

T
b
a

5. e skiftas till stacken. Stacken:

e
T
b
a

6. T e reduceras till T enligt produktionen T -> T e. Stacken:

T
b
a

7. e skiftas till stacken. Stacken:

e
T
b
a

8. T e reduceras till T enligt produktionen T -> T e. Stacken:

T
b
a

9. e skiftas till stacken. Stacken:

e
T
b
a

10. T e reduceras till T enligt produktionen T -> T e. Stacken:

T
b
a

11. a b T reduceras till S enligt produktionen S -> a b T. Stacken:

S

Uppgift 4 (5 p)

Här är lite treadresskod som ingår i ett större program: 

  (1) t1 = y * 2
  (2) t2 = z * 3
  (3) t3 = t1 + t2
  (4) if x >= t3 goto (11)
  (5) t4 = u * 4
  (6) u = t4 + 3
  (7) t5 = u * 4
  (8) t = t5 + 5
  (9) t6 = u * 4
 (10) v = t6 + 6
 (11) t7 = u * 4
 (12) w = t7 + 7

a) En del av koden verkar onödigt lång, med alla dessa temporära variabler som t1, t2 och så vidare. Kunde inte de tre första instruktionerna ersättas med en enda instruktion, t3 = y * 2 + z * 3? Om inte, varför?

Svar:

Det är treadresskod, inte femadresskod! Man ska till exempel kunna lagra en treadresinstruktion i en post ("struct"), med ett typfält och därefter tre "adresser", som kan vara variabler eller konstanter. Dessutom kan de vara instruktioner att hoppa till.

b) Vilka basic blocks finns det?

Svar:

Block 1: instruktion 1-4
Block 2: instruktion 5-10
Block 3: instruktion 11-12

c) Visa en optimering som går att göra på koden!

Svar:

Eliminering av gemensamma deluttryck: I instruktion (9), t6 = u * 4, kan u * 4 ersättas med t5, som redan innehålller värdet av u * 4. Därefter kan vi med copy propagation i instruktion (10) ersätta t6 med t5, och helt eliminera t6.

Vi kan inte göra den optimeringen i instruktion (7) och (11).

Uppgift 5 (5 p)

a) Vilka terminaler behövs för att man ska kunna skriva en grammatik för språket i scenariot?

Svar:

Datum, tid, ord, kolon, semikolon och nyckelordet klart.

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:

Datum: [12][0-9][0-9][0-9]-[0-1][0-9]-[0-3][0-9]
Tid: [012][0-9]:[0-5][0-9]
Ord: [a-zåäöA-ZÅÄÖ]+

Uppgift 6 (5 p)

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

Svar:

inmatning -> rapporter klartkommando
rapporter -> rapporter rapport
rapporter -> ingenting
klartkommando -> klart semikolon
rapport -> datum tid kolon ordlista semikolon
ordlista -> ordlista ord
ordlista -> ingenting

Kommentarer:

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

2023-01-10 08:27: krock;
2023-01-10 08:27: episk krock;
klart;

Svar:

Ett parse-träd

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.

Svar:

I grammatiken som vi skrivit ovan finns två vänsterrekursioner som först måste elimineras. Vi kan skriva om grammatiken så vi får en ny grammatik som beskriver samma språk:

inmatning -> rapporter klartkommando
rapporter -> rapport rapporter
rapporter -> ingenting
klartkommando -> klart semikolon
rapport -> datum tid kolon ordlista semikolon
ordlista -> ord ordlista
ordlista -> ingenting

Ladda ner: skoterparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation, skotrar.l, och en Bison-version av grammatiken, skotrar.y. Det finns också en Makefile för att bygga parsern.

Token-typer: DATUM TID KOLON ORD SEMIKOLON KLART 

int lookahead;

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

void inmatning(void) {
    rapporter(); klartkommando();
}

void rapporter(void) {
    if (lookahead == DATUM) {
        rapport(); rapporter();
    }
    else {
        // empty
    }
}

void klartkommando(void) {
    match(KLART); match(SEMIKOLON);
}

void rapport(void) {
    match(DATUM); match(TID); match(KOLON); ordlista(); match(SEMIKOLON);
}

void ordlista(void) {
    if (lookahead == ORD) {
        match(ORD); ordlista();
    }
    else {
        // empty
    }
}

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

int main() {
    printf("Skriv en inmatning av rapporter om elskotrar!\n");
    printf("Avsluta med CTRL-D!\n");
    parse();
}

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) 16 januari 2023