【编译原理课件】cha8-语法制导翻译和中间代码生成

2024/4/271第8章语法制导翻译和中间代码生成引言8.1属性文法8.2语法制导翻译概论8.3中间代码形式(重点)8.4简单赋值语句的翻译(重点)8.5布尔表达式的翻译(重点)8.6控制结构的翻译(重点难点)8.7说明语句的翻译〔略〕8.8数组和结构的翻译〔略〕作业课程目录2024/4/272语义分析的任务p169静态语义检查动态语义处理——翻译总目标验证语法结构合法的程序是否真正有意义。例：类型检查、控制流检查、一致性检查、相关名字检查。对程序意义的解释，执行真正的翻译。例：变量的存储分配表达式的求值例：语句的翻译〔中间代码的生成〕生成等价的中间代码。2024/4/273编译中的语义分析描述方法——属性文法利用属性文法描述如何将各种语句和表达式翻译成中间代码为每个文法符号赋予相应属性，对应每一个产生式编制一个语义子程序工作方式——语法制导翻译当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译每识别出一个语法结构时，完成相应的语义检查与中间代码生成章节目录2024/4/2748.1属性文法p169

属性文法举例

属性文法定义

属性的分类综合属性继承属性章节目录2024/4/275简单计算器的设计例3*5+4n表达式的文法L→EnE→E1+TE→TT→T1*FT→FF→(E)F→i

EnE1+TTT1*FFi3i5Fi4要解决的问题表达式求值.val3.val3.val5.val15.val15.val4.val4.val19L显示19.lexval3.lexval5.lexval4综合属性自下而上传递信息2024/4/276属性文法举例——简单计算器

p171用语义规那么描述表达式求值。该属性文法描述如下：产生式语义规那么(属性计算规那么)L→Enprint(E.val)(虚属性)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val*F.valT→FT.val:=F.valF→(E)F.val:=E.valF→iF.val:=i.lexval非终结符设有综合属性，代表表达式的值终结符i设有综合属性，其值由词法分析器提供2024/4/277说明语句的设计p171例realid1,id2,id3说明语句的文法D→TLT→intT→realL→L1,idL→idDTLrealL1,id3L2,id2id1要解决的问题记录标识符的类型类型信息传递realrealreal.typereal.inreal.inreal.inreal继承属性自上而下传递信息类型描述变量表2024/4/278D→TLL.in:=T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→idaddtype(id.entry,L.in)entry单词

id的属性，id在符号表的入口addtype在符号表中为变量添加类型信息用语义规那么描述变量说明。该属性文法描述如下：产生式语义规那么(属性计算规那么)说明语句的属性文法p171综合属性继承属性节目录2024/4/279属性文法定义p169属性文法是Knuth在1968年提出的。属性文法的特点：是一种接近形式化的语义描述方法。每个文法符号有相应的属性V——属性集合代表与文法符号相关的信息；例如类型、值、代码序列等。每个产生式配有相应的语义规那么F——规那么集合作用：计算属性的规那么,可以产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作，实现翻译；形式：b:=f(c1,c2,…,ck)。属性文法：三元组A=(G,V,F)在上下文无关文法的根底上，把每个文法符号和一组属性相关联，并给产生式附加以语义规那么。节目录2024/4/2710属性分类p170产生式A→α语义规那么b:=f(c1,c2,…,ck)综合属性用于“自下而上”传递信息b是A的综合属性,c1,c2,…,ck是右边文法符号的属性从其子结点的属性值计算出来的终结符只有综合属性，由词法分析器提供例如E.valT.valF.val继承属性用于“自上而下”传递信息b是右边某个文法符号的继承属性,c1,c2,…,ck是A或右边任何文法符号的属性从其兄弟结点和父结点的属性值计算出来开始符号的继承属性作为属性计算前初值例如L.in非终结符既可有综合属性也可有继承属性,一般对于出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规那么节目录2024/4/27118.2语法制导翻译概论p171语法制导翻译计算语义规那么依赖图S-属性文法和自下而上翻译L-属性文法在自上而下分析中的实现L-属性文法在自下而上分析中的实现章节目录2024/4/2712基于属性文法的处理方法p171对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规那么进行计算。输入串语法树依赖图语义规那么计算次序2024/4/2713语法制导翻译法由源程序的语法结构所驱动的处理方法为文法中每个产生式配上一组语义规那么，并且在语法分析的同时执行这些语义规那么，完成相应的语义处理问题：何时执行语义规那么？每当用一个产生式推导或归约时，就执行对应的语义规那么节目录2024/4/2714属性的计算——依赖图p172一张有向图描述语法树各结点属性之间的相互依赖关系如果属性b的计算依赖于属性c，那么附属性c到属性b有一条有向边c→b根据依赖关系决定计算顺序依赖图的任意一个拓扑排序TopologicalSort如果结点c→b，在序列中c必须在b之前2024/4/2715①例3*5+4n的语法树与属性计算L.val=3EnE1+TTT1*FFiiFi.val=3.val=5.val=15.val=15.val=4.val=4.val=19显示19.lexval=3.lexval=5.lexval=4依赖关系拓扑排序自下而上依赖图②③④⑤⑥⑦⑧⑨2024/4/2716例realid1,id2,id3的语法树和属性计算p172DTLrealL1,id3L2,id2id1addtype.type=real.in=real.in=real.in=real依赖关系拓扑排序自下而上无法直接实现.entry.entry.entry自上而下存在左递归,可改造realaddtyperealaddtypereal④⑤⑥⑦⑧⑨①②③⑩节目录2024/4/2717S-属性文法p173S-attributedDefinitionS-attributedGrammar仅包含综合属性的语法制导定义对于所有Ａ→Ｘ1Ｘ2…Ｘn，Ａ的属性计算仅用Ｘ1,Ｘ2,…,Ｘn的属性自下而上计算属性如算术表达式求值的属性文法节目录2024/4/2718L-属性文法p175L-attributedDefinitionL-attributedGrammar包含综合属性和继承属性的语法制导定义对于所有Ａ→Ｘ1Ｘ2…Ｘi-1Ｘi

…ＸnＸi属性计算仅使用Ｘ1,Ｘ2…Ｘi-1的属性和A的继承属性自上而下计算属性如说明语句的属性文法节目录2024/4/2719翻译模式p176语法制导翻译的两种描述形式属性文法(语法制导定义)(GrammarDirectedDefinition)语义的抽象说明，隐去实现细节翻译模式(TranslationScheme)规定实现方法，说明计算次序翻译模式的特征规定在语法分析中使用语义规那么进行计算的次序保证当动作使用某属性时，该属性必须是可用的翻译模式的构造方法将{语义动作}插入到产生式中的某个位置2024/4/2720表达式文法的翻译模式E→E1+T{E.val:=E1.val+T.val}E→T{E.val:=T.val}T→T1*F{T.val:=T1.val*F.val}T→F{T.val:=F.val}F→(E){F.val:=E.val}F→i{F.val:=i.lexval}2024/4/2721说明语句的翻译模式

将语义动作中的计算向前移，使继承属性的计算出现在其文法符号之前D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}问题：如何自下而上计算继承属性？2024/4/2722解决方法从翻译模式中去掉嵌入在产生式中间的动作自下而上计算继承属性p176D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id

{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}引入6.

M→ε{L.in:=T.type}

引入7.

N→ε{L1.in:=L.in}

MN2024/4/2723realid1,id2的翻译过程D→TMLT→int{T.type:=integer}T→real{T.type:=real}L→NL1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}M→ε{L.in:=T.type}N→ε{L1.in:=L.in}DTMLrealεNL1

,id2εid1T.type=realL.in=realL1.in=realrealreal节目录2024/4/27248.3中间代码形式

(Intermediatelanguage/code/representation)许多编译程序采用的独立于机器的、复杂性界于源语言和机器语言之间语言源程序的一种内部表示——中间代码序列〔中间语言的语句〕用中间语言过渡的好处便于进行与机器无关的优化工作使编译程序改变目标机容易，便于移植使编译程序的结构在逻辑上更为简单明确2024/4/2725中间语言p177章节目录常见形式后缀式〔逆波兰式〕图表示法抽象语法树、DAG图三地址代码〔抽象描述〕四元式、三元式、间接三元式〔具体实现〕特点形式简单、语义明确、便于翻译独立于目标语言2024/4/2726举例中缀式后缀式

(1)(a+b)*c(2)-a*(b+c)(3)(a+b)*(c+d)(4)not(AorB)后缀式〔逆波兰式〕p177是表达式的一种表示形式把运算符写在运算量(操作数)后面定义设E是表达式，那么假设E是变量或常量，E的后缀式为E自身E1OPE2==>E1’E2’OP，其中E1’和E2’分别为E1和E2的后缀式(E)==>E’ab+c*a@bc+*ab+cd+*ABornot2024/4/2727中缀式改写成后缀式课堂练习中缀式

1.-a+b*c2.a+b*(c-d)+e/(c-d)↑n乘幂运算

3.x:=a-b/(c+d)对应后缀式后缀式特点

1.运算量的顺序与中缀式相同

2.运算符的先后顺序即为运算的先后顺序

3.有利于表达式运算的实现BEGIN1.a@bc*+2.abcd-*+ecd-n↑/+3.xabcd+/-:=2024/4/2728中缀式改写成后缀式的属性文法 产生式 语义规那么E→E1opE2 E.code:=E1.code||E2.code||opE→(E1) E.code:=E1.codeE→id E.code:=id功能：完成中缀表达式到后缀表达式的翻译例如：id1+id2+id3后缀式：E.codeEE+EE+Eid2id1id3数组postid1id2+id3E1E2+节目录2024/4/2729

三地址代码一般形式x:=yopz(1)三个地址xyz为变量、常数或编译产生的临时变量(2)每条语句的右边只能有一个运算符op表达式x+y*z的三地址代码

(1)T1:=y*z(2)T2:=x+T1赋值语句a:=b*-c+b*-c的三地址代码

(1)T1:=-c(2)T2:=b*T1(3)T3:=-c(4)T4:=b*T3(5)T5:=T2+T4(6)a:=T5结果操作数操作数运算符2024/4/2730三地址代码种类x:=yopzx:=opyx:=ygotoLifxrelopygotoLparxcallpreturnxx:=y[i]x[i]:=yx:=&yx:=*y*x:=y双目运算单目运算赋值无条件转移条件转移实在参数过程调用过程返回数组运算(取数)(存数)地址和指针运算2024/4/2731三元式和树形表示p178表示方法：三个域

(i)(op，arg1，arg2)例：a+b*c三元式(i)(op,arg1,arg2)

(1)(*,b,c)

(2)(+,a,(1))arg1，arg2：或者是指向符号表的指针，或者是指向三元式表的指针。三元式编号存放结果操作数操作数运算符树形表示+a*bc2024/4/2732三元式课堂练习赋值语句A:=-B*(C+D)对应的三元式序列

(1)(@,B,_)(2)(+,C,D)(3)(*,(1),(2))

(4)(:=,A，(3))可以看出：三元式是按相应表达式的实际运算顺序出现的三元式间的相互引用非常频繁，而这些引用又是通过编号来实现的在优化时，要删除或挪动三元式会造成大量修改的局面BEGIN操作数为空用下划线表示节目录2024/4/2733间接三元式建立两个与三元式相关的表格三元式表执行表(间接代码表)

三元式表(1)(+,A,B)(2)(*,(1),C)(3)(:=,X,(2))(4)(↑,D,(1))(5)(:=,Y,(4))

间接代码

(1)(2)(3)

(1)(4)(5)

——用来存放各三元式本身——按各三元式执行顺序列出相应三元式在三元式表中位置例：X:=(A+B)*C;Y:=D↑(A+B);2024/4/2734间接三元式优点相同的三元式无需重复填进三元式表中，节省三元式空间需要调整运算顺序时，只需重新安排间接代码表，无需改变三元式表2024/4/2735间接三元式课堂练习赋值语句X:=(A+B)*CB:=A+BY:=C*(A+B)对应的间接三元式为：间接码表〔1〕〔2〕〔3〕〔1〕〔4〕〔1〕〔2〕〔5〕

三元式表(1)(+,A,B)(2)(*,1,C)(3)(:=,X,2)(4)(:=,B,1)(5)(:=,Y,2)三元式代码(1)(+,A,B)(2)(*,1,C)(3)(:=,X,2)(4)(+,A,B)(5)(:=,B,4)(6)(+,A,B)(7)(*,C,6)(8)(:=,Y,7)BEGIN节目录2024/4/2736四元式p172表示方法：四个域

(op，arg1，arg2，result)例：a+b*-c (op,arg1,arg2,result)(1)(@,c,_,T1)arg1，arg2和result是指向有关名字符号表的指针，可以是常量，变量或临时变量等结果操作数操作数操作数运算符操作数为空用下划线表示(2)(*,b,T1,T2)(3)(+,a ,T2,T3)2024/4/2737四元式课堂练习赋值语句A:=-B*(C+D)对应的四元式序列(1)(@,B,_,T1)BEGIN(2)(+,C,D,T2)(3)(*,T1,T2,T3)(4)(:=,T3,_,A)节目录2024/4/27388.4简单赋值语句的翻译p179语法id:=E语义计算表达式E的值之后把值赋给变量id文法G[S]:S→id:=EE→E1+E2E→E1*E2E→-E1E→(E1)E→id章节目录2024/4/2739语义过程及属性设置p178语义过程lookup()检查在符号表中是否存在

的表项。emit(x‘:=’y‘+’z)将生成的三地址代码x:=y+z发送到输出文件。newtemp每调用一次，生成一个临时变量。属性设置存储位置place。例如E.place,T.place等lookup()=id.entry在表中nil否那么2024/4/2740产生赋值语句三地址代码的翻译模式p180S→id:=E{p:=lookup();

(sub1)ifp<>nilthenemit(p‘:=’E.place)/*id在表中*/elseerror/*id不在表中*/}E→E1+E2{E.place=newtemp;(sub2)emit(E.place':='E1.place'+'E2.place')}E→E1*E2{E.place=newtemp;

(sub3)emit(E.place':='E1.place'*'E2.place')}E→-E1{E.place:=newtemp;(sub4)emit(E.place´:=´´uminus´E1.place}E→(E1){E.place:=E1.place}(sub5)E→id{p:=lookup();(sub6)ifp<>nilthenE.place:=p/*id在表中*/ elseerror/*id不在表中*/}2024/4/2741a:=-c+b*d自下而上语法制导翻译过程举例步骤符号栈输入串动作语义值三地址代码

0#a:=-c+b*d#预备

i

:=EaSE+E-EicE*Eibid1#i:=-c+b*d#移进

a2#i:=-c+b*d#移进

a_3#i:=-c+b*d#移进

a__4#i:=-i+b*d#移进

a__c5#i:=-E+b*d#归sub6a__c

6#i:=E+b*d#归sub5a_T1

T1:=-c

7#i:=E+b*d#移进

a_T1_8#i:=E+i*d#移进

a_T1_b9#i:=E+E*d#归sub6a_T1_b10#i:=E+E*d#移进

a_T1_b_11#i:=E+E*i#移进

a_T1_b_d12#i:=E+E*E#归sub6a_T1_b_d

13#i:=E+E#归sub3a_T1_T2

T2:=b*d

14#i:=E#归sub2

a_T3

T3:=T1+T215#S#归sub1

a:=T316分析成功结束

另见：教材p174图8.7

2024/4/2742x:=b+c*d自下而上的语法制导翻译课堂练习步骤符号栈输入串动作语义值三地址代码

0#x:=b+c*d#预备

1#i:=b+c*d#移进x2#i:=b+c*d#…x_3#i:=i+c*d#移进x_b4#i:=E+c*d#归sub6x_b5#i:=E+c*d#移进x_b_6#i:=E+i*d#…x_b_c7#i:=E+E*d#归sub6x_b_c8#i:=E+E*d#移进x_b_c_9#i:=E+E*i#…x_b_c_d10#i:=E+E*E#归sub6x_b_c_d11#i:=E+E#归sub3x_b_T1

T1:=c*d12#i:=E#归sub2

x_T2

T2:=b+T113#S#归sub1

x:=T214分析成功结束 Six:=EE+EibE*EicidBEGIN节目录2024/4/27438.5布尔表达式的翻译p181章节目录布尔表达式作用布尔表达式文法布尔表达式翻译方法数值表示法作为控制条件的布尔表达式翻译2024/4/2744

布尔表达式的作用p181布尔表达式的作用计算逻辑值控制流语句如if-then，if-then-else和while-do等之中的条件表达式例如1or(not0and0)or0a<borc<dande<fifa<borc<dande<fthenx:=1elsex:=-1whilea<bdoa:=a-b节目录2024/4/2745

布尔表达式的文法p182布尔表达式——用布尔运算符号(and,or,not)作用到布尔变量或关系表达式上而组成例如布尔表达式：aorbandc<d考虑如下生成布尔表达式的文法E→EorE|EandE|notE|(E)|id

relop

id|id

其中relop表示六个关系运算符之一例如E==>EorEabc<d对应语法树==>EorEandE==>EorEandidrelopid==>Eoridandidrelopid

==>idoridandidrelopid

节目录2024/4/2746数值表示法p182假设用1表示真，0表示假，那么布尔表达式可以象算术表达式一样来计算例如关系表达式a<b可等价地写成:ifa<bthen1else0翻译成三地址代码：

100ifa<bgoto103101T1:=0102goto104103T1:=1104例如逻辑表达式

aorbandnotc

翻译成三地址代码：(1)T1:=notc(2)T2:=bandT1

(3)T3:=aorT2100+3102+2a<b为假a<b为真后续代码nextstat2024/4/2747布尔式数值计算翻译模式中

有关属性和函数p182属性E.place

综合属性，表示存放布尔表达式值的名字relop.op

综合属性，表示六个关系运算符之一三地址代码的编号nextstat

给出输出三地址代码序列中下一条代码的编号(地址索引)函数emit将产生的三地址代码送到输出文件中,每产生一条三地址代码后，emit便把nextstat增12024/4/2748计算布尔表达式值三地址代码的翻译模式p182E→E1orE2{E.place:=newtemp;sub1emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp;sub2emit(E.place‘:=’E1.place‘and’E2.place)}E→notE1{E.place=newtemp;sub3emit(E.place‘:=’‘not’E1.place)}E→(E1){E.place:=E1.place)}sub4E→id1{E.place:=newtemp;relopid2emit(‘if’id1.placerelop.opid2.placesub5‘goto’nextstat+3);emit(E.place‘:=’‘0’);emit(‘goto’nextstat+2);emit(E.place‘:=’‘1’)}E→id{E.place:=id.place}(与教材不同)sub62024/4/2749把a<borc<dande<f

翻译

成三地址代码举例Eidarelop<idbEidcrelop<iddEiderelop<idfEandEor(1)sub5T1100ifa<bgoto103101T1:=0102goto104103T1:=1(2)sub5T2104ifc<dgoto107105T2:=0106goto108107T2:=1(3)sub5T3108ife<fgoto111109T3:=0110goto112111T3:=1(4)sub2112T4:=T2andT3(5)sub1113T5:=T1orT42024/4/2750把a>bandc>d翻译成三地址代码课堂练习Eidarelop>idbEidcrelop>iddEand(1)sub5T1100ifa>bgoto103101T1:=0102goto104103T1:=1(2)sub5T2104ifc>dgoto107105T2:=0106goto108107T2:=1(3)sub2108T3:=T1andT2BEGIN节目录2024/4/2751作为条件控制的布尔式的翻译p183语法S→ifEthenS1elseS2语义如果E的值为true，那么执行S1；否那么,执行S2代码模式E.code：E的目标代码判别E值的代码转向E.true的代码转向E.false的代码E.true:S1的目标代码转向S.next的代码E.false:S2的代码S.next:后继语句的代码if-then-else的代码结构E.codeS1.codeE.true:S2.codeE.false:gotoS.next...S.next:toE.truetoE.false2024/4/2752选择语句中布尔式的翻译思想p183设E形如a<b属性E.code为生成的三地址代码：

ifa<bgotoE.truegotoE.falseE.true为E为“真”时控制流转向的标号E.false为E为“假”时控制流转向标号函数newlabel每次调用返回一个新的符号标号该符号标号用来标识一条三地址代码2024/4/2753使用拉链-回填技术实现布尔式翻译p184采用四元式实现三地址代码，约定转移四元式的形式为：(jnz,a,_,p)表示ifagotop(jrop,x,y,p)表示ifxropygotop(j,_,_,p)表示gotop面临主要问题通过一编扫描来产生代码时，当生成某些转移语句时我们可能还不知道该语句要转移到的标号究竟是什么？解决方法——拉链-回填技术2024/4/2754拉链-回填技术p184拉链——在生成暂时不知道转移目标的转移四元式时，先建立链表，把转移目标相同的转移四元式链接在一起

E.truelist真链回填E的真出口E.true

E.falselist假链回填E的假出口E.false回填——一旦某条链的转移目标确定之后，再把转移目标填入到有关的四元式中例如

E的四元式中需回填真出口k的有p、q和r三个四元式E.truelist…(k)(*,*,*,*)E.trueE.true(p)(*,*,*,0)…(q)(*,*,*,0)pE.truelist…(r)(*,*,*,0)qE.truelistkkk2024/4/2755使用回填翻译布尔表达式的文法p185布尔表达式文法：〔1〕E→E1orME2〔2〕|E1andME2〔3〕|notE1〔4〕|(E1)〔5〕|id1relopid2〔6〕|id(与教材不同)〔7〕M→ε插入非终结符号M是为了引入一个语义动作，以便在适当的时候获得即将产生的下一个四元式的编号，或说四元式的索引〔E2.codebegin〕2024/4/2756翻译模式用到如下变量和函数p184变量nextquad〔教材nextstat〕指向下一条要产生四元式的编号，每执行一次emit，nextquad增1。函数makelist(i)创立一个仅包含编号为i的四元式的新链表，函数返回指向这个链的指针。函数merge(p1，p2)把以p1和p2为链首的两个链合并为一，合并后的链首p2作为函数值回送。过程backpatch(p，i)完成“回填”，把p所指向链的每个四元式第四个域都填为i。2024/4/2757作为控制条件的布尔表达式翻译模式p185sub1EE1orME2{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist}sub2EE1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)}sub3EnotE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}sub4E(E){E.truelist:=E1.truelist;E.falselist:=E1.falselist}2024/4/2758作为控制条件的布尔表达式翻译模式p185sub5Eid1relopid2{E.truelist:=makelist(nextquad);

E.falselist:=makelist(nextquad+1);

emit(‘j’relop.op‘,’id1.place‘,’id2.place,’0’);

emit(‘j,_,_,0’);}sub6Eid

{E.truelist:=makelist(nextquad);

E.falselist:=makelist(nextquad+1);

emit(‘jnz’’,’id.place‘,’‘_’‘,’’0’);

emit(‘j,_,_,0’);}sub7M{M.quad:=nextquad}2024/4/2759布尔表达式

a＜borc＜dande＜f翻译过程p185E.t={100,104}E.f={103,105}E.t={100}E.f={101}E.t={104}M.q=102

E.t={102}E.f={103}E.t={104}E.f={105}M.q=104c<def<

EandEEMa<borEME①100(j<,a,b,0)101(j,_,_,0

)②sub7102(j<,c,d,0

)103(j,_,_,0)③④sub7⑤104(j>,e,f,0)105(j,_,_,0)⑥sub2①sub5③sub5⑤sub5⑦sub1103E.falselist100E.truelist104E.f={103,105}102回填回填合并合并2024/4/2760布尔表达式a＜borc＜dande＜f翻译100(j<,a,b,0)101(j,_,_,0)102(j<,c,d,0)103(j,_,_,0)104(j<,e,f,0)105(j,_,_,0)103E.falselist100E.truelist104102回填回填合并合并E.truec<da＜bc＜de<fE.falsee＜fE.trueE.false2024/4/2761翻译布尔表达式a>1orb>1andb<9课堂练习100(j>,a,1,0)101(j,_,_,0)102(j>,b,1,0)103(j,_,_,0)104(j<,b,9,0)105(j,_,_,0)103E.falselist100E.truelist104102回填回填合并合并E.trueb>1a>1b>1b<9E.falseb<9E.trueE.falseBEGIN翻译布尔表达式AandB<CorD课堂练习2024/4/2762作为控制条件布尔表达式翻译总结拉链当四元式的转移目标不可知时应进行拉链。回填当知道了四元式的转移目标(条件为真时和条件为假时分别应做哪些事)时，就可以进行回填。翻译结果E.truelistE.flaselist2024/4/2763作为控制条件布尔表达式应用举例例ifa＜borc＜dande＜fthenx:=y+zelsex:=y-z

回填E.truelist回填E.falselist100(j<,a,b,0)101(j,_,_,102)102(j<,c,d,104)103(j,_,_,0)104(j<,e,f,100)105(j,_,_,103)E.falselistE.truelist106(+,y,z,T1)107(:=,T1,_,x)E.true106106S.next108(j,_,_,0)S.next109(-,y,z,T2)110(:=,T2,_,x)111E.false109109S.next111S.nextlist2024/4/2764作为控制条件布尔表达式应用举例例whilea＜borc＜dande＜fdox:=y+z

回填E.truelist回填E.falselist100(j<,a,b,0)101(j,_,_,102)102(j<,c,d,104)103(j,_,_,0)104(j<,e,f,100)105(j,_,_,103)E.falselistE.truelist106(+,y,z,T1)107(:=,T1,_,x)E.true106106S.next108(j,_,_,100)S.begin109E.false109109S.nextS.beginS.begin节目录2024/4/27658.6控制结构的翻译p1868.6.1条件转移if语句while语句8.6.6过程调用章节目录2024/4/2766if_then语句的代码结构p183语法S→ifEthenS1语义如果E的值为true，那么执行S1举例

ifc<dthena:=b+2

翻译成四元式序列为：E.codeS1.codeE.true:E.false:...toE.truetoE.false100(j<,c,d,0)E.true101(j,_,_,0)E.falseE.fE.t102(+,b,2,T1)103(:=,T1,_,a)104E.trueE.false1021042024/4/2767if_then_else的代码结构语法S→ifEthenS1elseS2语义如果E的值为true，那么执行S1；否那么执行S2举例ifc<dthenx:=y+zelsex:=y-z

翻译成四元式序列为：E.codeS1.codeE.true:S2.codeE.false:gotoS.next...S.next:toE.truetoE.false100(j<,c,d,0)101(j,_,_,0)E.trueE.falseE.fE.t102(+,y,z,T1)103(:=,T1,_,x)E.true102104(j,_,_,0)S.next105(-,y,z,T2)106(:=,T2,_,x)107E.false105S.next1072024/4/2768嵌套if_then_else的翻译练习ifa<bthenifc>dthenx:=y+zelsex:=y-zelsea:=b+2E1.trueE1.falseE1E2S1S2S3100(j<,a,b,0)101(j,_,_,0)E1.tE1.fE1.truec>d入口E1.falsea:=b+2E2.truex:=y+zE2.falsex:=y-zSQ102(j>,c,d,0)103(j,_,_,0)E2.trueE2.falseE1.true102104(+,y,z,T1)105(:=,T1,_,x)E2.true104106(j,_,_,0)Q.nextQ.nlist107(-,y,z,T2)108(:=,T2,_,x)E2.false107109(j,_,_,0)S.nextS.nlist110(+,b,2,T3)111(:=,T3,_,a)112E1.false110S.next106S.next合并S.nextlist回填S.nextlist112112BEGIN节目录2024/4/2769while_do的代码结构p183语法S→whileEdoS1语义如果E的值为true，那么执行S1；否那么退出循环举例

whilea<bdox:=y+z翻译成四元式序列为：E.codeS1.codeE.true:E.false:gotoS.begin...S.begin:toE.truetoE.falseE.trueE.false100(j<,a,b,0)101(j,_,_,0)S.beginE.tE.f102(+,y,z,T1)103(:=,T1,_,x)E.true102104(j,_,_,100)S.begin105E.false1052024/4/2770嵌套while_if的翻译练习p188whilea<bdoifc<dthenx:=y+zE1.trueE1.falseE1E2S1100(j<,a,b,0)101(j,_,_,0)S.begina<b入口E1.truec<d入口E1.falsewhile

出口E2.truex:=y+zQ.nlist回填

S.beginSQ102(j<,c,d,0)103(j,_,_,0)E2.trueE2.falseE1.true102104(+,y,z,T1)105(:=,T1,_,x)E2.true104106(j,_,_,100)107E1.falseQ.nlist107S.beginS.begin100BEGIN2024/4/2771控制流语句的文法p187(1)S→ifEthenSif_then语句(2)|ifEthenSelseSif_then_else语句(3)|whileEdoSwhile语句(4)|beginLend复合语句(5)|A赋值语句(6)L→L；S语句序列(7)|S一条语句

E为一个布尔表达式2024/4/2772翻译模式中的属性和函数设置〔略〕S→ifEthenM1S1NelseM2S2E.truelist需回填E.true的链E.falselist需回填E.false的链M.quad下一条四元式的标号S.nextlist需回填S.next的链N.nextlist需回填S.next的链S→beginLendL.nextlist需回填S.next的链变量和函数nextquadmakelistmergebackpatch2024/4/2773控制流语句的翻译模式〔略〕sub1SifEthenM1S1NelseM2S2{backpatch(E.truelist,M1.quad);M1处生成E.true，回填E.truelistbackpatch(E.falselist,M2.quad);M2处生成E.false，回填E.falselistS.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)

合并转移目标同为S.next的链}sub2N

{N.nextlist:=makelist(nextquad);emit(‘j,_,_,0’)N处生成转移指令gotoS.next}sub3M

{M.quad:=nextquadM处生成下一条四元式的标号}2024/4/2774控制流语句的翻译模式sub4SifEthenMS1{backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)}sub5SwhileM1EdoM2S1{backpatch(S1.nextlist,M1.quad);M1处生成标号S.begin，回填S1.nextlist(循环)backpatch(E.truelist,M2.quad);M2处生成E.true,回填E.truelistS.nextlist:=E.falselist;emit(‘j,_,_,’M1.quad)形成循环}2024/4/2775控制流语句的翻译模式sub6SbeginLend{S.nextlist:=L.nextlist}sub7SA{S.nextlist:=makelist()}sub8LL1;MS{backpatch(L1.nextlist,M.quad);M处生成标号L.next，回填L1.nextlistL.nextlist:=S.nextlist}sub9LS{L.nextlist:=S.nextlist}节目录2024/4/27768.6.6过程调用的处理p195功能把程序控制转移到子程序(过程段)任务把实在参数的信息传递给被调用的子程序保存子程序调用结束后的返回地址(不考虑)翻译工作生成一个调用序列，包括进入和离开每一个过程所采取的动作序列2024/4/2777过程调用的文法p195考虑如下的一个简单的过程调用语句的文法

(1)S→callid(arglist)调用语句

(2)arglist→arglist，E实参表

(3)arglist→E实参例过程调用calls(a+b,z)

翻译生成代码如下：计算a＋b置于单元T中/*T:=a+b*/

parT/*第一个实参地址*/parz/*第二个实参地址*/calls/*调用过程s*/

2024/4/2778过程调用的翻译模式p196E.place:存放实在参数的地址queue：存放实在参数的地址队列sub1S→callid(arglist〕｛for队列queue中的每一项doemit〔‘par’p)；为实参生成par语句emit〔'call'id.place〕call语句}sub2arglist→arglist，E{将E.place参加到queue的队尾}sub3arglist→E｛初始化queue仅包含E.place}节目录2024/4/27798.7说明语句的翻译p196翻译工作确定变量类型分配存储空间——相对地址全局数据表示为静态数据区的偏移值局部数据表示为局部数据域(活动记录的局部)的偏移值作用域地址空间的分配方式设置一个全局量offset，记录当前可用存储空间的开始地址，初值为0每次分配一个变量的空间，将offset增加相应的值2024/4/2780例存储布局设整数类型域宽为4

实数类型域宽为8说明语句

x:array[8]ofreal;i:integer;j:real;名字类型相对地址0offset63x6467i6875j76xarray(8,real)0iinteger64jreal682024/4/2781翻译模式中变量和函数类型描述符T的属性type类型width占用的字节数语义函数enter(name,type,offset)在符号表中设置变量name的类型type和地址offsetarray(num,type)描述数组类型pointer(type)描述指针类型全局量offset跟踪下一个可用的相对地址的位置2024/4/2782说明语句的翻译模式p196(1)P→D(2)D→D;D(3)D→id:T(4)T→integer(5)T→real(6)T→array[num]ofT1(7)T→↑T1说明段说明语句序列说明变量id类型为T数组指针{offset:=0}{}

{enter(,T.type,offset);offset:=offset+T.width}{T.type:=integer;T.width:=4}{T.type:=real;T.width:=8}{T.type:=array(num.val,T1.type);T.width:=num.val*T1.width}{T.type:=pointer(T1.type);T.width:=4}2024/4/2783xi例x:real;i:integer的翻译enter(x,real,0)offset=0offset=8T.type=realT.width=8offset=12T.type=integerT.width=4enter(i,integer,8)章节目录2024/4/27848.8数组元素的引用p198翻译工作计算数组元素的相对地址产生三地址代码完成相对地址的计算目标

T3:=T2[T1]

可变局部与下标有关不变局部与首地址和维数有关相对地址2024/4/2785一维数组元素地址的计算p199说明：VARa:ARRAY[low..high]OFreal;数组元素a[i]的起始地址:base+(i-low)*w=i*w+base-low*w=V+base-C=可变局部+不变局部(可在编译时计算出来)其中，base是数组a的首地址，w是元素的域宽例如VARa:ARRAY[1..10]OFreal;元素a[i]的起始地址：base+(i-low)*w=A+(i-1)*8=i*8+A-82024/4/2786二维数组元素地址的计算二维数组假设按行存放可如下计算a[i1,i2]的相对地址：base+((i1-low1)*n2+i2-low2)*w)=(i1*n2)+i2)*w+base-((low1*n2)+low2〕*w(7.5)=V+base-C其中，n2=high2-low2+1，称为第二维的界差(编译时可知)例二维整型数组a[1..10,1..20]n2=20-1+1=20w=4数组元素a[i,j]的相对地址：A+((i-1)*20+j-1))*4=(i*20+j)*4+A-((1*20)+1)*4=(i*20+j)*4+A-84x:=a[i,j]的三地址代码

(1)T1:=i*20

(2)T1:=T1+j(3)T2:=A-84

(4)T3:=4*T1(5)T4:=T2[T3](6)x:=T42024/4/2787多维数组元素

地址的计算推广公式，假设按行存放，计算k维数组元素a[i1,i2,…，ik]的相对地址：((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+base-((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w(7.6)=V+base-C其中，对任何j，nj=highj-lowj+1第j维的界差例如三维整型数组a[1..10,1..20，1..30]n2=20n3=30w=4数组元素a[i,j,k]的相对地址：((i*20+j)*30+k)*4+A-((1*20+1)*30+1)*4=((i*20+j)*30+k)*4+A-2524

a[i,j,k]

:=

x的三地址代码

(1)T1:=i*20(2)T1:=T1+j(3)T1:=T1*30(4)T1:=T1+k

(5)T2:=A-2524(6)T3:=4*T1(7)T4:=T2[T3](8)T4:=x2024/4/2788产生引用数组元素的三地址代码数组元素的三地址代码结构T1:=V计算可变局部(有假设干条三地址语句)T2:=base-C计算不变局部(base,C可从符号表中查找到)T3:=T2[T1]访问元素的地址T3假设x:=a[i1,i2,…，ik]那么x:=T3假设a[i1,i2,…，ik]:=x那么T3:=x详解2024/4/2789数组类型在符号表中的信息组织数组的类型信息：VARa:ARRAY[1..10,1..20]OFreal;名字表信息向量

a嵌套深度偏移量类型C=84low1=1n1=10low2=1n2=20A基类