Вы можете сохранить дерево в памяти или напрямую получить требуемый выходной код.Хранение промежуточной формы обычно выполняется, чтобы иметь возможность выполнить некоторую обработку кода на более высоком уровне перед генерацией вывода.
В вашем случае, например, было бы просто обнаружить, что ваше выражение не содержит переменных и, следовательно,Результатом является фиксированное число.Глядя только на один узел за раз, это, однако, невозможно.Чтобы быть более точным, если после просмотра «2 *» вы генерируете машинный код для вычисления двойного значения, этот код как бы теряется, когда другая часть, например, «3», потому что ваша программа вычислит «3», а затем вычислитудвоение этого значения каждый раз при простой загрузке «6» будет эквивалентно, но короче и быстрее.
Если вы хотите сгенерировать машинный код, то вам сначала нужно узнать, для какого типа машиныкод будет сгенерирован ... в простейшей модели используется стековый подход.В этом случае вам не нужна логика распределения регистров, и ее легко скомпилировать непосредственно в машинный код без промежуточного представления.Рассмотрим этот небольшой пример, который обрабатывает только целые числа, четыре операции, унарное отрицание и переменные ... вы заметите, что структура данных вообще не используется: символы исходного кода читаются, а машинные инструкции пишутся для вывода ...
#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;
}
Например, запустив компилятор с 1+y*(-3+x) в качестве ввода, вы получите в качестве вывода
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
Однако этот подход написания компиляторов не подходит для оптимизирующего компилятора.
Хотя можно добиться некоторой оптимизации, добавив оптимизатор «глазок» на стадии вывода, многие полезные оптимизации возможны только при взгляде на код с более высокой точки зрения.
Кроме того, даже генерация машинного кода может быть чистойвыиграйте, увидев больше кода, например, чтобы решить, какой регистр назначить тому или другому, или решить, какая из возможных реализаций ассемблера будет удобна для конкретного шаблона кода.
Например, то же самое выражение может быть скомпилировано оптимизирующимкомпилятор на
mov eax, dword ptr x
sub eax, 3
imul dword ptr y
inc eax