można przechowywać w pamięci drzewa lub można bezpośrednio wytworzyć wymagany kod wyjściowy. Przechowywanie formularza pośredniego zwykle odbywa się w celu umożliwienia przetwarzania kodu na wyższym poziomie przed wygenerowaniem danych wyjściowych.
W twoim przypadku na przykład łatwo odkryć, że twoje wyrażenie nie zawiera zmiennych, a zatem wynik jest liczbą stałą. Patrząc tylko na jeden węzeł na raz, nie jest to jednak możliwe. Aby być bardziej wyraźnym, jeśli po spojrzeniu na "2 *" wygenerujesz kod maszynowy do obliczenia podwójnego czegoś, co ten kod jest zmarnowany, gdy druga część to na przykład "3", ponieważ twój program obliczy "3", a następnie obliczy podwójne z tego za każdym razem, gdy, a samo ładowanie "6" byłoby równoważne, ale krótsze i szybsze.
Jeśli chcesz wygenerować kod maszynowy, musisz najpierw wiedzieć, jakiego rodzaju maszyna będzie generować kod ... Najprostszym modelem jest podejście oparte na stosie. W tym przypadku nie potrzebujesz logiki alokacji rejestru i łatwo ją skompilować bezpośrednio do kodu maszynowego bez pośredniej reprezentacji. Weźmy pod uwagę ten mały przykład, który obsługuje właśnie liczby całkowite, cztery operacje, jednoargumentowe negacje i zmienne ... zauważysz, że żadna struktura danych nie jest używana: znaki kodu źródłowego są odczytywane, a instrukcje maszynowe są zapisywane na wyjście ...
#include <stdio.h>
#include <stdlib.h>
void error(const char *what)
{
fprintf(stderr, "ERROR: %s\n", what);
exit(1);
}
void compileLiteral(const char *& s)
{
int v = 0;
while (*s >= '0' && *s <= '9')
{
v = v*10 + *s++ - '0';
}
printf(" mov eax, %i\n", v);
}
void compileSymbol(const char *& s)
{
printf(" mov eax, dword ptr ");
while ((*s >= 'a' && *s <= 'z') ||
(*s >= 'A' && *s <= 'Z') ||
(*s >= '0' && *s <= '9') ||
(*s == '_'))
{
putchar(*s++);
}
printf("\n");
}
void compileExpression(const char *&);
void compileTerm(const char *& s)
{
if (*s >= '0' && *s <= '9') {
// Number
compileLiteral(s);
} else if ((*s >= 'a' && *s <= 'z') ||
(*s >= 'A' && *s <= 'Z') ||
(*s == '_')) {
// Variable
compileSymbol(s);
} else if (*s == '-') {
// Unary negation
s++;
compileTerm(s);
printf(" neg eax\n");
} else if (*s == '(') {
// Parenthesized sub-expression
s++;
compileExpression(s);
if (*s != ')')
error("')' expected");
s++;
} else {
error("Syntax error");
}
}
void compileMulDiv(const char *& s)
{
compileTerm(s);
for (;;)
{
if (*s == '*') {
s++;
printf(" push eax\n");
compileTerm(s);
printf(" mov ebx, eax\n");
printf(" pop eax\n");
printf(" imul ebx\n");
} else if (*s == '/') {
s++;
printf(" push eax\n");
compileTerm(s);
printf(" mov ebx, eax\n");
printf(" pop eax\n");
printf(" idiv ebx\n");
} else break;
}
}
void compileAddSub(const char *& s)
{
compileMulDiv(s);
for (;;)
{
if (*s == '+') {
s++;
printf(" push eax\n");
compileMulDiv(s);
printf(" mov ebx, eax\n");
printf(" pop eax\n");
printf(" add eax, ebx\n");
} else if (*s == '-') {
s++;
printf(" push eax\n");
compileMulDiv(s);
printf(" mov ebx, eax\n");
printf(" pop eax\n");
printf(" sub eax, ebx\n");
} else break;
}
}
void compileExpression(const char *& s)
{
compileAddSub(s);
}
int main(int argc, const char *argv[])
{
if (argc != 2) error("Syntax: simple-compiler <expr>\n");
compileExpression(argv[1]);
return 0;
}
Na przykład uruchamiając kompilator z 1+y*(-3+x) jako wejście dostać jako wyjście
mov eax, 1
push eax
mov eax, dword ptr y
push eax
mov eax, 3
neg eax
push eax
mov eax, dword ptr x
mov ebx, eax
pop eax
add eax, ebx
mov ebx, eax
pop eax
imul ebx
mov ebx, eax
pop eax
add eax, ebx
Jednak to podejście do pisania kompilatorów nie dobrze skalować do kompilatora.
Chociaż można uzyskać optymalizację poprzez dodanie optymalizatora "peephole" na etapie wyjściowym, wiele użytecznych optymalizacji jest możliwe tylko patrząc na kod z wyższego punktu widzenia.
Nawet generacja kodu maszynowego może odnieść korzyści, widząc więcej kodu, na przykład, aby zdecydować, który rejestr przypisać do czego lub zdecydować, która z możliwych implementacji asemblera będzie wygodna dla określonego wzorca kodu.
Na przykład to samo wyrażenie może zostać skompilowany przez kompilatora do
mov eax, dword ptr x
sub eax, 3
imul dword ptr y
inc eax