发布时间 : 星期一 文章第八章 语法制导翻译和中间代码生成更新完毕开始阅读ce62181b650e52ea5518982d
第8章 语法制导翻译和中间代码生成
3 4 5 6 7 8 9 10 11 s5 s5 s5 r4 r6 r6 r1 r3 r5 r4 r6 s7 r3 r5 s4 s4 s4 r4 r6 s11 r1 r3 r5 r4 r6 r1 r3 r5 8 2 9 3 3 10
同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在例8.1的属性文法中描述的语义动作。每步工作后的语义值保存在扩充的分析栈里\语义值\栏中。采用的LR分析表见图8.6，其中使用d代替digit。分析和计值2+3*5的过程列在图8.7中。
图8.7 2+3*5的分析和计值过程 步骤 归约动作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
按照上述实现办法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法分析的制导下，随着分析的进展逐步生成中间代码。
r6 r4 r2 r6 r4 r6 r3 t1 接受
状态栈 0 05 03 02 01 016 0165 0163 0169 01697 016975
01697（10） 0169 01
语义栈（值栈） - -- -2 -2 -2 -2- -2-- -2-3 -2-3 -2-3- -2-3-- -2-2-5 -2-（15） （17）
符号栈 # #2 #F #T #E #E+ #E+3 #E+F #E+T #E+T· #E+T·5 #E+T·F #E+T #E
留余输入串
2+3*5# +3*5# +3*5# +3*5# +3*5# 3*5# *5# *5# *5# 5# # # # #
第8章 语法制导翻译和中间代码生成
8.3 中间代码的形式
编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。下面分别将它们做一介绍。
8.3.1 逆波兰记号
逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。
这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。图8.8给出了程序设计语言中的简单表达式和赋值语句相应的逆波兰表示形式：
图 8.8 逆波兰表示
程序设计语言中的表示 a+b a+b*c (a+b)*c a;=b*c+b*d 逆波兰表示 ab+ abc*+ ab+c* abc*bd*+:=
后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。
例如 B@CD*+（它的中缀表示为－B+C*D，使用@表示一目减）的计值过程为： 1. B进栈；
2. 对栈顶元素施行一目减运算，并将结果代替栈顶，即－B置于栈顶； 3. C进栈； 4. D进栈；
5. 栈顶两元素相乘，两元素退栈，相乘结果置栈顶；
6. 栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。 由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。
逆波兰表示很容易扩充到表达式以外的范围。在图8.8中已见到了赋值语句的后缀表示的例子。只要遵守运算对象后直接紧跟它们的运算符的规则即可。比如把转语句GOTO L写为\，运算对象L为语句标号，运算符jump表示转到某个标号。再比如条件语句if E then S1 else S2可表示为：ES1S2￥，把if then else看成三目运算符，用￥来表示。又如数组元素A[〈下标表达式1〉，…〈下标表达式n〉]可表示为〈下标表达式1〉〈下标表达式2〉……〈下标表达式n〉A subs，运算符Subs表示求数组的下标。
当然，这些扩充的后缀表示的计值远比后缀表达式的计值复杂得多，要注意对新添加的运算符的含义正确处理。以图8.8中的赋值语句为例，当计算到∶=时，执行的是将表达式B*C+B*D的值送到变量a，所以，而在执行完赋值后，栈中并不产生结果值，这与算术的二目运算符是不一样的，另外，因为需要的是a的地址，而不是a的值，这也必须注意到。
第8章 语法制导翻译和中间代码生成
8.3.2 三元式和树形表示
另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式。每个三元式由三个部分组成，分别是：算符op，第一运算对象ARG1和第二运算对象ARG2。运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。例如a∶ =b*c+b*d的表示为： （1）（*， b，c） （2）（*， b，d） （3）（+ （1）， （2）） （4）（∶＝ （2）， a）
与后缀式不同，三元式中含有对中间计算结果的显式引用，比如三元式（1）表示的是b*c的结果。三元式（3）中的（1）和（2）分别表示第一个三元式和第二个三元式的结果。
对于一目算符op，只需选用一个运算对象，不妨规定只用ARG1。至于多目算符，可用若干个相继的三元式表示。
树形表示是三元式表示的翻版。上述三元式可表示成下面的树表示：
表达式的树形表示很容易实现：简单变量或常数的树就是该变量或常数自身，如果表达式e1和e2的树分别为T1和T2，那么e1+e2，e1*e2，－e1的树分别为：
二目运算对应二叉子树，多目运算对应多叉子树，不过，为了便于安排存储空间，一棵多叉子树可以通过引进新结而表示成一棵二叉子树。
8.3.3 四元式
四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG@及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a∶=b*c+b*d的四元式表示如下： （1）（*， b， c， t1） （2）（*， b， d， t2） （3）（+， t1， t2， t3） （4）（∶=，t3， －， a）
四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。
也许读者已经发现，四元式表示很类似于三地址指令，确实，有时把这类中间表示称为\三地址代码\，因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条\指令\包含操作符和三个地址，两个是为运算对象的，一个是为结果的。这种表示对于代码优化和目标代码生成都较有利。
第8章 语法制导翻译和中间代码生成
有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成： （1）t1∶=b*c （2）t2∶=b*d （3）t3∶=t1+t2
（4）a∶=t3
把（jump，－，－，L）写成goto L
把（jrop，B，C，L）写成if B rop C goto L
本书中，为了叙述的方便，两种形式将同时使用。
如何用四元式表示各种语句，以及翻译各种语句的语义描述，将在后面各节陆续讨论。 为了复习与巩固一下前面所学习的几种中间代码的形式，下面举一个例子，分别用几种中间代码的形式来表示
例 : A + B * ( C - D ) + E / ( C - D ) ^N ^ 四元式：
（1）（ - C D T1） （2）（* B T1 T2） （3）（+ A T2 T3） （4）（－ C D T4） （5）（^ T4 N T5） （6）（/ E T5 T6） （7）（+ T3 T6 T7）
三元式： （1）（－ C D） （2）（* B （1）） （3）（+ A （2））
（4）（－ C D） （5）（^ （4） N）
（6）（/ E （5）） （7）（+ （3） （6））
间接三元式：间接三元式序列 （1）（－ C D） （2）（* B （1）） （3）（+ A （2）） （4）（ （1） N） （5）（/ E （4）） （6）（+ （3） （5）） 间接码表 （1） （2） （3） （1） （4） （5） （6）