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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七讲,语法制导翻译和中间代码,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,T,1,+T,2,T,1,.type=int AND T,2,.type=T,1,.type,E.type:=int ,E,T,1,or T,2,T,1,.type=bool AND T,2,.type=T,1,.type,E.type:=bool ,T n T.type:=int ,T true T.type:=bool ,T false T.type:=bool ,类型检查的属性文法：,语 义 规 则,L E,E E,1,+T,E T,T T,1,*F,T F,F (E),F digit,Print(E.val),E.val:=E,1,.val+T.val,E.val:=T.val,T.val:=T,1,.val,F.val,T.val:=F.val,F.val:=E.val,F.val:=digit.lexval,产 生 式,综合属性,val,综合属性,在分析树中，如果一个结点的某一个属性由其子结点的属性确定，则称这种属性为该结点的综合属性。,产生副作用的语义规则,，如打印一个值、向符号表中插入信息或更新一个全程变量等。,语义规则函数都不具有副作用的语法制导定义称为,属性文法。,在语法制导定义中，一条语义规则完成一个计算属性值的动作。,digit,是终结符，只使用综合属性，且其属性值由词法分析器提供，通常不要计算属性值。,L,E.val=19,E.val=15,T.val=4,T.val=15,F.val=4,T.val=3,F.val=3,F.val=5,digit.lexval=4,digit.lexval=5,digit.lexval=3,+,*,3*5+4,的带注释的分析树,如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为,S,属性定义,。通常采用,自底向上的方法,对其分析树加注释，即从树叶到树根，按照语义规则计算每个节点的属性值。,继承属性,一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。,生 产 式,语 义 规 则,D,TL,T,int,T,real,L,L,1,id,L,id,L.in:=T.type,T.type=integer,T.type:=real,L,1,.in:=L.in,addtype(id.entry,L.in),addtype(id.entry,L.in,),继承属性,L.in,语句：,real id1，id2，id3,的分析树，采用自上而下的分析方法,产 生 式,语 义 规 则,D,TL,T,int,T,real,L,L,1,id,L,id,L.in:=T.type,T.type=integer,T.type:=real,L,1,.in:=L.in,addtype(id.entry,L.in),addtype(id.entry,L.in,),D,L.in=real,L.in=real,L.in=real,T.type=real,real,id,2,id,1,id,3,.,.,，,，,语法制导翻译概论,在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的,语义子程序,（或语义规则描述的,语义动作,）进行翻译的办法称作语法制导翻译。,参见,P.157-159,对表达式2+3*5进行的分析,中间代码的形成,中间代码的常见形式：,逆波兰记号,三元式（树形表示）,间接三元式,四元式,逆波兰记号（后缀式）,将运算对象写在前面，把运算符号写在后面,表达式,逆波兰式,a+b,ab+,a+b*c,abc*+,(,a+b)*c,ab+c*,a:=b*c+b*d,abc*bd*+:=,计算方法：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈,。,逆波兰记号的扩充用途,-i,i,Goto L,L,jump,if E then S,1,else S,2,ES,1,S,2,￥,Anm,nmA,subs,复杂性：,压栈的可能是地址（如变量赋值），不是值；,栈中不一定产生结果。,逆波兰示例,把下述产生式定义的算术表达式映射到后缀式,表示：,E,E+T,E T,T TF,T F,F(E),F a,E,=,ET+,E=T,T=TF,T=F,F=E,F=a,产生式,翻译成分,确定输入,a+a,a,的输出：,(,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,+),E,E+T,E T,T TF,T F,F(E),F a,E,=,ET+,E=T,T=TF,T=F,F=E,F=a,产生式,翻译成分,将下列语句翻译成,后缀式：,if xy then y=y+z else x=x+z,错误的翻译：（,if E then S,1,else S,2,翻译成：,ES,1,S,2,￥）,x,y,y,z,y,+,=,z,+,x,x,=,￥,正确的翻译：,x,y,y,z,y,+,=,z,+,x,x,=,L1,Jz,L2,Jmp,L1 L2,三元式和树形表示,格式：(算符,第一运算对象,第二运算对象),如：,a:=b*c+b*d(1)(*，b，c)(2)(*，b，d)(3)(+，(1)，(2)(4)(:=，(3)，a),:=,a,+,*,*,b,c,b,d,三元式表示,树形表示,间接三元式,执行表,三元式表,例如：,x:=(a+b)*c b:=a+b y:=c*(a+b),三元式：,(+，a，b),(*，(1)，c),(:=，(2)，x),(+，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 ),四元式的特点,类似于三地址指令,利于优化和代码生成,四元式的直观表示,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,语义属性：,id.name,E.place,函数：,lookup(id.name);,过程：,emit(t:=arg1 op arg2);,newtemp;,返回指向,id,的指针,输出四元式,生成临时变量,E.place:,值,E,的位置,产生式和语义描述：,(1),S,id:=E,P:=lookup(id.name);,if P,nil then emit(P“:=”E.place),else error ,(2),E,E,1,+E,2,E.place:=newtemp;,emit(E.place“:=”E,1,.place“+”E,2,.place),(3),E,E,1*,E,2,E.place:=newtemp;,emit(E.place“:=”E,1,.place“*”E,2,.place),返回,(4),E,-E,1,E.place:=newtemp;,emit(E.place“:=”“uminus”E,1,.place),(5),E,(E,1,),E.place:=E,1,.place,(6),E,id,P:=lookup(id.name);,if P,nil then E.place:=P,else error,返回,例：将下列语句翻译成四元式形式：,A:=-B*(C+D),#,A:=-B*(C+D)#,查看语意义子程序13,查看语意义子程序46,栈 余留输入字符 语意义动作 产生的四元式,#,id,A,:=-B*(C+D)#,#,id,A,:=-B*(C+D)#,#,id,A,:=-B*(C+D)#,#,id,A,:=-id,B,*(C+D)#,#,id,A,:=-E,B,*(C+D)#Sub6,#,id,A,:=E,T1,*(C+D)#Sub4 (，B，T1）,#,id,A,:=E,T1,*(C+D)#,#,id,A,:=E,T1,*(C+D)#,#,id,A,:=E,T1,*(id,C,+D)#,#,id,A,:=E,T1,*(E,C,+D)#Sub6,#,id,A,:=E,T1,*(E,C,+D)#,查看语意义子程序13,查看语意义子程序46,栈 余留输入字符 语意义动作 产生的四元式,#,id,A,:=E,T1,*(E,C,+D)#,#,id,A,:=E,T1,*(E,C,+id,D,)#,#,id,A,:=E,T1,*(E,C,+E,D,)#Sub6,#,id,A,:=E,T1,*(E,T2,)#Sub2 (+，C，D，T2）,#,id,A,:=E,T1,*(E,T2,)#,#,id,A,:=E,T1,*E,T2,#Sub5,#,id,A,:=E,T3,#Sub3 (*，T1，T2，T3）,#,S,#Sub1 (:=，T3，A）,语句,A:=-B*(C+D),翻译成四元式形式为：,(1)（，,B ，T1）,(2)（+，,C ，D，T2）,(3)（*，,T1 ，T2，T3）,(4)（:=，,T3 ，A）,类 型 转 换 的 语 义 处 理,E,E,1,*E,2,E.place:=newtemp;,if E,1,.type=int AND E,2,.type=int then,Begin emit(E.place,:=,E,1,.place,*,i,E,2,.place,)；,E.type=int；End,else if E,1,.type=real AND E,2,.type=real then,Begin emit(E.place,:=,E,1,.place,*,r,E,2,.place,)；,E.type=real；End,else if E,1,.type=int,/*E,2,.type=real*/,then,Begin t:=newtemp;emit(t,:=,irt,E,1,.place,)；,emit(E.place,:=,t,*,r,E,2,.place,)；,E.type=real；End,else,/*E,1,.type=,real,AND,E,2,.type=int,*/,Begin t:=newtemp;emit(t,:=,irt,E,2,.place)；,emit(E.place,:=,E,1,.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:,1,.,把条件转移的布尔表达式,E,翻译成仅含,条件真,转,和,无条件,转,的四元式,E,：,a,rop b,?,if a,rop b,goto,E.true,goto,E.false,如,：,ab or