Se också boken eller föreläsningsanteckningarna, särskilt den här figurern, 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.
b = a;
while (a < d) {
c = c * 2 + a;
a = a - b + 2 * 3;
}
Översätt ovanstående programavsnitt till var och en av följande tre typer av mellankod.
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
lvalue b
rvalue a
assign
label 1:
rvalue a
rvalue d
lt
gofalse 2
lvalue c
rvalue c
push 2
times
rvalue a
plus
assign
lvalue a
rvalue a
rvalue b
minus
push 2
push 3
times
plus
assign
jump 1
label 2:
c) treadresskod
b = a
label 1:
if a ≥ d goto 2
temp1 = c * 2
c = temp1 + a
temp2 = a - b
temp3 = 2 * 3
a = temp2 + temp3
goto 1
label 2:
Man kan också använda temporärvariabler för varje deluttryck, så att exempelvis "c = temp1 + a" ovan i stället blir "temp2 = temp1 + a; c = temp2".
Samma treadresskod men lite annorlunda uppställd:
(1) b = a (2) if a ≥ d goto 9 (3) temp1 = c * 2 (4) c = temp1 + a (5) temp2 = a - b (6) temp3 = 2 * 3 (7) a = temp2 + temp3 (8) goto 2 (9) ....
Optimeringar i block 3:
(3) temp1 = c * c (4) c = temp1 + a (5) temp2 = a - b (6) temp3 = 2 * 3 (7) a = temp2 + temp3 (8) goto 2Om addition är snabbare än multiplikation på målmaskinen, kan vi byta ut c * 2 mot c + c. Det kallas reduktion i styrka, dvs att byta ut en operation mot en ekvivalent operation som går snabbare.
Vi kan att beräkna 2 * 3, vilket blir 6, och sedan byta ut instruktion (7) mot a = temp2 + 6. Då kan instruktion (6) och variabeln temp3 tas bort.
skapa, skick, kamin, klart, namn, nummer och semikolon (;)
b) Ange reguljära uttryck för de terminaler som inte har ett fast utseende.
Terminaler skrivs med fetstil, och icke-terminaler kursiverade. *tomt* står för en tom följd av terminaler och icke-terminaler.
inmatning -> kommandolista klart ';' kommandolista -> kommando kommandolista | *tomt* kommando -> kaminkommando | skapaskickkommando | skickkommando kaminkommando -> kamin nummer ';' skapaskickkommando -> skapa skick namn ';' skickkommando -> skick nummer namn ';'
skapa skick skrattretande; kamin 1; skick 2 absurd; klart;
Inte alls. Om man inte har en ganska underlig grammatik.
(Det finns språk där man måste ta hänsyn till semantisk information vid parsningen. I C++ kan man till exempel skriva int x(y);, vilket är en variabeldefinition om identifieraren y är namnet en variabel, men en funktionsdeklaration om y är namnet på en datatyp. Men i vårt kaminspråk finns det knappast någon anledning att krångla till det så.)
Ladda ner: kaminparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation kaminer.l
#include <stdlib.h>
#include <stdio.h>
#include "kaminer.tab.h" // Bara för att få tokenkoderna
// Från Bison: %token SKAPA SKICK KAMIN KLART NAMN NUMMER
extern int yylex(void);
int lookahead;
int scan(void) {
return yylex();
}
void error() {
printf("Det har tyvärr uppstått ett fel.\n");
exit(EXIT_FAILURE);
}
void match(int expected) {
if (lookahead != expected)
error();
else
lookahead = scan();
}
void inmatning(void), kommandolista(void), kommando(void), kaminkommando(void), skapaskickkommando(void), skickkommando(void);
void inmatning(void) {
kommandolista(); match(KLART); match(';');
}
void kommandolista(void) {
if (lookahead == KAMIN || lookahead == SKAPA || lookahead == SKICK) {
kommando(); kommandolista();
}
else {
// Tomt
}
}
void kommando(void) {
if (lookahead == KAMIN)
kaminkommando();
else if (lookahead == SKAPA)
skapaskickkommando();
else if (lookahead == SKICK)
skickkommando();
else
error();
}
void kaminkommando(void) {
match(KAMIN); match(NUMMER); match(';');
}
void skapaskickkommando(void) {
match(SKAPA); match(SKICK); match(NAMN); match(';');
}
void skickkommando(void) {
match(SKICK); match(NUMMER); match(NAMN); match(';');
}
void parse() {
lookahead = scan();
inmatning();
printf("Ok.\n");
}
int main() {
printf("Mata in kommandon. Avsluta med KLART-kommandot och EOF.\n");
parse();
}
// Behövs för Lex
int yywrap(void) {
return 1;
}