cmpl07old市公开课一等奖课件名师大赛获奖课件

第七章语义分析和中间代码产生内容：将属性文法和语法制导翻译技术应用于语义分析和中间代码产生。任务：1.静态语义检查:类型检查,控制流检查,一致性检查,有关名字检查,作用域分析等。2.翻译:产生中间代码,优化。地位：

语法分析器

静态检查器

中间代码产生器

优化器

8/11/20241语义分析和中间代码生成概述一种源程序通过词法分析、语法分析之后，表明该源程序在书写上是对的的，并且符合程序语言所规定的语法。但是语法分析并未对程序内部的逻辑含义加以分析，因此编译程序接下来的工作是语义分析。编译中的语义解决是指两个功效：第一，审查每个语法构造的静态语义，即验证语法构造正当的程序与否真正故意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义对的，语义解决则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表达形式（中间代码），或者将源程序翻译成目的代码。8/11/20242语义分析和中间代码生成类型检查。验证程序中执行的每个操作与否恪守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。控制流检查。控制流语句必须使控制转移到正当的地方。

例如，在C语言中break语句使控制跳离涉及该语句的最小while、for或switch语句。如果不存在涉及它的这样的语句，则就报错。一致性检查。在诸多场合规定对象只能被定义一次。例如Pascal语言规定同一标记符在一种分程序中只能被阐明一次，同一case语句的标号不能相似，枚举类型的元素不能重复出现等等。有关名字检查。有时，同一名字必须出现两次或多次。例如，Ada语言程序中，循环或程序块能够有一种名字，出现在这些构造的开头和结尾，编译程序必须检查这两个地方用的名字是相似的。名字的作用域分析静态语义分析普通涉及8/11/20243语义分析和中间代码生成中间代码所谓中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表达形式。为什么有的编译程序直接生成目的代码，有的编译程序采用中间代码。普通，快速编译程序直接生成目的代码，没有将中间代码翻译成目的代码的额外开销。但是为了使编译程序构造在逻辑上更为简朴明确，常采用中间代码，这样能够将与机器有关的某些实现细节置于代码生成阶段认真解决，并且能够在中间代码一级进行优化工作使得代码优化比较容易实现。8/11/20244语义分析和中间代码生成

§7.1中间语言7.1.1后缀式（逆波兰式）1.定义(1)如果E是一种常量或变量，则E的后缀式是E本身。(2)如果E是E1opE2形式的体现式，则E的后缀式是E1‘E2‘op，这里E1‘E2‘是E1、E2的后缀式。2.例：(a+b)*(c+d)的后缀式是：ab+cd+*3.把体现式翻译成后缀式的属性文法8/11/20245语义分析和中间代码生成7.1.2图表达法涉及DAG与抽象语法树(AST)。1.无循环有向图(DAG—DirectedAcyclicGragh)DAG与AST的区别是DAG能够有公共子体现式(结点可有多个父结点)。例:体现式a:=b*(-c)+b*(-c)的AST和DAG图及三地址码T1:=-c:=:=T1:=-cT2:=b*T1/\/\T2:=b*T1T3:=-ca+T5a+T3T3:=T2+T2T4:=b*T3/\()a:=T3T5:=T2+T4*T2*T4*T2a:=T5/\/\/\bT1bT3bT1|||-c-c-c8/11/20246语义分析和中间代码生成7.1.2图表达法(2)

2.产生建立赋值语句抽象语法树的属性文法 产生式 语义规则S→id:=ES.nptr:=mknode(‘assign”,mkleaf(id.id.place),E.nptr) E→E1+E2 E.nptr:=mknode(‘+’,E1.nptr,E2.nptr) E→E1*E2E.nptr:=mknode(‘*’,E1.nptr,E2.nptr) E→-E1E.nptr:=mknode(‘uminus’,E1.nptr) E→(E1)E.nptr:=E1.nptr E→idE.nptr:=mkleaf(id,id.place)

8/11/20247语义分析和中间代码生成7.1.2图表达法(3)例体现式a:=b*-c+b*-c的抽象语法树的表达：

8/11/20248语义分析和中间代码生成7.1.3三地址代码（1）普通形式：(1)x:=yopz(2)x:=opz(3)x:=y(4)gotoL(5)ifxrelopygotoL或ifxgotoL(6)paramxcallp,nreturny(7)x:=y[i],x[i]:=y(8)x:=&y,x:=*y,*x:=y例：体现式a:=b*-c+b*-c的三地址代码8/11/20249语义分析和中间代码生成7.1.3三地址代码（2）产生建立赋值语句三地址代码属性文法： 产生式 语义规则S→id:=ES.code:=E.code||gen(id.place’:=‘E.place) E→E1+E2

E.place:=newtempE.code:=E1.code||E2.code||gen(E.place’:=‘E1.place‘+’E2.place) E→E1*E2E.place:=newtempE.code:=E1.code||E2.code||gen(E.place’:=‘E1.place‘*’E2.place) E→-E1E.place:=newtempE.code:=E1.code||gen(E.place’:=‘’uminus’E1.place)E→(E1)E.place:=E1.placeE.code:=E1.codeE→idE.place:=id.placeE.code:=‘‘8/11/202410语义分析和中间代码生成7.1.4三地址代码的三种表达办法(1)例体现式a:=b*-c+b*-cd的三地址代码对应的1.四元式：用四个域的统计表达2.三元式：用三个域的统计表达8/11/202411语义分析和中间代码生成7.1.4三地址代码的三种表达办法(2)3.间接三元式：用三个域的统计和一种间接码表表达。语义规则中应增加产生间接码表的动作。例:X:=(A+B)*C;Y:=D(A+B)间接代码三元式表（1）（2）（3）（1）（4）（5）四元式、三元式和间接三元式的比较。8/11/202412语义分析和中间代码生成§7.2阐明语句7.2.1过程中的阐明语句(单层）P{offset:=0}DDD;DDid:T{enter(,T.type,offset);offset:=offset+T.width}Tinteger{T.type:=integer;T.width:=4}Treal{T.type:=real;T.width:=8}Tarray[num]ofT1{T.type:=array(num.val,T1.type);T.width:=num.val*T1.width}T↑T1{T.type:=pointer(T1.type);T.width:=4}8/11/202413语义分析和中间代码生成7.2.2 保存作用域信息（嵌套）(1)(1)programsort(input,output);(2)vara:array[0..10]ofinteger;(3)x:integer;(4)procedurereadarray;(5)vari:integer;(6)begin…a…end{readarray};(7)procedure

exchange(i,j:integer);(8)begin(9)x

a[i](10)end{exchange};(11)procedurequicksortm,n:integer);(12)vark,v:integer;(13)functionpartition(y,z:integer):integer;(14)vari,j:integer;(15)begin…a…v…exchange(i,j);…end(partition};(16)begin…end{quicksort};(17)begin…end{sort}.8/11/202414语义分析和中间代码生成7.2.2 保存作用域信息(2)

源程序8/11/202415语义分析和中间代码生成7.2.2 保存作用域信息(3)带嵌套的过程阐明的阐明语句的文法：PDDD;D|id:T|procid;D;S思路：*用一种栈tblptr管理符号表指针，用栈offset管理每个符号表的现在宽度*每一种过程都有一张符号表，即每碰到procid;时便创立一张新的符号表，返回指向外层的指针。*碰到D中的全部阐明都填入现在符号表。*在procid;D;S结束时，现在符号表填完，弹出tblptr和offset栈顶元素。并把id的项填入外层表，建立外层到现在符号表的指针。8/11/202416语义分析和中间代码生成7.2.2 保存作用域信息(4)带嵌套的过程阐明语句的翻译：PMD{addwidth(top(tblptr),top(offset));pop(tblptr);pop(offset)}/撤销最外层符号表/M{t:=mktable(nil);push(t,tblptr);push(0,offset)}/建最外层符号表/DD1;D2Dprocid;ND1;S{t:=top(tblptr);addwidth(t,top(offset));pop(tblptr);pop(offset);enterproc(top(tblptr),,t)}/一种过程结束时，计算该过程总宽度，并把该过程名字填入外层表中/Did:T{enter(top(tblptr),,T.type,top(offset));top(offset):=top(offset)+T.width}/id入表/N{t:=mktable(top(tblptr));push(t,tblptr);push(0,offset)}/进入新的一层符号表/8/11/202417语义分析和中间代码生成7.2.3统计中的域名统计的文法：TrecordLDend统计阐明的翻译：TrecordLDend{T.type:=record(top(tblptr));T.width:=top(offset);pop(tblptr);pop(offset)}L{t:=mktable(nil);push(t,tblptr);push(0,offset))}8/11/202418语义分析和中间代码生成§7.3赋值语句的翻译7.3.1 简朴算术体现式及赋值语句Sid:=E{p:=lookup();ifp≠nilthenemit(p’:=’E.place)elseerror}EE1+E2{E.place:=newtemp;emit(E.place’:=’E1.place‘+’E2.place)}EE1*E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘*’E2.place)}E-E1{E.place:=newtemp;emit(E.place‘:=’‘uminus’E1.place)}Eid{p:=lookup();ifp≠nilthenE.place:=pelseerror}8/11/202419语义分析和中间代码生成7.3.2数组元素的引用(1)按行持续寄存,静态存储以下：一维数组中，A[i]元素的地址：base+(i-low)×w=i×w+(base-low×w)=i×w+C二维数组中，A[i1,i2]元素的地址：base+((i1-low1)×n2+i2-low2)×w=((i1×n2)+i2)×w+(base-((low1×n2)+low2)×w)=(i1×n2)+i2)×w+Ck维数组中，A[i1,i2,…ik]元素的地址：((…(i1n2+i2)n3+i3)…)nk+ik)×w+base-…((low1n2+low2)n3+low3)…)nk+lowk)×w=((…(i1n2+i2)n3+i3)…)nk+ik)×w+C8/11/202420语义分析和中间代码生成7.3.2数组元素的引用(2)下标变量的定义：Lid[Elist]|idElistElist,E|E/下标体现式表Elist无法得到数组的定义信息/改写为:LElist]|idElistElist,E|id[E/下标体现式表Elist通过子节点得到数组的定义信息/8/11/202421语义分析和中间代码生成7.3.2数组元素的引用(3)

翻译模式:1.S

L:=E{ifL.offset=nullthenemit(L.place‘:=’E.place)elseemit(L.place‘[‘L.offset‘]’‘:=’E.place)}2.E

E1+E2{E.place:=newtemp;emit(E.place‘:=’E1place‘+’E2.place)}3.E

(E1){E.place:=E1.place}4.E

L{ifL.offset=nullthenE.place:=L.placeelsebeginE.place:=newtemp;emit(E.place‘:=’L.place‘[‘L.offset‘]’)end}5.L

Elist]{L.place:=newtemp;emit(L.place‘:=’Elist.array‘-’C);L.offset:=newtemp;emit(L.offset‘:=’w‘*’Elist.place)}8/11/202422语义分析和中间代码生成7.3.2数组元素的引用(4)6.L

id{L.place:=id.place;L.offset:=null}7.Elist

Elist1,E{t:=newtemp;m:=Elist1.ndim+1;emit(t‘:=’Elist1.place‘*’limit(Elist1.array,m));emit(t‘:=’t‘+’E.place);//lowi*ni+1+lowi+1Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=m}8.Elist

id[E{Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place}//记下数组的基本信息前半部分8/11/202423语义分析和中间代码生成7.3.2数组元素的引用(5)例7.1设A为一种10×20的数组,即n1=10,n2=20,并设w=4,界为1.对赋值语句x:=A[y,z]的带注释的语法分析树及三地址代码.S/|\L.place=x：=E.place=T4T1:=y×20L.offset=null|T1:=T1+z//y*20+z|L.place=T2T2:=A-84//(1×20+1)×4=84xL.offset=T3T3:=4×T1//(y*20+z)*4/\T4:=T2[T3]Elist.place=T1]x:=T4Elist.ndim=2Elist.array=A/|\Elist.place=y,E.place=zElist.ndim=1|Elist.array=AL.place=z/|\L.offset=nullA[E.place=y||zL.place=yL.offset=null|y8/11/202424算术体现式和赋值语句中的类型检查(1)体现式运算或规定同类型，或产生有关类型转换的指令。例：设x,y为实型，i,j为整型，则体现式x:=y=i*j的三地址码是：T1:=iint*jT3:=inttorealT1T2:=yreal+T3x:=T28/11/202425语义分析和中间代码生成算术体现式和赋值语句中的类型检查(2)有关产生EE1+E2的带语义检查的三地址码的语义动作以下：{E.place:=newtemp;ifE1.type=integerandE2.type=integerthenbeginemit(E.place’:=‘E1.place’int+’E2.place);E.type:=integerendelseifE1.type=realandE2.type=realthenbeginemit(E.place’:=‘E1.place’real+’E2.place);E.type:=realend8/11/202426语义分析和中间代码生成算术体现式和赋值语句中的类型检查(3)ElseifE1.type=integerandE2.type=realthenbeginu:=newtemp;emit(u’:=‘‘inttorealE1.place);emit(E.place’:=‘u‘real+’E2.place);E.type:=realendElseifE1.type=realandE2.type=integerthenbeginu:=newtemp;emit(u’:=‘‘inttorealE2.place);emit(E.place’:=‘E1.place‘real+’u);E.type:=realendelseE.type:=type_error类型检查(2)8/11/202427语义分析和中间代码生成7.3.3统计中域的引用用在符号表中查找名字的程序同样来查找域名。体现式pinfo+1的翻译过程以下：p是指向某个统计的指针，info是它的一种域，则p.type是pointer（record（t）），p是record（t）类型，t是该统计对应的符号表，域名info将在t所指向的符号表中找到。8/11/202428语义分析和中间代码生成7.4 布尔体现式的翻译(1)7.4.1 数值表达法EE1orE2{E.place:=newtemp;Emit(E.place‘:=’E1.place‘or’E2.place)}EE1andE2{E.place:=newtemp;Emit(E.place‘:=’E1.place‘and’E2.place)}EnotE1{E.place:=newtemp;Emit(E.place‘:=’‘not’E1.place)}E(E1)(E.place:=E1.place)

8/11/202429语义分析和中间代码生成7.4 布尔体现式的翻译(2)E

id1relopid2{E.place:=newtemp;emit(‘if’id1.placerelop.opid2.place‘goto’nextstat+3);emit(E.place‘:=’‘0’);emit(‘goto’nextstat+2);emit(E.place‘:=’‘1’)}E

id{E.place:=id.place}前半部分8/11/202430语义分析和中间代码生成7.4 布尔体现式的翻译(3)例7.2根据数值表达法对布尔体现式a<borc<dande<f翻译为三地址代码.100ifa<bgoto103108ife<fgoto111101T1:=0109T3:=0102goto104110goto112103T1:=1111T3:=1104ifc<dgoto107112T4:=T2andT3105T2:=0113T5:=T1orT4106goto108107T2:=18/11/202431语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（0）条件语句：ifEthenS1elseS2能够翻译成以下形式：8/11/202432语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（1）作为转移条件的布尔式,可翻译为一串跳转指令.例:语句ifa>corb<dthenS1elseS2可译为ifa>cgotoL2gotoL1L1:ifb<dgotoL2gotoL3L2:(有关S1的三地址代码序列)//E.truegotoLnextL3:(有关S2的三地址代码序列)//E.falseLnext:8/11/202433语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（2）产生布尔体现式三地址代码的语义规则/属性文法EE1orE2E1.true:=E.true;/E.true是E为真时应当执行的语句的起始位置/E1.false:=newlabel;/E1.false是E1为假时应当执行的语句的起始位置，即E2的起始位置/E2.true:=E.true;E2.false:=E.false/E.true和E.false由E所在的环境拟定/E.code:=E1.code||gen(E1.false‘:’)||E2.codeEE1andE2E1.true:=newlabelE1.false:=E.falseE2.true:=E.trueE2.false:=E.falseE.code:=E1.code||gen(E1.true‘:’)||E2.code8/11/202434语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（3）

E

notE1E1.true:=E.falseE1.false:=E.trueE.code:=E1.codeE

(E1)E1.true:=E.falseE1.false:=E.falseE.code:=E1.codeE

id1relopid2E.code:=gen(‘if’id1.placerelopid2.place‘goto’E.true)||gen(‘goto’E.false)E

trueE.code:=gen(‘goto’E.true)E

falseE.code:=gen(‘goto’E.false)前半部分8/11/202435语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（4）例语句a<borc<dande<f可译为：ifa<bgotoLtruegotoL1L1:ifc<dgotoL2gotoLfalseL2：ife<fgotoLtruegotoLfalse属性文法8/11/202436语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（5）产生布尔体现式的四元式代码的翻译模式EE1orME2{backpatch(E1.falselist,M.quad);/回填，此时找到了E1为假时应当转去的地方/E.truelist:=merge(E1.truelist,E2.truelist);/E.truelist是在拟定了E为真时应当去的地方之后需要回填指令的链表/E.falselist:=E2.falselist}EE1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)}EnotE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}E(E1){E.truelist:=E1.truelist;E.falselist:=E1.falselist}8/11/202437语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（6）Eid1relopid2{E.truelist:=makelist(nextquad);/下一条指令需要在确切懂得E为真时应当去的地方后回填/E.falselist:=makelist(nextquad+1);/下下一条指令需要在确切懂得E为假时应当去的地方后回填/emit(‘j’relop.op‘,’id1.place‘,’id2.place‘,’‘0’)emit(‘j,-,-,0’)}Eid{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘juz’‘,’id.place‘,’‘_’‘,’‘0’)emit(‘j,-,-,0’)}M{M.quad:=nextquad}前半部分8/11/202438语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（7）例:语句a<borc<dande<f带注释的分析树为:E.t=100.104E.f=103.105//\\E.t=100orM.q=102E.t=104E.f=101|E.f=103.105/|\ξ//\\a<bE.t=102andM.q=104E.t=104E.f=103|E.f=105/|\ξ/|\c<de<f8/11/202439语义分析和中间代码生成7.4.2作为条件控制的布尔式翻译（8）

100(j<,a,b,0)101(j,-,-,102)102(j<,c,d,104)103(j,-,-,0)104(j<,e,f.100)105(j,-,-,0)分析树

8/11/202440语义分析和中间代码生成§7.5控制语句的翻译7.5.1控制流语句（1）语句SIFEthenS1|IFEthenS1elseS2|whileEdoSd的代码构造：

8/11/202441语义分析和中间代码生成7.5.1控制流语句（2）控制流语句的属性文法S

ifEthenS1E.true:=newlabel;E.false:=S.next;S1.next:=S.next;S.code:=E.code||geu(E.true‘:’)||S1.codeS

ifEthenS1elseS2E.true:=newlabel；E.false:=newlabel；S1.next:=S.next；S2.next:=S.next；S.code:=E.code||gen(E.true‘:’)||S1.code||gen(‘goto’S.next)||gen(E.false‘:’)||S2.code8/11/202442语义分析和中间代码生成7.5.1控制流语句（3）S

whileEdoS1S.begin:=newlabelE.true:=newlabelE.false:=newlabelS1.next:=S.beginS.code:=gen(S.begin‘:’)||E.code||gen(S.true‘:’)||S1.code||gen(‘goto’S.begin)前半部分8/11/202443语义分析和中间代码生成7.5.1控制流语句（4）例7.5语句whilea<bdoifc<dthenx:=y+zelsex:=y-z;可翻译为:L1:ifa<bgotoL2gotoLnextL2:ifc<dgotoL3gotoL4L3:T1:=y+zx:=T1gotoL1L4:T2:=y-zx:=T2gotoL1Lnext:翻译模式8/11/202444语义分析和中间代码生成控制语句的一遍翻译模式（1）

S

ifEthenM1S1NelseM2S2{backpatch(E.truelist,M1.quad);backpatch(E.falselist,M2.quad);S1nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)}N

{N.nextlist:=makelist(nextquad);emit(‘j,-,-,-‘)}M

{M.quad:=nextquad}S

ifEthenMS1{backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1nextlist)}8/11/202445语义分析和中间代码生成控制语句的一遍翻译模式（2）S

whileM1EdoM2S1{backpatch(S1.nextlist,M1.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselistemit(‘j,-,-,’M1.quad)}S

beginLead{S.nextlist:=L.nextlist}S

A{S.nextlist:=makelist()}L

L1;MS{backpatch(L1.nextlist,M.quad);L.nextlist:=S.nextlist}L

S{L.nextlist:=S.nextlist}前半部分8/11/202446语义分析和中间代码生成控制语句的一遍翻译模式（3）例7.6语句while(a<b)doif(c<d)thenx:=y+z;可译为:

100(j<,a,b,102)E1.truelist101(j,-,-,107)E1.falselist=S.nextlist102(j<,c,d,104)E2.truelist103(j,-,-,100)E2.falselist104(+,y,z,t)105(:=,t,-,x)

106(j,-,-,100)107翻译模式8/11/202447语义分析和中间代码生成7.5.2 标号与goto语句(1)S

labelSlabel

i:{iflook()=falsethen{enter(,lab,y,addr),backpatch(I.gotolist,nextquad)}elseiflook()=trueandi.def=‘n’then{i.def=‘y’,i.addr=nextqudbackpatch(I.gotolist,nextquad)}elseerror}8/11/202448语义分析和中间代码生成7.5.2 标号与goto语句(2)S

gotoi{iflookup(I)=falsethen{enter(,lab,n,nextquad),makelist(nextquad)}elseiflook()=trueandi.def=‘n’then{enterlist(i.gotolist,nextquad),emit(j,-,-,i.addr)}