编译原理PPT课件第五章中间代码生成.ppt

资源描述

《编译原理PPT课件第五章中间代码生成.ppt》由会员分享，可在线阅读，更多相关《编译原理PPT课件第五章中间代码生成.ppt（37页珍藏版）》请在三一文库上搜索。

1、1 翻译方式有两种: 第五章中间代码生成源语言目标语言源语言 1) 2) 目标语言中间代码中间代码的特点: 结构简单,功能明确,易于优化,易于翻译. 馋垢执壕随辆锗胖舅苞级殊笺定苗些绥银躲缨梧酸例今和愚脐令河展膊养编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 2 第一节中间代码简介 1) 逆波兰表示法运算量在前,运算符在后的后缀式表示法. 例如: 表达式后缀式 a+bab+ (a+b)*cab+c* a*(b+c)abc

2、+* (a+b)*(c+d)ab+cd+* 章纱匈垒迄奋劈嚎炯小野啮讥塑污白验围经侧捕耻庆换黑予撅查唁予蚤愈编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 3 2) 三元式表示法三元式就是三元组: ( 操作符,操作数1,操作数2) 例如: 语句 D:=A+B*C 可翻译为下述三元式表: (1) (*,B,C) (2) (+,A,(1) (3) (:=,D,(2) 三元式没有明确指出结果放在何处. 在翔复址巩蛰臭夹推景

3、凸浮听馆菇渭粳听耙播奢哦匀塌颗把楞高筷捕捉傍编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 4 3) 四元式表示法四元式就是四元组: ( 操作符,操作数1,操作数2,结果) 例如: 语句 D:=A+B*C 可翻译为下述四元式表: (1) (* ,B ,C ,T1) (2) (+ ,A ,T1,T2) (3) (:= ,T2, , D ) 四元式间通过临时变量传值. 操作符实现的运算也非常简单, 本章主要介绍各种语句到四元式的翻译. 寇畸独玫娇

4、末妄醇蓟桂桓虞豫嵌吗部韶押典桅噪法番涨髓遭舶森洼铂喂臀编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 5 第二节语法制导翻译的基本思想 1 何谓语法制导翻译在语法分析的每次归约或推导时,根据产生式的语义进行翻译的一种方法. 翻译时,除了产生中间代码外,还有许多辅助工作,包括: 改变语法变量的值;查填符号表;诊查与报告源程序错误等. 2 与翻译相关的若干约定 1) 临时变量在翻译中,可能会引入许多临时变量存放中间结果. 通过调用 newte

5、mp() 返回一个临时变量 Ti . 钩颅碉敦牟障岔麻幢陪漳禾咒畔兽嫁扁瑶孰吼壤敷巩缠芳自踏乞政啡歼振编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 6 2) 分析栈分析栈中的内容为语法单位,每个语法单位包含两个部分: (语法单位名称,语法单位属性),属性可能有多个值. 例如: E 为表达式的语法单位, E.place 代表了该表达式值存放的地方. 3) 符号表符号表用于存放变量及属性值,由如干项构成,每个项为: (变量名, 变量

6、信息). 4) 四元式表四元式表用于存放翻译中产生的四元式,通过过程 Gen( 操作符,操作数1,操作数2,结果) 把四元式存入四元式表的 NXQ 所指空间中, NXQ 自动加 1. 四元式表 NXQ 蛹侣咨蠢遭簇访轨韶幻叔铡蝶边瑞霹揽谤算皱愤恕整首文香菊腐剿浮浪胎编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 7 5 一些基本操作 newtemp( ) 产生一临时变量; gen(操作符,操作数1,操作数2,结果) 填入四元式表;

7、 fill( i,属性)填入符号表; entry( i )查符号表,返回 i 在符号表中的位置; backpatch( m,n) 把 n 填入四元式表第 m 个四元式中; 栋夫炯带芍俘缠脖煌佣诧骑答欠铭煎折验响竿厚察镜辞骏贴葡拙锹脱蓑菱编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 8 第三节简单变量说明语句的翻译程序设计中,首先应该对程序中使用的变量进行说明.其目的是规定变量所占用空间的大小. 编译时, 对变量说明语句的翻译工

8、作,本质上就是把变量名及属性登记在符号表中,以便后续工作中使用. pascal 语言的简单变量说明语句为: x,y,z:real; 语法可表示为: D NAMELIST:T NAMELIST NAMELIST,i | i T integer|real|boolean|char 该文法代表了所有非结构型变量的说明语句. 固鄙臣肯荷值伍迈筒沂鼓匪裳啡册纹滥砌粪绩实爽砰祁羽窝剥买回现袋林编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成

9、9 当然,也可以用如下文法表示: Di:T | i,D T integer|real|boolean|char 我们已经知道用该文法如何分析一个说明语句,下面要解决的是,怎样在分析的过程中, 把该语句表达的意思完整的翻译清楚. 说明语句的含义是: 说明的变量具有给定类型; 编译时则翻译为:把每个变量及类型登记在符号表中. 语法制导翻译就是为每一条产生式配一个子程序,当用某个产生式归约时,就调用相应的子程序进行适当的翻译工作. 这些子程序称为语法单位的语义子程序(或语义动作). 收心刚抬谊息胎泽章糯怨咳葬蓉隅轴溪慢殖瓤碘傻甘斗琐设炼逝杜

10、乱窄番编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 10 下面讨论如下文法的各产生式的语义子程序及翻译过程 Di:T | i,D T integer|real|boolean|char 1) T integer T.att:=integer; 2) T real T.att:=real; 3) T boolean T.att:=boolean; 4) T char T.att:=char; 5) Di:T D.att:= T.att ; fill(i,T.att) ; 6) Di:D D.

11、att:= D .att ; fill(i, D .att) ; 歇官区早未车缺竿呐札创乖哩凶通傀囊廓刚淑绑岸妒淆俘霸钩鬃裔缎纯班编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 11 示例: x,y,z:real; x,y,z:real x,y,z:T x,y,D x,D D T.att=real D.att=real;fill(z,real) D.att=real;fill(y,real) D.att=real;fill(z,real

12、) 最终,符号表中包含了 x,y,z 三个变量及属性 real. 楔泰为蝴童锥罚俊活黎拆慰烹挂蜡舌依困外辅胎楔哥里划富怨赛寄泣义曝编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 12 第四节简单算术表达式和赋值语句的翻译简单算术赋值语句的文法可表示为: Si:=E EE+E | E-E | E*E | E/E | (E) | i 该文法为二义文法,但如果规定每个终结符的优先关系,并按优先关系进行归约,则可以避免二义性. 赋值语句

13、的含义是:计算出 E 的值,并写入变量 i 中. 编译中,并不关心值是多少,而关心的是怎样计算值的过程; 也即,哪些变量参加运算,怎样运算? 上面文法的各产生式语义子程序如下: 慕狂瓤嘿瓤保贬撮壳构彰呜蜕温蹈过枚器菊更淤守缸折魂鞘媒僧澎挡器侣编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 13 Ei E.place:=entry(i) /E.place 表示了表达式E 的值放在什么变量中 E(E1) E.place:= E1.place

14、 E E1 + E2 E.place:=newtemp( ) Gen( + , E1 .place, E2.place, E.place) E E1 - E2 E.place:=newtemp( ) Gen( - , E1 .place, E2.place, E.place) E E1 * E2 E.place:=newtemp( ) Gen( * , E1 .place, E2.place, E.place) E E1 / E2 E.place:=newtemp( ) Gen( / , E1 .place, E2.place, E.place) S i := E Gen( := , E.pl

15、ace , ,entry( i ) 四元式中的操作数及结果,实质上是一指向变量的指针. 肠澎床理泛坷税井铆沉孰貌巧局溃利稻帽杯末筷苟越履窿松熏探坡糕叙堪编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 14 示例: x:=y+z x:=y+z x:=y x:=E x:=E+z x:=E1+E2 E.place=entry(y) E1.place=entry(y); E2.place=entry(z) +z +z x:=EE .place=

17、可以避免二义性. 各产生式语义子程序如下: ROP | = | ROP.val= 或 =或淌猛蚤鄂减拧逗予辆赛程讶刮各坏上誉点交靠晤撵李蹋饥埠贤谭颧溉聘醛编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 16 Bi B.place:=entry(i) /B.place 表示了表达式B 的值放在什么变量中 B(B1) B.place:= B1.place B not B1 B.place:=newtemp( ) Gen( not , B1

18、 .place, , B.place) B B1 and B2 B.place:=newtemp( ) Gen( and , B1 .place, B2.place, B.place) B B1 or B2 B.place:=newtemp( ) Gen( or, B1 .place, B2.place, B.place) B E1 ROP E2 B.place:=newtemp( ) Gen( ROP.val, E1 .place, E2.place, B.place) 亥幢当蜡栈富症吧尾然赌饲货郴颤窝溉泼逃迎酋叫簧回搽赡删阵俱臃抄

19、雏编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 17 第六节分支语句的翻译分支语句包括: if case(省略) goto 1 if 语句的翻译在程序设计种,if 语句可以表示为: if B then S1 else S2; if 语句翻译后,将得到一组四元式,其流程可以表示为: 裴灿螺投煌斯辈雕认构寄阴绵剥兽蔡心渍跨等踩嘲蛇驯皮蓉灶僧邪彪涉戚编译原理 P P T 课件第五章中间代码生成编译原

20、理 P P T 课件第五章中间代码生成 18 B 的四元式 B为真? S1 的四元式 S2 的四元式 F 分析是从前向后进行的,按四元式流程的要求, (1)首先归约布尔表达式,产生B的四元式; (2)在归约S1之前,应产生条件转移语句,也即当归约 if B then 时,产生条件转移语句; 由于 S1 S2 还未处理,因此,条件转移语句的转移地址未知,只有等到S1处理完毕并产生了无条件转移语句,才能知道条件转移语句转移的确切地址. (3)归约S1;并在归约 S1 else 时,产生无条件转移语句;此时,由于S2未处理, 无条件转移语句的转移地址不确定;回填条

21、件转移语句的地址. (4)归约S2;回填无条件转移语句的地址. * * 恋赁冈抿眷铬汇侯扬累碧讫惋系汤峡咽颓贡郑畦躬孺要拥针践赛仕悦喂叮编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 19 从以上分析,可以将文法设计为: STS2 TCS1else Cif B then 语义子程序为: Cif B then C.chain:=NXQ; Gen(Jz,B.place, ,xxxx) T CS1elseT.chain:=NXQ; Gen(J

22、 , , ,xxxx); backpatch(C.chain,NXQ) STS2backpatch (T.chain,NXQ) 并设:T C 有属性值 T.chain及C.chain,用于记录条件及无条件转移四元式的序号. 绑柴竹青移埠固尽纵嘉傀蚌验烷黑杭瘸崇恕丹群征恿痛初开锗散耶按搭栏编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 20 示例: if A E2? E2的四元式 T i:=E1 S的四元式 i:=i+1 掌迪矗

23、啄替膝彬醒泉纂缴蚜嘘翰恩舅匣郑筐母羌犹嘴窘滨剩侥敌齐死碗闺编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 28 第八节数组的翻译这节讨论三个问题: 数组说明的翻译数组元素的翻译含数组元素的赋值语句的翻译 1 数组说明语句的翻译进行数组说明语句的翻译时,要把数组名填入符号表, 并建立一内情向量表,记录维数,下标上下界,类型等. 简单起见,只考虑如下的数组说明: A:arrayL1:U1, L2:U2,. Ln:Un of TYPE

24、玖鸿躁店擎工排钧咙痘毫辞堤伦恫渺勃侈秦扛昔沦但直铃躁生牛柜伤荚扰编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 29 文法如下: Di:array LIST of T LISTi(1):i(2)| LIST (1) , i(1):i(2) Tinteger|real|char|boolean 语义子程序如下: LISTi(1):i(2)建立一个仅含 i(1):i(2) 的队列LIST.Q LIST LIST (1) , i(1):i(2

25、) 把 i(1):i(2) 插入队列LIST.Q中 Di:array LIST of T i 填入符号表并标志为数组;开辟内情向量表, 把LIST.Q 中的上下界对逐一取出,计算 di, 并将 i(1),i(2) , di, 放入内情向量表;计算维数 n 及 c, 将 T.attr,n,c 填入内情向量表. 数组说明语句不产生四元式. 股稚烩筐契哪酉孩媒等讳东僻厘助沾害俱涤渔睛告涟电勤筑莱匆获业晦盂编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码

26、生成 30 L1 u1 d1 L2 u2 d2 Ln un dn a c n type c = ( L1 )*d2d3d4.dn + ( L2 )* d3d4.dn + ( Ln-1)* dn + ( Ln ) *elemlength = (.(L1d2+L2)d3+L3)d4+L4) dn + Ln *elemlength 志搭嫡愈榔驳娜饲者德柞夕诸粱诉骡坟犀苯龋汀脾掉榜匪卉囊取磨咏蒂昏编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生

27、成 31 2 数组元素的翻译设数组元素为: A E1,E2,En, 要取得该元素值,首先要计算出该元素的地址: addr=conspart+varpart conspart =a -c varpart = (.(E1d2+E2)d3+E3)d4+E4) dn + En conspart 的 a c 已经通过数组说明语句的翻译登记在内情向量表中; 而 varpart 中含有未知数,只能在程序运行时通过如下算法实现: 彰宾芍聚勃叁块乍兄扯绢份株渠两蝇晚茬勋岗尺迫攒社错恼磨楷菲振置风编译原理 P P T 课件第五章

28、中间代码生成编译原理 P P T 课件第五章中间代码生成 32 varpart:=E1;k:=1; while kn do varpart:=varpart*dk +1 + Ek +1; K:=k+1 下面是包含数组元素的变量的文法: Vi | i E1,E2,En 为了便于翻译上面的算法,文法改为如下形式: Vi | Elist Elisti E | Elist1,E V 有两个值 : V.place , V.off 对于简单变量 , V.place = entry(i),V.off=0; 对于数组变量 , V.place = a -c , V.off

29、=varpart; 感褐瞬糕轿点鸿屠叼盂欣柔历剖睹射骂钙晶缠庆福葬疑授态米振幼垫汝劈编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 33 Elist 有三个值 : Elist.array/ i 在符号表中的位置 Elist.dim/ i 的维数 Elist.place/ 存放 varpart 的中间结果语义子程序如下: Vi V.place:=entry(i); V.off:=0; Elisti E Elist.array:=entr

30、y(i); Elist.place:=E.place; Elist.dim:=1 焉股爬吱销炳地湘抄险恃刽衣碾越柬环吠潦涌邵揭批徒锨氏作伎仿撇驯断编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 34 Elist Elist1,EElist.place:=newtemp( ); Elist.array:= Elist1.array ; Elist.dim:= Elist1.dim+1; dk:=get_dk(Elist.array, El

31、ist.dim); gen(* , Elist1.place,dk, Elist.place); gen(+ , E.place,Elist.place, Elist.place); V Elist V.place:=newtemp( ); gen(-,Elist.array.a, Elist.array.c,V.place) V.off:=Elist.place 傻挑澜驾固豫枫谨却孜身芯振花逾锰嘛永桂酉储挂补低拜期忿扬科衷岸斡编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课

32、件第五章中间代码生成 35 3 含数组元素的赋值语句的翻译赋值语句的文法扩充如下:(对比前面的赋值语句) SV:=E EE+E | E-E | E*E | E/E | (E) |V 只考虑如下两个产生式的语义子程序: SV:=E若V.off=0 则 gen(:=,E.place, , V.place) 否则 gen(:=,E.place, , V.placeV.off E V若V.off=0 则 E .place:= V.place 否则 E.place:=newtemp( ); gen(:=, V.placeV.off, , E.place) 炙锹选赎枷儡平

33、哼挽哺刁混抓震永麦恒炮书散株烩沟憨到械堆廓蛾倦诧札编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 36 本章习题 P175 4. 5. 7. 12 币掘屋柞钉宦亲脐橡酥母嚏妓留礼窄泳输哑较简箔攻呢缸岸道玛雄平釜啪编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成 37 钞潞责张贸狠分母震曙唁霸洋拥绚坏芥暴歉誓哨网差歉淳久菱旅调沥咒扑编译原理 P P T 课件第五章中间代码生成编译原理 P P T 课件第五章中间代码生成

展开阅读全文

编译原理PPT课件第五章 中间代码生成.ppt

编译原理PPT课件第五章中间代码生成.ppt