语法制导翻译和中间代码生成详解演示文稿

语法制导翻译和中间代码生成详解演示文稿第一页，共二十五页。（优选）语法制导翻译和中间代码生成第二页，共二十五页。语法制导翻译和中间代码生成文法的语法制导定义(语义规则)和翻译方案--语法制导定义-->语义分析做什么

--翻译方案-->中间代码生成怎么做第三页，共二十五页。中间语言高级的：接近源语言。语法树，适合完成静态类型检查。低级的：接近目标语言。适合完成依赖于机器的任务。常用的中间语言：后缀式：逆波兰表示图表示：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.pl