《编译原理课件07-语义分析和中间代码产生》由会员分享，可在线阅读，更多相关《编译原理课件07-语义分析和中间代码产生（108页珍藏版）》请在金锄头文库上搜索。
1、第七章第七章 语义分析和中间代码产生语义分析和中间代码产生n静态语义检查静态语义检查类型检查类型检查控制流检查控制流检查一致性检查一致性检查 相关名字检查相关名字检查名字的作用域分析名字的作用域分析 语法分语法分析器析器中间代码中间代码产生器产生器静态检静态检查器查器中间代码中间代码优化器优化器n中间语言中间语言(复杂性界于源语言和目标语言复杂性界于源语言和目标语言之间之间)的好处：的好处：便于进行与机器无关的代码优化工作便于进行与机器无关的代码优化工作 易于移植易于移植使编译程序的结构在逻辑上更为简单明确使编译程序的结构在逻辑上更为简单明确 源语言源语言程序程序目标语目标语言程序言程序中间语
2、中间语言程序言程序CompilerCompilerFront EndFront EndCompilerCompilerBack EndBack Endn常用的中间语言：常用的中间语言：后缀式，逆波兰表示后缀式，逆波兰表示三地址代码三地址代码n三元式三元式n四元式四元式n间接三元式间接三元式DAG图表示图表示7.1 中间语言中间语言 7.1.1 7.1.1 后缀式后缀式 n后后缀缀式式表表示示法法：Lukasiewicz发发明明的的一一种种表表示示表达式表达式的方法，又称的方法，又称逆波兰逆波兰表示法。表示法。n一个表达式一个表达式E的后缀形式可以如下定义：的后缀形式可以如下定义：1.如果如果E
3、是一个变量或常量，则是一个变量或常量，则E的后缀式是的后缀式是E自身。自身。2.如果如果E是是E1 op E2形式的表达式，其中形式的表达式，其中op是是任何二元操作符，则任何二元操作符，则E的后缀式为的后缀式为E1 E2 op，其中其中E1 和和E2 分别为分别为E1 和和E2的后缀式。的后缀式。3.如果如果E是是(E1)形式的表达式，则形式的表达式，则E1 的后缀式的后缀式就是就是E的后缀式。的后缀式。n逆逆波波兰兰表表示示法法不不用用括括号号。只只要要知知道道每每个个算算符符的的目目数数，对对于于后后缀缀式式，不不论论从从哪哪一一端进行扫描，都能对它进行唯一分解。端进行扫描，都能对它进行
4、唯一分解。n后缀式的计算后缀式的计算用一个栈实现。用一个栈实现。一一般般的的计计算算过过程程是是：自自左左至至右右扫扫描描后后缀缀式式，每每碰碰到到运运算算量量就就把把它它推推进进栈栈。每每碰碰到到k目目运运算算符符就就把把它它作作用用于于栈栈顶顶的的k个个项项，并并用用运运算算结果代替这结果代替这k个项个项。把表达式翻译成后缀式的语义规则描述把表达式翻译成后缀式的语义规则描述产生式产生式EE(1)opE(2)E(E(1)Eid语义动作语义动作E.code:=E(1).code|E(2).code|opE.code:=E(1).codeE.code:=idE.code表示表示E后缀形式后缀形式
5、op表示任意二元操作符表示任意二元操作符“|”表示后缀形式的连接表示后缀形式的连接。n数组数组POST存放后缀式：存放后缀式：k为下标，初值为为下标，初值为1n上述语义动作可实现为：上述语义动作可实现为：产生式产生式程序段程序段EE(1)op E(2)POSTk:=op;k:=k+1E(E(1)EiPOSTk:=i;k:=k+1n例：输入串例：输入串a+b+c的分析和翻译的分析和翻译POST：1 2 3 4 57.1.2 图表示法图表示法n图表示法图表示法DAG抽象语法树抽象语法树 7.1.2 图表示法图表示法n无循环有向图无循环有向图(Directed Acyclic Graph，简称简称D
6、AG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAG中都有一个结中都有一个结点点一个内部结点代表一个操作符，它的孩子代表一个内部结点代表一个操作符，它的孩子代表操作数操作数在一个在一个DAG中代表公共子表达式的结点具有多个中代表公共子表达式的结点具有多个父结点父结点a:=b*(-c)+b*(-c)的图表示法的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc 产生赋值语句抽象语法树的属性文法产生赋值语句抽象语法树的属性文法 产产生生式式语义规则语义规则Sid:=ES.nptr:=mknode(assign,mk
7、leaf(id,id.place),E.nptr)EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(*,E1.nptr,E2.nptr)E-E1E.nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptrEidE.nptr:=mkleaf(id,id.place)7.1.3 三地址代码三地址代码 n三地址代码三地址代码x:=y op z n表达式表达式x+y z翻译成的三地址语句序列是翻译成的三地址语句序列是 t1:=y z t2:=x+t1 出于语句的右边只有一个算符的考虑n三地址代
8、码可以看成是抽象语法树或三地址代码可以看成是抽象语法树或DAG的一种的一种线性表示线性表示 三地址代码是语法树或三地址代码是语法树或dag的一种线性表示的一种线性表示a:=(b+c d)+c d语法树的代码语法树的代码 dag的代码的代码t1:=bt2:=c dt3:=t1+t2t4:=c dt5:=t3+t4 a:=t5 新增加的名字对应树新增加的名字对应树/图中的内部结点图中的内部结点assigna+bcdcduminus语法树语法树三地址代码是语法树或三地址代码是语法树或dag的一种线性表示的一种线性表示a:=(b+c d)+c d语法树的代码语法树的代码 dag的代码的代码t1:=bt
9、2:=c dt3:=t1+t2t4:=t3+t2a:=t4 新增加的名字对应树新增加的名字对应树/图中的内部结点图中的内部结点assigna+bcduminus(b)dag三地址语句的种类三地址语句的种类 本书常用的三地址语句本书常用的三地址语句n赋值语句赋值语句x:=y op z;x:=op y;x:=yn无条件转移无条件转移goto Ln条件转移条件转移if x relop y goto Ln过程调用过程调用param x 和和call p,nn过程返回过程返回 return yn索引赋值索引赋值x:=yi和和 xi:=yn地址和指针赋值地址和指针赋值x:=&y，x:=y和和 x:=yn生
10、成三地址代码时，生成三地址代码时，临时变量临时变量的名字对应的名字对应抽象语法树的抽象语法树的内部结点内部结点nid:=E对表达式对表达式E求值并置于变量求值并置于变量T中值中值id.place:=T从赋值语句生成三地址代码的从赋值语句生成三地址代码的S-属性文法属性文法n非终结符号非终结符号S有综合属性有综合属性S.code，它代表它代表赋值语句赋值语句S的三地址代码。的三地址代码。n非终结符号非终结符号E有如下两个属性：有如下两个属性：E.place表示存放表示存放E值的名字。值的名字。E.code表示对表示对E求值的三地址语句序列。求值的三地址语句序列。函函数数newtemp的的功功能能
11、是是，每每次次调调用用它它时时，将将返返回一个不同临时变量名字回一个不同临时变量名字,如如T1,T2,。为赋值语句生成三地址代码的为赋值语句生成三地址代码的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.
12、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=三地址语句三地址语句三地址语句可看成中间代码的一种抽象形式三地址语句可看成中间代码的一种抽象形式.编译程序中编译程序中,三地址代码语句的具三地址代码语句的具体实现可用记录表示体实现可用记录表示.通常有三种表示方法通常有三种表示方法:四元式、三元式、间接三元式四元式、三元式、间接三元式。n四元式四元式一个带有四个域的记录结构
13、，这四个域分别称一个带有四个域的记录结构，这四个域分别称为为op,arg1,arg2及及resultoparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a三地址语句三地址语句n三元式三元式 通过计算临时变量值的语句的位置来引用这通过计算临时变量值的语句的位置来引用这个临时变量个临时变量三个域：三个域：op、arg1和和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4)三地址语句三地址语句nxi:=yop
14、arg1arg2(0)=xi(1)assign（0）ynx:=yioparg1arg2(0)=yi(1)assignx(0)三地址语句三地址语句n间接三元式间接三元式 为为了了便便于于优优化化，用用 三三元元式式表表+间间接接码码表表 表表示示中间代码中间代码间间接接码码表表:一一张张指指示示器器表表，按按运运算算的的先先后后次次序列出有关三元式在三元式表中的位置。序列出有关三元式在三元式表中的位置。优点优点:方便优化，节省空间方便优化，节省空间n例如，语句例如，语句X:=(A+B)*C;Y:=D(A+B)的间接三元式表示如下表所示。的间接三元式表示如下表所示。7.2 声声 明明 语语 句句声
15、明的语法制导定义声明的语法制导定义 产产 生生 式式 语语 义义 规规 则则 D TL L.in:=T.type T int T.type:=integer T real T.type:=real L L1,id L1.in:=L.in;addtype(id.entry,L.in)L id addtype(id.entry,L.in)7.2 声声 明明 语语 句句D id L addtype(id.entry,L.type)L ,id L1 L.type:=L1.Type;addtype(id.entry,L1.type)L :T L.type:=T.typeT integer T.type:
16、=integerT real T.type:=real以上没有继承属性的翻译方案以上没有继承属性的翻译方案D:L,idLidintegerT7.2 声声 明明 语语 句句n为局部名字建立符号表条目为局部名字建立符号表条目n为它分配存储单元为它分配存储单元n符号表中包含名字的类型和分配给它的存储符号表中包含名字的类型和分配给它的存储单元的相对地址等信息单元的相对地址等信息7.2 声声 明明 语语 句句 过程中的声明过程中的声明P D SD D;DD id:TT integerTrealTarraynumofT1T T17.2 声声 明明 语语 句句计算被声明名字的类型和相对地址计算被声明名字的类型和相对地址P offset:=0D SD D;D D id:Tenter(id.name,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 of T1T.type:=array(num.val,T1.type);
