第七章语义分析和中间代码产生.ppt
《第七章语义分析和中间代码产生.ppt》由会员分享,可在线阅读,更多相关《第七章语义分析和中间代码产生.ppt(117页珍藏版)》请在三一文库上搜索。
1、国防科技大学计算机系602教研室,第七章 语义分析和中间代码产生,静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析,语法分 析器,中间代码 产生器,静态检 查器,中间代码,优化器,国防科技大学计算机系602教研室,中间语言(复杂性界于源语言和目标语言之间)的好处: 便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确,源语言 程序,目标语 言程序,中间语 言程序,国防科技大学计算机系602教研室,常用的中间语言: 后缀式,逆波兰表示 图表示: DAG、抽象语法树 三地址代码 三元式 四元式 间接三元式,7.1 中间语言,国防科技大学计算
2、机系602教研室,7.1.1 后缀式,后缀式表示法:Lukasiewicz发明的一种表示表达式的方法,又称逆波兰表示法。 一个表达式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教研室,逆波兰表示法不用括号。只要知道每个算符的目数,对于后缀式,不论从哪一端进行扫描,都能对它进行唯一分解。 后缀式的计算 用一个栈实现。
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教研室,数组POST存放后缀式:k为下标,初值为1 上述语义动作可实现为: 产生式 程序段
4、 EE(1)op E(2) POSTk:=op;k:=k+1 E (E(1) Ei POSTk:=i;k:=k+1 例:输入串a+b+c的分析和翻译 POST: 1 2 3 4 5,EE(1)op E(2) E.code:= E(1).code | E(2).code |op E (E(1) E.code:= E(1).code Eid E.code:=id,a,b,+,c,+,国防科技大学计算机系602教研室,7.1.2 图表示法,图表示法 DAG 抽象语法树,国防科技大学计算机系602教研室,7.1.2 图表示法,无循环有向图(Directed Acyclic Graph,简称DAG) 对
5、表达式中的每个子表达式,DAG中都有一个结点 一个内部结点代表一个操作符,它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点,国防科技大学计算机系602教研室,a:=b*(-c)+b*(-c)的图表示法,国防科技大学计算机系602教研室,抽象语法树对应的代码: T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,国防科技大学计算机系602教研室,DAG对应的代码: T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象语法树对应的代码: T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T
6、4 a:=T5,国防科技大学计算机系602教研室,产生赋值语句抽象语法树的属性文法,产 生 式 语义规则 Sid:=E S.nptr:=mknode(assign, mkleaf(id,id.place),E.nptr) EE1+E2 E.nptr:=mknode(+,E1.nptr,E2.nptr) EE1*E2 E.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、,7.1.3 三地址代码,三地址代码 x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示,国防科技大学计算机系602教研室,a:=b*(-c)+b*(-c)的图表示法,国防科技大学计算机系602教研室,T1:=-c T1:=-c T2:=b*T1 T2:=b*T1 T3:=-c T5:=T2+T2 T4:=b*T3 a:=T5 T5:=T2+T4 a:=T5 对于抽象语法树的代码 对于DAG的代码,国防科技大学计算机系602教研室,三地址语句的种类,x:=y op z x:=op y x:=y goto L if x relop y goto L或if a goto L
8、param x和call p,n,以及返回语句return y x:=yi及xi:=y的索引赋值 x:=&y, x:=*y和*x:=y的地址和指针赋值,国防科技大学计算机系602教研室,生成三地址代码时,临时变量的名字对应抽象语法树的内部结点 id:=E 对表达式E求值并置于变量T中值 id.place:=T,国防科技大学计算机系602教研室,从赋值语句生成三地址代码的S-属性文法,非终结符号S有综合属性S.code,它代表赋值语句S的三地址代码。 非终结符号E有如下两个属性: E.place表示存放E值的名字。 E.code表示对E求值的三地址语句序列。 函数newtemp的功能是,每次调用
9、它时,将返回一个不同临时变量名字,如T1,T2,。,国防科技大学计算机系602教研室,为赋值语句生成三地址代码的S-属性文法定义,产生式 语义规则 Sid:=E S.code:=E.code | gen(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)
10、 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教研室,三地址语句,四元式 一个带有四个域的记录结构,这四个域分别称为op, arg1, arg2及result op arg1 arg2 result (0) uminus c T1 (1) * b T1 T2 (2) uminus c T3 (3) * b T3 T4 (4
11、) + T2 T4 T5 (5) := T5 a,国防科技大学计算机系602教研室,三地址语句,三元式 通过计算临时变量值的语句的位置来引用这个临时变量 三个域:op、arg1和arg2 op arg1 arg2 (0) uminus c (1) * b (0) (2) uminus c (3) * b (2) (4) + (1) (3) (5) assign a (4),国防科技大学计算机系602教研室,三地址语句,xi:=y op arg1 arg2 (0) = x i (1) y x:=yi op arg1 arg2 (0) = y i (1) assign x (0),国防科技大学计算
12、机系602教研室,三地址语句,间接三元式 为了便于优化,用 三元式表+间接码表 表示中间代码 间接码表:一张指示器表,按运算的先后次序列出有关三元式在三元式表中的位置。 优点: 方便优化,节省空间,国防科技大学计算机系602教研室,例如,语句 X:=(A+B)*C; Y:=D(A+B) 的间接三元式表示如下表所示。,国防科技大学计算机系602教研室,7.2 说明语句,国防科技大学计算机系602教研室,7.3 赋值语句的翻译,7.3.1 简单算术表达式及赋值语句,国防科技大学计算机系602教研室,为赋值语句生成三地址代码的S-属性文法定义,产生式 语义规则 Sid:=E S.code:=E.co
13、de | gen(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) E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place) E (E1) E.place:=E1.
14、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:=
15、E.code | gen(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)
16、E(E1) E.place:=E1.place Eid p:=lookup(id.name); if pnil then E.place:=p else 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 数组元素的引用,数组元素地址的计算:,国防科技大学计算机系602教研室,设A为n维数组,每个
17、元素宽度为w, lowi 为第i维 的下界,ni 是为第i维 可取值的个数, base为A的第一个元素相对地址 元素Ai1,i2,ik相对地址公式 (i1 n2+i2)n3+i3)nk+ik)w + base-(low1 n2+low2)n3+low3)nk+lowk)w C= base-(low1 n2+low2)n3+low3)nk+lowk)w,国防科技大学计算机系602教研室,id出现的地方也允许下面产生式中的L出现 L id Elist | id ElistElist,E | E 为了便于处理,文法改写为 LElist | id ElistElist, E | id E,国防科技大学
18、计算机系602教研室,引入下列语义变量或语义过程: Elist.ndim :下标个数计数器 Elist.place :表示临时变量,用来临时存放已形成的Elist中的下标表达式计算出来的值 limit(array,j) :函数过程,它给出数组array的第j维的长度,国防科技大学计算机系602教研室,每个代表变量的非终结符L有两项语义值 L.place: 若L为简单变量i, 指变量i的符号表入口 若L为下标变量,指存放CONSPART的 临时变量的整数码 L.offset : 若L为简单变量,null, 若L为下标变量,指存放VARPART的临时变量的整数码,国防科技大学计算机系602教研室,
19、(1) SL:=E (2) EE+E (3) E(E) (4) EL (5) LElist (6) Lid (7) Elist Elist, E (8) Elistid E,国防科技大学计算机系602教研室,(1) SL:=E if L.offset=null then /*L是简单变量*/ emit(L.place := E.place) else emit( L.place L.offset := E.place) (2) EE1 +E2 E.place:=newtemp; emit(E.place := E 1.place + E 2.place),国防科技大学计算机系602教研室,(3
20、) E(E1) E.place:=E1.place (4) EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place := L.place L.offset ) end ,国防科技大学计算机系602教研室,Ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik)w + base-(low1 n2+low2)n3+low3)nk+lowk)w,(8) Elistid E Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.pl
21、ace ,国防科技大学计算机系602教研室,A i1,i2,ik ( (i1 n2+i2)n3+i3)nk+ik)w + base-(low1 n2+low2)n3+low3)nk+lowk)w,(7) Elist Elist1, E t:=newtemp; m:=Elist1.ndim+1; emit(t := Elist1.place * limit(Elist1.array,m) ); emit(t := t + E.place); Elist.array:= Elist1.array; Elist.place:=t; Elist.ndim:=m ,国防科技大学计算机系602教研室,Ai
22、1,i2,ik (i1 n2+i2)n3+i3)nk+ik) w + base-(low1 n2+low2)n3+low3)nk+lowk)w,(5) LElist L.place:=newtemp; emit(L.place := Elist.array C); L.offset:=newtemp; emit(L.offset := w * Elist.place) (6) Lid L.place:=id.place; L.offset:=null ,国防科技大学计算机系602教研室,类型转换,用E.type表示非终结符E的类型属性 对应产生式EE1 op E2的语义动作中关于E.type的
23、语义规则可定义为: if E1.type=integer and E2.type=integer E.type:=integer else E.type:=real 算符区分为整型算符int op和实型算符real op,,国防科技大学计算机系602教研室,x:=yi*j 其中x、y为实型;i、j为整型。这个赋值句产生的三地址代码为: T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2,国防科技大学计算机系602教研室,关于产生式EE1 E2 的语义动作, E.place:=newtemp; if E1.type=integer and E2.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七 语义 分析 中间 代码 产生
链接地址:https://www.31doc.com/p-2084275.html