版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
使用中间语言的好处:复杂性界于源语言和目标语言之间便于进行与机器无关的代码优化工作易于移植使编译程序的结构在逻辑上更为简单明确源语言程序目标语言程序中间语言程序CompilerFrontEndCompilerBackEnd---->编译程序---->
输入
输出
第一页,共二十六页。语法制导翻译和中间代码生成文法的语法制导定义(语义规则)和翻译方案--语法制导定义-->语义分析做什么
--翻译方案-->中间代码生成怎么做第二页,共二十六页。中间语言高级的:接近源语言。语法树,适合完成静态类型检查。低级的:接近目标语言。适合完成依赖于机器的任务。常用的中间语言:后缀式:逆波兰表示图表示:DAG、抽象语法树三地址代码三元式、四元式中间代码的选择可以是一种实际的语言也可以是编译各阶段共享的内部数据结构7.1中间语言第三页,共二十六页。P200后缀式定义写出3+4*5的后缀式写出b*(-c)+b*(-c)的后缀式后缀式表示:算术表达式、赋值语句、控制语句后缀式的计算用一个栈实现一般的计算过程是:自左至右扫描后缀式,每碰到运算量(操作量)就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项,并用运算结果代替这k个项。7.1.1后缀式
第四页,共二十六页。7.1.2图表示法图表示法DAG-无循环有向图抽象语法树
第五页,共二十六页。7.1.2图表示法无循环有向图(简称DAG)对表达式中的每个子表达式,DAG中都有一个结点一个内部结点代表一个操作符,它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点第六页,共二十六页。7.1.3三地址代码三地址代码x=yopz三地址代码可以看成是抽象语法树或DAG的一种线性表示树与其他中间代码的关系第七页,共二十六页。
a:=b*(-c)+b*(-c)的图表示法
请画出语法树和DAG
:=a+*b-cDAG:=a+*b-c抽象语法树*b-c第八页,共二十六页。抽象语法树对应的代码:t1=-c t2=b*t1
t3=-c t4=b*t3 t5=t2+t4
a=t5assigna+*buminusc抽象语法树*buminusc第九页,共二十六页。DAG对应的代码:
t1=-ct2=b*t1t5=t2+t2a=t5assigna+*buminuscDAG抽象语法树对应的代码:t1=-c t2=b*t1
t3=-c t4=b*t3 t5=t2+t4
a=t5第十页,共二十六页。作业:P2217.1第十一页,共二十六页。7.3中间代码生成
----赋值语句翻译成三地址代码
产生三地址代码赋值语句翻译方案填查符号表词法分析发布出错信息第十二页,共二十六页。语法制导翻译第十三页,共二十六页。三地址代码的形式:
1.三元式、2.四元式、3.间接三元式1、三元式
三元式:(i)(op,arg1,arg2)
三地址码:(i):=arg1oparg2例4.5
表达式x:=a+b*c的三元式:
(1)(*,b,c) (2)(+,a,(1)) (3)(:=,x,(2))
标识符a,b,c,x分别表示它们的存储位置,序号(1)、(2)、(3)分别是它们在三元式表中的位置。
■
第十四页,共二十六页。三地址代码的形式:
三元式、四元式、间接三元式2、四元式四元式:(i)(op,arg1,arg2,result)
四地址码:result
:=arg1oparg2例4.5
表达式x:=a+b*c的四元式:
(1)(*,b,c,T1) (2)(+,a,T1,T2) (3)(:=,x,T2)第十五页,共二十六页。属性文法是在上下文无关文法的基础上,为每个文法符号配备若干相关的“值”,称为属性,属性与变量一样可以进行计算和传递,属性加工的过程即是语义处理的过程。对文法的每个产生式配备的一组属性的计算规则,叫语义规则,语义分析和中间代码的产生就是根据该规则进行的,在自上而下或自下而上语法分析过程中,在适当的时候进行属性的计算,或其它语义动作(如查填符号表、产生中间代码、发布出错信息)就可进行语法制导翻译得到中间代码,这就是语法制导翻译的基本思想。语法制导翻译和中间代码产生第十六页,共二十六页。产生赋值语句抽象语法树的属性文法产生式 语义规则S→id:=E S.nptr:=mknode(‘assign’,
mkleaf(id,id.place),E.nptr)E→E1+E2
E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)E→E1*E2
E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)E→-E1
E.nptr:=mknode(‘uminus’,E1.nptr)E→(E1) E.nptr:=E1.nptrE→id E.nptr:=mkleaf(id,id.place)第十七页,共二十六页。LR分析翻译方案产生式与翻译方案A(1)A→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{A.code:=trip(:=,entry(),E.code)}{E.code:=trip(+,E1.code,E2.code)}{E.code:=trip(*,E1.code,E2.code)}{E.code:=E1.code}{E.code:=trip(@,E1.code,)}{E.code:=entry()}
产生式与翻译方案B
(1)A→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{A.code:=newtemp;emit(:=,entry(),E.code,A.code)}{E.code:=newtemp;emit(+,E1.code,E2.code,E.code)}{E.code:=newtemp;emit(*,E1.code,E2.code,E.code)}{E.code:=E1.code}{E.code:=newtemp;emit(@,E1.code,,E.code)}{E.code:=entry()}
分别生成三元式代码、四元式代码第十八页,共二十六页。.code=a
.code=b
.code=c.code=(1)(*,b,c)
.code=(3)(:=,x,(2)).code=(2)(+,a,(1))
(1)(*,b,c)(2)(+,a,(1))(3)(:=,x,(2))产生式与语义规则A:(1)A→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{A.code:=trip(:=,entry(),E.code)}{E.code:=trip(+,E1.code,E2.code)}{E.code:=trip(*,E1.code,E2.code)}{E.code:=E1.code}{E.code:=trip(@,E1.code,)}{E.code:=entry()}
例生成x:=a+b*c的三元式三元式序列:第十九页,共二十六页。语义规则B(1)A→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{A.code:=newtemp;emit(:=,entry(),E.code,A.code)}{E.code:=newtemp;emit(+,E1.code,E2.code,E.code)}{E.code:=newtemp;emit(*,E1.code,E2.code,E.code)}{E.code:=E1.code}{E.code:=newtemp;emit(@,E1.code,,E.code)}{E.code:=entry()}
例生成x:=a+b*c的四元式.code=a
.code=b
.code=c.code=(1)(*,b,c)
.code=(3)(:=,x,(2)).code=(2)(+,a,(1))
(1)(*,b,c)(2)(+,a,(1))(3)(:=,x,(2))三元式序列:四元式序列:
(*,b,c,T1)(+,a,T1,T2)(:=,x,T2,T3)第二十页,共二十六页。属性文法是在上下文无关文法的基础上,为每个文法符号配备若干相关的“值”,称为属性,属性与变量一样可以进行计算和传递,属性加工的过程即是语义处理的过程。对文法的每个产生式配备的一组属性的计算规则,叫语义规则,语义分析和中间代码的产生就是根据该规则进行的,在自上而下或自下而上语法分析过程中,在适当的时候进行属性的计算,或其它语义动作(如查填符号表、产生中间代码、发布出错信息)就可进行语法制导翻译得到中间代码,这就是语法制导翻译的基本思想。语法制导翻译和中间代码产生第二十一页,共二十六页。LR分析翻译方案的设计
LR分析中的语法制导翻译实质上是对LR语法分析的扩充:<1>扩充LR分析器的功能:当执行归约产生式的动作时,也执行产生式对应的语义动作。<2>扩充分析栈:增加一个与分析栈并列的语义栈,用于存放分析栈中文法符号所对应的属性值。例:E→E1+E2
val[top]:=val[top]+val[top+2];
对于表达式:5+3当归约为左部E时,同时也得到了值8。第二十二页,共二十六页。产生式算术表达式(语义规则)翻译方案-三地址码-P208(1)S→id:=E(2)E→E1+E2(3)E→E1*E2(4)E→(E1)(5)E→-E1(6)E→id{p=lookup(id.lexeme);if(p!-nil)emit(p,’=’
,E.place)elseerror}{E.place=newtemp();emit(E.place,’=’,E1.place,’+’,E2.place)}{E.place=newtemp();emit(E.place,’=’,E1.place,’*’,E2.place)}{……}{……}{……}
属性.place: 表示存放运算结果的变量;函数newtemp():返回一个新的临时变量,如t1,t2,...等;过程emit(result,’=’,arg1,op,arg2):
生成一个3地址指令。第二十三页,共二十六页。步骤栈内容当前输入移进-规约动作翻译动作(语义规则具体化)A1#0i1*i2+i3#移进:s52#0i15*i2+i3#规约:r6(F→i)F.place=porF.place=entry()3#0F3*i2+i3#规约:r4(T→F)T.place=F.place4#0T2*i2+i3#移进:s75#0T2*7i2+i3#移进:s56#0T2*7i25+i3#规约:r6(F→i)F.place=porF.place=entry()7#0T2*7F10+i3#规约r3(T→T*F)T.place=newtemp(),emit(T.place,’=’,T.place,’*’,F.place8#0T2+i3#规约:r2(E→T)E.place:=T.place9#0E1+i3#移进:s610#0E1+6i3#移进:s511#0E1+6i35#规约:r6(F→i)F.place=porF.place=entry()12#0E1+6F3#规约:r4(T→F)T.place=F.place13#0E1+6T9#规约:r1(E→E+T)E.place=newtemp();emit(E.place,’=’,E.place,’+’,T.place)}14#0E1#acc(1)t1=i1翻译动作(2)t1=t1(3)t2=i2(4)t3,t3=t1*t2(5)t3=t3(6)t4=i3
(7)t4=t4
(8)t5,t5=t3+t4P208,P113,P6(1)t1=i1三地址代码(2)t1=t1(3)t2=i2(4)t3,t3=t1*t2(5)t3=t3(6)t4=i3
(7)t4=t4
(8)t5,t5=t3+t4第二十四页,共二十六页。步骤栈内容当前输入移进-规约动作翻译动作B1#0i1*i2+i3#移进:s52#0i15*i2+i3#规约:r6(F→i)F.code:=entry()3#0F3*i2+i3#规约:r4(T→F)T.code:=F.code4#0T2*i2+i3#移进:s75#0T2*7i2+i3#移进:s56#0T2*7i25+i3#规约:r6(F→i)F.code:=entry()7#0T2*7F10+i3#规约:r3(T→T*F)T.code:=newtemp,emit(*,T.code,F.code,T.code)8#0T2+i3#规约:r2(E→T)E.code:=T.code9#0E1+i3#移进:s610#0E1+6i3#移进:s511#0E1+6i35#规约:r6(F
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 3.13 异域的憧憬-美术交流与美术作品的关系 教学设计高中美术湘美版(2019)美术鉴赏
- 房地产营销策划 -常德棚改项目定位及策略建议
- 《无人机无人船协同海洋测绘作业规程》(征求意见稿)
- 2025届高考语文复习:诗歌赏析技巧-如何读懂诗歌+课件
- 详解保育猪饲养存在的问题及管理技术
- 3个人开店入股协议书范文范本
- 【课件】质量+课件人教版物理八年级上学期
- 3.1 列代数式和代数式的值-2024-2025学年七年级数学上册《知识解读题型专练》(北师大版2024新教材)
- 新入职工入职安全培训试题附参考答案【培优】
- 工厂车间安全培训试题含答案(轻巧夺冠)
- 5.1 走近老师 课件- 2024-2025学年统编版道德与法治七年级上册-1
- 送电线路工(初级)技能鉴定理论考试题库(浓缩300题)
- 围栏喷漆翻新施工方案
- 2024年文化和旅游部直属事业单位招聘历年高频500题难、易错点模拟试题附带答案详解
- 《林教头风雪山神庙》名师课件2
- 医疗行业智能化医疗设备维修与保养方案
- GB/T 44236-2024增材制造用镍钛合金粉
- 2024年黑龙江省哈尔滨市道里区执法局招聘52人历年高频考题难、易错点模拟试题(共500题)附带答案详解
- 2024-2025学年人教版一年级数学上册 第二单元测试卷
- 2024-2025学年八年级物理上册 3.2 熔化和凝固教学设计(新版)新人教版
- 苏教版英语小学四年级上学期2024年复习试卷及解答参考
评论
0/150
提交评论