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

语法制导翻译和中间代码生成语法制导翻译和中间代码生成文法得语法制导定义(语义规则)和翻译方案--语法制导定义-->语义分析

做什么

--翻译方案-->中间代码生成怎么做中间语言高级得:接近源语言。语法树,适合完成静态类型检查。低级得:接近目标语言。适合完成依赖于机器得任务。常用得中间语言:后缀式:逆波兰表示图表示: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抽象语法树*buminuscDAG对应得代码:

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(:=,entr),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:=entr)}

产生式与翻译方案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(:=,entr),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:=entr)}

分别生成三元式代码、四元式代码、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(:=,entr),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:=entr)}

例生成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(:=,entr),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:=entr)}

例生成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+E2val[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,’+’