Puede almacenar el árbol en la memoria o se puede producir directamente el código de salida requerida. El almacenamiento de la forma intermedia normalmente se realiza para poder realizar algún procesamiento en el código en un nivel superior antes de generar la salida.
En su caso, por ejemplo, sería fácil descubrir que su expresión no contiene variables y, por lo tanto, el resultado es un número fijo. Sin embargo, mirando solo un nodo a la vez, esto no es posible. Para ser más explícito, si después de mirar "2 *" genera código de máquina para calcular el doble de algo, este código se desperdicia cuando la otra parte es, por ejemplo, "3" porque su programa calculará "3" y luego calculará el código el doble de ese cada vez mientras que solo cargar "6" sería equivalente pero más corto y más rápido.
Si desea generar el código de máquina, primero necesita saber para qué tipo de máquina se va a generar el código ... el modelo más simple es un enfoque basado en la pila. En este caso, no necesita lógica de asignación de registro y es fácil compilar directamente en el código de máquina sin la representación intermedia. Considere este pequeño ejemplo que solo maneja números enteros, cuatro operaciones, negación unaria y variables ... notará que no se usa ninguna estructura de datos: los caracteres del código fuente se leen y las instrucciones de la máquina se escriben en la salida ...
#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;
}
Por ejemplo ejecuta el compilador con 1+y*(-3+x) como entrada que se obtiene como salida
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
Sin embargo este enfoque de los compiladores de escritura no se adapta bien a un compilador de optimización.
Si bien es posible obtener algo de optimización agregando un optimizador "mirilla" en la etapa de salida, muchas optimizaciones útiles son posibles solo mirando el código desde un punto de vista más alto.
También la generación de código de máquina simple podría beneficiarse al ver más código, por ejemplo, decidir qué registro asignar a qué o decidir cuál de las posibles implementaciones del ensamblador sería conveniente para un patrón de código específico.
Por ejemplo, la misma expresión podría ser compilado por un compilador de optimización a
mov eax, dword ptr x
sub eax, 3
imul dword ptr y
inc eax