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

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

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

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

4、项，并用运算结果代替这这k个项。个项。7.1.1 后缀式后缀式 7.1.2 图表示法图表示法n图表示法图表示法DAG-无循环有向图无循环有向图抽象语法树抽象语法树 7.1.2 图表示法图表示法n无循环有向图无循环有向图(简称简称DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAG中都有一个中都有一个结点结点一个一个内部结点内部结点代表一个代表一个操作符操作符，它的孩子代表，它的孩子代表操作数操作数在一个在一个DAG中代表公共子表达式的结点具有多中代表公共子表达式的结点具有多个父结点个父结点7.1.3 三地址代码三地址代码 n三地址代码三地址代码x =y op z n三地址代码可以

5、看成是抽象语法树或三地址代码可以看成是抽象语法树或DAG的一种线性表示的一种线性表示 树与其他中间代树与其他中间代码的关系码的关系 a:=b*(-c)+b*(-c)的图表示法的图表示法 请画出语法树和请画出语法树和DAG :=a+*b-cDAG:=a+*b-c抽象语法树抽象语法树*b-c抽象语法树抽象语法树对应的代码：对应的代码： t1=-c t2=b*t1t3=-c t4=b*t3 t5=t2+t4 a=t5assigna+*buminusc抽象语法树抽象语法树*buminuscDAG对应的代码：对应的代码： t1=-ct2=b*t1t5=t2+t2a=t5assigna+*buminusc

6、DAG抽象语法树抽象语法树对应的代码：对应的代码： t1=-c t2=b*t1t3=-c t4=b*t3 t5=t2+t4 a=t5作业：作业：P221 7.17.3 中间代码生成中间代码生成 -赋值语句翻译成三地址代码赋值语句翻译成三地址代码 产生产生三地址代码三地址代码赋值语句赋值语句 翻译方案翻译方案填查填查符号表符号表词法词法分析分析发布发布出错信息出错信息 语法制导翻译语法制导翻译三地址代码的形式：三地址代码的形式： 1.三元式、三元式、2.四元式、四元式、3.间接三元式间接三元式1、 三元式三元式 三元式：三元式： (i) (op, arg1, arg2) 三地址码：三地址码： (

7、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)分别是它们分别是它们在三元式表中的位置。在三元式表中的位置。 三地址代码的形式：三地址代码的形式： 三元式、四元式、间接三元式三元式、四元式、间接三元式2、 四元式四元式 四元式：四元式： (i) (op, arg1, arg2，result) 四地址码：四地址码： result := arg1 op arg2例

8、例4.5 表达式表达式x:=a+b*c 的四元式：的四元式：(1) (*， b， c , T1)(2) (+， a，T1, T2)(3) (:=，x，T2)属性文法属性文法是在上下文无关文法的基础上，为每个是在上下文无关文法的基础上，为每个文法符号配备若干相关的文法符号配备若干相关的“值值”，称为属性，属，称为属性，属性与变量一样可以进行计算和传递，属性加工的性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程。对文法的每个产生式过程即是语义处理的过程。对文法的每个产生式配备的一组属性的计算规则，叫配备的一组属性的计算规则，叫语义规则语义规则，语义，语义分析和中间代码的产生就是根据

9、该规则进行的，分析和中间代码的产生就是根据该规则进行的，在自上而下或自下而上语法分析过程中，在适当在自上而下或自下而上语法分析过程中，在适当的时候进行属性的计算，或其它语义动作（如查的时候进行属性的计算，或其它语义动作（如查填符号表填符号表 、产生、产生中间代码中间代码、发布出错信息）就可、发布出错信息）就可进行语法制导翻译得到中间代码，这就是进行语法制导翻译得到中间代码，这就是语法制语法制导翻译导翻译的基本思想。的基本思想。 语法制导翻译和中间代码产生语法制导翻译和中间代码产生 产生赋值语句抽象语法树的属性文法产生赋值语句抽象语法树的属性文法 产产 生生 式式语义规则语义规则Sid:=ES.

10、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.nptr:=mknode(uminus,E1.nptr)E (E1)E.nptr:=E1.nptrEid E.nptr:=mkleaf(id,id.place)LR分析翻译方案分析翻译方案产生式与产生式与翻译方案翻译方案A(1) Aid:=E(2) EE1+E2(3) EE1*E2(4) E(E1)(5) E-E1(6) EidA.c

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

12、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() 分别生成三元式分别生成三元式代代码码、四元式代码、四元式代码Ax := E5E1 + E4aE2 * E3bc.code=a.code=a .code=b.code=b .code=c .code=c .code=(1)(.code=(1)(* *,b,c),b,c) .code=(3)

13、(:=,x,(2) .code=(3)(:=,x,(2) .code=(2)(+,a,(1) .code=(2)(+,a,(1) (1) (1) (* *, b, c ), b, c ) (2) (+, a,(1) (2) (+, a,(1) (3) (:=,x,(2) (3) (:=,x,(2)产生式与产生式与语义规则语义规则A A：(1) Aid:=E(2) EE1+E2(3) EE1*E2(4) E(E1)(5) E-E1(6) EidA.code:=trip(:=，entry()，E.code)E.code:=trip(+，E1.code，E2.code)E.code:=

14、trip(*，E1.code，E2.code)E.code:=E1.codeE.code:=trip(，E1.code， )E.code:=entry() 例例 生成生成x:=a+b*c的三元式的三元式三元式序列：三元式序列：语义规则语义规则B B(1)Aid:=E (2)EE1+E2(3)EE1*E2(4)E(E1)(5)E-E1(6)EidA.code:=newtemp; emit(:=，entry() , E.code, A.code)E.code:=newtemp; emit(+，E1.code,E2.code,E.code)E.code:=newtemp;

15、 emit(*，E1.code,E2.code,E.code)E.code:=E1.codeE.code:=newtemp; emit(,E1.code, , E.code)E.code:=entry() 例例 生成生成x:=a+b*c的四元式的四元式Ax := E5E1 + E4aE2 * E3bc.code=a.code=a .code=b.code=b .code=c .code=c .code=(1).code=(1)( (* *,b,c),b,c) .code=(3).code=(3)(:=,x,(2) (:=,x,(2) .code=(2).code=(2)(+,a,

16、(1) (+,a,(1) (1) (1) (* *, b, c ), 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)属性文法属性文法是在上下文无关文法的基础上，为每个是在上下文无关文法的基础上，为每个文法符号配备若干相关的文法符号配备若干相关的“值值”，称为属性，属，称为属性，属性与变量一样可以进

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

18、，这就是进行语法制导翻译得到中间代码，这就是语法制语法制导翻译导翻译的基本思想。的基本思想。 语法制导翻译和中间代码产生语法制导翻译和中间代码产生LR分析翻译方案的设计 LRLR分析中的语法制导翻译实质上是对分析中的语法制导翻译实质上是对LRLR语法分析的扩充：语法分析的扩充： 扩充扩充LRLR分析器的功能：分析器的功能：当执行归约产生式的动作时，也执行产当执行归约产生式的动作时，也执行产生式对应的语义动作。生式对应的语义动作。 扩充分析栈：扩充分析栈：增加一个与分析栈并列的语义栈，用于存放分析增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值。栈中文法符号所对应的属性值。

19、例：例： EE1+E2EE1+E2 valtop:=valtop+valtop+2; 驱动器输入记号流输出ip移进-归约分析表分析栈top 3 E ? + 5 Etop对于表达式：对于表达式： 5+35+3top8 E当归约为左部当归约为左部E E时，时，同时也得到了值同时也得到了值8 8。产生式产生式 算术表达式（算术表达式（语义规则）语义规则）翻译方案翻译方案- -三地址码三地址码-P208-P208(1)Sid:=E (1)Sid:=E (2)EE1+E2(2)EE1+E2(3)EE1(3)EE1* *E2E2(4)E(E1)(4)E(E1)(5)E-E1(5)E-E1(6)Eid(6)

20、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，o

21、p， arg2)： 生成一个生成一个3地址指令。地址指令。步骤步骤栈内容栈内容当前输入当前输入移进移进- -规约动作规约动作翻译动作（语义规则具体化）翻译动作（语义规则具体化）A A1#0i1*i2+i3#移进：移进：s52#0i15*i2+i3#规约：规约：r6（Fi）F.place=p or F.place=entry()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=

22、entry()7#0T2*7F10+i3#规约规约r3（TT*F）T.place=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()12#0E1+6F3#规约：规约：r4（TF）T. place= F. place13#0E1+6T9#规约：规约：r1（EE+T）E.pl

23、ace=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步骤步骤栈内容栈内容当前输入当前输入移进移进- -规约动作规约动作翻译动作翻译动作B B1#0i1

24、*i2+i3#移进：移进：s52#0i15*i2+i3#规约：规约：r6（Fi）F.code:=entry()3#0F3*i2+i3#规约：规约：r4（TF）T.code:= F.code4#0T2*i2+i3#移进：移进：s75#0T2*7i2+i3#移进：移进：s56#0T2*7i25+i3#规约：规约：r6（Fi）F.code:=entry()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

25、#0E1+i3#移进：移进：s610#0E1+6i3#移进：移进：s511#0E1+6 i35#规约：规约：r6（Fi）F.code:=entry()12#0E1+6F3#规约：规约：r4（TF）T.code:= F.code13#0E1+6T9#规约：规约：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、？根据此表中的翻译动作可得到？不同的翻译方案，可以得到不同的结果不同的翻译方案，可以得到不同的结果算术表达式算术表达式及赋值语句及赋值语句声明语句声明语句布尔表达式布尔表达式控制语句控制语句过程调用的处理过程调用的处理编译器编译器 动作（语义）规则：动作（语义）规则：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:=entry(i

27、) (1)Aid:=E (2)EE1+E2(3)EE1*E2(4)EidEE or E | E andE | E | (E) | i rop i | i符号表的创建和填写，符号表的创建和填写，为变量名、过程名建立符号表条目，并分配内存为变量名、过程名建立符号表条目，并分配内存；允许嵌套的语言为每个过程创建一个新表允许嵌套的语言为每个过程创建一个新表P204、P208Pascal源程序语句：源程序语句： var x, y, z : real; x := y + z * 60;var id1, id2, id3 : real; id1 := id2+id3*60; :=:, real id1 + , id3 id2 * id1 i