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

语法制导翻译和中间代码生成使用中间语言的好处：复杂性界于源语言和目标语言之间便于进行与机器无关的代码优化工作易于移植使编译程序的结构在逻辑上更为简单明确源语言程序目标语言程序中间语言程序CompilerFrontEndCompilerBackEnd---->编译程序---->

输入

输出

第2页,共27页，2024年2月25日，星期天语法制导翻译和中间代码生成文法的语法制导定义(语义规则)和翻译方案--语法制导定义-->语义分析

做什么

--翻译方案-->中间代码生成怎么做第3页,共27页，2024年2月25日，星期天中间语言高级的：接近源语言。语法树，适合完成静态类型检查。低级的：接近目标语言。适合完成依赖于机器的任务。常用的中间语言：后缀式：逆波兰表示图表示：DAG、抽象语法树三地址代码三元式、四元式中间代码的选择可以是一种实际的语言也可以是编译各阶段共享的内部数据结构7.1中间语言第4页,共27页，2024年2月25日，星期天P200后缀式定义写出3+4*5的后缀式写出b*(-c)+b*(-c)的后缀式后缀式表示：算术表达式、赋值语句、控制语句后缀式的计算用一个栈实现一般的计算过程是：自左至右扫描后缀式，每碰到运算量（操作量）就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。7.1.1后缀式

第5页,共27页，2024年2月25日，星期天7.1.2图表示法图表示法DAG-无循环有向图抽象语法树

第6页,共27页，2024年2月25日，星期天7.1.2图表示法无循环有向图(简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点第7页,共27页，2024年2月25日，星期天7.1.3三地址代码三地址代码x=yopz三地址代码可以看成是抽象语法树或DAG的一种线性表示树与其他中间代码的关系第8页,共27页，2024年2月25日，星期天

a:=b*(-c)+b*(-c)的图表示法

请画出语法树和DAG

:=a+*b-cDAG:=a+*b-c抽象语法树*b-c第9页,共27页，2024年2月25日，星期天抽象语法树对应的代码：t1=-c t2=b*t1

t3=-c t4=b*t3 t5=t2+t4

a=t5assigna+*buminusc抽象语法树*buminusc第10页,共27页，2024年2月25日，星期天DAG对应的代码：

t1=-ct2=b*t1t5=t2+t2a=t5assigna+*buminuscDAG抽象语法树对应的代码：t1=-c t2=b*t1

t3=-c t4=b*t3 t5=t2+t4

a=t5第11页,共27页，2024年2月25日，星期天作业：P2217.1第12页,共27页，2024年2月25日，星期天7.3中间代码生成

----赋值语句翻译成三地址代码

产生三地址代码赋值语句翻译方案填查符号表词法分析发布出错信息第13页,共27页，2024年2月25日，星期天语法制导翻译第14页,共27页，2024年2月25日，星期天三地址代码的形式：

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)分别是它们在三元式表中的位置。

■

第15页,共27页，2024年2月25日，星期天三地址代码的形式：

三元式、四元式、间接三元式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)第16页,共27页，2024年2月25日，星期天属性文法是在上下文无关文法的基础上，为每个文法符号配备若干相关的“值”，称为属性，属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程。对文法的每个产生式配备的一组属性的计算规则，叫语义规则，语义分析和中间代码的产生就是根据该规则进行的，在自上而下或自下而上语法分析过程中，在适当的时候进行属性的计算，或其它语义动作（如查填符号表、产生中间代码、发布出错信息）就可进行语法制导翻译得到中间代码，这就是语法制导翻译的基本思想。语法制导翻译和中间代码产生第17页,共27页，2024年2月25日，星期天产生赋值语句抽象语法树的属性文法产生式 语义规则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)第18页,共27页，2024年2月25日，星期天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()}

分别生成三元式代码、四元式代码第19页,共27页，2024年2月25日，星期天.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的三元式三元式序列：第20页,共27页，2024年2月25日，星期天语义规则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)第21页,共27页，2024年2月25日，星期天属性文法是在上下文无关文法的基础上，为每个文法符号配备若干相关的“值”，称为属性，属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程。对文法的每个产生式配备的一组属性的计算规则，叫语义规则，语义分析和中间代码的产生就是根据该规则进行的，在自上而下或自下而上语法分析过程中，在适当的时候进行属性的计算，或其它语义动作（如查填符号表、产生中间代码、发布出错信息）就可进行语法制导翻译得到中间代码，这就是语法制导翻译的基本思想。语法制导翻译和中间代码产生第22页,共27页，2024年2月25日，星期天LR分析翻译方案的设计

LR分析中的语法制导翻译实质上是对LR语法分析的扩充：<1>扩充LR分析器的功能：当执行归约产生式的动作时，也执行产生式对应的语义动作。<2>扩充分析栈：增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值。例：E→E1+E2

val[top]:=val[top]+val[top+2];

对于表达式：5+3当归约为左部E时，同时也得到了值8。第23页,共27页，2024年2月25日，星期天产生式算术表达式（语义规则）翻译方案-三地址码-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地址指令。第24页,共27页，2024年2月25日，星期天步骤栈内容当前输入移进-规约动作翻译动作（语义规则具体化）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第25页,共27页，2024年2月25日，星期天步骤栈内容当前输入移进-规约动作翻译动作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#移进：s5