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

1、第七讲 语法制导翻译和中间代码,7.1属性文法 7.2语法制导翻译概论 7.3中间代码 7.4一些语句的翻译,属性文法,属性文法(attribute grammar)是一个三元组:A=(G,V,F,F：关于属性的属性断言或谓词集.每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性,V：有穷的属性集，每个属性与文法的一个终结符或非终结符相连,G：是一个上下文无关文法,表达式文法 ET+T| T or T T n | true | false,E T1 + T2 T1.type = int AND T2.type = T1. type E.type :=int

2、E T1 or T2 T1.type = bool AND T2.type= T1.type E.type :=bool T n T.type := int T true T.type := bool T false T.type := bool,类型检查的属性文法,综合属性val,综合属性,在分析树中，如果一个结点的某一个属性由其子结点的属性确定，则称这种属性为该结点的综合属性,产生副作用的语义规则，如打印一个值、向符号表中插入信息或更新一个全程变量等,语义规则函数都不具有副作用的语法制导定义称为属性文法,在语法制导定义中，一条语义规则完成一个计算属性值的动作。digit是终结符，只使用综合

3、属性，且其属性值由词法分析器提供，通常不要计算属性值,如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为S属性定义。通常采用自底向上的方法对其分析树加注释，即从树叶到树根，按照语义规则计算每个节点的属性值,继承属性,一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的,生 产 式,语 义 规 则,D TL,T int,T real,L L1,id,L id,L.in:=T.type,T.type=integer,T.type:=real,L1.in:=L.in,addtype(id.entry,L.in,addtype(id.entry,L.in,继承属性L.in,

4、语句：real id1， id2， id3的分析树，采用自上而下的分析方法,语法制导翻译概论,在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。 参见P.157-159对表达式2+3*5进行的分析,中间代码的形成,中间代码的常见形式： 逆波兰记号 三元式（树形表示） 间接三元式 四元式,逆波兰记号（后缀式,将运算对象写在前面，把运算符号写在后面,计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈,逆波兰记号的扩充用途,复杂性： 压栈的可能是地址（如变量赋值），不是值

5、； 栈中不一定产生结果,逆波兰示例,把下述产生式定义的算术表达式映射到后缀式 表示,EE+T,E T,T TF,T F,F (E,F a,E = ET,E = T,T = TF,T = F,F = E,F = a,产生式,翻译成分,确定输入a+aa的输出： (E,E)(E+T，ET+) (T+T，TT+) (F+T，FT+) (a+T，aT+) (a+TF，aTF+) (a+FF，aFF+) (a+aF，aaF+) (a+aa，aaa,EE+T,E T,T TF,T F,F (E,F a,E = ET,E = T,T = TF,T = F,F = E,F = a,产生式,翻译成分,将下列语句翻

6、译成后缀式： if xy then y=y+z else x=x+z,错误的翻译： （if E then S1 else S2 翻译成：ES1S2,x,y,y,z,y,z,x,x,三元式和树形表示,格式：(算符, 第一运算对象, 第二运算对象) 如：a := b*c + b*d(1) ( *，b，c )(2) ( *，b，d )(3) ( +，(1)，(2) )(4) ( :=，(3)，a,三元式表示,树形表示,间接三元式,执行表 三元式表,例如：x:=(a+b)*c b:=a+b y:=c*(a+b,三元式： ( +， a ，b ) ( *， (1)，c ) ( :=，(2)，x ) ( +

7、， a ，b ) ( :=，(4)，b ) ( +， a， b ) ( *， c，(6) ) ( :=，(7)，y,间接三元式： 三元式表 执行表 ( +，a，b ) (1) ( *，(1)，c ) (2) ( :=，(2)，x ) (3) ( :=，(1)，b ) (1) ( :=，(2)，y ) (4) (1) (2) (5,四元式,格式：(算符, 第一运算对象, 第二运算对象, 结果) 如：a:=b*c+b*d (1)( *， b， c， t1 ) (2)( *， b， d， t2 ) (3)( +， t1，t2， t3 ) (4)( :=，t3， ， a,四元式的特点,类似于三地址指令

8、 利于优化和代码生成,四元式的直观表示,t1 := b * ct2 := b * dt3 := t1 + t2a := t3 (jump， ， ，L) goto L (jrop，B，C，L) if B rop C goto L,简单赋值语句的翻译,四元式形式 : t :=arg1 op arg2 语义属性：, E.place 函数：lookup() ; 过程：emit(t := arg1 op arg2); newtemp,返回指向id的指针,输出四元式,生成临时变量,E.place:值E的位置,产生式和语义描述,1) S id := E P:=lookup (id

9、.name) ; if Pnil then emit( P“:=”E.place) else error (2) EE1+E2 E.place:= newtemp; emit(E.place“:=” E1.place“+”E2.place) (3) EE1*E2 E.place:= newtemp; emit(E.place“:=” E1.place“*”E2.place,返回,4) E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place) (5) E( E1) E.place:= E1.place (6) Eid P:=looku

10、p(); if Pnil then E.place:=P else error,返回,例：将下列语句翻译成四元式形式： A:=-B*(C+D, A:=-B*(C+D),查看语意义子程序13,查看语意义子程序46,栈 余留输入字符 语意义动作 产生的四元式,idA :=-B*(C+D),idA := -B*(C+D),idA :=- B*(C+D),idA :=-idB *(C+D),idA :=-EB *(C+D)# Sub6,idA :=ET1 *(C+D)# Sub4 (，B， ，T1,idA := ET1 * (C+D),idA := ET1 * ( C+D),idA :=

11、 ET1 * (idC +D),idA := ET1 * (EC +D)# Sub6,idA := ET1 * (EC+ D),查看语意义子程序13,查看语意义子程序46,栈 余留输入字符 语意义动作 产生的四元式,idA := ET1 * (EC+ D),idA := ET1 * (EC+idD ),idA := ET1 * (EC+ED )# Sub6,idA := ET1 * (ET2 )# Sub2 (+，C，D，T2,idA := ET1 * (ET2) ,idA := ET1 * ET2 # Sub5,idA := ET3 # Sub3 (*，T1，T2，T3,S # Sub1 (

12、:=，T3， ，A,语句 A:=-B*(C+D) 翻译成四元式形式为,1) （ ， B ， ， T1 ） (2) （ +， C ， D， T2 ） (3) （ *， T1 ，T2， T3 ） (4) （ :=，T3 ， ， A,类 型 转 换 的 语 义 处 理,EE1*E2 E.place := newtemp; if E1.type=int AND E2.type=int then Begin emit(E.place, :=, E1.place, *i, E2.place,)； E.type = int； End else if E1.type=real AND E2.type=real

13、 then Begin emit(E.place, :=, E1.place, *r, E2.place,)； E.type = real； End else if E1.type=int /* E2.type=real */ then Begin t := newtemp; emit(t, :=, irt, E1.place,)； emit(E.place, :=, t, *r, E2.place,)； E.type = real； End else /* E1.type= real AND E2.type= int */ Begin t := newtemp; emit(t, :=, ir

14、t, E2.place)； emit(E.place, :=, E1.place, *r, t)； E.type = real； End,E.false,控制语句中布尔表达式的翻译,控制语句,S,if E then S,1,else S,2,E,的代码,E,true,E.true,S,1,的代码,goto out,E.false,S,2,的代码,out,语义描述使用的变量和过程,E.true,真”链,E,false,假”链,E.codebegin,E,的第一个四元式,Nextstat,下一四元式地址,过程,emit(,输出一条四元式,merge(p1, p2,把,p1,的链头填在,p2,的链尾

15、,例,merge(p1, p2,p10) 0,p1,链,p,10,0,p10,p1) p100,p20) 0,p2,链,p200) p20,p2) p200,backpatch,p,t,把,p,所链接的每个四元式,的第四区段都填为,t,语义描述使用的变量和过程,E.true,真”链,E,false,假”链,E.codebegin,E,的第一个四元式,Nextstat,下一四元式地址,过程,emit(,输出一条四元式,merge(p1, p2,把,p1,的链头填在,p2,的链尾,例,merge(p1, p2,p10) 0,p1,链,p,10,0,p10,p1) p100,p20) p100,p2,链,p200) p20,p2) p200,backpatch,p,t,把,p,所链接的每个四元式,的第四区段都填为,t,自下而上分析中的一种翻译方案,1,E,E,1,or E,2,backpatch(E,1,false, E,2,Codebegin,E.Codebegin:= E,1,codebegin,E.true:=merge(E,1,t