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"); }