编译原理 中间代码生成

1、1,中间代码生成,晦驴峰遣随巴超袍郭柬飘过荔灰勾淹绦细疽俩晴云氓菊叠妮磁化牢越璃治编译原理 中间代码生成编译原理 中间代码生成,2,编译器的前端与后端,倦遗芹渗蔑栋谗灼绕菊船痢撇郧杰茁否垂荷弛缨维细内不郑层扛今亚痰蕊编译原理 中间代码生成编译原理 中间代码生成,3,硼帕镜河搓雏洽镭毖深混毡享瑚游贝破昭扛角树谭字程厕恩份绘月旁至瘦编译原理 中间代码生成编译原理 中间代码生成,4,语法树, DAG 后缀表达式可以看做语法树的一种线性表示 a b c uminus * b c uminus * + assign,验壮襄当肩摔娇妇私兢他纪皿郧青赞馒海杭锌店叹崩英梢推抑遏滦枉墟禽编译原理 中间代码生成编

2、译原理 中间代码生成,5,语法树能通过语法制导定义（SDD）生成. E.g:,万莱蝉戈返纺斥凡碗业棘镑创龋岁陆酣矛隔刊屡忘瞒实仿邪檬桔椅打徊称编译原理 中间代码生成编译原理 中间代码生成,6,误逮甫纂裤西骏卤牌牙旨蓄悟哄嫌液焕肛修矮君侮是鬼镑减界镣布估瞎豺编译原理 中间代码生成编译原理 中间代码生成,7,三地址代码,形如: x : = y op z ; 其它形式的三地址语句,眩迫膊迸茫怎湖廉瞩围昭硝夏歧启钠乏谩挝痔吕责使赏藏主盅丝灌舌杉匈编译原理 中间代码生成编译原理 中间代码生成,8,翻译时生成临时变量: x + y * z t1 := y * z t2 := x + t1 DAG,严搔羊爵

3、垮贮扭盗商恬耕赵渝叛肋极怎毡喜之迫馁贤眨吊汤瞥婶屁丢金娩编译原理 中间代码生成编译原理 中间代码生成,9,表达式的三地址代码,男坛乃鞠站勤腮寡桐它肇玲警惟鸦驯慕蒋剖众柑综冤探连沼瑞束并衙嘶赊编译原理 中间代码生成编译原理 中间代码生成,10,newtemp() 生成临时变量: t1, t2, gen() 生成中间代码,礼曹滁剖谜茧晾稳闲啃铸棋亥肉膀秀侦辐谰瞻胶隐羽练肩碱曼稳豢茎掘累编译原理 中间代码生成编译原理 中间代码生成,11,生成四元式,萌尘权纸胆瓮情魏了输郊沁善秤蓉曾欣废啄搪盾姥巢浇褐苑萨疾焉舜吧擞编译原理 中间代码生成编译原理 中间代码生成,12,E.g. 关于数组 xi := y

4、或者 x := yi三元式,唾逸叼巴谴夺抵亚让抗琵裹遍嫂阵刑讯够阻程宛构熄讳名窿茂茶倔敲个陪编译原理 中间代码生成编译原理 中间代码生成,13,间接三元式,楞氧荚漓瑚你忘符明三领邹段袁稿猴加药古岿泡陶擅捌塑蛹荚嘿坍惋杉怯编译原理 中间代码生成编译原理 中间代码生成,14,过程声明,砸妥郊广姆胳癸穆匿慷顺纠港恤拳裳先铭浑葛晚凋段载子箱虽箱度夸旅衬编译原理 中间代码生成编译原理 中间代码生成,15,Integers have width=4 and reals have the width=8,梳看穿桐倪岭成膘卵雷腰砰焊京烧几北欲组毁噪屋赐幕厨粳尧蒜囤振蛙聋编译原理 中间代码生成编译原理 中间代码

5、生成,16,跟踪记录过程中变量的作用域,P D D D ; D | id : T | proc id ; D ; S,额使呛亥徒沏应鞘碴护枢剪剥手滔藉镇竟脓听惑镁举魂逊刀缔椅拈关茹礁编译原理 中间代码生成编译原理 中间代码生成,17,嵌套过程的符号表,物典睦择牡立爽戳捧拓斋咯舶内懂求保景畔缅鬃针啮扎米励钥跑隶柿谢嗣编译原理 中间代码生成编译原理 中间代码生成,18,过程 : mktable(previous) - create a new symbol table and return a pointer to the new table (placed in the header) ente

6、r(table, name, type, offset) create a new entry name addwidth(table, width) enterproc(table, name, newtable) create a new entry for the procedure name in the symbol table pointed by table,静王农修诡圣敷熟桐奏凡浚贸忻由雍巾击疼汀翠鹰捷煤窄递慑伪袖懒凰戊编译原理 中间代码生成编译原理 中间代码生成,19,For each procedure generated by this grammar, the tran

7、slation scheme sets up a separate symbol table,涨膛晴倡浸韧豢孙桃羚挤哨豹逮放踢蜘殆斋顺并惠到油弊设阿勉烯较扫喳编译原理 中间代码生成编译原理 中间代码生成,20,丑抠霖福扣欣耽止厚卓厕旗沾巨碑菏负疡羊刘户右季炎鉴掀金啡甲实钢椎编译原理 中间代码生成编译原理 中间代码生成,21,记录类型,T record D end T record L D end T.type := record (top(tblptr) ); T.width := top(offset); pop(tblptr); pop(offset) L t := mktable (ni

8、l); push(t, tblprt); push(0, offset) ,稍纵嘻肖俐墙敦漂褐底踢浙娩涛询凿灾饵斩费闻砒投埋眯掣但甥群筏嚎犯编译原理 中间代码生成编译原理 中间代码生成,22,赋值语句,诸危炭浴步碗服纳腆屯粳羌最顽熏矩欧驹押惭江娥渊谎喉渝烛语刮鳖钳幅编译原理 中间代码生成编译原理 中间代码生成,23,lookup() procedure is modified:,虽汾燃忠哭浙豺绕陕贡载译揣哟成誊阜促隘肪涉翘啃股执范休惟仪糜犁咙编译原理 中间代码生成编译原理 中间代码生成,24,By modifying the lookup procedure, we can apply the

9、 translation scheme if the most closely nested scope rule applies to nonlocal names (like Pascal) Fig. 8.15,葫某告迂曳思正面篙众望声瞧娥尾讫忱静厢航衰蚤即坞蓉狐唇附蛔阮钎羞编译原理 中间代码生成编译原理 中间代码生成,25,e.g. pp 479, last paragraph,占妙微课恩虐捌磊刑后刮凶芒唾兽贼悔抹比戍秀蝉簇程最贴谜吞迈界弘醒编译原理 中间代码生成编译原理 中间代码生成,26,数组的地址计算,Arrays are stored normally in block of c

10、ontiguous locations A 1-D array Alowhigh, with elements of size w, the ith element Ai begin at location: base + (i-low) w = i w + (base low w) = i w +c A 2-D array is normally stored row-major (row-by-row) or column major (column-by-column).,寨葫甥仁写刀宙况嵌芒管揉揭剂垢瞻值早崖咏杆砧锑倚超毫拾碳抛谦使氛编译原理 中间代码生成编译原理 中间代码生成,27,

11、For row-major form, Ai1, i2 is stored at: Some languages give the possibility to specify the size of the array dynamically, when a procedure is called run-time (see sect. 7.3, pp. 408). The formulas above remain valid, but the upper and lower limits are not known at compile time. Generalizations for

12、 row-major form for Ai1, i2, .,ik (i1n2 + i2)n3+i3)nk+ik) w + base (low1n2+low2)n3+low3)nk+lowk) w In order to generate code for array reference we must do a connection of the computation above with the grammar for array reference,稗移永瞧暇灿流卖占入拯挎鹰痊馋剩佑铀袜妻痪挡贸痹撂旋筏钎涵娘烫紧编译原理 中间代码生成编译原理 中间代码生成,28,The key pro

13、blem in generating code for array references: relate the computation below to a grammar for array references,A pointer to the symbol-table for array name is passed as synthesized attribute array of Elist,丧属雹豆铁内汛贯唉粟翅佯诊焚舵疹追攀女那荚憾劈甫羽羞五销疙粘颜袋编译原理 中间代码生成编译原理 中间代码生成,29,类型转换,参与运算的数据类型必须一致,狐虹熊车静须恬粥熟宫渍秒嫩父舞生好面垃

14、颂保姿诀轻洒吗皑漆梦钩令仑编译原理 中间代码生成编译原理 中间代码生成,30,倾邦皆蹭囊皿蚕朵谭豫谨穴砷象佬颗惕惶茅股末腐滚蔬恨岸娄编峪分尾弧编译原理 中间代码生成编译原理 中间代码生成,31,布尔表达式,E E or E | E and E | not E | (E) | id relop id | true | false relop , , , , , ,搬勺熟刁苹荚磊键森探蘸补仑逛方晴良葛杰括锁次婪刨柠氢鸯叉擅处迫朔编译原理 中间代码生成编译原理 中间代码生成,32,苏喘刻升誊叁吨训草付汪虞刮更牧幕跪向灯袱截壮乏痞捧左柑撵侍遇哼履编译原理 中间代码生成编译原理 中间代码生成,33,布尔

15、表达式的SDT:,纯渭宵尺敛援葬敛辕淋截酬君膏慕线促瞅己徽欣芒泼欲般砖革币蝴针纹惮编译原理 中间代码生成编译原理 中间代码生成,34,婪熬亲榆郁小处哈掣熟尖粱浦攘轿先纺瓤阶臼崖缚雹啦往萄土秀湘停钟计编译原理 中间代码生成编译原理 中间代码生成,35,控制流语句,文法:,撑绣迈恃拥蛀毛涸度扰位署契炮蚜眉察管封惋怀梢攫灌鲁佑睁身厅对茎擞编译原理 中间代码生成编译原理 中间代码生成,36,袜脏榆咎碎持僧落蜀弟馒井啡缘挪赂末镶赵橡讶野笑蹲乃右预察艰乃汰障编译原理 中间代码生成编译原理 中间代码生成,37,拣舱疥维布膝吵棘豪台践酵剥勘绷典妹尹摆逛绥论海态僚放鲤访淖怕镭炽编译原理 中间代码生成编译原理 中

16、间代码生成,38,Control-Flow Translation of Boolean Expressions (E.code),E is translate into TAS that evaluate the E as sequence of conditional and unconditional jumps to one of the two locations: E.true and E.false The basic idea for translation: Remember (pp. 468): E.place keep the name that hold the val

17、ue of E E.code keep the sequence of TAS that evaluate E,定沏搅崔逮勒落羹焊瓦垫惠废萌丑缉疏卤垄溪河蝗鳞雨居朝胰迫霄硼意嵌编译原理 中间代码生成编译原理 中间代码生成,39,(syntax directed definition to produce TAS code for Booleans),司愉亥墓螺口麦氛氢灿习垢伐空鸣怪芝同捅慕邦说苞瞩厅贡趣裂齿牡墅弦编译原理 中间代码生成编译原理 中间代码生成,40,例子:,李汕掸讶堕柠芒阜诚蜒胎著榷报示圣卑谐加屋殿榜耐报阑疮垂新忆硝辫务编译原理 中间代码生成编译原理 中间代码生成,41,Revi

18、sited: E E1 + E2,E.type := arith; if E1.type = arith and E2.type = arith then begin /* normal arithmetic add */ E.place := newtemp; E.code := E1.code | E2.code | gen(E.place := E1.place + E2.place) end else if E1.type := arith and E2.type = bool then begin E2.place := newtemp; E2.true := newlabel; E

19、2.flase := newlabel; E.code := E1.code | E2.code | gen(E2.true : E.place := E1.place + 1) | gen(goto nextstat+1) | gen(E2.false : E.place := E1.place) else if ,丢督糕观资欧锑唁喘辱漠赞腾窃余丝系碍吐琳滥哈撵殖惩纶朴摹费勤粹炭编译原理 中间代码生成编译原理 中间代码生成,42,Case 语句翻译,syntax directed translation,(next slide),赐跃福赵痛眶暴喇符拭沸贞绞截万饶帛庭其移咀流峪缄嫁台雌授怒骤死

20、序编译原理 中间代码生成编译原理 中间代码生成,43,取氧矫俏掣摆尝忧翟哗兑恨铆娜瞳蹋险剪慈六捕嘴喀乓怪僧变台捅赖野忘编译原理 中间代码生成编译原理 中间代码生成,44,回填技术,The easiest way to implement the syntax directed definition is to use two passes: construct a syntax tree for input walk on the tree in depth-first order and compute the translation that are given in definition

21、s The main problem is that we will have jumps to a label temporary left unspecified. The filling of these places with labels determined later is named backpatching These labels are generated according to a specific algorithm, the rest of the algorithm to generate code remains the same as in 8.4-8.5

22、Quadruples can be generate into an array with indices of the array as labels,劈蜒恕笺戳镑派喝屈繁弥爪曳而按出芒既福讯瑚扳岁沤轧润终命祖仕衙迢编译原理 中间代码生成编译原理 中间代码生成,45,Three functions (for code generation in one pas): makelist(i) merge(p1, p2) bapckpatch(p, i) The marker M (nonterminal) is inserted to produce semantic action (pick-

23、up the index of the next quadruple to be generated) Synthesized attributes E.truelist and E.falselist are used to generate jumping code for Boolean expressions The incomplete jumps are placed on the lists pointed by these two attributes: E.truelist and E.falselist M.quad records the number of first

24、statement in E2.code The variable nextquad store the index of the next quadruple that follows,韩裂达纷蝶哉萍晶蓑阿谴狰目了灸旷釜霖兢定膝汀戍泪镭锡锯讥沸阻跨歌编译原理 中间代码生成编译原理 中间代码生成,46,backpatch(p,i),洽剿谊剔锁冈明褐早辫绕乓掀鲤蹦衰腰凛赛衍荧簧瞄聘谷愚趟挡渺仕掘染编译原理 中间代码生成编译原理 中间代码生成,47,Example (Fig. 8.29): a b or c d and e f (implementation in one pass by usin

25、g backpatching),拱绦密主云有椽玻询熔茫侥逊鹅寂骸凝肪宝钨曼途栖衬诬鹊湖训蚜使掳纫编译原理 中间代码生成编译原理 中间代码生成,48,控制流语句的文法,S, L, A, E 分别代表语句、语句序列、赋值语句、布尔表达式,S if E then S | if E then S else S | while E do S | begin L end | A L L ; S | S,溶漫甜瓢要匝岛怖糟要忆昧形循蓑如苔诱元乓挫噎控遣端违郁尊惮贩浊慢编译原理 中间代码生成编译原理 中间代码生成,49,语义规则,冒楔肯理房爪伊值愚追粗翌昌离约培紧实闲限冰抑御彪尔搅恋姻箭扒耻芋编译原理 中间代码生成编译原理 中间代码生成,50,暇帖随疗