【精品】【考研计算机专业课】天津大学 编译原理ppt课件 part7语义分析与中间代码生成(可编辑.ppt
《【精品】【考研计算机专业课】天津大学 编译原理ppt课件 part7语义分析与中间代码生成(可编辑.ppt》由会员分享,可在线阅读,更多相关《【精品】【考研计算机专业课】天津大学 编译原理ppt课件 part7语义分析与中间代码生成(可编辑.ppt(70页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、【考研计算机专业课】天津大学 编译原理PPT课件 Part7语义分析与中间代码生成语义分析的位置和作用语义分析的位置和作用紧跟在语法分析和语法分析之后,编译程序要做的工紧跟在语法分析和语法分析之后,编译程序要做的工作就是进行静态语义检查和翻译。作就是进行静态语义检查和翻译。编译器必须要检查源程序是否符合源语言规定的语法编译器必须要检查源程序是否符合源语言规定的语法和语义要求。这种检查称为静态检查,检查并报告程和语义要求。这种检查称为静态检查,检查并报告程序中某些类型的错误。序中某些类型的错误。语法分析器语法分析器记号流记号流类型检查器类型检查器语法树语法树中间代码中间代码生成器生成器语法树语法
2、树中间表示中间表示静态语义检查静态语义检查静态语义检查通常包括:静态语义检查通常包括:类型检查:如果操作符作用于不相容的操作数,编译类型检查:如果操作符作用于不相容的操作数,编译器应该报错器应该报错控制流检查:引起控制流从某个结构中跳转出来的语控制流检查:引起控制流从某个结构中跳转出来的语句必须能够决定控制流转向的目标地址句必须能够决定控制流转向的目标地址唯一性检查:有时,有的对象只能被定义一次。比如,唯一性检查:有时,有的对象只能被定义一次。比如,同一同一case语句的标号不能相同,枚举类型的元素不能重语句的标号不能相同,枚举类型的元素不能重复。复。与名字相关的检查:有时候要求同一名字在特定
3、位置与名字相关的检查:有时候要求同一名字在特定位置出现两次或多次(如,标识结构的开始和结尾)出现两次或多次(如,标识结构的开始和结尾)中间语言中间语言源语言的中间表示方法源语言的中间表示方法抽象语法树抽象语法树后缀式后缀式三地址代码(包括三元式、四元式、间接三元式)三地址代码(包括三元式、四元式、间接三元式)DAG图表示图表示图表示法图表示法图表示法主要包括图表示法主要包括DAG(Directed Acyclic Graph)与抽象语法树与抽象语法树语法树描述了源程序的自然层次结构。语法树描述了源程序的自然层次结构。DAG以更紧凑的形式给出了相同的以更紧凑的形式给出了相同的信息。两者不同的是:
4、信息。两者不同的是:在一个在一个DAG中代表公共子表达式的结点具有多个父结点中代表公共子表达式的结点具有多个父结点在一颗抽象语法树中公共子表达式被表示为重复的子树。在一颗抽象语法树中公共子表达式被表示为重复的子树。assign+a*uminusbcuminusbca:=b*-c+b*-cassign+a*uminusbcabc uminus*bc numinus*+assign抽象语法树抽象语法树语法树中的边不会显式的出现在后缀表达式中,可以根据结点出现的顺序语法树中的边不会显式的出现在后缀表达式中,可以根据结点出现的顺序及结点上的操作符所要求的操作数的个数来恢复。其恢复过程类似使用栈及结点上
5、的操作符所要求的操作数的个数来恢复。其恢复过程类似使用栈对后缀表达式求值。对后缀表达式求值。如果函数如果函数mknode(op,child)和和mknode(op,left,right)尽可能返回一个指向一尽可能返回一个指向一个存在的结点的指针以代替建立新的结点,那么就会生成个存在的结点的指针以代替建立新的结点,那么就会生成DAG图。图。产生式产生式语义规则语义规则Sid:=ES.nptr:=mknode(assign,mkleaf(id,id.place),E.nptr)EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(*
6、,E1.nptr,E2.nptr)E-E1E.nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptr EidE.nptr:=mkleaf(id ,id.place)抽象语法树的表示形式抽象语法树的表示形式assignida+*uminusuminusidbidbidcidc0idb1idc2uminus13*024idb5idc6uminus57*468+379ida10assign9811三地址代码三地址代码三地址代码是下列一般形式的语句序列三地址代码是下列一般形式的语句序列x:=y op z其中,其中,x、y和和z是名字,常量或编译器生成的临时变量
7、是名字,常量或编译器生成的临时变量op代表任何操作符(定点运算符、浮点运算符、逻辑运算符等)代表任何操作符(定点运算符、浮点运算符、逻辑运算符等)这里不允许组合的算术表达式,因为语句右边只有一个操作符。这里不允许组合的算术表达式,因为语句右边只有一个操作符。像像x+y*z这样的表达式要翻译为如下;这样的表达式要翻译为如下;T1:=y*zT2:=x+T1其中其中T1,T2为编译时产生的临时变量。为编译时产生的临时变量。三地址代码三地址代码这种复杂算术表达式和嵌套控制流语句的拆解使得三这种复杂算术表达式和嵌套控制流语句的拆解使得三地址码适用于目标代码生成及优化。地址码适用于目标代码生成及优化。由程
8、序计算出来的中间值的名字的使用使得三地址码由程序计算出来的中间值的名字的使用使得三地址码容易被重排列容易被重排列而不像后缀表达式那样而不像后缀表达式那样三地址码可以看成是语法树或三地址码可以看成是语法树或DAG的线性表示。的线性表示。三地址码的得名原因是每条语句通常包含三个地址,三地址码的得名原因是每条语句通常包含三个地址,两个是操作数地址,一个是结果地址。两个是操作数地址,一个是结果地址。在实际的实现中,有程序员定义的名字被一个指向改在实际的实现中,有程序员定义的名字被一个指向改名字的符号表表项的指针所代替。名字的符号表表项的指针所代替。三地址码三地址码assign+a*uminusbcum
9、inusbcassign+a*uminusbct1:=-ct2:=b*t1t3:=-ct4:=b*t3t5:=t2+t4a:=t5t1:=-ct2:=b*t1t3:=t2+t2a:=t3三地址语句的类型三地址语句的类型三地址语句类似于汇编语言代码。语句可以由符号标三地址语句类似于汇编语言代码。语句可以由符号标号,而且存在各种控制流语句。号,而且存在各种控制流语句。符号标号代表存放中间代码的数组中三地址代码语句符号标号代表存放中间代码的数组中三地址代码语句的下标。下面列出本书中使用的三地址语句的种类:的下标。下面列出本书中使用的三地址语句的种类:形如形如x:=y op z的赋值语句,其中的赋值语
10、句,其中op为二元算术算符或为二元算术算符或逻辑算符逻辑算符形如形如x:=op y的赋值语句,其中的赋值语句,其中op为一元算符。为一元算符。形如形如x:=y的复制语句,将的复制语句,将y的值赋给的值赋给x形如形如goto L的无条件跳转语句,即下一条将被执行的语的无条件跳转语句,即下一条将被执行的语句是带有标号句是带有标号L的三地址语句的三地址语句三地址语句的类型三地址语句的类型下面列出本书中使用的三地址语句的种类:下面列出本书中使用的三地址语句的种类:形如形如if x relop y goto L或或 if a goto L的条件跳转语句。的条件跳转语句。第一种形式使用关系运算符号第一种形
11、式使用关系运算符号relop(等)等)第二种第二种a为布尔变量或常量为布尔变量或常量用于过程调用的语句用于过程调用的语句param x和和call p,n,以及返回语句,以及返回语句return y。源程序中的过程调用源程序中的过程调用p(x1,x2,xn):param x1param x2param x2call p,n n表示实参个数。表示实参个数。return y中中y为过程返回的一个值为过程返回的一个值三地址语句的类型三地址语句的类型下面列出本书中使用的三地址语句的种类:下面列出本书中使用的三地址语句的种类:形如形如x:=yi及及xi:=y的索引赋值。的索引赋值。形如形如x:=&y,x
12、:=*y和和*x:=y的地址和指针赋值。的地址和指针赋值。设计中间代码形式时,运算符的选择是非常重要的。设计中间代码形式时,运算符的选择是非常重要的。算符种类应足以用来实现源语言中的运算。算符种类应足以用来实现源语言中的运算。一个小型算符集合较易于在新的目标机器上实现。一个小型算符集合较易于在新的目标机器上实现。局限的指令集合会使某些源语言运算表示成中间形式局限的指令集合会使某些源语言运算表示成中间形式时代码加长,需要在目标代码生成时做较多的优化工时代码加长,需要在目标代码生成时做较多的优化工作。作。生成三地址码的生成三地址码的S-S-属性文法属性文法S具有综合属性具有综合属性S.code,代
13、表赋值语句,代表赋值语句S的三地址码的三地址码非终结符非终结符E有如下性质:有如下性质:E.place表示存放表示存放E值的名字值的名字E.code表示对表示对E求值的三地址语句序列求值的三地址语句序列函数函数newtemp的功能是每次调用它时,将返回一个不的功能是每次调用它时,将返回一个不同临时变量的名字。如同临时变量的名字。如T1,T2,.用用gen(x:=y+z)表示生成三地址语句表示生成三地址语句x:=y+z。在实际实现中,三地址码可能被送到输出文件中,而在实际实现中,三地址码可能被送到输出文件中,而不是生成不是生成code属性。属性。生成三地址码的生成三地址码的S-S-属性文法属性文
14、法产生式产生式语义规则语义规则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:=uminus E1.place)E(E1)E.place:=E1.
15、place E.code:=E1.codeEidE.place:=id.place E.code:=如何加入控制语句如何加入控制语句SWhile E do S1SWhile E do S1对应的语义规则是:对应的语义规则是:S.begin:=newlabel;S.after:=newlabel;S.code:=gen(S.begin:)|E.code|gen(if E.place=0 goto S.after)|S1.code|gen(goto S.begin)|gen(S.after:)E.codeif E.place=0 goto S.afterS1.codegoto S.beginS.b
16、egin:S.begin:三地址语句的实现三地址语句的实现三地址语句是中间代码的一种抽象形式。三地址语句是中间代码的一种抽象形式。这些语句可以以带有操作符和操作数域的记录来实现。这些语句可以以带有操作符和操作数域的记录来实现。四元式、三元式及简介三元式是三种这样的表示。四元式、三元式及简介三元式是三种这样的表示。四元式四元式一个四元式是带有四个域的记录结构,这四个域分别一个四元式是带有四个域的记录结构,这四个域分别称为称为op,arg1,arg2及及result。域域op包含一个代表运算符的内部码包含一个代表运算符的内部码三地址语句三地址语句x:=y op z通过将通过将y放入放入arg1,z
17、放入放入arg2,并,并且将且将x放入放入result,:=为算符。为算符。像像x:=y或或x:=-y这样的一元操作符语句不使用这样的一元操作符语句不使用arg2像像param这样的运算符仅使用这样的运算符仅使用arg1域。域。条件和无条件语句将目标标号存入条件和无条件语句将目标标号存入result域。域。临时变量也要填入符号表中。临时变量也要填入符号表中。三元式三元式为了避免把临时变量填入符号表,我们可以通过计算为了避免把临时变量填入符号表,我们可以通过计算这个临时变量的语句的位置来引用这个临时变量。这个临时变量的语句的位置来引用这个临时变量。这样三地址代码的记录只需要三个域这样三地址代码的
18、记录只需要三个域op,arg1和和arg。对于一目运算符对于一目运算符op,arg1和和arg2只需用其一。我们可只需用其一。我们可以随意选用一个。以随意选用一个。四元式举例四元式举例oparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5)assignT5aoparg1arg2(0)uminusc(1)*b0(2)uminusc(3)*b2(4)+13(5)assigna4a:=b*-c+b*-c三元式举例三元式举例oparg1arg2(0)=xi(1)assign(0)yoparg1arg2(0)=yi(1
19、)assignx(0)xi:=yx:=yi间接三元式间接三元式为了便于代码优化处理,有时不直接使用三元式表,为了便于代码优化处理,有时不直接使用三元式表,而是另设一张指示器(称为间接码表),它将运算的而是另设一张指示器(称为间接码表),它将运算的先后顺序列出有关三元式在三元表中的位置。先后顺序列出有关三元式在三元表中的位置。换句话说,我们用一张间接码表辅以三元式表的办法换句话说,我们用一张间接码表辅以三元式表的办法来表示中间代码。这种表示方法称为间接三元式。来表示中间代码。这种表示方法称为间接三元式。间接三元式举例间接三元式举例X:=(A+B)*C Y:=D(A+B)oparg1arg2(1)
20、+AB(2)*(1)C(3):=X(2)(4)D(1)(5):=Y(4)间接代码间接代码(1)(2)(3)(1)(4)(5)(1)(2)(3)(1)(4)(5)当在代码优化过程中需要调整运算顺序时,当在代码优化过程中需要调整运算顺序时,只需重新安排间接码表,无需改动三元式只需重新安排间接码表,无需改动三元式表表对于间接三元式表示,语义规则中应增添对于间接三元式表示,语义规则中应增添产生间接码表的动作,并且在向三元式表产生间接码表的动作,并且在向三元式表填进一个三元式之前,必须先查看一下此填进一个三元式之前,必须先查看一下此式是否已在其中,就无须填入。式是否已在其中,就无须填入。表示方法比较:间
21、址的使用表示方法比较:间址的使用三元式与四元式的差异可以看作在表示中引入了多少间址。三元式与四元式的差异可以看作在表示中引入了多少间址。使用四元式表示,定义或使用临时变量的三地址语句可通过符号使用四元式表示,定义或使用临时变量的三地址语句可通过符号表直接访问该临时变量的地址表直接访问该临时变量的地址使用四元式的一个更重要的好处体现在优化编译器中。在三元式使用四元式的一个更重要的好处体现在优化编译器中。在三元式中,如果要移动一条临时值的语句需要改变中,如果要移动一条临时值的语句需要改变arg1和和arg2数组中对数组中对该语句的引用。该语句的引用。间接三元式没有上述问题。间接三元式没有上述问题。
22、间接三元式看上去和四元式非常相似,他们都需要大约相同的间接三元式看上去和四元式非常相似,他们都需要大约相同的存储空间,并且对代码重新排序的效率相同。存储空间,并且对代码重新排序的效率相同。对于普通三元式,必须将对那些临时变量的存储分配推迟到代对于普通三元式,必须将对那些临时变量的存储分配推迟到代码生成阶段。码生成阶段。说明语句说明语句声明语句引起的翻译动作声明语句引起的翻译动作当过程或程序块内部的声明语句被考察的时候,我们当过程或程序块内部的声明语句被考察的时候,我们需要为需要为局部局部于该过程的名字分配存储空间。于该过程的名字分配存储空间。对每个局部名字,都将在符号表中创建一个表项,对每个局
23、部名字,都将在符号表中创建一个表项,填写类型、相对存储地址等相关信息填写类型、相对存储地址等相关信息相对地址指相对于静态数据区基址或活动记录基址的偏相对地址指相对于静态数据区基址或活动记录基址的偏移量移量单个过程中的声明语句单个过程中的声明语句允许嵌套过程中的声明语句允许嵌套过程中的声明语句单个过程中的声明语句单个过程中的声明语句变量和过程设计变量和过程设计设置全局变量:设置全局变量:offset,跟踪下一个可用的相对地址,跟踪下一个可用的相对地址过程过程enter(name,type,offset)为名字建立符号表表项为名字建立符号表表项综合属性综合属性type和和width说明非终结符说明
24、非终结符T的类型及宽度(或该类型的对象所占用的类型及宽度(或该类型的对象所占用的内存数。的内存数。Poffset:=0 DDD;DDid:Tenter(id.name,T.type,offset);offset:=offset+T.width TintegerT.type:=integer;T.width:=4 TrealT.type:=real;T.width:=8Tarraynumof T1T.type:=array(num.val,T1.type);T.width:=num.val*T1.widthTT1T.type:=pointer(T1.type);T.width:=4Poffset
25、:=0 DPMDD offset:=0允许嵌套过程中的声明语句允许嵌套过程中的声明语句PMDaddwidth(top(tblptr),top(offset);pop(tblptr);pop(offset)Mt=mktable(nil);push(t,tblptr);push(0,offset)DD1;D2Dproc id;N D1;S t:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t)Did:Tenter(top(tblptr),id.name,T.type
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精品 考研计算机专业课 【精品】【考研计算机专业课】天津大学 编译原理ppt课件 part7语义分析与中间代码生
链接地址:https://www.taowenge.com/p-86273652.html
限制150内