LET'S BUILD A COMPILER!
By
Jack W. Crenshaw, Ph.D.
第二部分：表达式分析
开始
假如你已经读过了本系列教程地入门篇，你就应该知道我们下一步将要做什么。你应该已经将cradle程序拷贝到你的Turbo Pascal中，并成功地编译了它。所以你应该已准备好开始新的学习了。
这篇文章的目的是学习如何分析和翻译数学表达式。我们定义的输出是一系列能够完成指定操作的汇编语句。在这里，我们定义表达式是写在等式的右边的部分，比如
x = 2*y + 3/(4*z)
开始时我们的进展的速度会很慢。那是为了使初学者不至于迷失方向。如果有些课程你以前学过，那么对后面的学习将会有很大好处。对那些稍有经验的读者，我要说：请暂且忍耐。我们稍后将会加快进度。
单个数字
为了保持本教程的一贯风格（KISS准则，还记得吗？）我们从最简单的例子入手。那是一个仅由单个数字组成的表达式。
开始编码之前，确保你已经有了我上次所给的那个例程。在其他试验里我们还会用到它。在例程中加入以下代码：
{---------------------------------------------------------------}
{ Parse and Translate a Math Expression }
procedure Expression;
begin
EmitLn('MOVE #' + GetNum + ',D0')
end;
{---------------------------------------------------------------}
在主程序中加入一行“Expression;”。
{---------------------------------------------------------------}
begin
Init;
Expression;
end.
{---------------------------------------------------------------}
现在运行这个程序。试着输入所有的单个数字做试验。得到的输出应该是一行汇编代码。现在试着输入任何其他的字符，你会看到分析器以恰当的方式报告了一个错误。
祝贺你！你已经写了一个可以运行的翻译器了！OK，我承认它的功能是很有限的。但不要轻易地就把它扔掉。这个小小的编译器在一个非常有限的范围内精确地完成了大型编译器所要做的所有工作：它正确地识别了我们为之定义的输入语言中的合法语句，并且生成了正确的、可执行的汇编代码，这些汇编代码也适合翻译成目标语言格式。很重要的是，它也能正确地识别出非法语句，并给出有意义的错误信息。谁还能要求得更多呢？当我们扩展这个分析器时，我们最好使它一直保持这两个特性。
这个小程序中还有其他的特点值得一提。首先，我们没有将代码生成和语法分析分离开……分析器一旦知道我们想要做什么，就直接生成目标代码。当然，在一个实际的编译器中，输入是用GetChar从磁盘文件读入，然后输出写到另一个磁盘文件中，但做试验时，我们使用的这种方法无疑容易得多。
同时注意一个表达式必须产生一个结果放到某个地方。我选用68000的D0寄存器来保存他们。我也可以选择别的寄存器，但用D0更合适。
二分表达式
不可否认，只含一个字符的表达式离我们的要求太远了，所以现在来看看如何扩展它。假定我们要处理的表达式形式如下：
1+2
或者 4-3
或者，用通用的形式就是，<term> +/- <term>
（那只是Backus-Naur 范式, 或称BNF范式的一小部分。）
为了做到这一步，我们需要一个过程来识别term和将结果保存在某处，还需要另一个过程来识别、分辨’+’和’-‘，并生成适当的代码。但有个问题，如果Expression过程准备把它的结果放在DO寄存器中，Term过程的结果应该放在哪里呢？答案是：同样的地方。在得到第二个Term的结果之前，我们不得不把第一个结果在某处保存起来。
OK，我们想要做的基本上就是让Term过程完成刚才Expression做的工作。所以只需要将Expression过程重命名为Term就可以了，并输入Expression过程的新版本。
{---------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
Term;
EmitLn('MOVE D0,D1');
case Look of
'+': Add;
'-': Subtract;
else Expected('Addop');
end;
end;
{--------------------------------------------------------------}
下面，在Expression过程之前输入下面两个过程。
{--------------------------------------------------------------}
{识别并翻译一个加法运算}
procedure Add;
begin
Match('+');
Term;
EmitLn('ADD D1,D0');
end;
{-------------------------------------------------------------}
{识别并翻译一个减法运算}
procedure Subtract;
begin
Match('-');
Term;
EmitLn('SUB D1,D0');
end;
{-------------------------------------------------------------}
输入完上述各个过程后，它们之间的顺序应该是：
o Term（实际上是原来的Expression版本）
o Add
o Subtract
o Expression
现在运行这个程序。试着输入你能想到的任何两个单数字，并把它们用’+’或’-‘连接起来。每次运行都会生成四条汇编指令。现在试着输入一些精心设计的包含错误的表达式。分析器捕捉到这些错误了吗？
看一下运行后生成的代码。有两处值得我们注意。首先，这些代码不像我们手写的代码，有点别扭。比如代码序列：
MOVE #n,D0
MOVE D0,D1
它是低效的。假如我们手工写这些代码的话，我们一般会将数据直接放到D1中。
关于这点有以下说明：编译器生成的代码一般比我们手写的代码效率要低。记住这点。它将会贯穿在我们的整个教程中。所有的编译器都不同程度地存在这个问题。许多计算机科学家将花了毕生心血来研究代码优化问题，也确实有一些成果可以用来提高目标代码质量。有些编译器在代码优化方面就做得很好，但是也由于其复杂性而卖得很贵，总之这是一个被遗忘的战场……在这部分结束之前，我会简要地介绍一些优化的方法，它们能完成一些轻度的优化，但这只是为了告诉你我们的确能够对代码做某些优化而不用费太多麻烦。请记住，这里我们只是为了学习，而不是为了检验我们到底能生成多么紧凑的目标代码。后面我们将故意忽略代码优化问题，将注意力集中在如何使生成的代码能正常的运行起来。
但是现在我们的程序还不能做到这点！生成的代码还有错误！出错的地方是做减法时，从D0（保存第一个参数）中减去D1（保存第二个参数）。这种方法是错误的，所以最后结果的符号错误。下面完善Subtract过程，补充进对符号的修改，
{-------------------------------------------------------------}
{识别并翻译一个减法运算}
procedure Subtract;
begin
Match('-');
Term;
EmitLn('SUB D1,D0');
EmitLn('NEG D0');
end;
{-------------------------------------------------------------}
现在我们的代码虽然效率低一点，但至少能给出正确的结果了！然而不幸的是，这种规则能表明数学表达式的意义，但表达式中term出现的次序我们却不太习惯。没办法，这只是你必须学会适应的的诸多方面之一。这一点我们在讲到除法时还会遇到。
OK，到这一步我们已经能让分析器识别两数的和与差了。早先我们还只能让它识别单个数字。但是实际问题中碰到的表达式，其形式都是任意的。输入单数字“1”运行程序，看看有没有问题。
它没有正常工作，是吗？为什么呢？因为前面我们告诉过分析器，表达式的唯一合法形式是有两个term的情况。我们必须重写Expression过程使其能处理更多的情况。一个真正的分析器快要成型了。
一般表达式
在实际问题中，一个表达式可以由一个或多个term组成，其间用“加法运算符” （’+’或‘-’）分割。用BNF的形式可以写作：
<expression> ::= <term> [<addop> <term>]*
我们可以向Expression过程加入一个简单的循环来描述这个新定义。
{---------------------------------------------------------------}
{ 分析并翻译表达式}
procedure Expression;
begin
Term;
while Look in ['+', '-'] do begin
EmitLn('MOVE D0,D1');
case Look of
'+': Add;
'-': Subtract;
else Expected('Addop');
end;
end;
end;
{--------------------------------------------------------------}
现在我们已经前进了一大步！这个版本可以处理任意数目的term，并且我们只是增加了两条代码而已。进一步深入的话，你会发现这是自顶向下分析器的特性……它只需要增加少量的代码就可以处理对这种语言的扩展。这就使得我们对分析器逐步改进的方案有可能实现。也要注意到，Expression过程的代码与表达式的BNF定义是十分匹配的，这也是此种方法的一个特性。当你精通这种方法后，会发现你很快就能将一个BNF表达式转换成对应的分析器代码。
OK，编译这个分析器的新版本，试运行它。像往常一样，验证这个“编译器“是否能处理任何合法的表达式，是否会对非法形式给出有意义的出错信息。它运行得还不错，是吗？你也许会发现在我们的试验版本中，出错信息是和生成的代码混杂在一起输出的。那只是因为我们在试验中是使用的显示器作为输出。在实际的产品中，会有两个分割开的输出，一个是输出文件，一个是输出到屏幕。
使用栈
以前我一直坚持在解释代码中的问题时，除非绝对有必要，否则不会引入任何复杂的理论，但是这里我准备打破这一点。目前的情况是，分析器使用D0作为主寄存器，用D1存放中间结果。迄今为止，它还工作良好，因为我们处理的只是“加法运算符”’+’和’-‘，只要一发现有新的term出现，它就被加到结果当中。但一般来说这是不完善的。考虑一下这个表达式
1+(2-(3+(4-5)))
假如我们把1放到D1中，那把2放到哪里？
幸运的是，有个简单的解决办法。像任何现代的微处理器一样，68000也有实现栈的结构，而栈是保存一系列数据的绝佳场所。所以不需要把term从D0转移到D1中，我们只要将它压入栈里就可以了。68000汇编中，压栈操作的语句是
-(SP)
而出栈则写作， (SP)+ .
好，我们把Expression过程中的EmitLn语句改为：
EmitLn('MOVE D0,-(SP)');
两条包含Add和Subtract的语句分别改为
EmitLn('ADD (SP)+,D0')
和 EmitLn('SUB (SP)+,D0'),
现在试运行分析器，以保证我们的更改没有破坏它。现在生成的代码比以前效率更低了，但是这是不可避免的。
乘法和除法
现在开始处理一些真正麻烦的事。你知道，除了“加法运算符”还有其他一些数学运算符……表达式还可以有乘法和除法运算符。你也知道，在表达式各运算符之间存在优先级的关系，所以如下表达式
2 + 3 * 4,
我们会认为是先做乘法，后做加法。（回头看看为什么我们需要用栈？）
在编译器技术发展的早期，人们用一些相当复杂的技术来实现各运算符之间的优先级关系。但那已经过时了，用自顶向下分析技术我们能漂亮地实现这些规则。现在为止，我们所考虑的term的形式一直都只是单个的十进制数字。
更一般地，我们将term定义成由因子（factor）的组合所生成的东西，也就是说，
<term> ::= <factor> [ <mulop> <factor ]*
什么是因子？现在我们对它的理解，因子就是过去讲的term……单个数字。
注意如下的对称性：term与表达式有着同样的形式。实际上，我们可以把处理表达式的过程稍做修改并重新命名为处理因子的过程，然后添加到分析器中。但为了避免混淆，下面列出的是分析器的最新完整代码。（注意我们在Divide过程中处理顺序颠倒的操作数所用的方法。）
{---------------------------------------------------------------}
{ 分析并翻译一个因子 }
procedure Factor;
begin
EmitLn('MOVE #' + GetNum + ',D0')
end;
{--------------------------------------------------------------}
{ 识别并翻译乘法运算}
procedure Multiply;
begin
Match('*');
Factor;
EmitLn('MULS (SP)+,D0');
end;
{-------------------------------------------------------------}
{识别并翻译除法运算}
procedure Divide;
begin
Match('/');
Factor;
EmitLn('MOVE (SP)+,D1');
EmitLn('DIVS D1,D0');
end;
{---------------------------------------------------------------}
{分析并翻译Term}
procedure Term;
begin
Factor;
while Look in ['*', '/'] do begin
EmitLn('MOVE D0,-(SP)');
case Look of
'*': Multiply;
'/': Divide;
else Expected('Mulop');
end;
end;
end;
{--------------------------------------------------------------}
{识别并翻译加法运算}
procedure Add;
begin
Match('+');
Term;
EmitLn('ADD (SP)+,D0');
end;
{-------------------------------------------------------------}
{识别并翻译减法运算}
procedure Subtract;
begin
Match('-');
Term;
EmitLn('SUB (SP)+,D0');
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ 分析并翻译表达式}
procedure Expression;
begin
Term;
while Look in ['+', '-'] do begin
EmitLn('MOVE D0,-(SP)');
case Look of
'+': Add;
'-': Subtract;
else Expected('Addop');
end;
end;
end;
{--------------------------------------------------------------}
好家伙！一个接近于实用的分析器/翻译器，只有55行的pascal语言源程序！假如你继续忽略它的效率问题，那这个输出看起来就很有用，我也希望你忽略效率问题。记住，我们的目的并不是要生成很紧凑的代码。
(未完待续）
