编译原理第5章语义分析和中间代码产生.ppt

1、第五章语法制导翻译和中间代码产生,2020年8月22日星期六,1,第五章语法制导翻译和中间代码产生,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,2,语义分析的任务：根据语法成分的结构，分析其含义，并用一种内部形式（中间代码）或直接用目标语言表示出来。 具体：静态语义检查和翻译 包括：类型检查（操作符是否相容，例如%） 控制流检查（break是否有switch和for,while） 一致性检查（int a; float a;） 相关名字检查、等等,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,3,5.1 属性文法一、属性,一、属性：一般用来描述客观存在的事物或人

2、的特性。例如，学生的姓名、年龄、性别等；商品的颜色、重量、单价等。编译技术中用属性来描述计算机处理对象的特征。例如：X . Type , X . Place , X.val等分别描述X的类型，存储位置、值等不同的特征。 属性分两类： 综合属性：一般用于“自下而上”传递信息。 继承属性：一般用于“自上而下”传递信息。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,4,二、属性文法,对于某个压缩了的上下文无关文法，当为每个文法符号引进一组属性，且让该文法中的重写规则附加以语义规则时，称该上下文无关文法为属性文法。 形式定义：一个属性文法形式上定义为一个三元组AG, AG=(G ,

3、V , E)。其中G表示一个上下文无关文法；V表示属性的有穷集；E表示属性的断言或谓词的有穷集。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,5,三、综合属性,从语法分析树的角度来看，如果一个结点的某一属性，其值由子结点的属性之值来计算，则称该属性为综合属性。 综合属性用于“自下而上”传递信息。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,6,例1：算术表达式求值的属性文法。 规则式语义规则 1.LEprint(E.val) 2.EE1+TE.val:=E1.val+T.val 3.ETE.val:=T.val 4.TT1*FT.val:=T1.val*F.

4、val 5.TFT.val:=F.val 6.F(E)F.val:=E.val 7.FdigitF.val:=digit.lexval,与规则式关联的每一个语义规则的左部符号E, T, F等的属性值的计算由右部非终结符决定，这种属性称为综合属性。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,7,求：3*5+4,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,8,四、继承属性,语法树分析中，若一个结点的某个属性之值由该结点的兄弟结点和/或父结点的属性之值来计算，则此结点的属性称为继承属性。 继承属性用于“自上而下”传递信息。,第五章语法制导翻译和中间代码产生,20

5、20年8月22日星期六,9,例2、说明语句中简单变量类型信息的属性文法。 规则式语义规则 1.DTLL.in:=T.type 2.TintT.type:=integer 3.TrealT.type:=real 4.LL1 ,idL1.in:=L.inaddtype(id.entry , L.in) 5.Lidaddtype(id.entry , L.in),过程addtype把每一个标识符id的类型信息(由L.in继承)登录在符号表的相关项id.entry中。,D T L int L , id id,T有一个综合属性type，其值为 integer或real。L.in由T.type确定 后逐步

6、传递到下边有关结点使用。 这种属性称为继承属性。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,10,五、属性的初始值, 终结符号只有综合属性，它们由词法分析器提供。 非终结符号既有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,11,5.2 语法制导翻译法,语法制导翻译法的基本思想：对文法的每一条产生式，设计语义子程序。在语法分析的过程中，当使用一条产生式推导或归约时，调用该语义子程序进行属性计算，完成预定的翻译工作。 语法制导翻译法：在语法分析的过程中，依随分析过程，根据每个产生式添加

7、的语义动作进行翻译的方法。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,12,语义子程序,语义子程序也称为翻译子程序，语义动作。它描述了有关产生式所对应的翻译工作。语义动作一方面指出了产生式所对应的符号串的意义；另一方面又按照这种意义规定了对应的属性计算加工动作。 语义动作：查填各种表格 计算某变量的值 生成某种中间代码 打印错误信息等等,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,13,LR分析制导的具体实现方法,1、为文法产生式设计语义子程序。 2、为文法构造一张无冲突的LR分析表。 3、修改总控程序，归约时调用语义子程序。 4、扩充LR分析栈，用来存放

8、各文法符号对应的语义信息。 例如： (1).EE1+E2E.val=E1.val+E2.val (2).EE1*E2E.val=E1.val*E2.val (3). E(E1)E.val=E1.val (4).EdigitE.val=lex.digit,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,14,#,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,15,扩充的LR分析栈：,(1).EE1+E2 E.val=E1.val+E2.val (2).EE1*E2 E.val=E1.val*E2.val (3). E(E1) E.val=E1.val (4).Edi

9、git E.val=lex.digit,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,16,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,17,5.3 中间语言,常用的中间语言有: 一、逆波兰式 二、三元式与间接三元式 三、树形表示法 四、四元式,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,18,一、逆波兰式,1、逆波兰式（后缀式）：每一运算符都置于其运算对象之后。（无括号表达式） 中缀表示后缀表示 A*BAB* A+B*CABC*+ (A+B)*(C+D)AB+CD+* (a=0 if (p = NULL) error( ); else em

10、it(pE.place 2. E E(1) E(2) E.place newtemp( ); emit(E.placeE(1).placeE(2).place ) 3. E E(1) * E(2) E.place newtemp( ); emit(E.placeE(1).place*E(2).place ) 4. E （E(1)） E.place E(1).place； 5. E i p Lookup (); if (p != NULL) E.place p; else error( ); ,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,31,第五章语法制导翻译和中

11、间代码产生,2020年8月22日星期六,32,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,33,二、布尔表达式的翻译,1、EE E 2、EE E 3、E E 4、E(E) 5、Eid rop id 6、Eid,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,34,1、类似算术表达式的翻译方法,（求每个因子，再求表达式的值） 例如：布尔表达式 ：a b c 三地址序列：T1:= c T2:=b T1 T3:=a T2,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,35,1. E E (1) E (2) E.place newtemp( )； emi

12、t ( E.placeE(1).placeE(2).place ) 2. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 3. E E (1) E.place newtemp( )； emit ( E.place E(1).place 4. E ( E (1) ) E.place E(1).place； 5. E i (1) rop i (2) E.place newtemp( )； emit (if i (1).place rop.op i (2).place goto next+3); emit

13、( E.place 0 ); emit ( goto next+2); emit ( E.place 1 ); 6. E i E.place i . place；,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,36,E E E a b E E cd ef,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,37,2、根据布尔表达式的特殊性采取某种优化措施,A Bif A then trun else B A Bif A then B else false A if A then false else true 对非终结符E赋予两个出口 真出口：布尔表达式为真时，需转移

14、的四元式地址。 假出口：布尔表达式为假时，需转移的四元式地址。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,38,设置两个语义变量： E.ture : 用来记录表达式E对应的四元式需回填真出口的四元式的地址所构成的链。 E.false:用来记录表达式E对应的四元式需回填假出口的四元式的地址所构成的链。 定义三个函数：,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,39,链接函数merge(P1 , P2)：把以P1和P2为链首的两条链合并为一，返回合并后的链首（当P2=0时，返回P1 ; 当P20时，返回P2）。 int merge(int P1 , int

15、P2 ) int P; if (! P2) return P1; else P=P2 ; while (P.result 0) P=P.result; P.result=P1; return P2 ; ,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,40,回填函数backpatch( p , t )：把p所链接的每个四元式的第四分量都回填为t。 void BP( int p , int t ) int q=p ; while (q) int q1=q.result ; q.result =t ; q=q1 ; return; 建链函数makelist(i)：创建一个仅含i的新链

16、表。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,41,定义三种四元式： (jnz , a ,- , p)if a goto p(当a为真时转向第p四元式） (jrop , x , y , p)if x rop y goto p (j , - , - , p)goto p (无条件转向第p四元式) 四元式表的指针nextquad（nextq）：每执行一次emit后，nextq自动加1。 E.code：为及时回填转移地址, 使用语义变量 E.code 记录表达式E的第一个四元式语句序号。,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,42,1. E i E.tr

17、= next ; E.fa= next +1; E.code= next ; emit(if i.place goto -); emit( goto _ ) ; 2. E i (1) rop i (2) E.tr= next ; E.code= next ; E.fa= next+1; emit ( if i (1).place rop.op i (2).place goto _ ) ; emit( goto _ ) ; 3. E ( E (1) ) E.code= E(1).code ; E.tr=E(1).tr ; E.fa= E(1).fa ; 4. E E (1) E.tr=E(1).

18、fa ; E.fa= E(1).tr ; 5. E E (1) E (2) bp( E(1).fa, E(2).code) ； E.code= E(1).code ; E.tr=merg( E(1).tr, E(2).tr ) ; E.fa= E(2).fa ; 6. E E (1) E (2) bp( E(1).tr, E(2).code) ； E.code= E(1).code ; E.tr= E(2).tr ; E.fa=merg( E(1).fa, E(2).fa ) ;,第五章语法制导翻译和中间代码产生,2020年8月22日星期六,43,例如布尔表达式 a bc d 的翻译过程如下:,E (1)c d,100 if a b goto 0,101 goto 0, E(1).tr=100 ; E(1).fa=101 ; E(1).code=100 ; ,E (1) E (2),102 if c d goto 0,103 goto 0, E(2).tr=102 ; E(2).fa=103 ; E(2).code=