第七章第七章语义分析和中间代码产生语义分析和中间代码产生n静态语义检查静态语义检查类型检查类型检查控制流检查控制流检查一致性检查一致性检查相关名字检查相关名字检查名字的作用域分析名字的作用域分析语法分语法分析器析器中间代码中间代码产生器产生器静态检静态检查器查器中间代码中间代码优化器优化器国防科技大学计算机系国防科技大学计算机系602教研室教研室n中间语言中间语言(复杂性界于源语言和目标语言复杂性界于源语言和目标语言之间之间)的好处：的好处：便于进行与机器无关的代码优化工作便于进行与机器无关的代码优化工作易于移植易于移植使编译程序的结构在逻辑上更为简单明确使编译程序的结构在逻辑上更为简单明确源语言源语言程序程序目标语目标语言程序言程序中间语中间语言程序言程序CompilerFront EndCompilerBack End国防科技大学计算机系国防科技大学计算机系602教研室教研室n常用的中间语言：常用的中间语言：后缀式，逆波兰表示后缀式，逆波兰表示图表示：图表示：DAG、抽象语法树、抽象语法树三地址代码三地址代码n三元式三元式n四元式四元式n间接三元式间接三元式7.1中间语言中间语言国防科技大学计算机系国防科技大学计算机系602教研室教研室7.1.1 7.1.1 后缀式后缀式 n后后缀缀式式表表示示法法：Lukasiewicz发发明明的的一一种种表表示示表达式的方法，又称表达式的方法，又称逆波兰逆波兰表示法。表示法。n一个表达式一个表达式E的后缀形式可以如下定义：的后缀形式可以如下定义：1.如果如果E是一个变量或常量，则是一个变量或常量，则E的后缀式是的后缀式是E自自身。身。2.如果如果E是是E1opE2形式的表达式，其中形式的表达式，其中op是任是任何二元操作符，则何二元操作符，则E的后缀式为的后缀式为E1 E2 op，其其中中E1 和和E2 分别为分别为E1和和E2的后缀式。的后缀式。3.如果如果E是是(E1)形式的表达式，则形式的表达式，则E1的后缀式就的后缀式就是是E的后缀式。的后缀式。国防科技大学计算机系国防科技大学计算机系602教研室教研室n逆逆波波兰兰表表示示法法不不用用括括号号。只只要要知知道道每每个个算算符符的的目目数数，对对于于后后缀缀式式，不不论论从从哪哪一一端进行扫描，都能对它进行唯一分解。端进行扫描，都能对它进行唯一分解。n后缀式的计算后缀式的计算用一个栈实现。用一个栈实现。一一般般的的计计算算过过程程是是：自自左左至至右右扫扫描描后后缀缀式式，每每碰碰到到运运算算量量就就把把它它推推进进栈栈。每每碰碰到到k目目运运算算符符就就把把它它作作用用于于栈栈顶顶的的k个个项项，并并用用运运算算结果代替这结果代替这k个项个项。国防科技大学计算机系国防科技大学计算机系602教研室教研室把表达式翻译成后缀式的语义规则描述把表达式翻译成后缀式的语义规则描述产生式产生式EE(1)op E(2)E (E(1)Eid语义动作语义动作E.code:= E(1).code | E(2).code |opE.code:= E(1).codeE.code:=idE.code表示表示E后缀形式后缀形式op表示任意二元操作符表示任意二元操作符“|”表示后缀形式的连接表示后缀形式的连接。国防科技大学计算机系国防科技大学计算机系602教研室教研室n数组数组POST存放后缀式：存放后缀式：k为下标，初值为为下标，初值为1n上述语义动作可实现为：上述语义动作可实现为：产生式产生式程序段程序段EE(1)opE(2)POSTk:=op;k:=k+1E(E(1)EiPOSTk:=i;k:=k+1n例：输入串例：输入串a+b+c的分析和翻译的分析和翻译POST：12345EE(1)op E(2) E.code:= E(1).code | E(2).code |opE (E(1)E.code:= E(1).codeEidE.code:=idab+c+国防科技大学计算机系国防科技大学计算机系602教研室教研室7.1.2图表示法图表示法n图表示法图表示法DAG抽象语法树抽象语法树国防科技大学计算机系国防科技大学计算机系602教研室教研室7.1.2图表示法图表示法n无循环有向图无循环有向图(DirectedAcyclicGraph，简称简称DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAG中都有一个中都有一个结点结点一个一个内部结点内部结点代表一个代表一个操作符操作符，它的孩子代表，它的孩子代表操作数操作数在一个在一个DAG中代表公共子表达式的结点具有多中代表公共子表达式的结点具有多个父结点个父结点国防科技大学计算机系国防科技大学计算机系602教研室教研室a:=b*(-c)+b*(-c)的图表示法的图表示法assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc国防科技大学计算机系国防科技大学计算机系602教研室教研室抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc抽象语法树抽象语法树*buminusc国防科技大学计算机系国防科技大学计算机系602教研室教研室DAG对应的代码：对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5国防科技大学计算机系国防科技大学计算机系602教研室教研室产生赋值语句抽象语法树的属性文法产生赋值语句抽象语法树的属性文法产产生生式式语义规则语义规则Sid:=ES.nptr:=mknode(assign,mkleaf(id,id.place),E.nptr)EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(*,E1.nptr,E2.nptr)E-E1 E.nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptrEidE.nptr:=mkleaf(id,id.place)国防科技大学计算机系国防科技大学计算机系602教研室教研室7.1.3三地址代码三地址代码n三地址代码三地址代码x:=yopzn三地址代码可以看成是抽象语法树或三地址代码可以看成是抽象语法树或DAG的一种线性表示的一种线性表示国防科技大学计算机系国防科技大学计算机系602教研室教研室a:=b*(-c)+b*(-c)的图表示法的图表示法assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc国防科技大学计算机系国防科技大学计算机系602教研室教研室 T1:=-cT1:=-c T2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2 T4:=b*T3a:=T5 T5:=T2+T4a:=T5对于抽象语法树的代码对于抽象语法树的代码对于对于DAG的代码的代码国防科技大学计算机系国防科技大学计算机系602教研室教研室三地址语句的种类三地址语句的种类nx:=yopznx:=opynx:=yngotoLnifxrelopygotoL或或ifagotoLnparamx和和callp,n，以及返回语句以及返回语句returnynx:=yi及及xi:=y的索引赋值的索引赋值nx:=&y,x:=*y和和*x:=y的地址和指针赋值的地址和指针赋值国防科技大学计算机系国防科技大学计算机系602教研室教研室n生成三地址代码时，临时变量的名字对应生成三地址代码时，临时变量的名字对应抽象语法树的内部结点抽象语法树的内部结点nid:=E对表达式对表达式E求值并置于变量求值并置于变量T中值中值id.place:=T国防科技大学计算机系国防科技大学计算机系602教研室教研室从赋值语句生成三地址代码的从赋值语句生成三地址代码的S-属性文法属性文法n非终结符号非终结符号S有综合属性有综合属性S.code，它代表赋它代表赋值语句值语句S的三地址代码。的三地址代码。n非终结符号非终结符号E有如下两个属性：有如下两个属性：E.place表示存放表示存放E值的名字。值的名字。E.code表示对表示对E求值的三地址语句序列。求值的三地址语句序列。函函数数newtemp的的功功能能是是，每每次次调调用用它它时时，将将返返回一个不同临时变量名字回一个不同临时变量名字,如如T1,T2,。国防科技大学计算机系国防科技大学计算机系602教研室教研室为赋值语句生成三地址代码的为赋值语句生成三地址代码的S-属性文法定义属性文法定义产生式产生式语义规则语义规则Sid:=ES.code:=E.code|gen(id.place:=E.place)EE1+E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place+E2.place)EE1*E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place*E2.place)E-E1E.place:=newtemp;E.code:=E1.code|gen(E.place:=uminusE1.place)E(E1)E.place:=E1.place;E.code:=E1.codeEid E.place:=id.place;E.code=国防科技大学计算机系国防科技大学计算机系602教研室教研室三地址语句三地址语句n四元式四元式一个带有四个域的记录结构，这四个域分别一个带有四个域的记录结构，这四个域分别称为称为op,arg1,arg2及及resultoparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a国防科技大学计算机系国防科技大学计算机系602教研室教研室三地址语句三地址语句n三元式三元式通过计算临时变量值的语句的位置来引用这通过计算临时变量值的语句的位置来引用这个临时变量个临时变量三个域：三个域：op、arg1和和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4)国防科技大学计算机系国防科技大学计算机系602教研室教研室三地址语句三地址语句nxi:=yoparg1arg2(0)=xi(1)ynx:=yioparg1arg2(0) =yi(1)assign x(0)国防科技大学计算机系国防科技大学计算机系602教研室教研室三地址语句三地址语句n间接三元式间接三元式为为了了便便于于优优化化，用用三三元元式式表表+间间接接码码表表表表示示中间代码中间代码间间接接码码表表:一一张张指指示示器器表表，按按运运算算的的先先后后次次序列出有关三元式在三元式表中的位置。序列出有关三元式在三元式表中的位置。优点优点:方便优化，节省空间方便优化，节省空间国防科技大学计算机系国防科技大学计算机系602教研室教研室n例如，语句例如，语句X:=(A+B)*C;Y:=D(A+B)的间接三元式表示如下表所示。的间接三元式表示如下表所示。国防科技大学计算机系国防科技大学计算机系602教研室教研室7.2说明语句说明语句国防科技大学计算机系国防科技大学计算机系602教研室教研室7.3赋值语句的翻译赋值语句的翻译n7.3.1简单算术表达式及赋值语句简单算术表达式及赋值语句国防科技大学计算机系国防科技大学计算机系602教研室教研室为赋值语句生成三地址代码的为赋值语句生成三地址代码的S-属性文法定义属性文法定义产生式产生式语义规则语义规则Sid:=ES.code:=E.code|gen(id.place:=E.place)EE1+E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place+E2.place)EE1*E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place*E2.place)E-E1E.place:=newtemp;E.code:=E1.code|gen(E.place:=uminusE1.place)E(E1)E.place:=E1.place;E.code:=E1.codeEid E.place:=id.place;E.code=国防科技大学计算机系国防科技大学计算机系602教研室教研室产生赋值语句三地址代码的翻译模式产生赋值语句三地址代码的翻译模式Sid:=Ep:=lookup(id.name);ifp nilthenemit(p:=E.place)elseerrorEE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place)EE1*E2E.place:=newtemp;emit(E.place:=E1.place*E2.place)Sid:=ES.code:=E.code|gen(id.place:=E.place)EE1+E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place+E2.place)EE1*E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place*E2.place)国防科技大学计算机系国防科技大学计算机系602教研室教研室产生赋值语句三地址代码的翻译模式产生赋值语句三地址代码的翻译模式E-E1E.place:=newtemp;emit(E.place:=uminusE1.place)E(E1)E.place:=E1.placeEidp:=lookup(id.name);ifp nilthenE.place:=pelseerrorE-E1E.place:=newtemp;E.code:=E1.code|gen(E.place:=uminusE1.place)E(E1)E.place:=E1.place;E.code:=E1.codeEidE.place:=id.place;E.code=国防科技大学计算机系国防科技大学计算机系602教研室教研室7.3.2数组元素的引用数组元素的引用n数组元素地址的计算：数组元素地址的计算：国防科技大学计算机系国防科技大学计算机系602教研室教研室n设设A为为n维数组，每个元素宽度为维数组，每个元素宽度为w，lowi为第为第i维维的下界，的下界，ni是为第是为第i维维可取值的个可取值的个数数,base为为A的第一个元素相对地址的第一个元素相对地址n元素元素Ai1,i2,ik相对地址公式相对地址公式(i1n2+i2)n3+i3)nk+ik)w+base-(low1n2+low2)n3+low3)nk+lowk)wnC=base-(low1n2+low2)n3+low3)nk+lowk)w国防科技大学计算机系国防科技大学计算机系602教研室教研室nid出现的地方也允许下面产生式中的出现的地方也允许下面产生式中的L出现出现LidElist|idElistElist,E|E为了便于处理，文法改写为为了便于处理，文法改写为LElist|idElistElist,E|idE国防科技大学计算机系国防科技大学计算机系602教研室教研室n引入下列语义变量或语义过程引入下列语义变量或语义过程:Elist.ndim：下标个数计数器下标个数计数器Elist.place：表表示示临临时时变变量量，用用来来临临时时存存放放已形成的已形成的Elist中的下标表达式计算出来的值中的下标表达式计算出来的值limit(array，j)：函函数数过过程程，它它给给出出数数组组array的第的第j维的长度维的长度国防科技大学计算机系国防科技大学计算机系602教研室教研室n每个代表变量的非终结符每个代表变量的非终结符L有两项语义值有两项语义值L.place：n若若L为为简单变量简单变量i,指变量指变量i的符号表入口的符号表入口n若若L为为下标变量下标变量，指存放，指存放CONSPART的的临时临时变量的整数码变量的整数码L.offset：n若若L为为简单变量简单变量，null，n若若L为为下标变量下标变量，指存放，指存放VARPART的临时变的临时变量的整数码量的整数码国防科技大学计算机系国防科技大学计算机系602教研室教研室(1)SL:=E(2)EE+E(3)E(E)(4)EL(5)LElist(6)Lid(7)ElistElist,E(8)ElistidE国防科技大学计算机系国防科技大学计算机系602教研室教研室(1)SL:=EifL.offset=nullthen/*L是简单变量是简单变量*/emit(L.place:=E.place)elseemit(L.placeL.offset:=E.place)(2)EE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place)国防科技大学计算机系国防科技大学计算机系602教研室教研室(3)E(E1)E.place:=E1.place(4)ELifL.offset=nullthenE.place:=L.placeelsebeginE.place:=newtemp;emit(E.place:=L.placeL.offset)end国防科技大学计算机系国防科技大学计算机系602教研室教研室Ai1,i2,ik(i1n2+i2)n3+i3)nk+ik)w+base-(low1n2+low2)n3+low3)nk+lowk)w(8)ElistidEElist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place国防科技大学计算机系国防科技大学计算机系602教研室教研室Ai1,i2,ik(i1n2+i2)n3+i3)nk+ik)w+base-(low1n2+low2)n3+low3)nk+lowk)w(7)ElistElist1,E t:=newtemp;m:=Elist1.ndim+1;emit(t:=Elist1.place*limit(Elist1.array,m);emit(t:=t+E.place); Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=m国防科技大学计算机系国防科技大学计算机系602教研室教研室Ai1,i2,ik(i1n2+i2)n3+i3)nk+ik)w+base-(low1n2+low2)n3+low3)nk+lowk)w(5)LElistL.place:=newtemp;emit(L.place:=Elist.arrayC);L.offset:=newtemp;emit(L.offset:=w*Elist.place)(6)LidL.place:=id.place;L.offset:=null国防科技大学计算机系国防科技大学计算机系602教研室教研室类型转换类型转换n用用E.type表示非终结符表示非终结符E的类型属性的类型属性n对应产生式对应产生式EE1opE2的语义动作中关于的语义动作中关于E.type的语义规则可定义为：的语义规则可定义为：ifE1.type=integerand E2.type=integerE.type:=integerelseE.type:=realn算算符符区区分分为为整整型型算算符符intop和和实实型型算算符符realop，国防科技大学计算机系国防科技大学计算机系602教研室教研室nx:=yi*j其其中中x、y为为实实型型；i、j为为整整型型。这这个个赋赋值值句句产生的三地址代码为：产生的三地址代码为：T1:=iint*jT3:=inttorealT1T2:=yreal+T3x:=T2国防科技大学计算机系国防科技大学计算机系602教研室教研室关于产生式关于产生式EE1E2的语义动作的语义动作E.place:=newtemp;ifE1.type=integerandE2.type=integerthenbeginemit(E.place:=E1.placeint+E2.place);E.type:=integerendelseifE1.type=realandE2.type=realthenbeginemit(E.place:=E1.placereal+E2.place);E.type:=realend国防科技大学计算机系国防科技大学计算机系602教研室教研室elseifE1.type=integerandE2.type=realthenbeginu:=newtemp;emit(u:=inttorealE1.place);emit(E.place:=ureal+E2.palce);E.type:=realendelseifE1.type=realandE1.type=integerthenbeginu:=newtemp;emit(u:=inttorealE2.place);emit(E.place:=E1.placereal+u);E.type:=realendelseE.type:=type_error国防科技大学计算机系国防科技大学计算机系602教研室教研室7.3.3记录中域的引用记录中域的引用n符号表表项之中保存记录中的域的类型和符号表表项之中保存记录中的域的类型和相对地址信息相对地址信息国防科技大学计算机系国防科技大学计算机系602教研室教研室7.4布尔表达式的翻译布尔表达式的翻译n布尔表达式的两个基本作用布尔表达式的两个基本作用:用于逻辑演算用于逻辑演算,计算逻辑值计算逻辑值;用于控制语句的条件式用于控制语句的条件式.n产生布尔表达式的文法产生布尔表达式的文法:EEorE|EandE| E|(E)|iropi|i国防科技大学计算机系国防科技大学计算机系602教研室教研室n计算布尔表达式通常采用两种方法计算布尔表达式通常采用两种方法:1.如同计算算术表达式一样如同计算算术表达式一样,一步步算一步步算1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采用某种优化措施采用某种优化措施把把AorB解释成解释成ifAthentrueelseB把把AandB解释成解释成ifAthenBelsefalse把把 A解释成解释成ifAthenfalseelsetrue国防科技大学计算机系国防科技大学计算机系602教研室教研室两种不同的翻译方法两种不同的翻译方法:n第一种翻译法：第一种翻译法：AorBandC=D翻译成翻译成(1)(=,C,D,T1)(2)(and,B,T1,T2)(3)(or,A,T2,T3)n第第二二种种翻翻译译法法适适合合于于作作为为条条件件表表达达式式的的布尔表达式使用布尔表达式使用.国防科技大学计算机系国防科技大学计算机系602教研室教研室7.4.1数值表示法数值表示法naorbandnotc翻译成翻译成T1:=notcT2:=bandT1T3:=aorT1nab的关系表达式可等价地写成的关系表达式可等价地写成ifabthen1else0，翻译成翻译成 100:ifabgoto103101:T:=0102:goto104103:T:=1104:国防科技大学计算机系国防科技大学计算机系602教研室教研室关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式n过程过程emit将三地址代码送到输出文件中将三地址代码送到输出文件中nnextstat给出输出序列中下一条三地址语句的给出输出序列中下一条三地址语句的地址索引地址索引n每产生一条三地址语句后，过程每产生一条三地址语句后，过程emit便把便把nextstat加加1国防科技大学计算机系国防科技大学计算机系602教研室教研室关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式EE1orE2E.place:=newtemp;emit(E.place:=E1.placeorE2.place)EE1andE2E.place:=newtemp;emit(E.place:=E1.placeandE2.place)EnotE1E.place:=newtemp;emit(E.place:=notE1.place)E(E1)E.place:=E1.place国防科技大学计算机系国防科技大学计算机系602教研室教研室关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式Eid1relopid2E.place:=newtemp;emit(ifid1.placerelop.opid2.placegotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1)EidE.place:=id.placeab翻译成翻译成100:ifabgoto103101:T:=0102:goto104103:T:=1104:国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式布尔表达式aborcdandef的翻译结果的翻译结果100:ifabgoto103101:T1:=0102:goto104103:T1:=1104:ifcdgoto107105:T2:=0106:goto108107: T2:=1108:ifecorbcgotoL2“真真”出口出口gotoL1L1:ifbdgotoL2“真真”出口出口gotoL3“假假”出口出口L2:(关于关于S1的三地址代码序列的三地址代码序列)gotoLnextL3:(关于关于S2的三地址代码序列的三地址代码序列)Lnext:国防科技大学计算机系国防科技大学计算机系602教研室教研室n每次调用函数每次调用函数newlabel后都返回一个新的后都返回一个新的符号标号符号标号n对于一个布尔表达式对于一个布尔表达式E，引用两个标号引用两个标号E.true是是E为为真真时控制流转向的标号时控制流转向的标号E.false是是E为为假假时控制流转向的标号时控制流转向的标号国防科技大学计算机系国防科技大学计算机系602教研室教研室产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则产生式产生式语义规则语义规则EE1orE2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true; E2.false:=E.false;E.code:=E1.code|gen(E1.false:)|E2.codeE1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.false国防科技大学计算机系国防科技大学计算机系602教研室教研室产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则产生式产生式语义规则语义规则EE1andE2E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.fasle;E.code:=E1.code|gen(E1.true:)|E2.codeE1.codeTo E. falseTo E1. trueE2.codeTo E.trueTo E.false国防科技大学计算机系国防科技大学计算机系602教研室教研室产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则产生式产生式语义规则语义规则EnotE1E1.true:=E.false;E1.false:=E.true;E.code:=E1.codeE(E1) E1.true:=E.true;E1.false:=E.false;E.code:=E1.code国防科技大学计算机系国防科技大学计算机系602教研室教研室产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则产生式产生式语义规则语义规则Eid1relopid2E.code:=gen(ifid1.placerelop.opid2.placegotoE.true)|gen(gotoE.false)Etrue E.code:=gen(gotoE.true)Efalse E.code:=gen(gotoE.false)国防科技大学计算机系国防科技大学计算机系602教研室教研室考虑如下表达式：考虑如下表达式：aborcdandef假定整个表达式的真假出口已分别置为假定整个表达式的真假出口已分别置为Ltrue和和Lfalse，则按定义将生成如下的代码：则按定义将生成如下的代码：ifabgotoLtruegotoL1L1:ifcdgotoL2gotoLfalseL2:ifefgotoLtruegotoLfalse国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译布尔表达式的翻译n两遍扫描两遍扫描为给定的输入串构造一棵语法树；为给定的输入串构造一棵语法树；对语法树进行深度优先遍历，进行语义规则中对语法树进行深度优先遍历，进行语义规则中规定的翻译。规定的翻译。n一遍扫描一遍扫描国防科技大学计算机系国防科技大学计算机系602教研室教研室一遍扫描实现布尔表达式的翻译一遍扫描实现布尔表达式的翻译n采用四元式形式采用四元式形式n把四元式存入一个数组中，数组下标就代表四元把四元式存入一个数组中，数组下标就代表四元式的标号式的标号n约定约定四元式四元式(jnz,a,-,p)表示表示ifagotop四元式四元式(jrop,x,y,p)表示表示ifxropygotop四元式四元式(j,-,-,p)表示表示gotop国防科技大学计算机系国防科技大学计算机系602教研室教研室n有有时时,四四元元式式转转移移地地址址无无法法立立即即知知道道,我我们们只只好好把把这这个个未未完完成成的的四四元元式式地地址址作作为为E的语义值保存的语义值保存,待机待机回填回填。国防科技大学计算机系国防科技大学计算机系602教研室教研室n为为非非终终结结符符E赋赋予予两两个个综综合合属属性性E.truelist和和E.falselist。它它们们分分别别记记录录布布尔尔表表达达式式E所所应应的的四四元元式式中中需需回回填填“真真”、“假假”出出口口的的四四元元式式的的标号所构成的链表标号所构成的链表n例例如如:假假定定E的的四四元元式式中中需需要要回回填填真真出出口口的的p，q，r三个四元式，则三个四元式，则E.truelist为下列链为下列链:(p)(x，x，x，0)(q)(x，x，x，p)(r)(x，x，x，q)链尾链尾E. truelist =r国防科技大学计算机系国防科技大学计算机系602教研室教研室n为为了了处处理理E.truelist和和E.falselist，引引入入下下列列语义变量和过程语义变量和过程:变量变量nextquad，它指向下一条将要产生但尚未形它指向下一条将要产生但尚未形成的四元式的地址成的四元式的地址(标号标号)。nextquad的初值为的初值为1，每当执行一次，每当执行一次emit之后，之后，nextquad将自动增将自动增1。函数函数makelist(i)，它将创建一个仅含它将创建一个仅含i的新链表，的新链表，其中其中i是四元式数组的一个下标是四元式数组的一个下标(标号标号)；函数返回；函数返回指向这个链的指针。指向这个链的指针。函数函数merge(p1,p2)，把以把以p1和和p2为链首的两条链为链首的两条链合并为一，作为函数值，回送合并后的链首。合并为一，作为函数值，回送合并后的链首。过程过程backpatch(p,t)，其功能是完成其功能是完成“回填回填”，把把p所链接的每个四元式的第四区段都填为所链接的每个四元式的第四区段都填为t。国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的文法布尔表达式的文法(1)E E1orME2(2)|E1andME2(3)|notE1(4)|(E1)(5)|id1relopid2(6)|id(7)M 国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译模式布尔表达式的翻译模式(7)M M.quad:=nextquad国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译模式布尔表达式的翻译模式(1)EE1orME2backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist(2)EE1andME2backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)E1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.falseE1.codeTo E. falseTo E1. trueE2.codeTo E.trueTo E.false国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译模式布尔表达式的翻译模式(3)EnotE1E.truelist:=E1.falselist;E.falselist:=E1.truelist(4)E(E1)E.truelist:=E1.truelist;E.falselist:=E1.falselist国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译模式布尔表达式的翻译模式(5)Eid1relopid2E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place,id2.place,0);emit(j,0)(6)EidE.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jnz,id.place,0)；emit(j,-,-,0)国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译模式布尔表达式的翻译模式n作作为为整整个个布布尔尔表表达达式式的的真真假假出出口口(转转移移目标目标)仍待回填仍待回填.国防科技大学计算机系国防科技大学计算机系602教研室教研室aborcdandef100 (j,a,b,0)101 (j,-,-,102)102 (j,c,d,104)103 (j,-,-,0)104 (j,e,f,100)truelist105 (j,-,-,103)falselist国防科技大学计算机系国防科技大学计算机系602教研室教研室n计算布尔表达式通常采用两种方法计算布尔表达式通常采用两种方法:1.如同计算算术表达式一样如同计算算术表达式一样,一步步算一步步算1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采用某种优化措施采用某种优化措施把把AorB解释成解释成ifAthentrueelseB把把AandB解释成解释成ifAthenBelsefalse把把 A解释成解释成ifAthenfalseelsetrue回顾：布尔表达式的翻译回顾：布尔表达式的翻译国防科技大学计算机系国防科技大学计算机系602教研室教研室关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式Eid1relopid2E.place:=newtemp;emit(ifid1.placerelop.opid2.placegotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1)EidE.place:=id.placeEE1orE2E.place:=newtemp;emit(E.place:=E1.placeorE2.place)EE1andE2E.place:=newtemp;emit(E.place:=E1.placeandE2.place)国防科技大学计算机系国防科技大学计算机系602教研室教研室回顾：布尔表达式的翻译回顾：布尔表达式的翻译n作为条件控制的布尔式翻译作为条件控制的布尔式翻译n一遍扫描实现布尔表达式的翻译一遍扫描实现布尔表达式的翻译国防科技大学计算机系国防科技大学计算机系602教研室教研室7.4.2作为条件控制的布尔式翻译作为条件控制的布尔式翻译n条件语句条件语句ifEthenS1elseS2赋予赋予E两种出口两种出口:一真一假一真一假E.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.nextE.true:E.false:国防科技大学计算机系国防科技大学计算机系602教研室教研室产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则产生式产生式语义规则语义规则EE1orE2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true; E2.false:=E.false;E.code:=E1.code|gen(E1.false:)|E2.codeE1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.false国防科技大学计算机系国防科技大学计算机系602教研室教研室产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则产生式产生式语义规则语义规则EE1andE2E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.fasle;E.code:=E1.code|gen(E1.true:)|E2.codeE1.codeTo E. falseTo E1. trueE2.codeTo E.trueTo E.false国防科技大学计算机系国防科技大学计算机系602教研室教研室产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则产生式产生式语义规则语义规则EnotE1E1.true:=E.false;E1.false:=E.true;E.code:=E1.codeE(E1) E1.true:=E.true;E1.false:=E.false;E.code:=E1.code国防科技大学计算机系国防科技大学计算机系602教研室教研室产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则产生式产生式语义规则语义规则Eid1relopid2E.code:=gen(ifid1.placerelop.opid2.placegotoE.true)|gen(gotoE.false)Etrue E.code:=gen(gotoE.true)Efalse E.code:=gen(gotoE.false)国防科技大学计算机系国防科技大学计算机系602教研室教研室回顾：布尔表达式的翻译回顾：布尔表达式的翻译n作为条件控制的布尔式翻译作为条件控制的布尔式翻译n一遍扫描实现布尔表达式的翻译一遍扫描实现布尔表达式的翻译国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的文法布尔表达式的文法(1)E E1orME2(2)|E1andME2(3)|notE1(4)|(E1)(5)|id1relopid2(6)|id(7)M 国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译模式布尔表达式的翻译模式(1)EE1orME2backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist(2)EE1andME2backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)(3)EnotE1E.truelist:=E1.falselist;E.falselist:=E1.truelist(4)E(E1)E.truelist:=E1.truelist;E.falselist:=E1.falselist国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译模式布尔表达式的翻译模式(5)Eid1relopid2E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place,id2.place,0);emit(j,0)(6)EidE.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jnz,id.place,0)；emit(j,-,-,0)(7)M M.quad:=nextquad国防科技大学计算机系国防科技大学计算机系602教研室教研室布尔表达式的翻译模式布尔表达式的翻译模式n作作为为整整个个布布尔尔表表达达式式的的真真假假出出口口(转转移移目标目标)仍待回填仍待回填.国防科技大学计算机系国防科技大学计算机系602教研室教研室7.5控制语句的翻译控制语句的翻译n考虑下列产生式所定义的语句考虑下列产生式所定义的语句SifEthenS1|ifEthenS1elseS2|whileEdoS1其中其中E为布尔表达式。为布尔表达式。国防科技大学计算机系国防科技大学计算机系602教研室教研室nif-then语句语句SifEthenS1E.codeS1.codeTo E.trueTo E.falseE.true:E.false:国防科技大学计算机系国防科技大学计算机系602教研室教研室if-then语句的属性文法语句的属性文法产生式产生式语义规则语义规则SifEthenS1E.true:=newlabel;E.flase:=S.next;S1.next:=S.nextS.code:=E.code|gen(E.true:)|S1.codeE.codeS1.codeTo E.trueTo E.falseE.true:E.false:国防科技大学计算机系国防科技大学计算机系602教研室教研室nif-then-else语句语句SifEthenS1elseS2E.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.nextE.true:E.false:国防科技大学计算机系国防科技大学计算机系602教研室教研室if-then-else语句的属性文法语句的属性文法产生式产生式语义规则语义规则SifEthenS1elseS2E.true:=newlabel;E.false:=newlabel;S1.next:=S.nextS2.next:=S.next;S.code:=E.code|gen(E.true:)|S1.code|gen(gotoS.next)|gen(E.false:)|S2.codeE.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.nextE.true:E.false:国防科技大学计算机系国防科技大学计算机系602教研室教研室nwhile-do语句语句SwhileEdoS1E.codeS1.codeTo E.trueTo E.falsegoto S.beginS.begin:E.true:E.false:国防科技大学计算机系国防科技大学计算机系602教研室教研室while-do语句的属性文法语句的属性文法产生式产生式语义规则语义规则SwhileEdoS1S.begin:=newlabel;E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin:)|E.code|gen(E.true:)|S1.code|gen(gotoS.begin)E.codeS1.codeTo E.trueTo E.falsegoto S.beginS.begin:E.true:E.false:国防科技大学计算机系国防科技大学计算机系602教研室教研室考虑如下语句考虑如下语句:whileabdoifcdthenx:=y+zelsex:=y-zn生成下列代码：生成下列代码：L1:ifabgotoL2gotoLnextL2:ifcdgotoL3gotoL4L3:T1:=y+zx:=T1gotoL1L4:T2:=y-zx:=T2gotoL1Lnext:国防科技大学计算机系国防科技大学计算机系602教研室教研室一遍扫描翻译控制流语句一遍扫描翻译控制流语句n考虑下列产生式所定义的语句考虑下列产生式所定义的语句:(1)SifEthenS(2)|ifEthenSelseS(3)|whileEdoS(4)|beginLend(5)|A(6)LL;S(7)|SnS表示语句，表示语句，L表示语句表，表示语句表，A为赋值语句，为赋值语句，E为一个布尔表达式为一个布尔表达式国防科技大学计算机系国防科技大学计算机系602教研室教研室nif语句的翻译语句的翻译相关产生式相关产生式SifEthenS(1)|ifEthenS(1)elseS(2)改写后产生式改写后产生式SifEthenMS1SifEthenM1S1NelseM2S2M N 国防科技大学计算机系国防科技大学计算机系602教研室教研室翻译模式翻译模式:1.SifEthenMS1backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)2.SifEthenM1S1NelseM2S2 backpatch(E.truelist,M1.quad);backpatch(E.falselist,M2.quad);S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)3.M M.quad:=nextquad4.N N.nextlist:=makelist(nextquad);emit(j,)国防科技大学计算机系国防科技大学计算机系602教研室教研室nwhile语句的翻译语句的翻译相关产生式相关产生式SwhileEdoS(1)n翻译为：翻译为：E的代码的代码S (1)的代码的代码“真真”出口出口“假假”出口出口为了便于为了便于回填回填，改写产生式为，改写产生式为:Swhile M1 E do M2 S1 M 国防科技大学计算机系国防科技大学计算机系602教研室教研室n翻译模式翻译模式:1.SwhileM1EdoM2S1 backpatch(S1.nextlist,M1.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselistemit(j,M1.quad)2.M M.quad:=nextquad国防科技大学计算机系国防科技大学计算机系602教研室教研室n产生式产生式LL;S改写为：改写为：LL1;MSM 国防科技大学计算机系国防科技大学计算机系602教研室教研室n翻译模式翻译模式:1.LL1;MSbackpatch(L1.nextlist,M.quad);L.nextlist:=S.nextlist2.M M.quad:=nextquad国防科技大学计算机系国防科技大学计算机系602教研室教研室n其它几个语句的翻译其它几个语句的翻译1.SbeginLendS.nextlist:=L.nextlist2.SAS.nextlist:=makelist()3.LSL.nextlist:=S.nextlist国防科技大学计算机系国防科技大学计算机系602教研室教研室翻译语句翻译语句while(ab)doif(cd)thenx:=y+z;P190(5)Eid1relopid2E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place,id2.place,0);emit(j,0)P179Sid:=Ep:=lookup(id.name);ifp nilthenemit(p:=E.place)elseerrorEE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place)P195SifEthenMS1backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist, S1.nextlist)M M.quad:=nextquadSAS.nextlist:=makelist()P195SwhileM1EdoM2S1 backpatch(S1.nextlist,M1.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselistemit(j,M1.quad)M M.quad:=nextquad国防科技大学计算机系国防科技大学计算机系602教研室教研室翻译语句翻译语句while(ab)doif(cd)thenx:=y+z;100(j,a,b,102)101(j,-,-,107)102(j,c,d,104)103(j,-,-,100)104(+,y,z,T)105(:=,T,-,x)106 (j,-,-,100)107国防科技大学计算机系国防科技大学计算机系602教研室教研室7.5.2标号与标号与goto语句语句n标号定义形式标号定义形式L:S；n标号引用标号引用gotoL；n示例：示例：向后转移：向后转移：L1: goto L1;向前转移：向前转移：goto L1; L1: 国防科技大学计算机系国防科技大学计算机系602教研室教研室符号表信息符号表信息名字名字类型类型定义否定义否地址地址L标号标号r(P)(j,-,-,0)(q)(j,-,-,p)(r)(j,-,-,q)已已未未国防科技大学计算机系国防科技大学计算机系602教研室教研室产生式产生式S gotoL的语义动作的语义动作:查找符号表；查找符号表；IFL在符号表中且在符号表中且定义否定义否栏为栏为已已THENGEN(J，-，-，P)ELSEIFL不在符号表中不在符号表中THENBEGIN把把L填入表中；填入表中；置置定义否定义否为为未未，地址地址栏为栏为NXQ；GEN(J，-，-，0)ENDELSEBEGINQ:=L的地址栏中的编号；的地址栏中的编号；置地址栏编号为置地址栏编号为NXQ；GEN(J，-，-，Q)END国防科技大学计算机系国防科技大学计算机系602教研室教研室n带标号语句的产生式带标号语句的产生式:SlabelSlabeli:nlabeli:对应的语义动作对应的语义动作:1.若若i所所指指的的标标识识符符(假假定定为为L)不不在在符符号号表表中中，则则把把它它填填入入，置置类类型型为为标标号号，定定义义否否为为已已，地址地址为为nextquad；2.若若L已已在在符符号号表表中中但但类类型型不不为为标标号号或或定定义义否否为为已已，则报告出错；，则报告出错；3.若若L已在符号表中，则把标号已在符号表中，则把标号未未改为改为已已，然，然后，把地址栏中的链头后，把地址栏中的链头(记为记为q)取出，同时把取出，同时把nextquad填在其中，最后，执行填在其中，最后，执行BACKPATCH(q，nextquad)。国防科技大学计算机系国防科技大学计算机系602教研室教研室7.5.3CASE语句的翻译语句的翻译n语句结构语句结构caseEofC1:S1;C2:S2;Cn-1: Sn-1;otherwise:Snend国防科技大学计算机系国防科技大学计算机系602教研室教研室n翻译法翻译法(一一):T:=EL1:ifT C1gotoL2S1的代的代码gotonextL2:ifT C2gotoL3S2的代码的代码gotonextL3:Ln-1: ifT Cn-1gotoLnSn-1的代码的代码gotonextLn:Sn的代码的代码next:改进改进:国防科技大学计算机系国防科技大学计算机系602教研室教研室n翻译法翻译法(二二):计算计算E并放入并放入T中中gototestL1:关于关于S1的中间码的中间码gotonextLn-1: 关于关于Sn-1的中间码的中间码gotonextLn:关于关于Sn的中间码的中间码gotonexttest: ifT=C1gotoL1ifT=C2gotoL2ifT=Cn-1gotoLn-1gotoLnnext:(case, C1, P1)(case, C2, P2)(case, Cn-1, Pn-1)(case, T, Pn)(label, NEXT, -, -)Pi是是Li在在符号表中符号表中的位置的位置国防科技大学计算机系国防科技大学计算机系602教研室教研室7.6过程调用的处理过程调用的处理n过程调用主要对应两种事过程调用主要对应两种事:传递参数传递参数转子转子n传传地地址址:把把实实在在参参数数的的地地址址传传递递给给相相应应的的形形式式参参数数调调用用段段预预先先把把实实在在参参数数的的地地址址传传递递到到被被调调用用段段可以拿到的地方可以拿到的地方；程程序序控控制制转转入入被被调调用用段段之之后后，被被调调用用段段首首先先把把实在参数的实在参数的地址地址抄进自己相应的形式单元中抄进自己相应的形式单元中；过过程程体体对对形形式式参参数数的的引引用用域域赋赋值值被被处处理理成成对对形形式单元的式单元的间接访问间接访问。国防科技大学计算机系国防科技大学计算机系602教研室教研室n翻翻译译方方法法：把把实实参参的的地地址址逐逐一一放放在在转转子子指指令的前面令的前面.例如，例如，CALLS(A，X+Y)翻译为翻译为:计算计算X+Y置于置于T中的代码中的代码 parA/*第一个参数的地址第一个参数的地址*/ parT/*第二个参数的地址第二个参数的地址*/ callS/*转子转子*/国防科技大学计算机系国防科技大学计算机系602教研室教研室过程调用的翻译过程调用的翻译n过程调用文法过程调用文法:(1)Scallid(Elist)(2)ElistElist,E(3)ElistEn参数的地址存放在一个队列中参数的地址存放在一个队列中n最最后后对对队队列列队队列列中中的的每每一一项项生生成成一一条条par语语句句国防科技大学计算机系国防科技大学计算机系602教研室教研室n翻译模式翻译模式3.ElistE初始化初始化queue仅包含仅包含E.place2.ElistElist,E将将E.place加入到加入到queue的队尾的队尾1.Scallid(Elist)for队列队列queue中的每一项中的每一项pdoemit(paramp);emit(callid.place)国防科技大学计算机系国防科技大学计算机系602教研室教研室作业作业nP217-1，3，4，5，6，7，12国防科技大学计算机系国防科技大学计算机系602教研室教研室