あなたは、メモリ内のツリーを保存することもできますし、直接必要な出力コードを生成することができます。中間形式を格納することは、通常、出力を生成する前に、より高いレベルでコード上で何らかの処理を行うことができるように行われる。
たとえば、式に変数が含まれていないことがわかり、その結果が固定数になっていることがわかります。一度に1つのノードだけを見ることは可能ですが、これは不可能です。 "2 *"を見た後で、何かの倍を計算するためのマシンコードを生成すると、プログラムは "3"を計算してから、他の部分が例えば "3"のときにこのコードは無駄になります。そのたびの倍数 "6"をロードするだけで同等ですが、より短く高速です。
マシンコードを生成したい場合は、コードが生成されるマシンの種類をまず知る必要があります。最も単純なモデルはスタックベースのアプローチです。この場合、レジスタ割り当てロジックは不要で、中間表現なしで直接マシンコードにコンパイルするのは簡単です。整数、4つの演算、単項否定と変数を扱うこの小さな例を考えてみましょう。データ構造はまったく使われていないことに気づくでしょう：ソースコード文字が読み込まれ、機械命令が出力に書き出されます...あなたが出力
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
として取得する入力として1+y*(-3+x)でコンパイラを実行しているたとえば
#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;
}
しかし書き込みコンパイラのこのアプローチは、最適化コンパイラにうまくスケールしません。
出力段に「ピープホール」オプティマイザを追加することで最適化することは可能ですが、多くの有用な最適化はより高い視点からのコードを見るだけで可能です。
また、ベアマシンコードの生成でも、どのレジスタをwhatに割り当てるかを決定したり、特定のコードパターンに便利なアセンブラ実装を決定したりするなど、より多くのコードを見ることで利益を得ることができます。
例えば同じ式はだから私はメモリ内のツリーを保存するか、単に再帰呼び出しを使用する必要があります
mov eax, dword ptr x
sub eax, 3
imul dword ptr y
inc eax