《现代编译器设计》是一本关于编译器的好书。在它的源代码中，让我讨厌的是AST或抽象语法树。假设我们想要编写一个带括号的表达式解析器，它解析如下内容：((2+3)*4) * 2！书中说我们有一个类似AST的：
((2+3)*4) * 2
/ |
(2+3) *4 * 2
/ |
(2+3) * 4
/ |
2 + 3
那么，我应该在内存中保存一棵树，还是只使用递归调用；注意：如果我不将其存储在内存中，我如何将其转换为机器代码？
解析程序代码：
int parse(Expression &expr)
{
if(token.class=='D')
{
expr.type='D';
expr.value=token.val-'0';
get_next_token();
return 1;
}
if(token.class=='(')
{
expr.type='P';
get_next_token();
parse(&expr->left);
parse_operator(&expr->op);
parse(&expr->right);
if(token.class!=')')
Error("missing )");
get_next_token();
return 1;
}
return 0;
}
语法为：
expr -> expr | (expr op expr)
digit -> 0|1|2....|9
op -> +|*
您可以将树存储在内存中，也可以直接生成所需的输出代码。存储中间表单通常是为了能够在生成输出之前在更高级别上对代码进行一些处理。
例如，在您的情况下，很容易发现您的表达式不包含变量，因此结果是一个固定的数字。然而，一次只看一个节点是不可能的。更明确地说，如果在看了"2*"之后，你生成了用于计算某个东西的二重的机器代码，当另一部分是"3"时，这个代码有点浪费，因为你的程序将计算"3"，然后每次计算的二重，而只加载"6"将是等效的，但更短更快。
如果你想生成机器代码，那么你首先需要知道代码将为哪种机器生成。。。最简单的模型使用基于堆栈的方法。在这种情况下，您不需要寄存器分配逻辑，而且很容易在没有中间表示的情况下直接编译为机器代码。考虑一下这个小例子，它只处理整数、四个运算、一元否定和变量。。。您会注意到根本没有使用任何数据结构：读取源代码字符，编写机器指令以输出。。。
#include <stdio.h>
#include <stdlib.h>
void error(const char *what) {
fprintf(stderr, "ERROR: %sn", what);
exit(1);
}
void compileLiteral(const char *& s) {
int v = 0;
while (*s >= '0' && *s <= '9') {
v = v*10 + *s++ - '0';
}
printf(" mov eax, %in", 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 eaxn");
} 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 eaxn");
compileTerm(s);
printf(" mov ebx, eaxn");
printf(" pop eaxn");
printf(" imul ebxn");
} else if (*s == '/') {
s++;
printf(" push eaxn");
compileTerm(s);
printf(" mov ebx, eaxn");
printf(" pop eaxn");
printf(" idiv ebxn");
} else break;
}
}
void compileAddSub(const char *& s) {
compileMulDiv(s);
for (;;) {
if (*s == '+') {
s++;
printf(" push eaxn");
compileMulDiv(s);
printf(" mov ebx, eaxn");
printf(" pop eaxn");
printf(" add eax, ebxn");
} else if (*s == '-') {
s++;
printf(" push eaxn");
compileMulDiv(s);
printf(" mov ebx, eaxn");
printf(" pop eaxn");
printf(" sub eax, ebxn");
} 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
在词法分析和解析完成后，十有八九会将AST保存在内存中。
一旦你有了AST，你可以做很多事情：
- 直接评估它（也许使用递归，也许使用您自己的自定义堆栈）
- 将其转换为其他输出，例如其他语言的代码或其他类型的翻译
- 将其编译为首选指令集
- 等等
您可以使用Dijkstra的调车场算法创建AST。
在某个时刻，您将在内存中拥有整个表达式或AST，除非您在解析时计算即时结果。这适用于仅包含文字或编译时常数的（子）表达式，但不适用于在运行时计算的任何变量。
那么，我应该在内存中保存一棵树，还是只使用递归调用；
您将在解析器中使用递归调用来在内存中构建树。
当然，您需要将树保存在内存中进行处理
优化编译器将代码的几个表示形式保存在内存中（并对其进行转换）。
这个问题的答案取决于你想要一个编译器、一个解释器还是介于两者之间的东西（一个围绕中间语言的解释器）。如果您想要一个解释器，递归下降解析器将同时计算表达式，因此不需要将其保存在内存中。如果你想要一个编译器，那么像例子这样的常量表达式可以也应该优化，但大多数表达式都会对变量进行操作，在转换为线性形式之前，你需要转换为树形形式作为中间步骤。
混合编译器/解释器通常会编译表达式，但没有必要。这通常是一种廉价的编写程序的方法，可以输出可执行文件，简单地用源代码封装解释器。Matlab使用了这种技术——代码过去是真正编译的，但与交互式版本的一致性存在问题。然而，我不允许为表达式生成解析树的困难决定问题。