Kompilatorer och interpretatorer: Lösningar till tentamen 2008-11-03

Observera att detta är förslag på lösningar. Det kan finnas andra lösningar som också är korrekta, och 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.

Uppgift 1: Språk, grammatiker och parsning (15 p)

a) (2p)

create, table, drop, insert, into, values, integer, string, primary, key, unique, vänsterparentes ("("), högerparentes (")"), kommatecken (","), semikolon (";"), heltalskonstant (heltal), strängkonstant (sträng), identifierare (id)

b) (5p)

En lösning:

kommando -> create-kommando | drop-kommando | insert-kommando
create-kommando -> create table id "(" kolumn-lista ")" ";"
drop-kommando -> drop table id ";"
insert-kommando -> insert into id values "(" värde-lista ")" ";"
kolumn-lista -> kolumn "," kolumn-lista | kolumn
värde-lista -> värde "," värde-lista | värde
kolumn -> id datatyp villkor
datatyp -> integer | string
villkor -> primary key | unique | ingenting
värde -> heltal | sträng
ingenting står för en tom produktion. Startsymbolen är kommando.

En alternativ lösning:

kommando ->
      create table id "(" kolumn fler-kolumner ")" ";"
    | drop table id ";"
    | insert into id values "(" värde fler-värden ")" ";"
fler-kolumner -> "," kolumn fler-kolumner | ingenting
fler-värden -> "," värde fler-värden | ingenting
kolumn -> id datatyp villkor
datatyp -> integer | string
villkor -> primary key | unique | ingenting
värde -> heltal | sträng

c) (2p)

Den första grammatiken ovan är inte vänsterrekursiv, men de två produktionerna för kolumn-lista har FIRST()-konflikter. Samma sak gäller för de två produktionerna för värde-lista. Två olika vänsterfaktorisering ger en ny delgrammatik:

kolumn-lista -> kolumn fler-kolumner
fler-kolumner -> "," kolumn-lista | ingenting
värde-lista -> värde fler-värden
fler-värden -> "," värde-lista | ingenting

Så här gjorde vi vänsterfaktoriseringarna. Man skriver om dessa två produktioner, där A är en icke-terminal och x, y och z står för godtyckliga sekvenser av terminaler och icke-terminaler:

A -> x y | x z
till dessa tre produktioner, där R är en ny icke-terminal:
A -> x R
R -> y | z

d) (6p)

Vi använder förstås den transformerade grammatiken. Det här är inte riktig C-kod, men man kan också titta på hela det riktiga C-programmet: parser.c

int lookahead;

void error(char* meddelande) {
    printf("Ledsen error: %s\n", meddelande);
    abort();
}

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

void kommando() {
    if (lookahead == CREATE)
        create_kommando();
    else if (lookahead == DROP)
        drop_kommando();
    else if (lookahead == INSERT)
        insert_kommando();
    else
        error("Syntax error: Inte ett tillåtet kommando.");
}

void create_kommando() {
    match(CREATE); match(TABLE); match(ID); match("("); kolumn_lista(); match(")"); match(";");
}

void drop_kommando() {
    match(DROP); match(TABLE); match(ID);
}

void insert_kommando() {
    match(INSERT); match(INTO); match(ID); match(VALUES); match("("); värde_lista(); match(")"); match(";");
}

void kolumn_lista() {
    kolumn(); fler_kolumner();
}

void fler_kolumner() {
    if (lookahead == ",") {
        match(","); kolumn_lista();
    }
    else {
        /* Ingenting */
    }
}

void värde_lista() {
    värde(); fler_värden();
}

void fler_värden() {
    if (lookahead == ",") {
        match(","); värde_lista();
    }
    else {
        /* Ingenting */
    }
}

void kolumn() {
    match(ID); datatyp(); villkor();
}

void datatyp() {
    if (lookahead == INTEGER)
        match(INTEGER);
    else if (lookahead == STRING)
        match(STRING);
    else
        error("Syntax error: Inte en tillåten datatyp.");
}

void villkor() {
    if (lookahead == PRIMARY) {
        match(PRIMARY); match(KEY);
    }
    else if (lookahead == UNIQUE)
        match(UNIQUE);
    else {
        /* Ingenting */
    }
}

void värde() {
    if (lookahead == HELTAL) {
        match(HELTAL);
    }
    else if (lookahead == STRÄNG)
        match(STRÄNG);
    else
        error("Syntax error: Inte ett tillåtet värde.");
}

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

Uppgift 2: Faser (4 p)

faser.c:4: error: missing terminating " character -- scannern
faser.c:6: error: expected identifier or '(' before '=' token -- parsern
faser.c:8: error: incompatible types in assignment -- semantisk analys
faser.c:7: undefined reference to `arcsin' -- länkaren

Uppgift 3: Mellankod (10 p)

a) ett abstrakt syntaxträd (genom att rita upp trädet!)

Syntaxträdet

b) postfixkod för en stackmaskin

lvalue i
push 1
=
lvalue j
push 17
=
label 1
rvalue i
rvalue j
<
gofalse 2
lvalue m
rvalue i
rvalue j
+
push 1
-
push 2
/
=
lvalue i
rvalue i
rvalue j
+
=
lvalue j
rvalue i
rvalue j
+
=
rvalue i
rvalue x
>
gofalse 3
lvalue x
rvalue j
=
label 3
goto 1
label 2

c) treadresskod, i form av en flödesgraf ("flow graph") med treadresskoden indelad i basic blocks

Flödesgrafen

Man kan också stoppa in labels ("programlägesetiketter"), och hoppa till dem i stället för till instruktionsnummer.

Uppgift 4: Optimering (5 p)

(Copy propagation är kanske inte egentligen en optimering i sig, men den kan möjliggöra eliminering av variabler i ett senare steg.)

Ytterligare optimeringar kan kanske göras, beroende på hur den efterföljande delen av funktionens kod ser ut:

Uppgift 5: Några termer (6 p)

(Se även kurslitteraturen eller föreläsningsanteckningarna.)
  1. Nyckelhålsoptimering ("peep-hole optimization")
    Man tittar på några få maskin- eller assemblerinstruktioner i taget, och kan ibland ta bort en eller ett par av dem, eftersom deras effekter är redundanta. till exempel när det gäller att placera värden i register.
  2. Typsystem
    En samling datatyper (dvs värden plus operationer som arbetar med dessa värden), tillsammans med en samling regler som anger vilka datatyper som olika delar av ett program ska ha.
  3. Strukturekvivalens ("structural equivalence")
    Två datatyper betraktas som "samma" datatyp om de ser likadana ut. Exempelvis anses två posttyper vara samma typ om de har samma antal fält, av samma typ och i samma ordning.
  4. Aktiveringspost ("activation record")
    Ett minnesutrymme med plats för lokala variabler, återhoppsadress med mera, som allokeras när en funktion anropas. I vanliga moderna språk och exekveringsomgivningar placeras aktiveringsposterna på en stack.
  5. Döda data ("dead data")
    Data som inte kommer att användas mer av det körande programmet.
  6. Onåbara data ("unreachable data")
    Data som inte går att komma åt från det körande programmet, eftersom det inte finns några pekare dit från rotmängden. (Rotmängden är de data som är direkt åtkomliga.) Alla onåbara data är garanterat döda. (Vid automatisk skräpsamling är det onåbara data som tas bort, inte döda, eftersom det är svårt och ibland omöjligt att avgöra vilka data som är döda. Vid konservativ skräpsamling är det inte ens säkert att alla onåbara data tas bort.)


Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se), 5 november 2008