Ответ 1
Вы можете сохранить дерево в памяти или вы можете напрямую создать требуемый код вывода. Хранение промежуточной формы обычно выполняется, чтобы выполнить некоторую обработку кода на более высоком уровне перед генерированием вывода.
В вашем случае, например, было бы просто обнаружить, что ваше выражение не содержит переменных, и поэтому результат является фиксированным числом. Глядя только на один node за один раз, это, однако, невозможно. Чтобы быть более явным, если после просмотра "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