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:
ingenting står för en tom produktion. Startsymbolen är kommando.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:
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: