Kompilatorer och interpretatorer: Lösningar till tentamen 200-11-07

Uppgift 1 (5 p)

typ, slut, sportnamn, semikolon

b) (1p)

[0-9][0-9][0-9][0-9]-[0-9][0-9]-[0-9][0-9]

c) (2p)

([0-9]+:)?[0-9]?[0-9]:[0-9][0-9](\.[0-9]+)?

Uppgift 2 (5 p)

dagbok -> satser slut ;
satser -> sats satser | empty
sats -> typsats | träningssats
typsats -> typ sportnamn ;
träningssats -> datum sportnamn ; | datum sportnamn tid ;

b) (2p)

De två produktionerna

träningssats -> datum sportnamn | datum sportnamn tid ;

ger en FIRST()-konflikt, och måste vänsterfaktoriseras. Skriv om dem till:

träningssats -> datum sportnamn valfri-tid;
valfri-tid -> tid | empty

Uppgift 3 (3 p)

Här är en kort träningsdagbok:

typ vila; 2009-10-19 vila 24:00:00; 2009-10-20 fika 1:00:00; slut;

Rita upp ett parse-träd för denna träningsdagbok, med din grammatik från (b-)uppgiften ovan.

Uppgift 4 (5 p)

Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.

Uppgift 5 (4 p)

#include <stdlib.h>
#include <stdio.h>

int x = 1;

int apa(int a, int b) {
    int* p = malloc(sizeof(int));
    *p = a;
    x = a;
    if (a <= 2) {
        /* Här! */
        return 3;
    }
    else {
        return apa(a - 4, b);
    }
}

void svamp(int a, int y) {
    int z;
    z = 5;
    z = apa(6, x);
}

int main(void) {
    int a;
    int y;
    a = 7;
    y = 8;
    svamp(a, y);
    a = 9;
    return 0;
}

Uppgift 6 (7 p)

i = 0;
j = 10;
n = 0;
while (i < j) {
    if (i % 2 == 0)
         i = i + 2;
    else
         j = j - 1;
    n = (j - i - 1) / 2;
}

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

b) postfixkod för en stackmaskin

c) treadresskod

Uppgift 7 (5 p)

a) Skriv en grammatikregel för while-satsen i C.

b) Välj en form av mellankod (bland dem från uppgift 6 ovan), och tala om vilken du valde. Skriv sedan en syntax-styrd definition eller ett syntaxstyrt översättningsschema (och tala om vilken du valde) för översättning av while-satsen till mellankod. (Tala också om vilket du valde.)

Uppgift 8 (6 p)

a) Kompilatorn har ju faser som "scanning", "parsning" och så vidare. Varför finns det ingen fas i kompilatorn som heter "skräpsamling"? Skräpsamling är ju ett ändå ganska viktigt begrepp i modern programmering?

b) Jag tycker att man borde sluta med kompilatorer och bara använda interpretatorer, för interpretatorer måste ju vara mycket snabbare. En kompilator översätter ju först källkoden, innan den kan köras, medan en interpretator börjar köra programmet direkt!

c) Bison säger att jag har en massa "shift/reduce"-konflikter här i min grammatik. Vad kan det bero på? Är det farligt?

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

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

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

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)

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

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

Uppgift 4: Optimering (5 p)

• Eliminering av gemensamma deluttryck inom ett basic block:
  (7) i = i + j
  byts ut mot
  (7) i = temp1
• En algebraisk transformation:
  (6) m = temp2 / 2
  byts ut mot
  (6) m = temp2 >> 1
• Copy propagation:
  (8) j = i + j
  byts ut mot
  (8) j = temp1 + j
• Copy propagation:
  (9) if (i <= x) goto 3
  byts ut mot
  (9) if (temp1 <= x) goto 3

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

• Eliminering av död kod:
  Om m är en lokal variabel som inte används efter kodsnutten, så är m död, och instruktion (6) kan tas bort. Då blir även temp2 död, och även (5) kan tas bort.
• Eliminering av död kod:
  Om x är en lokal variabel som inte används efter kodsnutten, så är x död, och instruktionerna (9) och (10) kan tas bort.

Uppgift 5: Några termer (6 p)

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.)