编译原理 第四章语义分析及中间代码生成.ppt

第四章 语义分析和中间代码生成 属性文法 属性文法(attribute grammar)是一个三元组: A=(G,V,F),其中 G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连, F:关于属性的属性断言或谓词集.每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性 表达式文法 E→T+T| T or T T → n | b E → T1 + T2 { T1.type = int T2.type= T1.type E.type :=int} E → T1 or T2 { T1.type = bool T2.type= T1.type E.type :=bool} T → n { T.type := int} T → b { T.type := bool} 综合属性用于“自下而上”传递信息。 由相应分析树中结点的分支结点属性计算得到。 继承属性用于“自上而下”传递信息。 由相应分析树中结点的父结点属性计算得到。 float id1,id2,id3的带注释的分析树 几种常见的中间语言 1.语法树 ①根与内部结点由表达式中的操作符标记； ②叶子由表达式中的操作数标记； ③用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中； 例： 语法树只反映句型的结构，忽略了推导句型的过程。 几种常见的中间语言 2.逆波兰表示法 a.表达式的逆波兰表示: ①若E是变量或常数，则表示为：E ②若为E1 op E2形式，且 op为二元运算符，则表示为：E1E2op ③若为op E1形式，且 op为一元运算符，则表示为：E1op ④若为（E）形式，则表示为：E 例：a*(b+c)可看成E op (E op E),可写成abc+* (-a)*b+c*d 几种常见的中间语言 2.逆波兰表示法 b.程序语句的逆波兰表示: ①BL:转向某标号; ②BT:条件为真时转移; ③BF:条件为假时转移; ④BR:无条件转移. 几种常见的中间语言 3.三地址代码 三地址代码语句的一般形式为 x=y op z 例:表达式x+y*z的三地址语句为: t1=y*z t2=x+t1 x=t2 常用的三地址语句: 几种常见的中间语言 三地址代码的具体实现:四元式、三元式、间接三元式 a.四元式的记录结构为：(op,arg1,arg2,result) 例:求赋值语句a=b*(c+d)的四元式代码: 首先写出这个赋值语句的三地址代码语句为： t1=c+d t2=b*t1 a=t2 再根据三地址代码语句写出四元式代码为： (+,c,d,t1) (*,b,t1,t2) (=,t2,_,a) 几种常见的中间语言 b.三元式的记录结构为：(op,arg1,arg2) 例:求赋值语句a=b*(c+d)的三元式代码: 首先写出这个赋值语句的三地址代码语句为： t1=c+d t2=b*t1 a=t2 再根据三地址代码语句写出三元式代码为： ①(+,c,d) ②(*,b,①) ③(=,a,②) 几种常见的中间语言 c.间接三元式 例:求赋值语句a=b*(c+d)的三元式代码: 首先写出这个赋值语句的三地址代码语句为： t1=c+d t2=b*t1 a=t2 再根据三地址代码语句写出间接三元式代码为： 三元式表: ①(+,c,d) ②(*,b,①) ③(=,a,②) 间接码表: ① ② ③ 表达式及赋值语句的翻译 1.简单算术表达式和赋值语句的翻译 例:分析赋值语句X=-B*(C+D)的翻译过程. 先转化为三地址代码: 再翻译成四元式: T1=-B (uminus,B,_,T1) T2=C+D (+,C,D,T2) T3=T1*T2 (*,T1,T2,T3) X=T3 (=,T3,_,X) 例:文法 A?i=E E?E+E|E*E|-E|(E)|i 语义变量：i.name, E.place 语义函数：lookup(i.name)， newtemp（