语法制导翻译和中间代码生成.ppt

《语法制导翻译和中间代码生成.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码生成.ppt（27页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、语法制导翻译和中间代码生成现在学习的是第1页，共27页n使用中间语言的好处：使用中间语言的好处：复杂性界于源语言和目标语言之间复杂性界于源语言和目标语言之间便于进行与机器无关的代码优化工作便于进行与机器无关的代码优化工作 易于移植易于移植使编译程序的结构在逻辑上更为简单明确使编译程序的结构在逻辑上更为简单明确 源语言源语言程序程序目标语目标语言程序言程序中间语中间语言程序言程序CompilerFront EndCompilerBack End -编译程序编译程序-输入输入 输出输出 现在学习的是第2页，共27页语法制导翻译和中间代码生成语法制导翻译和中间代码生成n文法的语法制导定义文法的语法制

2、导定义(语义规则语义规则)和翻译方案和翻译方案 -语法制导定义语法制导定义-语义分析语义分析做什么做什么 -翻翻 译方案译方案-中间代码生成中间代码生成怎么怎么做做现在学习的是第3页，共27页n中间语言中间语言高级的：接近源语言。语法树，适合完成静态类型检查。高级的：接近源语言。语法树，适合完成静态类型检查。低级的：接近目标语言。适合完成依赖于机器的任务。低级的：接近目标语言。适合完成依赖于机器的任务。n常用的中间语言：常用的中间语言：后缀式：逆波兰表示后缀式：逆波兰表示图表示：图表示：DAG、抽象语法树、抽象语法树三地址代码三地址代码n三元式、四元式三元式、四元式n中间代码的选择中间代码的选

3、择可以是一种实际的语言可以是一种实际的语言也可以是编译各阶段共享的内部数据结构也可以是编译各阶段共享的内部数据结构7.1 中间语言中间语言 现在学习的是第4页，共27页nP200后缀式定义后缀式定义写出写出3+4*5的后缀式的后缀式 写出写出b*(-c)+b*(-c)的后缀式的后缀式后缀式表示：后缀式表示：算术表达式、赋值语句、控制语句算术表达式、赋值语句、控制语句n后缀式的计算后缀式的计算用一个栈实现用一个栈实现一一般般的的计计算算过过程程是是：自自左左至至右右扫扫描描后后缀缀式式，每每碰碰到到运运算算量量（操操作作量量）就就把把它它推推进进栈栈。每每碰碰到到k目目运运算算符符就就把把它它作

4、作用用于栈顶的于栈顶的k个项，并用运算结果代替这个项，并用运算结果代替这k个项。个项。7.1.1 后缀式后缀式 现在学习的是第5页，共27页7.1.2 图表示法图表示法n图表示法图表示法DAG-无循环有向图无循环有向图抽象语法树抽象语法树 现在学习的是第6页，共27页7.1.2 图表示法图表示法n无循环有向图无循环有向图(简称简称DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAG中都有一个中都有一个结点结点一个一个内部结点内部结点代表一个代表一个操作符操作符，它的孩子代表，它的孩子代表操作数操作数在一个在一个DAG中代表公共子表达式的结点具有多中代表公共子表达式的结点具有多个父

5、结点个父结点现在学习的是第7页，共27页7.1.3 三地址代码三地址代码 n三地址代码三地址代码x=y op z n三地址代码可以看成是抽象语法树或三地址代码可以看成是抽象语法树或DAG的一种线性表示的一种线性表示 树与其他中间代码树与其他中间代码的关系的关系现在学习的是第8页，共27页 a:=b*(-c)+b*(-c)的图表示法的图表示法 请画出语法树和请画出语法树和DAG:=a+*b-cDAG:=a+*b-c抽象语法树抽象语法树*b-c现在学习的是第9页，共27页抽象语法树抽象语法树对应的代码：对应的代码：t1=-c t2=b*t1t3=-c t4=b*t3 t5=t2+t4 a=t5as

6、signa+*buminusc抽象语法树抽象语法树*buminusc现在学习的是第10页，共27页DAG对应的代码：对应的代码：t1=-ct2=b*t1t5=t2+t2a=t5assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代码：t1=-c t2=b*t1t3=-c t4=b*t3 t5=t2+t4 a=t5现在学习的是第11页，共27页作业：作业：P221 7.1现在学习的是第12页，共27页7.3 中间代码生成中间代码生成 -赋值语句翻译成三地址代码赋值语句翻译成三地址代码 产生产生三地址代码三地址代码赋值语句赋值语句 翻译方案翻译方案填查填查符号表符号表词法

7、词法分析分析发布发布出错信息出错信息现在学习的是第13页，共27页 语法制导翻译语法制导翻译现在学习的是第14页，共27页三地址代码的形式：三地址代码的形式：1.三元式、三元式、2.四元式、四元式、3.间接三元式间接三元式1、三元式三元式 三元式：三元式：(i)(op,arg1,arg2)三地址码：三地址码：(i):=arg1 op arg2例例4.5 表达式表达式x:=a+b*c 的三元式：的三元式：(1)(*，b，c)(2)(+，a，(1)(3)(:=，x，(2)标识符标识符a，b，c，x分别表示它们的存储位置，分别表示它们的存储位置，序号序号(1)、(2)、(3)分别是它们分别是它们在三

8、元式表中的位置。在三元式表中的位置。现在学习的是第15页，共27页三地址代码的形式：三地址代码的形式：三元式、四元式、间接三元式三元式、四元式、间接三元式2、四元式四元式 四元式：四元式：(i)(op,arg1,arg2，result)四地址码：四地址码：result:=arg1 op arg2例例4.5 表达式表达式x:=a+b*c 的四元式：的四元式：(1)(*，b，c,T1)(2)(+，a，T1,T2)(3)(:=，x，T2)现在学习的是第16页，共27页属性文法属性文法是在上下文无关文法的基础上，为每个文法符是在上下文无关文法的基础上，为每个文法符号配备若干相关的号配备若干相关的“值值

9、”，称为属性，属性与变量一样，称为属性，属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的可以进行计算和传递，属性加工的过程即是语义处理的过程。对文法的每个产生式配备的一组属性的计算规则，过程。对文法的每个产生式配备的一组属性的计算规则，叫叫语义规则语义规则，语义分析和中间代码的产生就是根据该，语义分析和中间代码的产生就是根据该规则进行的，在自上而下或自下而上语法分析过程中，规则进行的，在自上而下或自下而上语法分析过程中，在适当的时候进行属性的计算，或其它语义动作（如在适当的时候进行属性的计算，或其它语义动作（如查填符号表查填符号表、产生、产生中间代码中间代码、发布出错信息）就可进

10、、发布出错信息）就可进行语法制导翻译得到中间代码，这就是行语法制导翻译得到中间代码，这就是语法制导翻译语法制导翻译的的基本思想。基本思想。语法制导翻译和中间代码产生语法制导翻译和中间代码产生现在学习的是第17页，共27页 产生赋值语句抽象语法树的属性文法产生赋值语句抽象语法树的属性文法 产产 生生 式式语义规则语义规则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.

11、nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptrEid E.nptr:=mkleaf(id,id.place)现在学习的是第18页，共27页LR分析翻译方案分析翻译方案产生式与产生式与翻译方案翻译方案A(1)Aid:=E(2)EE1+E2(3)EE1*E2(4)E(E1)(5)E-E1(6)EidA.code:=trip(:=，entry(id.name)，E.code)E.code:=trip(+，E1.code，E2.code)E.code:=trip(*，E1.code，E2.code)E.code:=E1.codeE.code:=trip

12、(，E1.code，)E.code:=entry(id.name)产生式与产生式与翻译方案翻译方案B (1)Aid:=E(2)EE1+E2(3)EE1*E2(4)E(E1)(5)E-E1(6)EidA.code:=newtemp;emit(:=，entry(id.name),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.codeE.code:=newtemp;emit(,E1.code,E.code)E.co

13、de:=entry(id.name)分别生成三元式代码、分别生成三元式代码、四元式代码四元式代码现在学习的是第19页，共27页.code=a.code=a.code=b.code=b.code=c.code=c.code=(1)(*,b,c).code=(1)(*,b,c).code=(3)(:=,x,(2).code=(3)(:=,x,(2).code=(2)(+,a,(1).code=(2)(+,a,(1)(1)(*,b,c)(1)(*,b,c)(2)(+,a,(1)(2)(+,a,(1)(3)(:=,x,(2)(3)(:=,x,(2)产生式与产生式与语义规则语义规则A A：(1)Aid:

14、=E(2)EE1+E2(3)EE1*E2(4)E(E1)(5)E-E1(6)EidA.code:=trip(:=，entry(id.name)，E.code)E.code:=trip(+，E1.code，E2.code)E.code:=trip(*，E1.code，E2.code)E.code:=E1.codeE.code:=trip(，E1.code，)E.code:=entry(id.name)例例 生成生成x:=a+b*c的三元式的三元式三元式序列：三元式序列：现在学习的是第20页，共27页语义规则语义规则B B(1)Aid:=E(2)EE1+E2(3)EE1*E2(4)E(E1)(5)

15、E-E1(6)EidA.code:=newtemp;emit(:=，entry(id.name),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.codeE.code:=newtemp;emit(,E1.code,E.code)E.code:=entry(id.name)例例 生成生成x:=a+b*c的四元式的四元式.code=a.code=a.code=b.code=b.code=c.code=c.code=

16、(1).code=(1)(*,b,c)(*,b,c).code=(3).code=(3)(:=,x,(2)(:=,x,(2).code=(2).code=(2)(+,a,(1)(+,a,(1)(1)(*,b,c)(1)(*,b,c)(2)(+,a,(1)(2)(+,a,(1)(3)(:=,x,(2)(3)(:=,x,(2)三元式序列：三元式序列：四元式序列：四元式序列：(*,b,c(*,b,c，T1)T1)(+,a,T1,T2)(+,a,T1,T2)(:=,x,T2,T3)(:=,x,T2,T3)现在学习的是第21页，共27页属性文法属性文法是在上下文无关文法的基础上，为每个文法符是在上下文无

17、关文法的基础上，为每个文法符号配备若干相关的号配备若干相关的“值值”，称为属性，属性与变量一样，称为属性，属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的可以进行计算和传递，属性加工的过程即是语义处理的过程。对文法的每个产生式配备的一组属性的计算规则，过程。对文法的每个产生式配备的一组属性的计算规则，叫叫语义规则语义规则，语义分析和中间代码的产生就是根据，语义分析和中间代码的产生就是根据该规则进行的，在自上而下或自下而上语法分析过该规则进行的，在自上而下或自下而上语法分析过程中，在适当的时候进行属性的计算，或其它语义程中，在适当的时候进行属性的计算，或其它语义动作（如查填符号表动

18、作（如查填符号表、产生、产生中间代码中间代码、发布出错信、发布出错信息）就可进行语法制导翻译得到中间代码，这就是息）就可进行语法制导翻译得到中间代码，这就是语法制导翻译语法制导翻译的基本思想。的基本思想。语法制导翻译和中间代码产生语法制导翻译和中间代码产生现在学习的是第22页，共27页LR分析翻译方案的设计 LRLR分析中的语法制导翻译实质上是对分析中的语法制导翻译实质上是对LRLR语法分析的扩充：语法分析的扩充：扩扩充充LRLR分分析析器器的的功功能能：当当执执行行归归约约产产生生式式的的动动作作时时，也也执执行行产产生生式式对对应应的语义动作。的语义动作。扩充分析栈：扩充分析栈：增加一个与

19、分析栈并列的语义栈，用于存放分析栈中文法增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值。符号所对应的属性值。例：例：EE1+E2EE1+E2 valtop:=valtop+valtop+2;对于表达式：对于表达式：5+35+3当归约为左部当归约为左部E E时，时，同时也得到了值同时也得到了值8 8。现在学习的是第23页，共27页产生式产生式 算术表达式（算术表达式（语义规则）语义规则）翻译方案翻译方案-三地址码三地址码-P208-P208(1)Sid:=E(1)Sid:=E(2)EE1+E2(2)EE1+E2(3)EE1*E2(3)EE1*E2(4)E(E1)(4)E(E

20、1)(5)E-E1(5)E-E1(6)Eid(6)Eidp=lookup(id.lexeme);if(p!-nil)emit(p,=，E.place)else errorE.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

21、，arg2)：生成一个生成一个3地址指令。地址指令。现在学习的是第24页，共27页步骤栈内容当前输入移进-规约动作翻译动作（语义规则具体化）A1#0i1*i2+i3#移进：s52#0i15*i2+i3#规约：r6（Fi）F.place=p or F.place=entry(i.name)3#0F3*i2+i3#规约：r4（TF）T.place=F.place4#0T2*i2+i3#移进：s75#0T2*7i2+i3#移进：s56#0T2*7i25+i3#规约：r6（Fi）F.place=p or F.place=entry(i.name)7#0T2*7F10+i3#规约r3（TT*F）T.pl

22、ace=newtemp(),emit(T.place,=，T.place,*，F.place8#0T2+i3#规约：r2（ET）E.place:=T.place9#0E1+i3#移进：s610#0E1+6i3#移进：s511#0E1+6 i35#规约：r6（Fi）F.place=p or F.place=entry(i.name)12#0E1+6F3#规约：r4（TF）T.place=F.place13#0E1+6T9#规约：r1（EE+T）E.place=newtemp();emit(E.place,=,E.place,+，T.place)14#0E1#acc（1）t1=i1 翻译动作翻译动

23、作（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现在学习的是第25页，共27页步骤栈内容当前输入移进-规约动作翻译动作B1#0i1*i2+i3#移进：s52#0i15*i2+i3#规约：r6（Fi）F.code:=entry(i.name)3#0F3*i2+i3#规约：r4（TF）T.code:=F.code4

24、#0T2*i2+i3#移进：s75#0T2*7i2+i3#移进：s56#0T2*7i25+i3#规约：r6（Fi）F.code:=entry(i.name)7#0T2*7F10+i3#规约：r3（TT*F）T.code:=newtemp,emit(*,T.code,F.code,T.code)8#0T2+i3#规约：r2（ET）E.code:=T.code9#0E1+i3#移进：s610#0E1+6i3#移进：s511#0E1+6 i35#规约：r6（Fi）F.code:=entry(i.name)12#0E1+6F3#规约：r4（TF）T.code:=F.code13#0E1+6T9#规约：

25、r1（EE+T）E.code:=newtemp,emit(+,E.code,T.code,E.code)14#0E1#acc产生中间代码产生中间代码 四元式序列四元式序列（1）（）（*，i1，i2，T1）（2）（）（+，i3，T1，T2）带带有有变变量的表达式量的表达式 id1*id2+id3根据此表中的翻根据此表中的翻译动译动作可得到？作可得到？不同的翻译方案，可以得到不同的结果不同的翻译方案，可以得到不同的结果现在学习的是第26页，共27页算术表达式算术表达式及赋值语句及赋值语句声明语句声明语句布尔表达式布尔表达式控制语句控制语句过程调用的处理过程调用的处理编译器编译器 动作（语义）规则：

26、动作（语义）规则：A.code:=newtemp;emit(:=，entry(id.name),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:=entry(id.name)(1)Aid:=E(2)EE1+E2(3)EE1*E2(4)EidEE or E|E andE|E|(E)|i rop i|i符号表的创建和填写，符号表的创建和填写，为变量名、过程名建立符号表条目，并分配内存为变量名、过程名建立符号表条目，并分配内存；允许嵌套的语言为每个过程创建一个新表允许嵌套的语言为每个过程创建一个新表P204、P208现在学习的是第27页，共27页