Svar:
Se också boken eller föreläsningsanteckningarna, särskilt den här figuren, med tillägget att den maskinberoende optimeringen ger som utdata målkod i målspråket, men mindre och snabbare jämfört med den kod som är utdata från kodgeneratorn.
a = b - 2 * c - 3;
d = 1;
while (e * 4 < f * 5) {
g = g + 6;
h = j + 7;
k = g + 6;
m = j + 7;
}
a) Översätt ovanstående programavsnitt till antingen ett abstrakt syntaxträd (genom att rita upp trädet) eller postfixkod för en stackmaskin. (Inte båda!)
Abstrakt syntaxträd:
En kommentar:
Postfixkod för en stackmaskin:
lvalue a
rvalue b
push 2
rvalue c
*
-
push 3
-
=
lvalue d
push 1
=
label WHILE-START:
rvalue b
push 4
*
rvalue f
push 5
*
<
gofalse AFTER-WHILE
lvalue g
rvalue g
push 6
+
lvalue h
rvalue j
push 7
+
=
lvalue k
rvalue g
push 6
+
=
lvalue m
rvalue j
push 7
+
=
jump WHILE-START
label AFTER-WHILE:
En kommentar:
b) Översätt programavsnittet till treadresskod. Identifiera vilka basic blocks som finns, och rita upp flödesgrafen. (Flödesgrafen, med treadresskoden i, räcker som svar.)
Treadresskoden:
temp1 = 2 * c
temp2 = b - temp1
a = temp2 - 3
d = 1
label WHILE-START:
temp3 = e * 4
temp4 = f * 5
if temp3 >= temp4 goto AFTER-WHILE
g = g + 6
h = j + 7
k = g + 6
m = j + 7
goto WHILE-START
label AFTER-WHILE:
En kommentar:
Vi kan också numrera instruktionerna och översätta programlägesetiketterna, så ser det likadant ut som exemplet från föreläsningarna:
(1) temp1 = 2 * c (2) temp2 = b - temp1 (3) a = temp2 - 3 (4) d = 1 (5) temp3 = e * 4 (6) temp4 = f * 5 (7) if temp3 >= temp4 goto 13 (8) g = g + 6 (9) h = j + 7 (10) k = g + 6 (11) m = j + 7 (12) goto 5 (13)
Flödesgrafen:
c) Visa någon optimering som går att göra inom ett av dessa basic blocks.
Det tredje blocket, (8)-(12):
Här finns ett gemensamt deluttryck j + 7 (men inte g + 6, eftersom g ändras) som kan elimineras:(8) g = g + 6 (9) h = j + 7 (10) k = g + 6 (11) m = j + 7 (12) goto 5
(8) g = g + 6 (9) h = j + 7 (10) k = g + 6 (11) m = h (12) goto 5
Svar:
[A-Za-z]+
b) (1p) En annan av terminalerna som behövs är text, som är en textsträng med enkla citationstecken, som 'Kalle'. Innanför citationstecknen kan det finnas vilka tecken som helst utom just de citationstecknen. Skriv ett reguljärt uttryck som beskriver hur en textsträng får se ut.
Svar:
'[^']*'
c) (2p) Vilka andra terminaler, förutom namn och textsträng, behövs för att man ska kunna skriva en grammatik för SQL-delmängden?
Svar:
select
from
where
and
heltal
= (eq)
!= (ne)
< (lt)
<= (le)
> (gt)
>= (ge)
; (semikolon)
, (komma)
Svar:
kommando -> select namnlista from namnlista valfritt_villkor semikolon
namnlista -> namnlista komma namn | namn
valfritt_villkor -> where villkor | ingenting
villkor -> villkor and delvillkor | delvillkor
delvillkor -> operand operator operand
operand -> namn | tal | text
operator -> le | ge | lt | gt | eq | ne
ingenting står för en tom produktion, och brukar oftast skrivas med en liten "e"-symbol (ε) som tyvärr inte verkar fungera överallt i HTML.
select Nr from Bilar, Fiskar where Kod = 'X7';
Svar:
Svar:
Skriv en grammatik för SQL-delmängden. Startsymbolen ska vara kommando, som representerar en enda SQL-fråga enligt scenariot ovan.
Svar:
I grammatiken som vi skrivit ovan finns vänsterrekursion, som först måste elimineras. Vi får en ny grammatik som beskriver samma språk:
kommando -> select namnlista from namnlista valfritt_villkor semikolon
namnlista -> namn fler_namn
fler_namn -> komma namn fler_namn | ingenting
valfritt_villkor -> where villkor | ingenting
villkor -> delvillkor fler_delvillkor
fler_delvillkor -> and delvillkor fler_delvillkor | ingenting
delvillkor -> operand operator operand
operand -> namn | tal | text
operator -> le | ge | lt | gt | eq | ne
Ladda ner: sqlparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation sql.l, och en Bison-version av grammatiken sql.y
void match(int expected) {
if (lookahead != expected)
error();
else
lookahead = scan();
}
void kommando(void);
void namnlista(void);
void fler_namn(void);
void valfritt_villkor(void);
void villkor(void);
void fler_delvillkor(void);
void delvillkor(void);
void operand(void);
void operator(void);
void kommando(void) {
match(SELECT); namnlista(); match(FROM); namnlista(); valfritt_villkor(); match(SEMIKOLON);
}
void namnlista(void) {
match(NAMN); fler_namn();
}
void fler_namn(void) {
if (lookahead == KOMMA) {
match(KOMMA); match(NAMN); fler_namn();
}
else {
/* Tomt */
}
}
void valfritt_villkor(void) {
if (lookahead == WHERE) {
match(WHERE); villkor();
}
else {
/* Tomt */
}
}
void villkor(void) {
delvillkor(); fler_delvillkor();
}
void fler_delvillkor(void) {
if (lookahead == AND) {
match(AND); delvillkor(); fler_delvillkor();
}
else {
/* Tomt */
}
}
void delvillkor(void) {
operand(); operator(); operand();
}
void operand(void) {
if (lookahead == NAMN)
match(NAMN);
else if (lookahead == TAL)
match(TAL);
else if (lookahead == TEXT)
match(TEXT);
else
error();
}
void operator(void) {
if (lookahead == LE)
match(LE);
else if (lookahead == GE)
match(GE);
else if (lookahead == LT)
match(LT);
else if (lookahead == GT)
match(GT);
else if (lookahead == EQ)
match(EQ);
else if (lookahead == NE)
match(NE);
else
error();
}
void parse() {
lookahead = scan();
kommando();
printf("Ok.\n");
}
int main() {
printf("Mata in ett kommando. Avsluta med EOF.\n");
parse();
}