《编译原理课件CHAPTER5(SemanticAnalysisandIntermediateCodeGeneration-1).ppt》由会员分享，可在线阅读，更多相关《编译原理课件CHAPTER5(SemanticAnalysisandIntermediateCodeGeneration-1).ppt（44页珍藏版）》请在三一文库上搜索。
1、2019/8/28,1,Chapter5 Semantic Analysis and Intermediate Code Generation,语义分析概述 语法制导翻译 （Syntax-Directed Translation） 类型确定与类型检查 （Type Checking） 中间代码生成 （Intermediate Code Generation）,2019/8/28,2,5.1 语义分析概述,词法分析、语法分析 程序在书写上是正确的、在语法上是正确的，不能保证含义（语义）上的正确性,2019/8/28,3,5.1 语义分析概述,语义分析阶段分析源程序的含义，并作相应的处理，语义分析的
2、基本功能：,确定类型：确定标识符所关联数据对象的类型，即处理源程序的说明部分,类型检查：对运算及进行运算的运算分量进行类型检查，检查运算的合法性与运算分量类型的一致性（相容性），必要时作相应的类型转换,2019/8/28,4,5.1 语义分析概述,识别含义：确定程序中各构成成分组合到一起的含义，对可执行语句生成中间代码或目标代码,* 语义分析往往是和中间代码生成紧密联系的,其他一些静态语义检查： 控制流检查：如对于PASCAL语言，不允许从循环外跳转到循环内，C语言的Break引起控制离开最小包围的while、for等语句，检查是否这样的语句存在,唯一性检查：如标识符只能定义一次，枚举类型的元
3、素不能重复等,2019/8/28,5,5.1 语义分析概述,语义分析的输入是语法分析的输出（分析树），输出是中间代码，但同时它还完成了很多语义处理工作（见上）,语义分析的主流技术 语法制导翻译技术,2019/8/28,6,5.2 语法制导翻译,文法符号的属性：,文法符号（Grammar Symbols）代表语言结构（Language Construct），如标识符、表达式、语句、程序,为每个文法符号引入一个属性（attribute）集合，反映相应语言结构的语义信息，如标识符的类型、常量的值、变量的存储地址等,2019/8/28,7,属性的类型（从分析过程中属性值的计算方法来分类）：,5.2 语
4、法制导翻译,1、综合属性（Synthesized Attributes）：属性值是分析树中该结点的子结点的属性值的函数,2、继承属性（Inherited Attributes）：属性值是分析树中该结点的父结点和/或兄弟结点的属性值的函数,2019/8/28,8,5.2 语法制导翻译,对于产生式 AX1 X2 Xn,A,X1,X2,Xn,计算 A 的综合属性, S ( A ) : = f ( I ( X1 ) , , I ( Xn ) ),计算 Xj 的继承属性, T ( Xj ) : = f ( I ( A ) , ., I ( Xn ) ),综合属性用于“自下而上”传递信息，继承属性用于“自
5、上而下”传递信息,2019/8/28,9,5.2 语法制导翻译,非终结符（开始符号除外）既可有综合属性也可有继承属性,文法开始符号没有继承属性,终结符号只有综合属性，一般由词法分析器提供,2019/8/28,10,5.2 语法制导翻译,语法制导定义： 为每一条产生式（A ）引入一套语义规则,规则形式：b := f (c1,c2,ck),b 是 A 的综合属性，则c1,c2,ck是产生式文法符号的属性,b 是产生式右部某文法符号的继承属性，则c1,c2,ck是产生式文法符号的属性,2019/8/28,11,5.2 语法制导翻译,虚（综合）属性 （Dummy synthesized attribu
6、te） ： 针对语义动作（过程或语义子程序） 只是为了形式上的统一,语义规则可以计算属性值，也可以（语义动作）在符号表中登录信息、输出错误信息、进行类型检查、产生中间代码等,2019/8/28,12,5.2 语法制导翻译,例1 P281 Fig.5.2 （只有综合属性） 虚属性 终结符号的属性 某些非终结符加下标是为了区分一个产生式中同一非终结符的多次出现,例2 P283 Fig.5.4 （带有继承属性）,2019/8/28,13,5.2 语法制导翻译,属性文法：语法制导定义对上下文无关文法进行了扩充，扩充后的文法称为属性文法（attribute grammar）。,2019/8/28,14,
7、5.2 语法制导翻译,语法制导翻译 （Syntax-Directed Translation）: 根据语法分析中产生式对应的语义规则进行翻译的方法称为语法制导翻译。,语法制导：基于语法分析中用到的文法产生式,翻译：完成语义分析的各项功能，不仅指生成中间代码,2019/8/28,15,5.2 语法制导翻译,属性之间的依赖关系 语义规则 b := f (c1,c2,ck),只有在已知 c1,ck 值的基础上，才能计算属性值 b,称属性 b 依赖于属性 c1,ck,2019/8/28,16,5.2 语法制导翻译,依赖图（Dependency Graphs）:,有向边，a b，表示属性 b 依赖于属性
8、 a,用来表示属性之间依赖关系的有向图（Directed Graph）称为依赖图,2019/8/28,17,5.2 语法制导翻译,依赖图的构造算法：P284 考虑的是分析树中的结点 一个属性建立一个结点 为每个语义动作引入一个虚属性,例 Fig.5.6,2019/8/28,18,5.2 语法制导翻译,依赖图的例子：,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,+,*,Fig.5.3的依赖图,n,2019/8/28
9、,19,5.2 语法制导翻译,依赖图的例子： Fig.5.7（Fig.5.5的依赖图）,2019/8/28,20,5.2 语法制导翻译,属性计算顺序,有向非循环图（directed acyclic graph）的拓扑排序（topological sort）：,图中所有结点的一个排列,若 mimj 是一有向边，则在结点序列中 mi 在 mj 的前面,2019/8/28,21,5.2 语法制导翻译,例子：,1,2,3,4,7,6,5,拓扑排序：7 6 5 4 3 2 1 7 5 6 4 3 2 1 4 7 6 3 5 2 1,* 依赖图的任一拓扑排序是一个合理的属性计算顺序,2019/8/28,2
10、2,5.2 语法制导翻译,属性计算实例： P286 Example 5.6,2019/8/28,23,5.2 语法制导翻译,属性计算的三种方法： 1、分析树法： （1）按基础文法构造句子（程序）的分析树（语法分析） （2）按分析树构造依赖图 （3）对依赖图进行拓扑排序，得到语义规则的执行顺序 （4）按上述顺序执行语义规则，计算属性值，得到句子的翻译结果,* 如果依赖图存在回路，这种方法会失败,2019/8/28,24,5.2 语法制导翻译,2、基于语义规则的方法（Rule-based methods）： 语法分析和属性计算分开，先构造分析树，然后按预先定义的策略遍历分析树来计算属性,语义规则的
11、定义和计算顺序(翻译模式)在编译器构造之前确定,2019/8/28,25,5.2 语法制导翻译,分析树遍历策略的确定（构造编译器时）要考虑语义规则的定义及计算顺序，因此是基于规则的方法,优点：不构造依赖图，不对依赖图进行拓扑排序，提高了时空效率,2019/8/28,26,5.2 语法制导翻译,3、忽略语义规则的方法（Oblivious methods）： 在进行语法分析的同时进行翻译，即边分析边计算属性，计算次序由分析方法确定而与语义规则无关,缺点：这样确定计算次序将限制能实现的语法制导定义的种类,优点：不构造依赖图，不对依赖图进行拓扑排序，提高了时空效率,2019/8/28,27,5.2 语
12、法制导翻译,S -属性定义（S-attributed definitions）：,只含有综合属性的语法制导定义,例：P281 Fig.5.2,2019/8/28,28,5.2 语法制导翻译,只有综合属性时（以 P282 Fig.5.3 的依赖图为例）依赖图中有向边的走向和自底向上分析时建立分析树的顺序是一致的,因此，可以考虑在进行语法分析（自底向上）的同时进行翻译（执行语义规则）,2019/8/28,29,5.2 语法制导翻译,具体实现：扩充 LR分析器，为栈中的每一个文法符号增加一个属性域，存放分析过程中该文法符号的综合属性值，当用产生式进行归约时，产生式左边文法符号入栈，其属性值由栈中正在
13、归约的产生式右边符号的属性值计算,2019/8/28,30,5.2 语法制导翻译,例子1： P294,top,top,2019/8/28,31,5.2 语法制导翻译,例子2：P295-296 Fig.5.16 Fig.5.17,ntop = top r + 1 r是产生式右部符号个数,PRODUCTION SEMANTIC RULE L E n print(valtop) E E1 + T valntop = valtop-2+valtop E T T T1 * F valntop = valtop-2*valtop T F F (E) valntop = valtop-1 F digit,2
14、019/8/28,32,5.2 语法制导翻译,* Fig.5.16 是 Fig.5.2 的一种具体实现方法,2019/8/28,33,5.2 语法制导翻译,L -属性定义（L-attributed definitions）：,是一种语法制导定义,对于产生式 AX1X2Xn 右部 Xj 的继承属性，它依赖于： 1、 X1，X2，Xj-1 （ Xj左边的文法符号）的属性 2、A 的继承属性,* L-属性定义包含 S-属性定义,2019/8/28,34,5.2 语法制导翻译,例子： P298 Fig.5.19,（非L-属性定义）,2019/8/28,35,5.2 语法制导翻译,翻译模式（transl
15、ation scheme）：,将语义规则放到 中，并插入到产生式右部的适当位置，以反映语义规则的计算顺序，这种书写形式称之为翻译模式,翻译模式与语法制导定义的区别：翻译模式中指明了语义规则的执行顺序,2019/8/28,36,5.2 语法制导翻译,例子：P298 例5.12 （5.1）是一个翻译模式,用此翻译模式去分析一个句子（9-5+2）,把语义动作作为终结符号,2019/8/28,37,E,T,R,9,print(“9”),-,T,print(“-”),print(“5”),print(“+”),print(“2”),5,2,R,T,1,2,3,4,5,对分析树（Fig.5.20）进行深度
16、优先遍历，执行语义动作，完成翻译工作（95-2+）,（5.1）是一个适合以深度优先顺序计算属性的翻译模式,R,+,2019/8/28,38,5.2 语法制导翻译,为 L-属性定义构造翻译模式：,适合以深度优先顺序计算属性的翻译模式需满足的条件：,1、产生式右部文法符号的继承属性必须在这个符号以前的动作中计算出来；,2、一个动作不能引用该动作右边符号的综合属性；,3、产生式左部非终结符号的综合属性只有在其引用的所有属性都计算出来以后才能计算。计算该属性的动作通常放在产生式右部的末尾,2019/8/28,39,5.2 语法制导翻译,从 L-属性定义出发，构造一个满足要求的翻译模式,* L-属性定义
17、本身考虑到了满足这些条件,（第一条件）将计算产生式右边某文法符号的继承属性的语义规则插入到此符号之前,（第二条件）L-属性定义本身满足,（第三条件）将计算产生式左边非终结符号综合属性的语义规则放在产生式右端的末尾,2019/8/28,40,5.2 语法制导翻译,例子：P300-301 例5.13,Fig.5.22-语法制导定义（ L-属性定义）,Fig.5.23-翻译模式,2019/8/28,41,PRODUCTION SEMANTIC RULE S B B.ps = 10; S.ht = B.ht B B1 B2 B1.ps = B.ps; B2.ps = B.ps; B.ht = max(
18、B1.ht, B2.ht) B B1 sub B2 B1.ps = B.ps; B2.ps = shrink(B.ps); B.ht = disp(B1.ht, B2.ht) B text B.ht = text.h * B.ps,TRANSLATION SCHEME S B.ps = 10 B S.ht = B.ht B B1.ps = B.ps B1 B2.ps = B.ps B2 B.ht = max(B1.ht, B2.ht) B B1.ps = B.ps B1 sub B2.ps = shrink(B.ps) B2 B.ht = disp(B1.ht, B2.ht) B text B
19、.ht = text.h * B.ps ,2019/8/28,42,5.2 语法制导翻译,分析一个句子：text sub text text,S,B,B2,B1,text,B3,sub,B4,text,text,分析树,2019/8/28,43,带语义动作的分析树,S,B,B.ps:=10,S.ht:=B.ht,B1.ps:=B.ps,B.ht:=max(B1.ht,B2.ht,B2.ps:=B.ps,B1,B2,B3.ps:=B1.ps,B4.ps:=shrink(B1.ps),B1.ht:=disp(B3.ht,B4.ht,B4,sub,B3,text,B2.ht:=text.h*B2.ps,text,B3.ht:=text.h*B3.ps,text,B4.ht:=text.h*B4.ps,1,2,3,4,5,6,7,8,9,10,11,* 深度优先计算属性,2019/8/28,44,The End!,