第六章 中间代码生成.pptx
《第六章 中间代码生成.pptx》由会员分享,可在线阅读,更多相关《第六章 中间代码生成.pptx(167页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、HUANG Xiaoxi编译原理编译原理Principle of Compiler第六章 中间代码生成黄孝喜在编译器的“分析-综合”模型中,前端前端对源程序进行分析并产生中间表示,而关于目标机器的细节则在后端后端处理。本章内容涉及中间代码表示、静态类型检查和中间代码生成。2引子引子语法语法 分析器分析器静态检静态检查程序查程序中间代码中间代码生成器生成器代码代码 生成器生成器中间中间代码代码前端前端后端后端“中间代码生成”的任务任务把经过语法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。不同的编译器对中间表示的选择和设计各有不同。中间表示可以是一种真正的语言,也可以是各个处理阶段共享
2、的多个内部数据结构。早期的C+编译器就把C语言作为中间表示方法:语法制导翻译采用独立于机器的中间代采用独立于机器的中间代 码的好处码的好处1.便于编译系统建立和编译系统的移植;2.便于进行独立于机器的代码优化工作。3引子引子中间语言语法树有向非循环图DAG三地址代码表示类型检查常用语句的中间代码生成方法说明语句赋值语句布尔表达式与控制流语句回填4提纲提纲常用的中间代码(语言)语法树后缀式(逆波兰式)三地址代码表示特点形式简单、语义明确、便于翻译独立于目标语言56.1 6.1 中间语言中间语言抽象语法(AbstractSyntax)从具体语法中抽象出抽象出语言结构的本质性的东西,而不考虑语言的具
3、体符号表示,从而可简化语义的形式描述。在不同的语言中赋值语句有不同的写法x=y;x:=y;yx等等可以用抽象形式assignment(variable,expression)把前面各种具体形式统一起来。66.1.16.1.1图表示法图表示法抽象语法(AbstractSyntax)抽象语法树(AST)反映了抽象的语法结构,而分析树反映的是具体语法结构。语法树是分析树的抽象形式或压缩形式。在抽象语法树表示中,每一个叶结点都表示诸如常量或变量这样的运算对象,而其它内部结点则表示运算符。抽象语法树不同于分析树,它展示了一个操作过程并同时描述了源程序的层次结构。76.1.16.1.1图表示法图表示法语法
4、规则中包含的某些符号可能起标点符号标点符号作用作用,也可能起解释作用解释作用。回顾前述的赋值语句,其产生式规则是SV=e其中的赋值号“=”仅仅起标点符号作用,目的是把V和e分隔开而条件语句的产生式规则:SifBthenS1elseS2其中的关键字if、then、else起注释作用,说明当布尔表达式B为真时执行S1语句,否则执行S28抽象语法树抽象语法树赋值语句的本质部分是V和e条件语句的本质部分是B,S1和S2把语法规则中本质部分抽象出来而将非本质部分去掉后,便得到抽象语法规则这种去掉不必要信息的做法可以获得高效的源程序中间表示。上述语句的抽象语法规则为:(1)赋值语句:左部表达式(2)条件语
5、句:表达式语句1语句29抽象语法树抽象语法树根据这种方法得到两种语句的语法树如下:10抽象语法树抽象语法树assignmentvariableexpressionif-then-elseBS1S2赋值语句语法树赋值语句语法树条件语句语法树条件语句语法树在语法树中,运算符号和关键字都不在叶结点,而是在内部在语法树中,运算符号和关键字都不在叶结点,而是在内部结点中出现。结点中出现。赋值语句x=a+b*c的抽象语法树和分析树11抽象语法树抽象语法树assignmentx+a*bc抽象语法树SV=ExE+EaE*Ebc分析树分析树表达式的语法树构建方法(利用语法制导定义)辅助函数:1.mknode(o
6、p,left,right)建立一个运算符号结点,标号是op,两个域left和right指向运算分量结点的指针。2.mkleaf(id,entry)建立一个标识符结点,由标号id标识,一个域entry指向标识符符号表中相应的项。3.mkleaf(num,val)建立一个数结点,标号为num,域val用于存放数的值。返回新建立结点的指针。12抽象语法树抽象语法树建立表达式语法树的语法制导定义13抽象语法树抽象语法树 产生式产生式语义规则语义规则EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.
7、nptr:=T.nptrT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val)表达式表达式a-4+c的语法树建立过程的语法树建立过程14ididto entry for ato entry for aididto entry for cto entry for cnum num 4 4idid1 1T T1 1.nptr.nptrE E2 2.nptr.nptrE E1 1.nptr.nptrT T2 2.nptr.nptrT T3 3.nptr.nptridid2 2E.nptrE.npt
8、rnumnum+表达式表达式a-4+c的语法树建立过程的语法树建立过程15ididto entry for ato entry for aididto entry for cto entry for cnum num 4 4建立赋值语句语法树的语法制导定义16抽象语法树抽象语法树 产生式产生式语义规则语义规则Sid:=ES.nptr:=mknode(:=,mkleaf(id,entry),E.nptr)EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1E2E.nptr:=mknode(,E1.nptr,E2.nptr)EE1E.nptr:=mkunode(um
9、inus,E1.nptr)E(E1)E.nptr:=E1.nptrEidE.nptr:=mkleaf(id,id.entry)EnumE.nptr:=mkleaf(num,num.val)赋值语句赋值语句a:=b*c的语法树构建过程的语法树构建过程17id1S.nptrE1.nptr:=E2.nptr*E3.nptrid2E4.nptrid3ididto entry for bto entry for bididto entry for cto entry for cididto entry for ato entry for auminusuminus*:=赋值语句赋值语句a:=b*c的语法
10、树构建过程的语法树构建过程18ididto entry for bto entry for bididto entry for cto entry for cididto entry for ato entry for auminusuminus*:=表达式的有向非循环图表示(DAG,DirectedAcyclicGraphs)用途:提取表达式中的公共子表达式,以取得目标程序的局部优化。方法:执行mknode和mkleaf时,检查是否已有相同的结点,若有,则返回相应结点的指针。与语法树的区别:语法树中公共子表达式由重复的子树表示,而DAG中只用一个子树表示,因此代表公共子表达式的结点有多个父节
11、点196.1.16.1.1图表示法图表示法表达式a+a*(b-c)+(b-c)*d的语法树和DAG206.1.16.1.1图图表示法表示法ididto entry for ato entry for aididto entry for ato entry for aididto entry for bto entry for bididto entry for cto entry for c*ididididto entry for bto entry for bto entry for cto entry for c*ididto entry for dto entry for d表达式a+
12、a*(b-c)+(b-c)*d的语法树和DAG216.1.16.1.1图图表示法表示法p1:=mkleaf(id,entry-a);p2:=mkleaf(id,entry-a);p3:=mkleaf(id,entry-b);p4:=mkleaf(id,entry-c);P5:=mknode(-,p3,p4);P6:=mknode(*,p2,p5);P7:=mknode(+,p1,p6);P8:=mkleaf(id,entry-b);P9:=mkleaf(id,entry-c);P10:=mknode(-,p8,p9);p11:=mkleaf(id,entry-d);P12:=mknode(*,
13、p10,p11);P13:=mknode(+,p7,p12)修改建立表达式语法树的语法制导定义,产生表达式的DAG在构造结点前检查现有结点,若存在相同结点则返回该结点的指针表达式a+a*(b-c)+(b-c)*d的语法树和DAG226.1.16.1.1图图表示法表示法idtoentryforaidtoentryforbidtoentryforc*idtoentryford12345678910111213波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示法。这种表示法把运算量(操作数)写在前面,把运算符写在后面,因而又称后缀表示法。例如,把a+b写成ab+,把a*(b+c)写成ab
14、c+*。一般,若e1,e2为任意的后缀表达式,为任意双目运算符,则用作用于e1和e2所代表的结果用后缀式e1e2表示。推而广之,为k目运算符,则作用于e1e2ek的结果用e1e2ek来表示。236.1.26.1.2逆波兰式表示法逆波兰式表示法中缀式:a*d+b*c+e24由抽象语法树生成后缀式由抽象语法树生成后缀式+*+ad*ebc抽象语法树抽象语法树后根遍历生成后缀式:ad*bc*+e+25由语法制导定义生成后缀式由语法制导定义生成后缀式产生式产生式语义规则语义规则Sid:=EPrint(id.name|E.code|“:=”)EE1+E2E.code:=E1.code|E2.code|“+
15、”EE1*E2E.code:=E1.code|E2.code|“*”E-E1E.code:=E1.code|“-”E(E1)E.code:=E1.codeEidE.code:=id.nameEnumE.code:=num.val;属性属性code表示生成的代码表示生成的代码后缀表示法的优点:易于计算机处理表达式。常用的算法:使用一个栈,自左至右扫描算术表达式(后缀表示):扫描到运算对象,就把它推进栈;扫描到运算符:p若该运算符是二目的,则对栈顶部的两个运算对象实施该运算,并将运算结果代替这两个运算对象而进栈;p若是一目运算符,则对栈顶元素执行该运算,并以运算结果代替该元素进栈。最后的结果留在栈
16、顶26后缀式的求值后缀式的求值ab+c*的求值(a=1,b=3,c=5)27后缀式的求值后缀式的求值13+5*13+41+3=45*4*5=2020计算完毕,结果为计算完毕,结果为20一般形式x:yopz一般含三个地址(名字、常数、临时变量):两个操作分量和一个结果的抽象地址为方便起见,通常用变量名代替抽象地址如,源语言表达式x+y*z可以被翻译为:t1:=y*zt2:=x+t1其中t1和t2是编译时产生的临时变量286.1.3 6.1.3 三地址代码三地址代码三地址代码与语法树、DAG的关系三地址代码是语法树或DAG的线性表示表达式a+a*(b-c)+(b-c)*d的语法树和DAG对应的三地
17、址代码296.1.3 6.1.3 三地址代码三地址代码t1:=bct2:=a*t1t3:=a+t2t4:=bct5:=t4*dt6:=t3+t5根据语法树根据语法树t1:=bct2:=a*t1t3:=a+t2t4:=t2*dt5:=t3+t4根据根据DAGDAG三地址代码的类型(1)赋值语句x:yopz,op为二目算术算符或逻辑算符(2)赋值语句x:opy,op为一目算符,如一目减uminus、逻辑非not、移位算符及转换算符(3)无条件转移语句gotoL(4)条件转移语句ifxrelopygotoL,关系运算符号relop(,=,=等等)(5)复制语句x:y306.1.3 6.1.3 三地址
18、代码三地址代码三地址代码的类型(6)过程调用语句paramx和callp,n。过程调用语句p(x1,x2,xn)产生如下三地址代码:paramx1paramx2paramxncallp,n过程返回语句returny316.1.3 6.1.3 三地址代码三地址代码三地址代码的类型(7)索引赋值语句:x:=yixi:=y(8)地址和指针赋值语句x:=&yx:=*y*x:=y在设计中间代码形式时,选择多少种算符需要平衡326.1.3 6.1.3 三地址代码三地址代码例子:doi:=i+1;while(aiv);的三地址翻译336.1.3 6.1.3 三地址代码三地址代码L:t1=i+1i=t1t2=
19、i*8t3=at2if(t3v)gotoL100:t1=i+1101:i=t1102:t2=i*8103:t3=at2104:if(t3v)goto100用标签形式用标签形式用标号形式用标号形式假设数组假设数组a中每个元素占用存储单元为中每个元素占用存储单元为8p语法制导翻译生成三地址代码定义几个属性:(1)E.place表示存放E值的名字。(2)E.code表示对E求值的三地址语句序列。(3)newtemp是个函数,对它的调用将产生一个新的临时变量。346.1.3 6.1.3 三地址代码三地址代码35语法制导翻译生成三地址代码语法制导翻译生成三地址代码 产生式产生式语义规则语义规则Sid:=
20、ES.code:=E.code|gen(id.place:=E.place)EE1+E2E.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)EE1E.place:=newtemp;E.code:=E1.code|gen(E.place:=uminusE1.place)E(E1)E.place:=E1.place;E.code:=E1.codeEid
21、E.place:=id.place;E.code:=三地址语句序列是语法树的线性表示,用临时变量代替语法树中的结点。实际实现中,三地址语句序列往往是被存放到一个输出文件中,而不是将三地址语句序列置入code属性之中36语法制导翻译生成三地址代码语法制导翻译生成三地址代码 三地址代码的具体实现1.四元式op,arg1,arg2,result2.三元式op,arg1,arg23.间接三元式间接码表+三元式表376.1.3 6.1.3 三地址代码三地址代码三地址代码的具体实现四元式有四个字段,分别称为op,arg1,arg2,result。字段op包含一个运算符的内部编码,如对于三地址指令x=y+z
22、的相应四元式中,op字段存放+,arg1中为y,arg2中为z,result中为x。对于形如x=opy的单目运算符指令和赋值指令x=y,不使用arg2。像param这样的运算既不使用arg2也不使用result。条件或非条件转移指令将目标标号放入result字段386.1.3 6.1.3 三地址代码三地址代码对于语句a:=b*-c+b*-c的三种表示方法39三地址代码的具体三地址代码的具体实现实现t1=uminusct2=b*t1t3=uminusct4=b*t3t5=t2+t4a=t5三地址代码三地址代码oparg1arg2result0uminusct11*bt1t22uminusct33
23、*bt3t44+t2t4t55=t5a四元式四元式对于语句a:=b*-c+b*-c的三种表示方法40三地址代码的具体三地址代码的具体实现实现oparg1arg2 result0uminusct11*bt1t22uminusct33*bt3t44+t2t4t55=t5a四元式四元式oparg1arg20uminusc1*b(0)2uminusc3*b(2)4+(1)(3)5assigna(4)三元式三元式三元式中使用指向三元式语句的指针指向三元式语句的指针。对于语句a:=b*-c+b*-c的三种表示方法41三地址代码的具体三地址代码的具体实现实现oparg1arg20uminusc1*b(0)2
24、uminusc3*b(2)4+(1)(3)5assigna(4)间接三元式表示statement1001(0)1002(1)1003(2)1004(3)1005(4)1006(5)三地址代码三种实现形式的比较代码优化时,经常因调整计算次序而要移动三地址语句四元式调整顺序方便,但引入的临时变量多,需存储空间大三元式需存储空间最小,但调整顺序不便间接三元式优化方便,在有公共子表达式时,需存储空间比四元式小中间代码优化处理时,四元式比三元式方便的多,间接三元式与四元式同样方便,两种实现方式需要的存储空间大体相同。426.1.3 6.1.3 三地址代码三地址代码例:a+b*(c-d)+e/(c-d)n
25、求:1.后缀式2.四元式3.三元式4.间接三元式43中间语言练习中间语言练习例:a+b*(c-d)+e/(c-d)n后缀式abcd-*+ecdn/+三地址代码t1=cdt2=b*t1t3=a+t2t4=cdt5=t4nt6=e/t5t7=t3+t644中间语言练习中间语言练习例:a+b*(c-d)+e/(c-d)n四元式45中间语言练习中间语言练习oparg1arg2 result0-cdt11*bt1t22+at2t33-cdt44 t4nt55/et5a6+t3t6t7t1=cdt2=b*t1t3=a+t2t4=cdt5=t4nt6=e/t5t7=t3+t6例:a+b*(c-d)+e/(c
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六章 中间代码生成 第六 中间 代码 生成
限制150内