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.
if (a < b) {
while (c > d) {
b = a + 1;
a = c * (b + c);
a = a + 1;
d = c * (b + c);
}
b = a + 1;
}
c = a + 1;
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:
rvalue a
rvalue b
<
gofalse AFTER-IF
label WHILE-START:
rvalue c
rvalue d
>
gofalse AFTER-WHILE
lvalue b
rvalue a
push 1
+
=
lvalue a
rvalue c
rvalue b
rvalue c
+
*
=
lvalue a
rvalue a
push 1
+
=
lvalue d
rvalue c
rvalue b
rvalue c
+
*
=
jump WHILE-START
label AFTER-WHILE:
lvalue b
rvalue a
push 1
+
=
label AFTER-IF:
lvalue c
rvalue a
push 1
+
=
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:
if a >= b goto AFTER-IF
label WHILE-START:
if c <= d goto AFTER-WHILE
b = a + 1
temp1 = b + c
a = c * temp1
a = a + 1
temp2 = b + c
d = c * temp2
goto WHILE-START
label AFTER-WHILE:
b = a + 1
label AFTER-IF:
c = a + 1
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) if a >= b goto 11 (2) if c <= d goto 10 (3) b = a + 1 (4) temp1 = b + c (5) a = c * temp1 (6) a = a + 1 (7) temp2 = b + c (8) d = c * temp2 (9) goto 2 (10) b = a + 1 (11) c = a + 1
Flödesgrafen:
c) Visa någon optimering som går att göra inom ett av dessa basic blocks.
Det tredje blocket, (3)-(9):
Här finns ett gemensamt deluttryck b + c (men inte a + 1). Genom copy propagation och eliminering av temp2 fås:(3) b = a + 1 (4) temp1 = b + c (5) a = c * temp1 (6) a = a + 1 (7) temp2 = b + c (8) d = c * temp2 (9) goto 2
(3) b = a + 1 (4) temp1 = b + c (5) a = c * temp1 (6) a = a + 1 (8) d = c * temp1 (9) goto 2
Snart är det Halloween, och barnen går en "godisrunda", där de går runt till grannarna och frågar "bus eller godis". För att dokumentera sina aktiviteter behöver de ett särskilt Halloween-språk, där en inmatning kan se ut så här:
började godisrundan; godis: tre karameller; bus: gjorde ruskiga ljud; godis: ett kilo choklad; godis: en morot; bus: eldade upp grannens bil; gick hem;
Inmatningen beskriver en godisrunda. Den börjar med började godisrundan; och slutar med gick hem;. Däremellan anger man noll eller flera noteringar om bus eller godis. En sådan notering börjar med antingen bus eller godis, ett kolon (:), ett eller flera ord som anger vad man gjorde, och ett semikolon (;).
Inmatningen ska kunna skrivas på fritt format, som de flesta vanliga programmeringsspråk, till exempel så här:
började godisrundan ; godis : tre karameller ; bus : gjorde ruskiga ljud ; godis : ett kilo choklad ; godis : en morot ; bus : eldade upp grannens bil ; gick hem ;
Svar: [a-z]+
b) (2p) Vilka andra terminaler, förutom ord, behövs för att man ska kunna skriva en grammatik för språket?
Svar: började, godisrundan, bus, godis, gick, hem, kolon, semikolon
Svar:
godisrunda -> började godisrundan semikolon busellergodislista gick hem semikolon
busellergodislista -> busellergodis busellergodislista | ingenting
busellergodis -> bus kolon ordlista semikolon | godis kolon ordlista semikolon
ordlista -> ord ordlista | ord
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.
började godisrundan; godis: ett tuggummi; gick hem;
Svar:
Svar:
Grammatiken i uppgift 5 har en FIRST-konflikt, så först måste vi vänsterfaktorisera:
godisrunda -> började godisrundan semikolon busellergodislista gick hem semikolon
busellergodislista -> busellergodis busellergodislista | ingenting
busellergodis -> bus kolon ordlista semikolon | godis kolon ordlista semikolon
ordlista -> ord flerord
flerord -> ordlista | ingenting
Eller så här:
godisrunda -> började godisrundan semikolon busellergodislista gick hem semikolon
busellergodislista -> busellergodis busellergodislista | ingenting
busellergodis -> bus kolon ordlista semikolon | godis kolon ordlista semikolon
ordlista -> ord flerord
flerord -> ord flerord | ingenting
Ladda ner: halloweenparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation halloween.l, och en Bison-version av grammatiken halloween.y
void match(int expected) {
if (lookahead != expected)
error();
else
lookahead = scan();
}
void godisrunda(void) {
match(BORJADE); match(GODISRUNDAN); match(SEMIKOLON); busellergodislista(); match(GICK); match(HEM); match(SEMIKOLON);
}
void busellergodislista(void) {
if (lookahead == BUS || lookahead == GODIS) {
busellergodis(); busellergodislista();
}
else {
/* empty */
}
}
void busellergodis(void) {
if (lookahead == BUS) {
match(BUS); match(KOLON); ordlista(); match(SEMIKOLON);
}
else if (lookahead == GODIS) {
match(GODIS); match(KOLON); ordlista(); match(SEMIKOLON);
}
else {
error();
}
}
void ordlista(void) {
match(ORD); ordlisterest();
}
void ordlisterest(void) {
if (lookahead == ORD) {
match(ORD); ordlisterest();
}
else {
/* empty */
}
}
void parse() {
lookahead = scan();
godisrunda();
printf("Ok.\n");
}