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]+)?
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
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.
Du kan anta att det redan finns en funktion som heter scan, och att den returnerar typen på nästa token.
Ett programs adressrymd kan delas upp i fyra delar: programkod och konstanter, statiska data, heap och stack. Rita upp hur stacken, heapen och statiska data ser ut när programkörningen kommer till kommentaren "Här!".#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; }
Översätt ovanstående programavsnitt till var och en av följande tre typer av mellankod.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
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.)
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?
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: