Kompilatorer och interpretatorer: Lösningar till tentamen 2021-10-29

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 tal, och sen skriver ut talens genomsnitt. Körexempel, med användarens inmatning understruken: 

Ange antalet tal: 5
Ange tal nummer 1: 10
Ange tal nummer 2: 20
Ange tal nummer 3: 10
Ange tal nummer 4: -4
Ange tal nummer 5: 100
Genomsnitt: 27.200000

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 Lösningsförslag
#include <stdio.h>

int start(void) {
    int antal;
    printf("Ange antalet tal: ");
    scanf("%d", &antalet);
    Int summa = 0;
    for (int i = 0; i < antal; ++i) {
        int talet = "0"
        printf("Ange tal nummer %d: ",
               i + 1);
        scanf("%d", talet);
        summa += 3talet;
    }
    printf("Genomsnitt: %f\n",
           1.0 * summa div antal);
}



(1) undefined reference to "main"


(2) error: "antalet" undeclared
(3) error: unknown type name "Int"
(4) warning: "antal" is used uninitialized
(5) warning: initialization of "int" from "char *"
(6) error: expected "," or ";" before "printf"

(7) Segmentation fault (core dumped)
(8) error: invalid suffix "talet" on integer constant


(9) error: expected ")" before "div"
(10) warning: control reaches end of non-void function




länkaren


semantisk analys
semantisk analys
optimering, semantisk analys...?
semantisk analys
parser

programkörning
scanner


parser
semantisk analys

Uppgift 2 (5 p)

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

if (x * y == z * t * t) {
    x = y;
    while (z < t) {
        x = y * z * t;
        y = z * t;
    }
    x = y;
}
else {
    z = t;
}
t = 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!)

Lösningsförslag:

Ett (abstrakt) syntaxträd

b) postfixkod för en stackmaskin

Lösningsförslag: 

        rvalue x
        rvalue y
        *
        rvalue z
        rvalue t
        *
        rvalue t
        *
        ==
        gofalse ELSE-START
        lvalue x
        rvalue y
        =
label WHILE-START:
        rvalue z
        rvalue t
        <
        gofalse AFTER-WHILE
        lvalue x
        rvalue y
        rvalue z
        *
        rvalue t
        *
        =
        lvalue y
        rvalue z
        rvalue t
        *
        =
        jump WHILE-START
label AFTER-WHILE:
        lvalue x
        rvalue y
        =
        goto AFTER-IF
label ELSE-START:
        lvalue z
        rvalue t
        =
label AFTER-IF:
        lvalue t
        rvalue x
        =

c) treadresskod

Lösningsförslag: 

        temp1 = x * y
        temp2 = z * t
        temp3 = temp2 * t
        if temp1 != temp3 goto ELSE-START
        x = y
label WHILE-START:
        if z >= t goto AFTER-WHILE
        temp4 = y * z
        x = temp4 * t
        y = z * t
        goto WHILE-START
label AFTER-WHILE:
        x = y
        goto AFTER-IF
label ELSE-START:
        z = t
label AFTER-IF:
        t = x

Uppgift 3 (4 p)

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

Lösningsförslag: Semikolon, kommatecken, textsträng samt nyckelorden klass, elev, i och klart.

b) Det kan hända att en eller flera av terminalerna inte har fixa lexem, utan kan se ut på olika sätt. Skriv i så fall reguljära uttryck som beskriver hur de får se ut.

Lösningsförslag: Textsträng, med det reguljära uttrycket \"[^"]\"

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

Lösningsförslag: Här är en Flex-fil (skola.l): 

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

%%

[\n\t ] { /* Ignorera whitespace, inklusive radslut */ }
"," { return KOMMATECKEN; }
";" { return SEMIKOLON; }
\"[^"]*\" { return TEXTSTRANG; }
"klass" { return KLASS; }
"elev" { return ELEV; }
"i" { return I; }
"klart" { return KLART; }
. { fprintf(stderr, "[Ignorerar felaktigt tecken: '%c']\n", *yytext); }

%%

Uppgift 5 (5 p)

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

Lösningsförslag:

inmatning -> kommandlista klartkommando
kommandolista -> kommando kommandolista
kommandolista -> tomt
kommando -> klasskommando
kommando -> elevkommando
klasskommando -> klass textsträng semikolon
elevkommando -> elev elevlista i klass textsträng semikolon
elevkommando -> elev elevlista semikolon
elevlista -> textsträng
elevlista -> textsträng kommatecken elevlista
klartkommando -> klart semikolon

tomt markerar en tom produktion.

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: 

elev "Anna Alm" i klass "3b";
elev "Bob Berg", "Conny C Cornström III", "Napoleon";
klart;

Lösningsförslag:

Ett parse-träd

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.

Lösningsförslag:

Grammatiken i lösningsförslaget till uppgift 5 ovan har två FIRST()-konflikter, så vi behöver först vänsterfaktorisera. Produktionerna för elevkommando:

elevkommando -> elev elevlista i klass textsträng semikolon
elevkommando -> elev elevlista semikolon

blir i stället:

elevkommando -> elev elevlista elevkommandorest
elevkommandorest -> i klass textsträng semikolon
elevkommandorest -> semikolon

Produktionerna för elevlista:

elevlista -> textsträng
elevlista -> textsträng kommatecken elevlista

blir i stället:

elevlista -> textsträng elevlisterest
elevlisterest -> kommatecken elevlista
elevlisterest -> empty

Som en komplett grammatik:

inmatning -> kommandlista klartkommando
kommandolista -> kommando kommandolista
kommandolista -> tomt
kommando -> klasskommando
kommando -> elevkommando
klasskommando -> klass textsträng semikolon
elevkommando -> elev elevlista elevkommandorest
elevkommandorest -> i klass textsträng semikolon
elevkommandorest -> semikolon
elevlista -> textsträng elevlisterest
elevlisterest -> kommatecken elevlista
elevlisterest -> empty
klartkommando -> klart semikolon

En nedladdningsbar komplett fil finns här: skolparser.c 

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

void kommandolista(void) {
    if (lookahead == ELEV || lookahead == KLASS) {
        kommando(); kommandolista();
    }
    else {
        /* Ingenting */
    }
}

void kommando(void) {
    if (lookahead == KLASS) {
        klasskommando();
    }
    else if (lookahead == ELEV) {
        elevkommando();
    }
    else {
        error();
    }
}

void klasskommando(void) {
    match(KLASS); match(TEXTSTRANG); match(SEMIKOLON);
}

void elevkommando(void) {
    match(ELEV); elevlista(); elevkommandorest();
}

void elevkommandorest(void) {
    if (lookahead == I) {
        match(I); match(KLASS); match(TEXTSTRANG); match(SEMIKOLON);
    }
    else if (lookahead == SEMIKOLON) {
        match(SEMIKOLON);
    }
}

void elevlista(void) {
    match(TEXTSTRANG); elevlisterest();
}

void elevlisterest(void) {
    if (lookahead == KOMMATECKEN) {
        match(KOMMATECKEN); elevlista();
    }
    else {
        /* Ingenting */
    }
}

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

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

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 14 november 2021