语义分析和中间代码生成_第1页
语义分析和中间代码生成_第2页
语义分析和中间代码生成_第3页
语义分析和中间代码生成_第4页
语义分析和中间代码生成_第5页
已阅读5页,还剩61页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

语义分析和中间代码生成翻译为中间语言的好处(1)便于进行与机器无关的代码优化;(2)使编译程序改变目标机更容易;易于编译器的移植(3)使编译程序的结构在逻辑上更为简单明确,以中间语言为界面,编译前端和后端的接口更清晰。第2页,共66页,2024年2月25日,星期天主要内容中间语言的形式后缀式,图表方法,三元式编译过程中不同语言的翻译或处理方法说明语句的翻译赋值语句的翻译布尔表达式的翻译控制语句的翻译第3页,共66页,2024年2月25日,星期天7.1中间语言中间语言的形式:逆波兰表示:后缀式图表示法:DAG和AST三地址代码:四元式、三元式、间接三元式

第4页,共66页,2024年2月25日,星期天7.1.1后缀式

后缀式表示法又称逆波兰表示法。这种方法是,把运算量(操作数)写在前面,把算符写在后面(后缀)。一个表达式的后缀式可以如下定义:(1)如果E是一个变量或常量,则E的后缀式是E自身。(2)如果E是E1opE2形式的表达式,这里op是任何二元操作符,则E的后缀式为E1’E2’op,这里E1’

和E2’分别为E1和E2的后缀式。(3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。第5页,共66页,2024年2月25日,星期天后缀式的优点

便于计算机处理,因为在后缀式中,表达式的求值顺序与运算符出现的顺序一致,这样只要用一个栈就可以实现表达式的求值。实现过程:自左向右扫描后缀表达式;遇到运算对象入栈,遇到N元运算符,就从栈顶取出N个运算对象进行计算,再将结果入栈;当全部后缀表达式扫描结束,则栈顶的值即为表达式结果。第6页,共66页,2024年2月25日,星期天后缀式特点:无括号运算对象的顺序与中缀式一致根据操作符(运算符)的优先级和结合性进行相关的处理例:5+4*6546*+第7页,共66页,2024年2月25日,星期天7.1.2图表示法图表示法包括DAG与AST(抽象语法树)。有向无环图(DirectedAcyclicGraph,简称DAG).与抽象语法树一样,对于表达式中的每个子表达式,DAG图中都有一个结点。一个内部结点代表一个操作符,它的孩子代表操作数。两者不同的是,在DAG图中代表公共子表达式的结点具有多个父结点,而在一棵抽象语法树中公共子表达式被表示为重复的子树。例:第8页,共66页,2024年2月25日,星期天5+4*6的DAG图5+64*5+4*6+4*6的DAG图5+64*+5+4*6+4*6的AST图5+64*+64*第9页,共66页,2024年2月25日,星期天后缀式与抽象语法树的关系后缀式是抽象语法树的线性表示:每个结点都是在它的所有子节点之后立即出现的。通过对抽象语法树的不同形式的遍历可以形成不同形式的缀式表达式前序遍历:前缀式中序遍历:中缀式后序遍历:后缀式5+64*+64*第10页,共66页,2024年2月25日,星期天产生赋值语句抽象语法树的属性文法S.nptr:=mknode('assign',mkleaf(id,id.place),E.nptr)

E.nptr:=mknode('+',E1.nptr,E2.nptr)E.nptr:=mknode('*',E1.nptr,E2.nptr)mkleaf(id,id.place)S→id:=EE→E1+E2E→E1*E2

E->id产生式语义规则第11页,共66页,2024年2月25日,星期天S.nptr:=mknode('assign',mkleaf(id,id.place),E.nptr)

E.nptr:=mknode('+',E1.nptr,E2.nptr)E.nptr:=mknode('*',E1.nptr,E2.nptr)E.nptr:=mkleaf(id,id.place)mkleaf(id,id.place)S→id:=EE→E1+E2E→E1*E2E->id

a:=b+cabc+:=第12页,共66页,2024年2月25日,星期天抽象语法树的存储表示二叉树的形式:算术运算通常都是二元运算树中每个节点包含三个域:数组的形式表示:每一个数组元素形式如下:节点类型|操作数1|操作数2节点类型|操作数1|操作数2第13页,共66页,2024年2月25日,星期天*

uminus

id

c

id

b

赋值语句:a:=b*-c+b*-c后缀式:abcuminus*bcuminus*+assignassign

+

*

uminus

id

a

id

c

id

b

idb

idcunimus1*02

idb

idc

unimus5

*46

+37

ida

assign98

...

第14页,共66页,2024年2月25日,星期天7.1.3三地址代码三地址代码是由下面一般形式的语句构成的序列:X:=yopz

其中,x、y、z为名字、常数或编译时产生的临时变量(存放中间结果,对应于语法树的内部节点);

op代表运算符号如定点运算符、浮点运算符、逻辑运算符等。每个语句的右边只能有一个运算符。每条语句通常包含三个地址:两个操作数地址,一个操作结果地址第15页,共66页,2024年2月25日,星期天三地址码示例t1:=-ct2:=b*t1t3:=-ct4:=b*t3t5:=t2+t4a:=t5assigna+*bcuminus*uminuscba:=b*-c+b*-c第16页,共66页,2024年2月25日,星期天三地址码示例(2)assigna+*bcuminust1:=-ct2:=b*t1t5:=t2+t2a:=t5

a:=b*-c+b*-c第17页,共66页,2024年2月25日,星期天三地址代码的具体表示1.四元式:op,arg1,arg2,result(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcbt2t5arg1t1t3t4arg2resultt1t2t3t4t5aop

t1:=-ct2:=b*t1t3:=-ct4:=b*t3t5:=t2+t4a:=t5a:=b*(-c)+b*(-c)第18页,共66页,2024年2月25日,星期天三地址代码的具体表示2.三元式:op,arg1,arg2(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcb(1)aarg1(0)(2)(3)(4)arg2op

t1:=-ct2:=b*t1t3:=-ct4:=b*t3t5:=t2+t4a:=t5a:=b*(-c)+b*(-c)第19页,共66页,2024年2月25日,星期天三地址代码的具体表示3.间接三元式:间接码表+三元式表目的:便于优化处理t1:=-ct2:=b*t1t3:=-ct4:=b*t3t5:=t2+t4a:=t5(1)(2)(3)(4)uminus*+assigncb(2)aarg1(1)(2)(3)arg2op间接代码表(1)(2)(1)(2)(3)(4)a:=b*(-c)+b*(-c)第20页,共66页,2024年2月25日,星期天t1:=a+bt2:=t1*cX:=t2t3:=a+bt4:=d^t3Y:=t4(1)(2)(3)(4)(5)+*:=^:=a(1)xdYarg1bc(2)(1)(4)arg2op间接代码表(1)(2)(3)(1)(4)(5)X:=(a+b)*cY:=d^(a+b)第21页,共66页,2024年2月25日,星期天语义分析中各种语句的处理说明语句的翻译赋值语句的翻译布尔表达式的翻译控制语句的翻译第22页,共66页,2024年2月25日,星期天7.2说明语句的翻译说明语句的处理方式:不生成可执行代码,只涉及符号表的操作。说明语句的处理:对每个局部名字,在符号表中建立相应的表项,填写有关的信息如类型、嵌套深度、相对地址等。相对地址:相对静态数据区基址或活动记录中局部数据区基址的一个偏移值。第23页,共66页,2024年2月25日,星期天因为每进入一次过程需分配一次内存,因此在处理过程内的说明语句时,要分配每个标识符的相对地址。设变量offset用来记录相对地址,每次进入一个过程,先将offset置为0。每次遇到一个新名字,则把名字同offset的当前值一起录入符号表,然后offset的值增加,其增加的值由该名字的数据类型所决定,称为数据对象的宽度,用属性width表示。假设integer型对象宽度为4,real型对象宽度为8,则下表为过程中说明语句的翻译方案。第24页,共66页,2024年2月25日,星期天过程中的说明语句的翻译P→D {offset:=0}

D→D;DD→id:T {enter(,T.type,offset); offset:=offset+T.width}T→integer {T.type:=integer;T.width:=4}T→real {T.type:=real;T.width:=8}T→array[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}第25页,共66页,2024年2月25日,星期天7.3赋值语句的翻译在本节中赋值语句中的表达式的类型可以是整型、实型、数组和记录。作为翻译赋值语句为三地址代码的一部分,我们将主要讨论:

简单赋值语句的翻译

第26页,共66页,2024年2月25日,星期天7.3.1简单算术表达式及赋值语句的翻译所讨论的简单赋值语句不包含对数组元素、记录元素的引用,仅包含对简单变量的算术表达式的引用。并且假定赋值语句中所有变量均为同一类型,不必考虑类型转换的问题。简单赋值语句的文法G[s]如下:S→id:=EE→E+T|TT→T*F|FF→(E)|id分析文法G[S],可以看到文法中包含两类不同语义操作的产生式,一类含有运算符操作,一类仅含有传值操作。因此,要使语义分析后能产生三地址语句中间代码,应该对这两类不同的产生式进行不同的处理,含有运算符操作的产生式的语义动作应该产生相应的三地址语句,而仅含有传值操作的产生式则只进行传值的语义处理。根据这种思想,可以构造出各产生式的语义子程序如下表所示。第27页,共66页,2024年2月25日,星期天产生赋值语句三地址代码的翻译模式S→id:=E {p:=lookup(); ifp<>nilthenemit(p':='E.place)elseerror}E→E1+E2 {E.place=newtemp;

emit(E.place':='E1.place'+'E2.place')}E→E1*E2 {E.place=newtemp;

emit(E.place':='E1.place'*'E2.place')}E→-E {E.place:=newtemp; emit(E.place´:=´´uminus´E1.place}E→(E1) {E.place:=E1.place}E→id {p:=lookup(); ifp<>nilthenE.place:=pelseerror}有关说明:(1)语义变量E.place:表示存放E值的变量名在符号表的位置或一整数码(若此变量是一个临时变量);

(2)语义变量id.name:表示单词id的名字;

(3)语义过程newtemp:表示生成一个临时变量,每调用一次,生成一新的临时变量;

(4)语义过程lookup:表示检查id.name是否出现在符号表中,若在则返回一指向该登记项的指针,否则返回nil:

(5)语义过程emit:表示产生三地址语句并输出到文件上。第28页,共66页,2024年2月25日,星期天t1:=-ct2:=b*t1t3:=-ct4:=b*t3t5:=t2+t4a:=t5assigna+*bcuminus*uminuscba:=b*-c+b*-c产生赋值语句三地址代码的翻译模式S→id:=E{p:=lookup(); ifp<>nilthenemit(p':='E.place)elseerror}E→E1+E2{E.place=newtemp;

emit(E.place':='E1.place'+'E2.place')}E→E1*E2{E.place=newtemp;

emit(E.place':='E1.place'*'E2.place')}E→-E {E.place:=newtemp; emit(E.place´:=´´uminus´E1.place}E→(E1){E.place:=E1.place}E→id {p:=lookup(); ifp<>nilthenE.place:=pelseerror}第29页,共66页,2024年2月25日,星期天7.4布尔表达式的翻译布尔表达式:

用布尔运算符号(and,or,not)作用到布尔变量或关系表达式上而组成。布尔表达式的作用:

1.用作计算逻辑值

2.用作控制流语句如if-then,if-then-else和while-do等之中的条件表达式第30页,共66页,2024年2月25日,星期天◆一个布尔表达式的值的计算

方法一:用数值表示真和假,从而对布尔表达式的求值,可以象对算术表达式的求值那样一步一步地来计算

方法二:优化的方法。AorB解释成ifAthentrueelseBAandB解释成ifAthenBelsefalsenotA解释成ifAthenfalseelsetrue第31页,共66页,2024年2月25日,星期天7.4.1数值表示法的翻译(用作计算逻辑值)用1表示真,0表示假来实现布尔表达式的翻译例如,布尔表达式:aorbandnotc

翻译成三地址代码序列:

100:t1:=notc101:t2:=bandt1102:t3:=aort1oraandbcnot第32页,共66页,2024年2月25日,星期天关系表达式:a<b等价于ifa<bthen1else0翻译成三地址代码序列:

100:ifa<bgotol03

101:t:=0102:gotol04

103:t:=1104:

第33页,共66页,2024年2月25日,星期天关于布尔表达式的数值表示法的翻译模式E→E1orE2 {E.place:=newtemp; emit(E.place‘:=‘E1.place‘or’E2.place)}E→E1andE2 {E.place:=newtemp; emit(E.place':='E1.place'and’E2.place)}E→notE1 {E.place:=newtemp;emit(E.place':=''not'E1.place)}第34页,共66页,2024年2月25日,星期天E→id1relopid2注:relop是关系运算符

{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→ture {E.place:=newtemp;emit(E.place':=''1')}

E→false {E.place:=newtemp;emit(E.place':=''0')}

a<b的翻译:

100:ifa<bgotol03

101:t:=0102:gotol04

103:t:=1104:

第35页,共66页,2024年2月25日,星期天例:考虑如下语句:X=a<bandc<dore<fa<bEandC<dEor

e<fEEE100:ifa<bgoto103101:t1=0102:goto104103:t1=1104:ifc<dgoto107105:t2=0106:goto108107:t2=1109:ife<fgoto112110:t4=0111:goto113112:t4=1X=S108:T3=t1andt2113:T5=t3ort4114:x:=t5第36页,共66页,2024年2月25日,星期天7.4.2作为条件控制语句的布尔表达式的翻译(采用简化的方法进行布尔表达式的计算)文法:ifEthenS1elseS2

E.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.false生成的代码结构:S2.code……S.next:第37页,共66页,2024年2月25日,星期天控制语句中的条件表达式翻译的基本思想给控制语句中的条件表达式设两个属性:E.true,和E.false,记录控制语句所转向的两个语句的标号。对条件表达式的翻译如下:E:a<b,生成如下的代码Ifa<bgotoE.trueGotoE.falseE.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.falseS2.code……s.next:第38页,共66页,2024年2月25日,星期天控制语句中的条件表达式翻译的基本思想假定E形如E1orE2。若E1为真,则立即可知E为真,于是E1.true与E.true是相同的。若El为false则必须对E2求值,因此我们置E1.false:为E2的代码的第一条指令的标号。而E2的真、假出口可以分别与E的真、假出口相同。类似可考虑形如E1andE2的E的翻译。至于形如notE1的布尔表达式E不必生成新的代码,只要把E1的假、真出口作为E的真、假出口即可。按此方式可以写出布尔表达式译成三地址代码的语义规则。注意E的true和false属性均为继承属性。E:E1orE2E1.true=E.true,E1.false=E2的第一条代码E2.true=E.true,E2.false=E.false第39页,共66页,2024年2月25日,星期天控制语句中的条件表达式翻译的基本思想E:E1orE2E1.true=E.trueE1.false=E2的第一条代码E2.true=E.trueE2.false=E.falseE1.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.falseS2.code……s.next:E2.codetoE.truetoE.false第40页,共66页,2024年2月25日,星期天控制语句中的条件表达式翻译的基本思想E:E1andE2E1.true=E2的第一条语句;E1.false=E.falseE2.true=E.true;E2.false=E.falseE1.codeS1.codeE.true:Gotos.nextE.false:toE.truetoE.falseS2.code……s.next:E2.codetoE.truetoE.false第41页,共66页,2024年2月25日,星期天产生式语义规则E→E1orE2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.falseE.code:=E1.code||gen(E1.false’:’)||E2.code第42页,共66页,2024年2月25日,星期天产生式语义规则E→E1andE2E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code‖gen(E1.true’:’)‖E2.codeE→notE1E1.true:=E.false;E1.false:=E.true;E.code:=E1.code第43页,共66页,2024年2月25日,星期天产生式语义规则E→id1relopid2E.code:=gen(‘if’id1.placerelop.opid2.place‘goto’E.true)||gen(‘goto’E.false)E→trueE.code:=gen(‘goto’E.true)E→falseE.code:=gen(‘goto’E.false)E的true和false属性都是继承属性,E.code是综合属性。因此该语义规则的不能通过一遍扫描完成。E→(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.code第44页,共66页,2024年2月25日,星期天例:考虑如下语句:

a<borc<dande<f假定整个表达式的真假出口分别置为Ltrue和Lfalse

a<bEorC<dEande<fEEEifa<bgotoE.truegotoE.falseifc<dgotoE.truegotoE.falseife<fgotoE.truegotoE.falseifc<dgotoE.truegotoE.falseL2:ife<fgotoE.truegotoE.falseifa<bgotoE.truegotoE.falseL1:ifc<dgotoE.truegotoE.falseL2:ife<fgotoE.truegotoE.false第45页,共66页,2024年2月25日,星期天例:考虑如下语句:

a<borc<dande<f假定整个表达式的真假出口分别置为Ltrue和Lfalsea<bEorC<dEande<fEEEifc<dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalseifa<bgotoLtruegotoL1L1:ifc<dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalseL1:L2:ifa<bgotoE.truegotoE.falseifc<dgotoE.truegotoE.falseife<fgotoE.truegotoE.false第46页,共66页,2024年2月25日,星期天例:考虑如下语句:a<bandc<dore<fa<bEandC<dEore<fEEEifa<bgotoE.truegotoE.falseifc<dgotoE.truegotoE.falseife<fgotoE.truegotoE.falseifa<bgotoE.truegotoE.falseL1:ifc<dgotoE.truegotoE.falseifa<bgotoE.truegotoE.falsel1:ifc<dgotoE.truegotoE.falsel2:ife<fgotoE.truegotoE.falseL1:L2:第47页,共66页,2024年2月25日,星期天例:考虑如下语句:a<bandc<dore<fa<bEandC<dEore<fEEEifa<bgotoE.truegotoE.falseL1:ifc<dgotoE.truegotoE.falseL2:ife<fgotoE.truegotoE.falseL1:L2:ifa<bgotoL1gotoE.falseL1:ifc<dgotoE.truegotoL2L2:ife<fgotoE.truegotoE.false第48页,共66页,2024年2月25日,星期天

我们假设实现三地址代码时采用四元式形式实现,并且假定:(jnz,a,-,p)表示ifagotop(jrop,x,y,p)表示ifxropygotop(j,-,-,p)表示gotop第49页,共66页,2024年2月25日,星期天控制语句中布尔表达式的翻译模式一遍扫描的表达式翻译中存在的问题:生成某些转移语句时,转移到的目标的标号是未知的解决方案:当目标语句的标号确定后,进行回填第50页,共66页,2024年2月25日,星期天用四元式表示1:(j<,a,b,3)2:(j,-,-,6)3:(+,a,1,t1)4:(:=,t1,-,a)5:(j,-,-,8)6:(+,b,1,t2)7:(:=,t2,-,b)8:……例:ifa<bthena:=a+1elseb:=b+1第51页,共66页,2024年2月25日,星期天7.5控制语句的翻译任何程序都可有顺序结构、选择结构和while循环结构表示,这三类结构可用如下的文法描述:(1)S→ifEthenS

(2)|ifEthenSelseS

(3)|whileEdoS

(4)|beginLend

(5)|A

(6)L→L;S

(7)|SS表示语句 E为一个布尔表达式L表示语句块A为赋值语句 第52页,共66页,2024年2月25日,星期天控制流语句的翻译模式:SifEthenS1

的四元式序列

1.(j,E,-,3)2.(j,-,-,q)3.

……q.……S1的四元式序列第53页,共66页,2024年2月25日,星期天2.SifEthen

S1elseS2的四元式序列

1.(j,E,-,3)2.(j,-,-,p+1)3.……p.(j,-,-,q)p+1.……q.……

S1的四元式序列S2的四元式序列第54页,共66页,2024年2月25日,星期天3.S

whileEdoS1的四元式序列

1.(j,E,-,3)2.(j,-,-,p+1)3.……p.(j,-,-,1)p+1.……

S1的四元式序列第55页,共66页,2024年2月25日,星期天(4)S

beginLend

(5)S

A

(6)L→L;S

(7)S

S1语句块L的四元式序列赋值语句A的四元式序列语句块L的四元式序列语句S的四元式序列语句S1的四元式序列第56页,共66页,2024年2月25日,星期天翻译为四元式例:将语句ifa<borc<dande<fthens1elses21(j<,a,b,?)2(j,-,-,?)3(j<,c,d,?)4(j,-,-

?)5(j<,e,f,?)6(j,-,-,?)7S1的四元式序列

……p(j,-,-,?)p+1S2的四元式序列

……q……1(j<,a,b,7)2(j,-,-,3)3(j<,c,d,5)4(j,-,-

p+1)5(j<,e,f,7)6(j,-,-,p+1)7S1的四元式序列

……p(j,-,-,q)第57页,共66页,2024年2月25日,星期天例:考虑如下语句:

whilea<bdoifc<dthenx:=y+z100(j<,a,b,?)101(j<,--,--,?)106(j,--,--,100)104(+,y,z,T)105(:=,T,--,x)102(j<,c,d,?)103(j<,--,--,?)102(j<,c,d,104)103(j<,--,--,?)102(j<,c,d,104)103(j<,--,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论