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:
till dessa tre produktioner, där R är en ny icke-terminal: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");
}
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
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.
(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: