编译原理语义分析和中间代码产生ppt课件.ppt
《编译原理语义分析和中间代码产生ppt课件.ppt》由会员分享,可在线阅读,更多相关《编译原理语义分析和中间代码产生ppt课件.ppt(107页珍藏版)》请在三一办公上搜索。
1、语义分析和中间代码产生,静态语义检查类型检查控制流检查一致性检查 相关名字检查名字的作用域分析,语法分析器,中间代码产生器,静态检查器,中间代码,优化器,中间语言(复杂性界于源语言和目标语言之间)的好处:便于进行与机器无关的代码优化工作 易于移植使编译程序的结构在逻辑上更为简单明确,源语言程序,目标语言程序,中间语言程序,常用的中间语言:后缀式,逆波兰表示三地址代码三元式四元式间接三元式DAG图表示,7.1 中间语言,7.1.1 后缀式,后缀式表示法:Lukasiewicz发明的一种表示表达式的方法,又称逆波兰表示法。一个表达式E的后缀形式可以如下定义:1. 如果E是一个变量或常量,则E的后缀
2、式是E自身。2. 如果E是E1 op E2形式的表达式,其中op是任何二元操作符,则E的后缀式为E1 E2 op,其中E1 和E2 分别为E1 和E2的后缀式。3. 如果E是(E1)形式的表达式,则E1 的后缀式就是E的后缀式。,逆波兰表示法不用括号。只要知道每个算符的目数,对于后缀式,不论从哪一端进行扫描,都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是:自左至右扫描后缀式,每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项,并用运算结果代替这k个项。,把表达式翻译成后缀式的语义规则描述,产生式EE(1)op E(2)E (E(1)Eid,语义动作E.code
3、:= E(1).code | E(2).code |opE.code:= E(1).codeE.code:=id,E.code表示E后缀形式op表示任意二元操作符“|”表示后缀形式的连接。,数组POST存放后缀式:k为下标,初值为1上述语义动作可实现为:产生式程序段EE(1)op E(2) POSTk:=op;k:=k+1E (E(1)EiPOSTk:=i;k:=k+1例:输入串a+b+c的分析和翻译POST: 1 2 3 4 5,7.1.2 图表示法,图表示法DAG抽象语法树,7.1.2 图表示法,无循环有向图(Directed Acyclic Graph,简称DAG)对表达式中的每个子表达
4、式,DAG中都有一个结点一个内部结点代表一个操作符,它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点,a:=b*(-c)+b*(-c)的图表示法,产生赋值语句抽象语法树的属性文法,产 生 式语义规则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.nptrEi
5、d E.nptr:=mkleaf(id,id.place),7.1.3 三地址代码,三地址代码x:=y op z 表达式x + y z翻译成的三地址语句序列是 t1 := y z t2 := x + t1 出于语句的右边只有一个算符的考虑三地址代码可以看成是抽象语法树或DAG的一种线性表示,三地址代码是语法树或dag的一种线性表示a := (b + cd ) + cd语法树的代码dag的代码t1 := bt2 := c dt3 := t1 + t2t4 := c dt5 := t3 + t4 a := t5 新增加的名字对应树/图中的内部结点,三地址代码是语法树或dag的一种线性表示a :=
6、(b + cd ) + cd语法树的代码dag的代码t1 := bt2 := c dt3 := t1 + t2t4 := t3 + t2a := t4 新增加的名字对应树/图中的内部结点,三地址语句的种类,本书常用的三地址语句赋值语句x:=y op z; x:=op y; x:= y无条件转移goto L条件转移if x relop y goto L过程调用param x 和call p , n过程返回 return y索引赋值x := yi和 xi := y地址和指针赋值x := &y,x := y和x := y,生成三地址代码时,临时变量的名字对应抽象语法树的内部结点id:=E对表达式E求
7、值并置于变量T中值id.place:=T,从赋值语句生成三地址代码的S-属性文法,非终结符号S有综合属性S.code,它代表赋值语句S的三地址代码。非终结符号E有如下两个属性:E.place表示存放E值的名字。E.code表示对E求值的三地址语句序列。函数newtemp的功能是,每次调用它时,将返回一个不同临时变量名字,如T1,T2,。,为赋值语句生成三地址代码的S-属性文法定义,产生式语义规则Sid:=ES.code:=E.code | gen(id.place := E.place)EE1+E2E.place:=newtemp; E.code:=E1.code | E2.code | ge
8、n(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.codeEid E.place:=id.place; E.code= ,三地址语句,三地址语句可看成中间代码的一种抽象形式.编译程序中,三地址代码
9、语句的具体实现可用记录表示.通常有三种表示方法:四元式、三元式、间接三元式。四元式一个带有四个域的记录结构,这四个域分别称为op, arg1, arg2及resultoparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a,三地址语句,三元式 通过计算临时变量值的语句的位置来引用这个临时变量三个域:op、arg1和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4),三地址语句,xi:=y op arg1
10、arg2 (0) = x i (1) assign (0) yx:=yiop arg1 arg2(0) = y i(1) assign x (0),三地址语句,间接三元式 为了便于优化,用 三元式表+间接码表 表示中间代码间接码表:一张指示器表,按运算的先后次序列出有关三元式在三元式表中的位置。优点: 方便优化,节省空间,例如,语句X:=(A+B)*C;Y:=D(A+B)的间接三元式表示如下表所示。,7.2 声 明 语 句,声明的语法制导定义,7.2 声 明 语 句,D id L addtype (id. entry, L. type)L , id L1 L. type := L1. Type
11、; addtype (id. entry, L1. type)L : T L. type := T. typeT integer T. type := integerT real T. type := real以上没有继承属性的翻译方案,7.2 声 明 语 句,为局部名字建立符号表条目为它分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息,7.2 声 明 语 句,7.2.1 过程中的声明,P D SD D ; D D id : TT integer T realT array num of T1T T1,7.2 声 明 语 句,计算被声明名字的类型和相对地址P offset
12、 := 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);T.width := num.val T1.widthT T1 T.type := pointer (T1.type); T.width := 4 offset:用于跟踪可
13、用的相对地址的位置。enter(name,type,offset): 用于填充符号表。,7.2 声 明 语 句,7.2.2 作用域信息的保存所讨论语言的文法P D SD D ; D | id : T | proc id ; D ; S 语义动作用到的函数mktable(previous)enter(table, name, type, offset) addwidth(table, width)enterproc(table, name, newtable),7.2 声 明 语 句,处理嵌套过程中的说明语句P M D S addwidth (top (tblptr), top (offset)
14、 ); pop(tblptr); pop (offset) M t := mktable (nil);push(t, tblprt); push (0, offset) D D1 ; D2D proc id ; N D1; S t := top(tblptr);addwidth(t, top(offset) ); pop(tblptr); pop(offset);enterproc(top(tblptr), id.name, t) Did : T enter(top(tblptr), id.name, T.type, top(offset); top(offset) := top(offset
15、) + T.width N t := mktable(top(tblptr) ); push(t, tblptr); push(0, offset) tblptr与offset是两个栈名, tblptr为主过程的符号表头,offset为存放各嵌套过程的当前相对地址。,7.2 声 明 语 句,7.3 赋值语句的翻译,7.3.1 简单算术表达式及赋值语句,为赋值语句生成三地址代码的S-属性文法定义,产生式语义规则Sid:=ES.code:=E.code | gen(id.place := E.place)EE1+E2E.place:=newtemp; E.code:=E1.code | E2.co
16、de | 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.codeEid E.place:=id.place; E.code= ,产生赋值语句三地址代码的翻译模式,Sid:=E p:=loo
17、kup(id.name); if pnil thenemit(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),产生赋值语句三地址代码的翻译模式,E-E1 E.place:=newtemp; emit(E.place:= uminusE 1.place)E(E1) E.place:=E1.placeEid p:=lookup(id.name); i
18、f pnil then E.place:=p else error ,7.3.2 数组元素的引用,数组元素地址的计算:,设A为n维数组,每个元素宽度为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,id出现的地方也允许下面产生式中的L出现 L id Elist | idElistElist,E | E 为
19、了便于处理,文法改写为 LElist | id ElistElist, E | id E,引入下列语义变量或语义过程:Elist.ndim :下标个数计数器Elist.place :表示临时变量,用来临时存放已形成的Elist中的下标表达式计算出来的值 Elist.array:记录指向符号表中相应树组名字表项的指针limit(array,j) :函数过程,它给出数组array的第j维的长度,每个代表变量的非终结符L有两项语义值L.place:若L为简单变量i, 指变量i的符号表入口 若L为下标变量,指存放CONSPART的临时变量的整数码 L.offset :若L为简单变量,null,若L为下
20、标变量,指存放VARPART的临时变量的整数码,(1) SL:=E(2) EE+E(3) E(E)(4) EL(5) LElist (6) Lid(7) Elist Elist, E(8) Elistid E,(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),(3) E(E1)E.place:=E1.
21、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 ,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.place ,Ai1,i2,ik(i1 n2+i2)n3+i3)nk+ik)w +
22、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 ,Ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w,(5) LElist L.pl
23、ace:=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 ,例: 赋值语句: x:=Ay,z,T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T4:=T2T3x:=T4,类型转换,用E.type表示非终结符E的类型属性 对应产生式EE1 op E2的语义动作中关于E.type的语义规则可定义为: if E1.type=integer a E2.type=in
24、teger E.type:=integer else E.type:=real 算符区分为整型算符int op和实型算符real op,,x:=yi*j 其中x、y为实型;i、j为整型。这个赋值句产生的三地址代码为: T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2,关于产生式EE1 E2 的语义动作, E.place:=newtemp; if E1.type=integer and E2.type=integer then begin emit (E.place := E 1.place int+ E 2.place); E.type:=i
25、nteger end else if E1.type=real and E2.type=real then begin emit (E.place := E 1.place real+ E 2.place); E.type:=real end,else if E1.type=integer and E2.type=real then beginu:=newtemp;emit (u := inttoreal E 1.place);emit (E.place := u real+ E 2.palce);E.type:=realendelse if E1.type=real and E1.type=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 语义 分析 中间 代码 产生 ppt 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-1626967.html