编 译 原 理 指导教师:杨建国 二零一零年三月

第八章 语法制导翻译和中间代码生成 第一节 属性文法 第二节 语法制导翻译概论 第三节 中间代码的形式 第四节 简单赋值语句的翻译 第八章　语法制导翻译和中间代码生成 第一节 属性文法 第二节 语法制导翻译概论 第三节 中间代码的形式 第四节 简单赋值语句的翻译 第五节 布尔表达式的翻译 第六节 控制结构的翻译 第七节 说明语句的翻译 第八节 数组和结构的翻译

知识结构

第八章 语法制导翻译和中间代码生成 8.1 属性文法 语义处理的功能： 静态语义审查：验证语法结构合法的程序是否真正有意义 第八章　语法制导翻译和中间代码生成 8.1　属性文法 语义处理的功能： 静态语义审查：验证语法结构合法的程序是否真正有意义 翻译：生成中间代码或目标代码

静态语义审查： 类型检查：验证程序中执行的每个操作是否遵守语言 　的类型系统的过程，编译程序必须报告不符合类型系 　统的信息 控制流检查：控制流语句必须使控制转移到合法地方 一致性检查：在很多场合要求对象只能被定义一次 相关名字检查：有时，同一名字必须出现两次或多次 名字的作用域分析：

中间代码（中间语言）： 是复杂性介于源程序语言和机器语言的一种表示形式 一般，快速编译程序直接生成目标代码 为了使编译程序结构在逻辑上更为简单明确，常采用中间 　代码，这样可以将与机器相关的某些实现细节置于代码生 　成阶段仔细处理，并且可以在中间代码一级进行优化工作 　使得代码优化比较容易实现

语义分析的任务: 翻译说明语句，把名字的属性登记到符号表中 翻译可执行语句，设计出目标代码结构，给出变换方 法，将可执行语句变换为目标代码

一个属性文法是一个三元组A＝（G，V，F）： 　系, 可以是“类型”、“值”或“存储位置” F 中的每个断言与文法的某个产生式相对应, 可以是语 　义规则或者程序段等 因此可知, 一个属性文法包含一个上下文无关文法和 　一系列语义规则， 这些语义规则附在每个产生式上

例如文法G为： E　　T1+T2| T1 or T2 T　　num| true |false 对输入串3+4的语法树如图： 图8.1 静态语义审查

属性文法记号中常使用N.T的形式表示与非终结符N相 类型检查的属性文法如下: E→T1+T2 { T1.type = int AND T2.type =int } E→T1 or T2 { T1.type = bool AND T2.type =bool } T →num { T.type := int } T → true { T.type := bool } T → false { T.type := bool }

属性文法最早由克努特(D.E.Knuth)提出，他把属性分成： 　继承属性、综合属性 属性文法中，对应于每个产生式A　　a都有一套与之相关 　联的语义规则，每条规则的形式为b:=f(c1,c2,…,ck)。 　f是一个函数，b和c1,c2,…,ck是该产生式文法符号的属性 （1）如果b是A的一个属性，c1,c2,…,ck是产生式右部文法 　符号的属性或A的其他属性，则称b是A的综合属性 （2）如果b是产生式右部某个文法符号X的一个属性，并且 　c1,c2,…,ck是A或产生式右边任何文法符号的属性，则称b 　是文法符号X的继承属性

对每个产生式，设属性定义性出现的集合为 若Xi是产生式左部非终结符（即i=0），则称属性Xi.a是综 合属性（SynthesizedAttributes） 若Xi出现在产生式的右部（即），则称Xi.a是继承属性（ Inherited Attributes） 例如：Ap Xq,r Ys,t [p=q+s,r=p+t]其中，p、q、r、s、t 　是属性，分别属于A、X和Y，则： 　p是综合属性，r是继承属于，而q、s、t的性质不能确定

在计算时： 综合属性沿属性语法树向上传递 继承属性沿属性语法树向下传递 若产生式左部的单非终结符A的属性值由右部各非终结符的 　属性值决定, 则A的属性称为综合属性 若产生式右部符号B的属性值是根据左部非终结符的属性值 　或者右部其它符号的属性值决定的,则B的属性为继承属性

在两种情况下，我们说属性b依赖于属性c1,c2,…,ck 　(1)非终结符既可有综合属性也可有继承属性，但文法开 始符号没有继承属性 （2）终结符只有综合属性，它们由词法程序提供

例8.1　简单算术表达式求值的语义描述： 　产生式　　　　　　　　　　语义规则　 　（0）L　　En　　　　　　　print(E.val) 　（1）E　　E1+T　　　　　 E.val:=E1.val+T.val 　（2）E　　T　　　　　　　 E.val:=T.val 　（3）T　　T1*F　　　　　 T.val:=T1.val×F.val 　（4）T　　F　　　　　　　 T.val:=E.val 　（5）F　　(E)　　　　　　　F.val:=E.val 　（6）F　　digit　　　　　　 F.val:=digit.lexval 　E、T和F的val属性是综合属性,digit仅有综合属性，它 　的值是由词法分析程序提供的，L的属性是空的，n换行符

例8.2　描述说明语句中各种变量的类型信息的语义规则： 产生式　　　　　　　　　　语义规则　 　（1）D　　TL　　　　　　L.in:=T.type 　（2）T　　int　　　　　　 T.type:=integer 　（3）T　　real　　　　　 T.type:=real 　（4）L　　L1,id　　　　　 L1.in:=L.in 　　　　　 addtype(id.entry,L.in) 　（5）L　　id　　　　　　　addtype(id.entry,L.in) 过程addtype的功能是把每个标识符的类型信息登录在符号 表的相关项中 T的综合属性type,它的值由(int或real)决定,L.in是继承属性

图8.3是句子 int id1,id2的语法树，使用　　表示属性的传递情况 图8.3　属性信息传递情况

8.2 语法制导翻译概论 语法制导翻译是指在语法分析过程中，完成附加在所 使用的产生式上的语义规则描述的动作 8.2　语法制导翻译概论 语法制导翻译是指在语法分析过程中，完成附加在所 　使用的产生式上的语义规则描述的动作 基于属性文法的处理过程（语法制导翻译）： 　　对单词符号串进行语法分析，构造语法分析树，然后 根据需要构造属性依赖图，遍历语法树并在语法树的各结 点处按语义规则进行计算

一.计算语义规则 依赖图：是一个有向图，用于描述分析树中的属性和属性 　间的相互依赖关系

依赖图的构造算法如下： 　for 分析树中每一个结点n do for 结点的文法符号的每一个属性a do 为a在依赖图中建立一个结点； 　for 分析树中每一个结点 n do for 结点n所用产生式对应的每一个语义规则　 b:=f(c1,c2,…,ck) do for i:=1 to k do 从ci结点到b结点构造一条有向边

例8.2的句子Real id1,id2,id3分析树的依赖图（图中的结点 　用数字表示）如图8.4： D T Real L , id3 id2 id1 5 in 3 entry 6 4 type 7 in 2 entry 8 9 in 1 entry 10

从依赖图的拓扑排序中，可以得到所有计算语义规则的顺 　序。用这个顺序来计算语义规则就得到输入符号串的翻 　译 属性计算有树遍历的和一遍扫描的方法

二.S－属性文法和自下而上翻译 S-属性文法是只含有综合属性的属性文法 综合属性可以在分析输入符号串的同时自下而上来计算 S－属性文法的翻译器通常可借助于LR分析器实现 分析器可以保存与栈中文法符号有关的综合属性值，每当 　进行归约时，新的属性值就由栈中正在归约的产生式右 　边符号的属性值来计算

对例8.1的输入串2+3*5语法树如图8.5：

假定有一个LR语法分析器，现在把它的分析栈扩充，使 　得每个文法符号都跟有语义值，即把栈的结构看成图8.6 　所示：

同时把LR分析器的能力扩大，使它不仅执行语法分析任 　务，还能在用某个产生式进行归约的同时调用相应的语 　义子程序，完成在例8.1的属性文法中描述的语义动作 每步工作后的语义值保存在扩充栈的“语义值栈”栏中 采用的LR分析表为表7.8，不过要将其中的i改为digit，分 　析和计值2+3*5的过程列在图8.7所示：

S5 S4 1 2 3 S6 acc r2 S7 r2 r2 r4 r4 r4 r4 S5 S4 8 2 3 r6 r6 r6 r6 S5 ACTION GOTO d + * ( ) # E T F 1 2 3 4 5 6 7 8 9 10 11 S5 S4 1 2 3 S6 acc r2 S7 r2 r2 r4 r4 r4 r4 S5 S4 8 2 3 r6 r6 r6 r6 S5 S4 9 3 S5 S4 10 S6 S11 r1 S7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5

-2-3-5 2+3*5的分析和计值过程

三.L－属性文法在自上而下分析中的实现 一个属性文法称为L－属性文法，如果对于每个产生式 　A　　X1X2…Xn,其每个语义规则中的每个属性或者是综 　合属性，或者是Xj(1≤j ≤n)的一个继承属性且这个继承 　属性仅依赖于： （1）产生式Xj在左边符号X1,X2,…Xj-1的属性 （2）A的继承属性

例8.2描述变量证明语句中类型信息的属性文法是L－属性 　文法 S－属性文法一定是L－属性文法，因为（1）、（2）限制 　只用于继承属性 L－属性文法允许一次遍历就计算出所有属性值

例8.3　将中缀表达式翻译成相应的后缀表达式的属性文法, 其中addop表示+或- E　　E addop T print(addop,Lexeme) | T T　　num print(num,val) 　　比如对串2+3-5的分析同时执行语义动作打印出23+5-

语法分析树中加虚线联结的语义结点，形成一个可说明语义 　动作的树，如图8.8：

LL(1)这种自上而下分析文法的分析过程，从概念上说可以 　看成是深度优先建立语法树的过程，因此，可以在自上而 　下语法分析的同时实现L属性文法的计算

例8.3是一个含左递归规则的文法，如采用LL（1）分析必 　须改写文法如下： E　　TR R　　 addop TR1｜ε T　　num 这时2+3-5的语法树如图8.9：

将后缀式23+-5输出的动作在语法树中应出现的位置如图 　8.10所示：

例8.4　（中缀表达式翻译成相应的后缀表达式）： E　　TR R　　 addop T｛print(addop,Lexeme)}R1｜ε T　　num {print(num.val)} 把语义动作嵌在右部文法符号T和R之间，这种语义处理的 　描述形式称为翻译模式 翻译模式是适合语法制导翻译的另一种描述形式 翻译模式给出了使用语义规则进行计算的次序，可把某些 　实现细节表示出来

一般转换左递归翻译模式的方法简述如下： 假设翻译模式为： A　　A1Y{A.a:=g(A1.a,Y.y)} A　　X {A.a:=f(X.x)} 每个文法符号都有一个综合属性，用相应的小写字母表示, 　g和f是任意函数。消除左递归，文法转换成： A　　XR R　　YR｜ε

再考虑语义动作，则翻译模式为，其中使用了R的继承属性 i和综合属性s: A　　X　　{R.i:=f(X.x)} R {A.a:=R.s} R　　Y {R1.i:=g(R.i,Y.y)} R1 {R.s:=R1.s} R　　ε {R.s:=R.i}

四.L－属性文法在自下而上分析中的实现 实现自下而上计算继承属性方法： 方法一：从翻译模式中去掉嵌入在产生式中间的动作 　引入新的非终结符N和产生式N　　ε，把嵌入在生产式中 间的动作用非终结符N代替，并把这个动作放在产生式后面

例如下面的翻译模式： E　　T R R　　+T{print(‘+’)}R1 R　　-T {print(‘-’)}R1 R　　ε T　　num{print(num,val)}

引入M和N，变换后的翻译模式如下，原嵌入在产生式中间 　的动作都在产生式后面了 E　　T R R　　+TMR1 R　　-T NR1 R　　ε T　　num{print(num,val)} M　　ε{print(‘+’)} N　　ε{print(‘-’)}

方法二：用综合属性代替继承属性，改变基础文法是一种可 　能的办法 例如，一个Pascal的说明由一标识符序列后跟类型组成，如 　m,n:integer。这种说明语句的文法可由下面的形式的产生 　式构成： D　　L:T T　　integer|char L　　L,id|id

一个解决的方法是重新构造文法，借以实现用综合属性代 　替继承属性 例如一个等价的文法如下： D　　id L L　　,id L |:T T　　integer|char 属性文法如下： D　　id L {addtype(id.entry,L.type)} L　　id L1{L.type:=L1.type:addtype(id.entry,L.type)} |:T{L.type:=T.type} T　　integer{T.type:=int}|char{T.type:=ch}

8.3 中间代码的形式 一.逆波兰式（后缀式）(后根遍历） 由波兰逻辑学家卢卡西维奇发明 这种表示法将运算对象写在前面，把运算符号写在后面 8.3　中间代码的形式 一.逆波兰式（后缀式）(后根遍历） 由波兰逻辑学家卢卡西维奇发明 这种表示法将运算对象写在前面，把运算符号写在后面 图8.11给出了程序设计语言中的逆波兰表示形式： 程序设计语言中的表示 逆波兰表示 a*b ab* a*b+c ab*c+ a*(b+c/d) abcd/+* a*b+c*d ab*cd*+

例如　B@CD*+（它的中缀表示：-B+C*D)的计值过程为： 5.栈顶两元素相乘，两元素退栈，相乘结果置栈顶 6.栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存 　放的是整个表达式的值

二.三元式和树形表示 每个三元式的组成：(op，ARG1，ARG2) 例如：a:=b*c+b*d (1)(*, b,c) (2)(* ,b,d) (3)(+ ,(1),(2)) (4)(:= ,(3),a) 树形表示是三元式表示 　的翻版，上述三元式可 　表示成右边的树表示：

表达式的树形表示很容易实现：简单变量或常数的树就是 　该变量或常数自身，如果表达式e1和e2的树分别为T1和 　T2，那么e1+e2,e1*e2,-e1的树分别为：

三.四元式 四元式的组成：(op，ARG1,ARG2,RESULT) 例如：a:=b*c+b*d (1)(*, b,c,t1) (2)(*, b,d,t2) (3)(+ ,t1,t2,t3) (4)(:= ,t3,－,a)

为了直观，也把四元式的形式写成简单赋值形式： (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,Tl) (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）（↑,（1）,N） （5）（/,E,（4）） （6）（+,（3）,（5）） 间接码表（1）（2）（3）（1） （4）（5）（6）间接码表表明 了执行间接三元式的顺序 ②表达式的三元式序列 (1)(－,C,D) (2)(*,B,(1)) (3)(+,A,(2)) (4)(－,C,D) (5)(↑,(4),N) (6) (/,E,(5)) (7)(＋，(3)，(6))

④逆波兰: ABCD-*+ECD-N↑/+ ⑤树形表示:

真题：（5分）在答题纸上给出下面表达式的逆波兰表示 　 （用@表示取负操作，用-表示减法操作） -a+b*(-c+d) 答案：a@bc@d+*+

例题：(上海交大2000年研究生试题) 　 语句 While A<B do if C<D then x:=F[i,j] else x:=x+l 经翻译后的三地址语句或四元式是什么？（设三 地址语句或四元式自 100 开始存放，数组 F 的内情向量 自 300 开始存放，数组首地址 500, 每个数组元素占四 字节。）

【解答】 内情向量表如图5.12所示，语句代码结构图如图5.13所示

按图5.13翻译后的四元式如下： 100　 (j<,A,B,102) 101　 (j,_,_,115) 102 　(j<,C,D,104) 103 　(j,_,_,113) 104 　(+,i,[309],T1) 　　　/*[309]为第二维长度d2*/ 105 　(+,j,T1,T2) 106 　(*,T2,4,T3) 　　　　　/*(i+d2+j)X4*/ 107 　(+,[309],1,T4) 　　　/*d2+1*/ 108　 (*,4,T4,T6) 　　　　/*(d2+1)X4*/ 109 　(-,500,T5,T6）　　　/*F的首地址500-(d2+1)X4*/ 110 　(＝[],T6[T3],_,T7) /*形成F[i,j]*/ 111 　(:=,T7,_,X) 　　　　/*X:=F[i,j]*/ 112 　(j,_,_,114) 113 　(+,X,1,X) 114 　(j,_,_,100) 115

8.4 简单赋值语句的翻译 简单赋值语句为不包含数组元素﹑记录的赋值语句 四元式的组成：(op，ARG1,ARG2,ti) 8.4　简单赋值语句的翻译 简单赋值语句为不包含数组元素﹑记录的赋值语句 四元式的组成：(op，ARG1,ARG2,ti) 赋值语句的四元式是怎么翻译的呢？

首先对id表示的单词定义－属性id.name，用做语义变 　量，用Lookup(id.name)语义函数审查id.name是否出现 　符号表中，如在，则返回一指向该登录项的指针，否 　则返回nil。 语义过程emit:表示输出四元式到输出文件上 语义过程newtemp:表示生成一临时变量，每调用一次， 生成一新的临时变量 语义变量E.place:表示存放E值的变量名在符号表的登录 项或一整数项（若此变量是一个临时变量）

图8.12列出了翻译赋值语句到四元式的语义描述： (1)Sid:=E { p:=lookup(id.name); if p≠nil then emit(p ‘:=’ E.place) else error} (2)EE1+E2 { E.place:=newtemp; emit(E.place ‘:=’ E1.place ‘+’ E2.place)} (3)EE1*E2 { E.place:=newtemp; emit(E.place ‘:=’ E1.place ‘*’ E2.place)}

(4)E-E1 { E.place:=newtemp; emit(E.place ‘:=’ ‘uminus’ E1.place)} (5)E(E1) { E.place := E1.place) (6)Eid { p:=lookup(id.name); if p≠nil then E.place:=p) else error}

图8.12中的第（3）条产生式及其有关语义描述如图8.13： ｛E．place∶=newtemp； if E1．type＝int AND E2．type＝int then begin emit（E.place，′∶=′，E1．place，′*i′, E2．place）； 　　　　　　E．type∶=int end else if E1．type＝real AND E2．type＝real then begin emit (E．place,′∶=′,E1．place,′*r′,E2．place); 　　　　　　E．type∶=real end

else if E1．type＝int/. and E2．type=real else if E1．type＝int/* and E2．type=real　*/　then begin t∶=newtemp； 　　　emit（t，′∶=′，′itr′，E1．place）； 　　　emit（E．place，′∶=′，t，′*r′，E2．place）； 　　　E．type∶=real end else　/*E1·type＝real and E2．type＝int*/ begin t∶=newtemp； 　　　emit（t，′∶=′；′itr′，E2．place）； 　　　emit（E．place，′∶=′，E1．place，′*r′,t）； 　　　E．type∶=real end； ｝

8.5　布尔表达式的翻译 布尔表达式的两个作用： 计算逻辑值 用做改变控制流语句中的条件表达式

布尔表达式是由布尔算符（not、and、or）施于布尔 　变量或关系表达式而成。即布尔表达式的形式为E1 　rop E2，其中E1和E2都是算术表达式，rop是关系符， 　如<=,<,=,>=, ≠

E　　E and E | E or E | not E | id rop id | true | false， 　按通常习惯，约定布尔算符的优先顺序（从高到低） 　为not、and、or，并且and 和 or 服从左结合

一.布尔表达式的翻译方法 步步计算出各部分的真假值，最后计算出整个表达式的值 如表达式: 1 or (not 0 and 0) or 0 布尔表达式：a or b and not c翻译成的四元式序列为： （1）t1:=not c （2）t2:=b and t1 （3）t3:=a or t2 采取某种优化措施，只计算部分表达式

对a<b可看成等价的条件语句if a<b then 1 else 0,它翻译成 　的四元式序列为： （1）if a<b goto (4) （2）t:=0 （3）goto (5) （4）t:=1 （5）… 　　其中用临时变量t存放布尔表达式a<b的值，（5）为后 续的四元式序号

图8.14给出了将布尔表达式翻译成四元式的描述，其中 nextstat给出在输出序列中下一四元式序号 emit过程每被调用一次，nextstat增加1

E→E1 or E2 　　｛E．place∶=newtemp； 　emit（E．place′∶=′E1．place　′or′E2．place）｝ E→E1 and E2 　　｛E．place∶ =newtemp； 　emit（E．place′∶=′E1．place ′and′E2．place）｝ E→not E1 　　｛E．place∶ =newtemp：； 　　emit（E．place′∶=′not′E1．place）｝ E→（E1） 　　｛E．place∶=E1．place｝

E→id1 relop id2 　　{E．place∶=newtemp； 　　emit（′if′id1．place relop id2．place′goto′　nextstat+3）； 　　emit（E．place′∶=′′0′）； 　　emit（′goto′nextstat+2）； 　　emit（E．place′∶=′′1′）｝ E→true 　　｛E．place∶=newtemp； 　　emit（E．place′∶=′′1′）｝ E→false 　　{E．place∶=newtemp； 　　emit（E．place′∶=′′0′）｝

二.控制语句中布尔表达式的翻译 If-then、if-then-else、while-do的语法为： 　S　　if E then S1 | if E then S1 else S2 | while E do S1 这些语句的代码结构示意图分别在图8.15中：

翻译的基本思路：对于E为a rop b的形式生成代码为： 　if a rop b goto E.true 和goto E.false 　其中，使用E.true和E.false分别表示E的真假出口转移目标 例8.5　a<b or c<d and e>f翻译为如下四元式序列： （1）if a<b goto E.true （2）goto （3） （3）if c<d goto （5） （4）goto E.false （5）if e>f goto E.true （6）goto E.false

例 if　a<b or c<d and e>f then S1 else S2的四元式序列： （1）if a<b goto （7） （2）goto （3） （3）if c<d goto （5） （4）goto （p+1） （5）if e>f goto （7） （6）goto （p+1) （7）（关于S1的四元式） ┇ （p)goto(q) （p+1）（关于S2的四元式） （q）

为了记录需回填地址的四元式，常采用一种“拉链”的办法 　，把需回填E.true/E.false的四元式拉成一链，称做真/假链 拉链的方式是这样的，若有四元式序列： （10）… goto E.true ┇ （20）… goto E.true （30）… goto E.true 　　则链成 （10）… goto （0） （20）… goto （10） （30）… goto （20）

地址（30）称作链首，地址（10）为链尾，0为链尾标志 Merge(p1,p2)，把p1和p2为链首的两条链合并为1条，返回 　合并后的链首值。即将p2的链尾第4区段改为p1，合并后 　的链首为p2，除非p2是空链 Backpatch(p,t)，把p所链接的每个四元式的第4区段都填为t 其中使用语义值codebegin与非终结符E相连，表示表达式E 　的第1个四元式语句序号

自下而上的分析中布尔表达式的一种翻译方案如图8.16： (1)EE1 or E2 { backpatch (E1.false, E2.codebegin); E.codebegin:=E1.codebegin; E.true:=merge(E1.true, E2.true) E.false:= E2.false } (2)EE1 and E2 { backpatch (E1.true, E2.codebegin); E.true:= E2.true; E.false:= merge(E1.false, E2.false);}

(3)Enot E1 { E.true:= E1.false; E.codebegin:=E1.codebegin; E.false:= E1. true; } (4)E(E1 ) { E.true:= E1. true; E.false:= E1. false; }

(5)Eid1 rop id2 { E.true:= nextstat; E.codebegin:= nextstat; E.false:= nextstat+1; emit(jrop, id1 ,id2 ,_) emit(j ,_ ,_ ,_ ) } (6)Etrue { E.true:= nextstat; emit(jnz ,_ ,_ ,_ ) } (7)Efalse { E. false := nextstat;

例a<b or c<d and e>f　将分析产生语法树时的语义动作结 　果真、假链情况注释在相应结点处，如图8.17所示：

8.6 控制结构的翻译 一.条件转移 一般使用下面文法G[S]定义这些语句： （1）S if E then S 8.6　控制结构的翻译 一.条件转移 一般使用下面文法G[S]定义这些语句： （1）S 　　 if E then S （2）| if E then S else S （3）| while E do S （4）| begin L end （5）| A （6）L　　L；S （7）| S 　S语句，L语句串，A赋值句，E布尔表达式

为了能及时地回填有关四元式串的转移目标，对G[S] （1）S 　　CS1 （2）| TpS2 （3）| WdS3 （4）| begin L end （5）| A （6）L　　LsS1 （7）S2 （8）C　　if E then （9）Tp　　CS else （10）Wd　　WE do （11）W　　while （12）Ls　　L；

下面给出这个文法的各个产生式相应的语义动作： S 　　CS1　｛S.chain := merge(C.chain,S1.chain)｝ S　　 TpS2　｛S.chain:=merge(Tp.chain,S2.chain)} S　　 WdS3　｛backpatch(S3.chain,Wd.codebegin) emit(‘GOTO’ W.codebegin) S.chain:=Wd.chain} S　　 begin L end　｛S.chain:=L.chain｝ S　　 A　｛S.chain:0 /*空链*/｝ L　　LsS1　｛L.chain:=s1.chain｝ L　　S　｛L.chain:=S.chain｝

C 　　if E then｛backpatch(E.true,nextstat) C.chain:=E.false｝ Tp　　 C S else　｛q:=nextstat emit(‘GOTO’-) backpatch(C.chain,nextstat) Tp.chain:=merge(S.chain,q)} W　　 while　｛W.codebegin:=nextstat} Wd　 W E do　｛backpatch(E.true,nextstat Wd.chain:=E.false Wd.codebegin:=W.codebegin｝ Ls　　 L;　｛backpatch(L.chain,nextstat)｝

按照上述文法产生式相应的语义动作，加上前述关于 　赋值句和布尔表达的翻译法，语句while (A<B) do if 　(C<D) then X:=Y+Z将被翻译成如下的一串四元式： 100　if A<B goto 102 101　goto 107 102　if C<D goto 104 103　goto 100 104　T:=Y+Z 105　X:=T 106　goto 100 107

二.开关语句 假定要讨论的开关语句的形式为： switch E of case V1: S1 case V2: S2 ┇ case Vn-1: Sn-1 default:Sn end

case语句翻译成如下的一连串条件转移语句： t:=E; L1: if t≠V1 goto L2 S1; goto next; L2: if t≠V2 goto L3 S2 ┇ Ln-1: if t≠Vn-1 goto Ln Sn-1; Ln:Sn; next;

另外一种实现办法： 建立一个n项的二元组表，第1元为Vi的值，第2元为Vi 　对应的语句Si的标号（或序号） 编译程序构造一张这样的表，产生把选择子E的值传送 　到该表末项第一元的指令。该项的另一元是缺省情况 　的语句号 并构造一个对E值查该表的程序，即该程序把E的值和 　二元组表项中的各个Vi值相比，若与某个Vi匹配，就 　去执行相应的Si，如果找不到这样的Vi,则末项自动匹 　配，便去执行Sn

图8.18给出开关语句的一种翻译结果（中间代码），其中 　把所有的测试都放在最后，以便目标代码生成阶段产生高 　质量的目标指令

三.for循环语句 for i:=E1 step E2 util E3 do S1 上述循环句的ALGOL意义等价于： i:= E1; goto OVER; AGAIN:i:=i+E2; OVER: if i≤E3 then begin S1;goto AGAIN end; 　改写成如下的产生式： F1　　for i:=E1 F2　　F1 step E2 F3　　F2 until E3 S　　F3 do S1

下面是这些产生式相应的语义动作： F1　　for i:=E1　 ｛emit(entry(i),’:=‘,E1.place); F1.place:=entry(i);/*保存控制变量在符号表中的位置*/ F1.chain:=nextstat; emit(‘goto’-); /*goto OVER*/ F1.codebegin:=nextstat;/*保存AGAIN的地址*/　｝

F2　　F1 step E2　 ｛F2.codebegin:=F1.codebegin;/*保存AGAIN的地址*/ 　 F2.place:=F1.place;/*保存控制变量在符号表中的位置*/ 　 emit(F1.place ‘:=‘,E2.place,’+’F1.place); backpatch(F1.chain,nextstat);/*回填上面的goto OVER*/}

F3　　F2 until E3 {F3.codebegin:=F2.codebegin; q:=nextstat; emit(‘if’ F2.place,’ ≤’,E3.place,’goto’q+2); /*若i ≤ E3转去执行循环体的第1个四元式*/； F3.chain:=nextstat; emit(‘goto’-);/*转离循环*/｝

S　　F3 do S1　　　/*这里是语句S1的相应代码*/ 　{emit(‘goto’ F3.codebegin) /*goto AGAIN*/； backpatch(S1.chain,F3.codebegin); S.chain:=F3.chain/；*转离循环的转移目标留待处理外层 S时再回填*/｝

例如，循环语句 for I:=1 step 1 until N do M:=M+I将被翻译 　成如下的四元式序列： 100　I:=1 101　goto 103 102　I:=I+1 103　if I≤N goto 105 104　goto 108 105　T:=M+I 106　M:=T 107　goto 102 108　

四.出口语句 exit、break，是一种结构化的方式跳出循环而设置的 　语句，它们的作用是引起外层循环的终止 为处理exit语句，编译程序对每个循环可使用一个称为 　“循环描述符”的量来记录一些必要的信息

exit语句所指的循环可以是无名的，即是最内层循环， 　可以使用一指针currentloop指向其描述符，所有打开 　循环的描述符使用栈式方式存储

五.goto语句 带标号语句的形式是 L:S；goto语句的形式是goto L 如果goto L是一个向上转移的语句，那么L是定义的 如果goto L是一个向下转移的语句，那么L尚未定义

六.过程调用的四元式产生 过程调用的实质是把程序控制转移到子程序（过程段） 如果实在参数是一个变量或数组元素，那么就直接传递 　它的地址 如果实参是其他表达式，如A＋B或2，那么就先把它的 　值计算出来并存放在某个临时单元T中，然后传送T的地 　址，所有实在参数的地址应存放在被调用的子程序能够 　取得到的地方

在被调用的子程序（过程）中，每个形式参数都有一个单元 　（形式单元）用来存放相应的实在参数的地址,在子程序段 　中对形式参数的任何引用都当作是对形式单元的间接访问 当通过转子指令进入子程序后，子程序段的第一步工作就是 　把实在参数的地址取到对应的形式单元中，然后再开始执 　行本段中的语句 传递实在参数地址的简单办法，把实参的地址逐一放在转子 　指令的前面

如过程调用 call S(A+B,Z)被翻译成： 计算A＋B置于T中的代码 /*T:=A+B*/ par T /*第1个实参地址*/ par Z /*第2个实参地址*/ call S /*转子指令*/

考虑一个描述过程调用语句的文法： （1）S　　call i ( <arglist> ) （2）<arglist>　　<arglist>1,E （3）<arglist>　　E 赋予非终结符arglist一项语义值，叫数据队列，用它记录每 　个实在参数地址。通过计数par的个数来记录实在参数个数

过程调用语法制导翻译的基本语义描述： （1）S　　call i ( <arglist> ) 　　｛FOR 队列arglist.queue的每一项p DO GEN (par,-,-,p); GEN(call,-,-,entry(i))｝ （2）<arglist>　　<arglist>1,E {把E.place排在arglist1.queue的末端； arglist.queue:=arglist1.queue} （3）<arglist>　　E {建立一个arglist.queue,它只包含一项E.place}

E=a<b and c<d and e<f or g<h四元式序列： 真题：（5分）布尔表达式 　E=a<b and c<d and e<f or g<h四元式序列： E.codebegin ____ E.true E.false 100 if a<b goto____ 101 goto____ 102 if c<d goto ____ 103 goto ____ 104 if e<f goto ____ 105 106 if g<h goto ____ 107 108 表达式为真的代码段 200 表达式为假的代码段

(1)EE1 or E2 { backpatch (E1.false, E2.codebegin); E.codebegin:=E1.codebegin; E.true:=merge(E1.true, E2.true) E.false:= E2.false } (2)EE1 and E2 { backpatch (E1.true, E2.codebegin); E.true:= E2.true; E.false:= merge(E1.false, E2.false);} backpatch(p,t)把p所链接的每个四元式的第4个区段都填为t E.codebegin表示表达式E的第1个四元式语句序号 merge(p1,p2)把p1和p2为链首的两条链合并为1条，返回 　合并后的链首值。即将p2的链尾第4区段改为p1，合并后 　的链首为p2，除非p2是空链 E.true和E.false分别表示E的真假出口转移目标 一旦整个布尔表达式的真假出口确定，则可沿“真”“假”链为 　相应的四元式填上

E=a<b and c<d and e<f or g<h四元式序列： 真题答案一：（5分）布尔表达式 　E=a<b and c<d and e<f or g<h四元式序列： 100 if a<b goto　102 101 goto　106 102 if c<d goto 104 103 goto 106 104 if e<f goto 0/-/真出口 105 106 if g<h goto 0/-/真出口 107 goto 0/-/假出口 108 表达式为真的代码段 200 表达式为假的代码段 E.codebegin 100 E.true 106 E.false 107

E=a<b and c<d and e<f or g<h四元式序列： 真题答案二：（5分）布尔表达式 　E=a<b and c<d and e<f or g<h四元式序列： 100 if a<b goto　102 101 goto　106 102 if c<d goto 104 103 goto 106 104 if e<f goto 108 105 goto 200 106 if g<h goto 108 107 108 表达式为真的代码段 200 表达式为假的代码段 E.codebegin 100 E.true 106 E.false 107

E=a<b and c<d and e<f or g<h四元式序列： 真题答案三：（5分）布尔表达式 　E=a<b and c<d and e<f or g<h四元式序列： 100 if a<b goto　102 101 goto　106 102 if c<d goto 104 103 goto 101 104 if e<f goto - 105 goto 103 106 if g<h goto 104 107 goto - E.codebegin 100 E.true 106 E.false 107

E= g<h or a<b and c<d and e<f 四元式序列： 真题答案四：（5分）布尔表达式 　 E= g<h or a<b and c<d and e<f 四元式序列： 100 if g<h goto　- 101 goto　102 102 if a<b goto 104 103 goto - 104 if c<d goto 106 105 goto 103 106 if e<f goto 100 107 goto 105 E.codebegin 100 E.true 106 E.false 107

8.7 说明语句的翻译 程序设计语言中的说明语句旨在定义各种形式的有名名体 ，如常量、变量、数组、记录（结构）、过程、子程序等 8.7　说明语句的翻译 程序设计语言中的说明语句旨在定义各种形式的有名名体 　，如常量、变量、数组、记录（结构）、过程、子程序等 　等，说明语句的种类也多，对象说明、变量说明、类型说 　明、过程说明等

编译程序把说明语句中定义的名字和性质登记在符号表中 　，用以检查名字的引用和说明是否一致 许多说明语句的翻译并不生成目标代码 过程说明和动态数组的说明有相应的代码

一.简单说明语句的翻译 最简单的说明语句的语法描述为： D　　integer<namelist>|real<namelist> <namelist>　　<namelist>,id | id 即使用关键字integer和real定义一串名字的性质 对这种说明语句的翻译是指在符号表中登录该名和性质 用8.2.4的方法把上述文法改写成： D　　D1,id 　　　| integer id 　　　|real id

给非终结符D一个语义变量D.att，用以记录说明语句所引入 　的名字的性质（int还是real），使用过程enter(id,A)把名字id 　和性质A登录在名表中 （1）D　　integer id {enter(id,int); D.att:=int} （2）D　　real id {enter(id,real); D.att:=real} （3）D　　D1, id {enter(id,D1.att); D.att:=D1.att}

二.过程中的说明 过程的翻译包括：处理说明、处理调用 为记录相对地址，可以使用一个变量offset 在处理过程的第一个说明之前，置offset为零 每看见一个新名字，则把名字连同offset的当前值登入符 　号表，然后offset增加 一般，offset增加由该名字类型决定的量，称为数据对象 　的宽度，用属性width表示

假如real型对象宽度为8，则8.7.1中的产生式（2）相对应 　的语义动作为： D　　real id {enter(id,real,offset); D.att:=real; D.width:=8; offset:=offset+D.width;}

过程嵌套的语言过程中的说明又可引入一过程，如图8.21 　所示的Pascal程序段：

8.8 数组和结构的翻译 一.数组说明和数组元素的引用 如果一个数组所需的存储空间的大小在编译时就已知 8.8　数组和结构的翻译 一.数组说明和数组元素的引用 如果一个数组所需的存储空间的大小在编译时就已知 　道，则称此数组是一个确定数组（静态数组），否则 　，称为可变数组（动态数组） 数组的存储表示有多种形式，最简单的一种是把整个 　数组按行（或按列）存放在一片边续存储区中

例如，若A是一个2×3的二维数组，每个元素占一个单元, 　那么，所谓按行和按列的存储方式分别如图8.22、8.23：

数组元素的地址计算和数组的存储方式密切相关 例如，假定A是一个10×20的二维数组，各维的下限为1， 　每个元素占用一个机器字（令存储器是以字编址的），数 　组的首地址，即A[1,1]的地址为a，那么，数组元素A[i,j] 　的地址为：a+(i-1) ×20+(j-1)=(a-21)+(20i+j) 如果是M × N的二维数组，则A[I,J]的地址： 　a+(I-1)*N+(J-1)=(a-N-1)+(I*N+J) =T1[T2] CONSPART VARSPART T1 T2

一般而言，设A是下面说明句所定义的一个ALGOL　 　n维数组　array A[l1:u1,l2:u2,…,ln:un] 令di=ui-li+1,i=1,2,…,n,a为数组的首地址，即 　A[l1,l2,…,ln]的地址 那么，在按行排列的前提下，元素A[i1,i2,…,in]的地址 　为：D=a+(i1-l1)d2d3…dn+(i2-l2)d3d4…dn+…+(in-1- 　ln-1)dn+(in-ln) 经因子分解后得：D=CONSPART+VARPART　 其中：CONSPART=a-C 　　C=(…((l1d2+l2)d3+l3)d4+…+ln-1)dn+ln 　　VARPART=(…((i1d2+i2)d3+i3)d4+…+in-1)dn+in

一般编译程序对数组说明的处理是把数组的有关信息汇集 　在一个叫做“内情向量”（“信息向量”）的表格中，以便以 　后计算数组元素的地址时引用这些信息 每个数组有一个内情向量 其中的信息包括：数组的类型、维数、各维的上下限、数 　组的首地址 例如，对于数组　array A[l1:u1,l2:u2,…,ln:un] 相应的内 　情向量可设为：

其中，di=ui-li+1,i=1,2,…,n。n为维数，a为数组的首地址， 　type是数组元素的类型，C是CONSPART=a-C中的第2项

产生两组计算数组元素地址的四元式： 一组计算VARPART，并将它放在某个临时单元T中 另一组计算CONSPART，并把它放在另一个临时单元T1 　中。同时用T1[T]表示数组元素的地址 对应“数组元素引用”（引用其值）和“对数组元素赋值”有 　两个相应的四元式：“变址取数”和“变址存数” “变址取数”的四元式是： 　(=[],T1[T],-,X) /*相当于X:=T1[T]*/ “变址存数”的四元式是： 　([]=,X1,-,T1[T]) /*相当于T1[T]:=X*/

例如，A是一个10×20的数组，即，d1=10,d2=20,那么， 　赋值句　X:=A[I,J]的四元式为： 　(*,I,20,T1) /*其中20指d2*/ 　(+,J,T1,T1) /*T1为VARPART*/ 　(-,A,21,T2) /*相当于T2:=a-C*/ 　(=[],T2[T1],_,T3) /*T3:=T2[T1]*/ 　(:=,T3,_,X)

例如，赋值句A[I+2,J+1]:=M+N的四元式序列为： 　(+,I,2,T1) 　(+,J,1,T2) 　(*,T1,20,T3) 　(+,T2,T3,T3) /*T3=VARPART*/ 　(-,A,21,T4) /*T4=CONSPART*/ (+,M,N,T5) ([]=,T5,_,T4[T3]) /*T4[T3]:=T5*/

二.结构（记录）说明和引用的翻译 结构（记录）是由已知类型的数据组合起来的一种数据类型 比如：struct(C)、record(Pascal)，如：　 struct date{ int day; char month-name[4]; int year };

<type> struct{f1}; |int |char |pointer f1 f1:f | f 结构说明的文法如下： <type>　　struct{f1}; |int |char |pointer f1　　f1:f | f f　　<type> i | <type> i[n] 结构的最简单存储方式是连续存放 编译时，必须记录所有分量的信息，假定带n个分量的 　结构按以下形式登录在一张单独的表中： 分量1 分量2 …… 分量n

每个分量的前面各分量的长度总和，用offse表示该值， 　将offset也记录下来 对于非终结符type、f和f1，分别用不同的语义变量len表 　示长度，i.name表示i当前所代表的名字，f.name表示分 　量名，n.val表示整数值，语义过程FILN(name,L)和 　FILO(name,L)将分别把分量名表中名为name的项的长 　度len和offset填为L 下面是处理结构类型说明的基本语义动作：

【本章小结】 中间代码是复杂性介于源程序语言和机器语言的一种表式形式。编译程序中所使用的中间代码有多种形式，常见的有逆波兰记号、三元式和四元式等等。 源程序翻译成中间表示，要在保证源语言语句语义的条件下进行源语句到目标语句结构上的变换。学习了本章应能掌握一般语法成分，如条件语句，循环语句和简单说明语句等结构的翻译。 语法制导翻译指的是编译实现的方法，分析过程和分析树用于制导语义分析和源程序的翻译，常用的办法是扩充惯用的文法，加上控制语义分析和翻译的信息，这样的文法称为属性文法。Yacc这类工具接受这种方式提供的语义分析和翻译信息，因而成为编译程序的生成器。

第8章　作业题 P202： 1.(1)(7) 2. 3. 5.