《编译原理 国防科技大学 Chapt7》由会员分享，可在线阅读，更多相关《编译原理 国防科技大学 Chapt7（117页珍藏版）》请在金锄头文库上搜索。
1、第七章 语义分析和中间代码产生n静态语义检查类型检查控制流检查一致性检查 相关名字检查名字的作用域分析 语法分 析器中间代码 产生器静态检 查器中间代码优化器602教研室n中间语言(复杂性界于源语言和目标语言之 间)的好处：便于进行与机器无关的代码优化工作 易于移植使编译程序的结构在逻辑上更为简单明确 源语言 程序目标语 言程序中间语 言程序Compiler Front EndCompiler Back End602教研室n常用的中间语言：后缀式，逆波兰表示图表示： DAG、抽象语法树三地址代码n三元式n四元式n间接三元式7.1 中间语言 602教研室7.1.1 后缀式 n后缀式表示法：Luk
2、asiewicz发明的一种表示 表达式的方法，又称逆波兰表示法。n一个表达式E的后缀形式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式 是E自身。 2. 如果E是E1 op E2形式的表达式，其中 op是任何二元操作符，则E的后缀式为E1 E2 op，其中E1 和E2 分别为E1 和E2的后缀式。 3. 如果E是(E1)形式的表达式，则E1 的后 缀式就是E的后缀式。602教研室n逆波兰表示法不用括号。只要知道每个 算符的目数，对于后缀式，不论从哪一端 进行扫描，都能对它进行唯一分解。n后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀 式，每碰到运算量就把它推进栈。每碰
3、到k 目运算符就把它作用于栈顶的k个项，并用 运算结果代替这k个项。602教研室把表达式翻译成后缀式的语义规则描述 产生式 EE(1)op E(2) E (E(1) Eid语义动作 E.code:= E(1).code | E(2).code |op E.code:= E(1).code E.code:=id E.code表示E后缀形式 op表示任意二元操作符 “|”表示后缀形式的连接。602教研室n数组POST存放后缀式：k为下标，初值为1n上述语义动作可实现为： 产生式程序段 EE(1)op E(2)POSTk:=op;k:=k+1 E (E(1) EiPOSTk:=i;k:=k+1n例：
4、输入串a+b+c的分析和翻译 POST： 1 2 3 4 5EE(1)op E(2) E.code:= E(1).code | E(2).code |op E (E(1)E.code:= E(1).code EidE.code:=idab+c+602教研室7.1.2 图表示法n图表示法DAG抽象语法树 602教研室7.1.2 图表示法n无循环有向图(Directed Acyclic Graph， 简称DAG)对表达式中的每个子表达式，DAG中都有一 个结点一个内部结点代表一个操作符，它的孩子代 表操作数在一个DAG中代表公共子表达式的结点具有 多个父结点602教研室a:=b*(-c)+b*(-
5、c)的图表示法 assigna+*buminusc DAGassigna+*buminusc 抽象语法树*buminusc602教研室抽象语法树对应的代码：T1:=-cT2:=b*T1 T3:=-cT4:=b*T3T5:=T2+T4 a:=T5assigna+*buminusc 抽象语法树*buminusc602教研室DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5assigna+*buminusc DAG抽象语法树对应的代码：T1:=-cT2:=b*T1 T3:=-cT4:=b*T3T5:=T2+T4 a:=T5602教研室产生赋值语句抽象语法树的属性文法
6、产 生 式语义规则 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.nptr Eid E.nptr:=mkleaf(id,id.place)602教研室7.1.3 三地址代码 n三地址代码x:=y op z n三地址代码可以看成是抽象语法树或DAG 的一种线性表示 6
7、02教研室a:=b*(-c)+b*(-c)的图表示法 assigna+*buminusc DAGassigna+*buminusc 抽象语法树*buminusc602教研室T1:=-c T1:=-cT2:=b*T1T2:=b*T1 T3:=-cT5:=T2+T2T4:=b*T3a:=T5T5:=T2+T4 a:=T5 对于抽象语法树的代码对于DAG的代码602教研室三地址语句的种类 nx:=y op z nx:=op y nx:=y ngoto L nif x relop y goto L或if a goto Lnparam x和call p,n，以及返回语句return ynx:=yi及xi
8、:=y的索引赋值nx:=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.place;E.code:=E1.code Eid E.place:=id.place;E.code
9、= 602教研室三地址语句n四元式一个带有四个域的记录结构，这四个域 分别称为op, arg1, arg2及result oparg1arg2result (0)uminuscT1 (1)*bT1T2 (2)uminuscT3 (3)*bT3T4 (4)+T2T4T5 (5):=T5a 602教研室三地址语句n三元式 通过计算临时变量值的语句的位置来引 用这个临时变量三个域：op、arg1和arg2 oparg1arg2 (0)uminusc (1)*b(0) (2)uminusc (3)*b(2) (4)+(1)(3) (5)assigna(4)602教研室三地址语句nxi:=y op ar
10、g1 arg2 (0) = x i (1) ynx:=yi op arg1 arg2 (0) = y i (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-属性文法定义 产生式语义规则
11、 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.
12、place:=E1.place;E.code:=E1.code Eid E.place:=id.place;E.code= 602教研室产生赋值语句三地址代码的翻译模式 Sid:=E p:=lookup(id.name);if pnil then emit(p := E.place)else error EE1+E2 E.place:=newtemp;emit(E.place := E1.place + E2.place)EE1*E2 E.place:=newtemp;emit(E.place := E 1.place * E 2.place)Sid:=E S.code:=E.code | g
13、en(id.place := E.place) EE1+E2 E.place:=newtemp;E.code:=E1.code | E2.code |gen(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp;E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place)602教研室产生赋值语句三地址代码的翻译模式 E-E1 E.place:=newtemp;emit(E.place:= uminusE 1.place)E(E1) E.place:=E1.placeEid
14、 p:=lookup(id.name);if pnil thenE.place:=pelse error E-E1 E.place:=newtemp;E.code:=E1.code | gen(E.place := uminus E1.place) E (E1) E.place:=E1.place;E.code:=E1.code Eid E.place:=id.place;E.code= 602教研室7.3.2 数组元素的引用n数组元素地址的计算：602教研室n设A为n维数组，每个元素宽度为w， lowi 为第i维 的下界，ni 是为第i维 可取值的个数 , base为A的第一个元素相对地址
15、n元素Ai1,i2,ik相对地址公式 (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w nC= base-(low1 n2+low2)n3+low3)nk+lowk)w 602教研室nid出现的地方也允许下面产生式中的L出现 L id Elist | id ElistElist,E | E 为了便于处理，文法改写为LElist | id ElistElist, E | id E 602教研室n引入下列语义变量或语义过程:Elist.ndim ：下标个数计数器Elist.place ：表示临时变量，用来临时 存放已形成的Elist中的下标表达式计算出来 的值 limit(array，j) ：函数过程，它给出数组 array的第j维的
