法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。
与抽象语法相对应的语法树称为抽象语法树或抽象树 2．逆波兰表示法
逆波兰表示法把运算量(操作数)写在前面，把运算符写在后面，因而又称后缀表示法。例如，把a+b写成ab+，把a*(b+c)写成abc+*。 表达式E的后缀表示的递归定义如下：
(1) 如果E是变量或常数，则E的后缀表示即E自身。
(2) 如果E为E1 op E2形式，则它的后缀表示为E1'E2'op；其中op是二元运算符，而E1'、E2'分别又是E1和E2的后缀表示。若op为一元运算符，则视E1和E1'为空。
(3) 如果E为(E1)形式，则E1的后缀表示即为E的后缀表示 为了用逆波兰式表示一些控制语句，我们定义转移操作如下： (1) BL：转向某标号； (2) BT：条件为真时转移； (3) BF：条件为假时转移； (4) BR：无条件转移。 部分程序语句的逆波兰表示：
(1) 赋值语句。赋值语句“<左部>=<表达式>”的逆波兰表示为 <左部><表达式>=
(2) GOTO语句。转向语句“GOTO<语句标号>”的逆波兰表示为 <语句标号>BL
其中，“BL”为单目后缀运算符，“<语句标号>”则为BL的一个运算分量。
(3) 条件语句。BR表示无条件转移单目后缀运算符。例如，“<顺序号>BR”表示无条件转移到“<顺序号>”处，这里的顺序号是BR的一个特殊运算分量，用来表示逆波兰式中单词符号的顺序号(即第几个单词)，它不同于GOTO语句中的语句标号。BT和BF表示按条件转移的两个双目后缀运算符。例如： <布尔表达式e的逆波兰式><顺序号>BT <布尔表达式e的逆波兰式><顺序号>BF
(4) 循环语句。for循环语句为：for(i=m；i<=n；i++)S；其中，i为循环控制变量，m为初值，n为终值，S为循环体。循环语句不能直接用逆波兰表示，因而将其展开为等价的条件语句后再用逆波兰表示，即 i=m；
10：if(i<=n) { S； i=i+1； goto l0 }
3． 三地址代码
三地址代码语句的一般形式为 x=y op z
其中，x、y和z为名字、常量或编译时产生的临时变量；op为运算符，如定点运算符、浮点算符和逻辑运算符等。三地址代码的每条语句通常包含三个地址，两个用来存放运算对象， 表达式及赋值语句的翻译
例2-4 试分析赋值语句X= ?B*(C+D)的语法制导翻译过程。 [解答] 赋值语句X=?B*(C+D)的语法制导翻译过程如表所示
表2-1 赋值语句X=?B*(C+D)的语法制导翻译过程
输入串 X=?B*(C+D)
#
=?B*(C+D)#
?B*(C+D)#
B*(C+D)#
*(C+D)#
*(C+D)#
*(C+D)#
归约产生式 (6) (6) (4)
符号栈 # #i #i= #i=?
#i=?i
#i=?E #i=E
语义栈(place)
_ _X _X_
_X_ _
_X_ _B
_X_ _B
_X_T1
四元式
(uminus,B, _,T)
(C+D)# C+D)# +D)# +D)# D)# )# )# )# # # # #
(6) (6) (2) (5) (3) (1)
#i=E* #i=E*( #i=E*(i #i=E*(E #i=E*(E+ #i=E*(E+i #i=E*(E+E
#i=E*(E #i=E*(E) #i=E*E #i=E #A
_X_T1_ _X_T1_ _ _X_T1_ _C _X_T1_ _C _X_T1_ _C_ _X_T1_ _C_D _X_T1_ _C_D
_X_T1_ _T2 _X_T1_ _T2_ _X_T1_T2 _X_T3 _X
(+,C,D,T2)
(*,T1,T2,T3) (=,T3, _,X)
控制语句的翻译
在源程序中，控制语句用于实现程序流程的控制。一般程序流程控制可分为下面三种基本结构：
(1) 顺序结构，一般用复合语句实现； (2) 选择结构，用if和case等语句实现；
(3) 循环结构，用for、while、do(即repeat)等语句实现。 三种基本控制结构的文法G[S]如下： G[S]： (1) S→CS (2) ∣TP S (3) ∣Wd S (4) ∣{L}
(5) ∣A /*A代表赋值语句*/ (6) L→LS S (7) ∣S (8) C→if(E) (9) TP→CS; else (10) Wd→W(E) (11) W→while (12) LS→L;
G[S]中各产生式对应的语义子程序如下：
(1) S→C S(1) {S.chain=merge(C.chain, S(1).chain);} (2) S→TP S(2) {S.chain=merge(TP.chain, S(2).chain);} (3) S→Wd S(1) {Backpatch(S(1) .chain, Wd.quad); emit(j,_,_,Wd.quad); S.chain=Wd.chain;} (4) S→{L} {S.chain=L.chain};} (5) S→A {S.chain=0; /*空链*/ } (6) L→LS S(1) {L.chain=S(1).chain} (7) L→S {L.chain=S.chain} (8) C→if(E) {Backpatch(E.tc, nxq); C.chain=E.fc;} (9) TP→C S(1) ; else {q=nxq; emit(j,_,_,0);
Backpatch(C.chain, nxq); TP.chain=merge(S(1).chain,q);} (10) W→while {W.quad=nxq;} (11) Wd→W(E) {Backpatch(E.tc, nxq); Wd.chain= E.fc; Wd.quad= W.quad;} (12) LS→L; {Backpatch(L.chain, nxq);} 数组元素的引用和赋值就有如下两种不同的四元式：
(1) 变址存数：若有T1[T]=X，则可以用四元式([ ]=，X，_，T1[T])表示。 (2) 变址取数：若有X=T1[T]，则可用四元式(=[ ]，T1[T]，_，X)表示。 例2-5 试给出下列语句的四元式序列： if (p1==0∧p2＞10) X[1,1]=1; else X[7,6]=0;
其中，X是10×20的数组(每维下界为1)且按行存放；一个数组元素占用两个字节，机器按字节编址。
[解] 拓展数组元素翻译的语义子程序功能，得到该语句对应的四元式序列如下： 100 (j=, P1, 0, 102)
101 (j,_, _,110) 102 (j>,P2,10,104) 103 (j, _,_,110) 104 (*,1,40,T1)
105 (*,1,2,T2) 106 (+,T1,T2,T3) 107 (?,X,42,T4) 108 ([ ]=,1, _,T4[T3]) 109 (j, _,_,115) 110 (*,7,40,T1) 111 (*,6,2,T2) 112 (+,T1,T2,T3) 113 (?,X,42,T4) 114 ([ ]=,0, _,T4[T3]) 115
第5章 代码优化
主要内容： 1 局部优化 2 循环优化 3 代码优化示例
代码优化的任务是：产生的中间代码进行等价变换，使生成的目标代码更为高效（时间和空间）。优化的目的主要是提高运行效率，节省存储空间。优化主要有两类，一是与机器有关的优化，主要设计如何分配寄存器，如何选择指令，这类优化是在生成目标代码时进行的；另一类优化与机器无关，主要是对中间代码的优化。
根据优化所涉及的程序范围，优化又分为局部优化，循环优化，全局优化。一个程序从结构上看，作为终点的基本块是其基础。因为基本块的够最简单、因素最单纯，左翼它也是优化的基础，对基本块的优化就是局部优化。循环是程序中要反复执行的部分，优化的效益当然很大，所以循环优化是优化工作的重点。针对整个程序的优化即全局优化，它涉及到对策划能够许数据流分析的问题。 局 部 优 化
局部优化是指对代码的每一个线性部分所进行的优化，使得在这个线性部分只存在一个入口和一个出口，而这个线性部分我们称之为基本块。