本节中，我们将展现一种抽象栈机器，并显示如何为它生成代码。该机器有独立的指令和数据内存，所有的算术运算都对栈上的值进行。指令非常有限，分为3类：整数运算，栈操纵和控制流。Fig 2.31演示该机器。pc指针标示我们即将执行的指令。指令的含义后面马上讨论。
pc指针是我们将要执行的指令。指令的含义很快将在后面讨论。
Arithmetic Instructions
抽象机器必须实现中间语言的每一个操作符。一个基本的操作符，例如加或者减，被抽象机器直接支持。但是，更加复杂的操作符，可能需要被实现为一个抽象机器指令的序列。我们简化机器的描述，通过假设每一个算术操作符都有对应的抽象机器指令。
一个算术表达式的抽象机器代码用一个栈模拟了该表达式后缀表现形式的计算。计算过程从左到右处理后缀表达形式，碰到操作数就把它压入栈中。在碰到一个k-ary的操作符时，它最左边的参数是栈顶下面k-1位置，而最右边的参数是栈顶。计算把操作符应用到栈顶的k个值，弹出操作数，然后把结果压回栈。例如，在计算后缀表达式1 3 + 5 *，执行下面的动作：
- Stack 1
- Stack 3
- 把最顶上的两个成员相加，弹出它们，把结果4压回栈
- Stack 5
- 把最顶上的两个成员相乘，弹出它们，把结果20压回栈
最后留在栈顶的值（这里的20）就是整个表达式的值。
在中间语言中，所有的值都是整数，其中0对应false，而非零对应true。boolean操作符and 和or需要他们的参数都被计算。
L-values and R-values
赋值左边和右边的标识符具有不同的含义。在每一个赋值中：
i := 5;
i := i + 1;
右边指定一个整数值，而左边指定值将被存储的地方。类似的，如果p和q是指向字符的指针，而且
p↑ := q↑;
右边q↑指定一个字符，而p↑指定字符将要被保存的地方。术语l-value左值和r-value右值，分别指一个赋值的左边和右边的值。也就是，我们通常把r-value考虑为值，而把l-value考虑为位置。
Stack Manipulation
除了把一个整数常量压到栈上以及从栈顶弹出一个值这些明显的指令之外，还有一些指令用来存取数据内存：
push v 把v压入栈
rvalue l 压入数据位置l的内容
lvalue l 压入数据位置l的地址
pop 丢掉栈顶值
:= 栈顶的rvalue放入它下面的lvalue中，两者都被弹出
copy 压入一个栈顶值的拷贝
Translation of Expressions
在一个栈机器计算一个表达式的代码和该表达式的后缀记法紧密相关。按照定义，表达式E + F的后缀形式是E的后缀形式，F的后缀形式，以及+的连接。类似的，计算E+F的栈机器代码，是计算E的代码，计算F的代码，以及增加他们值的指令的连接。把表达式翻译为栈机器代码，因此可以通过修改Section 2.6和2.7的翻译器完成。
这里我们为表达式生成栈代码，其中的数据位置用符号地址（标识符的数据位置分配在第7章讨论）。表达式a+b翻译为：
rvalue a
rvalue b
+
把赋值翻译为栈机器代码的过程如下：
分配给标识符的l-value被压入栈，表达式被计算，它的右值被分配给标识符。例如，赋值
day := (1461*y) div 4 + (153*m + 2) div 5 + d (2.17)
翻译为Fig. 2.32的代码
lvalue day
push 1461
rvalue y
*
push 4
div
push 153
rvalue m
*
push 2
+
push 5
div
+
rvalue d
+
:=
Fig. 2.32 Translation of day := (1461*y) div 4 + (153*m + 2) div 5 + d
形式化的表达如下。每一个非终结符具有一个属性t给出他的翻译。id的属性lexeme给出这个标识符的字符串表现形式
stmt → id := expr
{ stmt.t := 'lvalue' || id.lexeme || expr.t || ':='}
Control Flow
栈机器按照数字序列执行指令，除非用一个条件或无条件跳转指令告诉它其它事情。可以用几种方法指定跳转的目标：
- 指令操作数给出目标位置
- 指令操作数指定跳转的相对位置，正的或负的
- 用符号指定目标，也就是是说，机器支持标签
我们为抽象机器选择第3种选择，因为容易生成这样的跳转。另外，如果我们之后为抽象机器生成代码，不需要对符号地址进行改变，我们在代码中进行一定的改进，导致指令的插入和删除。
栈机器的控制流指令是：
label l 掉转到l的目标，没有其它影响
goto l 下一条指令取自具有label l 的语句
gofalse l 弹出栈顶值，为0则跳转
gotrue l 弹出栈顶值，非0则跳转
halt 停止执行
Translation of Statements
Fig. 2.33的布局勾勒了条件语句和while语句的抽象机器代码。下面的讨论集中在如何创建label标签。
考虑Fig. 2.33中if语句的代码布局。在一个源程序的翻译中，只能有一条label out指令，不然的话goto out语句就不知道跳转到哪个out去了。因此，我们需要某中机制，每次一个if语句被翻译的时候，生成一个唯一的标签。
假设newlabel是一个每次被调用就返回一个新标签的过程。在下面的语义动作中，对newlabel调用返回的新标签用一个局部变量out纪录下来：
stmt → if expr then stmt1 { out := newlabel;
stmt.t := expr.t ||
'gofalse' out || (2.18)
stmt1.t ||
'label' out}
Emitting a Translation
Section 2.5中表达式翻译器使用print语句增量地生成一个表达式的翻译。类似的print语句可以用来生成语句的翻译。取代print语句，我们用一个过程emit来隐藏打印的细节。例如，emit能够关心是否每一条抽象机器指令需要在单独的一行。使用过程emit，我们可以把(2.18)写成。
stmt → if
expr { out := newlabel; emit('gofalse', out); }
then
stmt1 {emit('label', out); }
当语义动作出现在一个产生式中间时，我们用从左到右的顺序考虑产生式的右边。对上面的产生式，动作的顺序如下：在expr解析动作完成后，out被设置为newlabel返回的标签，gofalse指令被输出，stmt1解析动作完成后，最后label指令被输出。假设expr和stmt1输出这些非终结符的代码，那么上面的产生式实现Fig. 2.33的代码布局。
procedure stmt;
var out:integer;
begin
if lookahead = id then begin
emit('lvalue', tokenval);match(id);match(':=');expr
end
else if lookahead='if' then begin
match('if');
expr;
out := newlabel;
emit('goflase', out);
match('then');
stmt;
emit('label', out);
end
/* code for remaining statements goes here */
else error;
end
Fig 2.34. Pseudo-code for translating statements.
翻译赋值语句和条件语句的伪代码如Fig 2.34所示。因为变量是过程stmt的局部变量，它的值不受对expr和stmt过程的调用。标签的生成需要一些考虑。假设翻译中的标签是L1, L2,.....。操纵这样标签的伪代码使用L后跟整数。因此，out被定义为一个整数，newlabel返回一个整数变成out的值，emit用这个整数输出标签。
while语句的代码布局也可以用类似的方法产生。对一系列语句的翻译就是简单地把序列的语句串起来。
绝大多数单入口，但出口的构造都可以类似while语句一样翻译。我们通过考虑表达式中的控制流来演示这一点。
Example 2.10 Section 2.7的词法分析器包含一个条件，以下形式：
if t == blank or t == tab then
如果t是一个空格，那么显然没有必要检查t是否一个tab，因为第一个等号已经隐含条件为真。表达式
epr1 or expr2
因此可以实现为
if expr1 the true else expr2
读者可以检查下面的操作实现or操作符：
code for expr1
copy
gotrue out
pop
code for expr2
lable out
回忆一下，为了简化条件和while语句的代码生成，gotrue和gofalse指令弹出栈顶值。通过copy expr1的值，我们确保栈顶的值为true，如果gotrue指令导致一个跳转的话。
没有评论:
发表评论