编译原理课件CHAPTER5(SemanticAnalysisandIntermediateCodeGeneration1).ppt

Chapter5Semantic Analysis and Intermediate Code Generationn语义分析概述语义分析概述n语法制导翻译语法制导翻译 （（Syntax-Directed Translation））n类型确定与类型检查类型确定与类型检查 （（Type Checking））n中间代码生成中间代码生成 （（Intermediate Code Generation））8/30/202415.1 5.1 语义分析概述语义分析概述n词法分析、语法分析词法分析、语法分析 —— 程序在书写上程序在书写上是正确的、在语法上是正确的，不能保证是正确的、在语法上是正确的，不能保证含义（语义）上的正确性含义（语义）上的正确性8/30/202425.1 5.1 语义分析概述语义分析概述n语义分析阶段分析源程序的含义，并作相语义分析阶段分析源程序的含义，并作相应的处理，语义分析的基本功能：应的处理，语义分析的基本功能：n确定类型确定类型：确定标识符所关联数据对象的类型，即处理源程序的说明部分n类型检查类型检查：对运算及进行运算的运算分量进行类型检查，检查运算的合法性与运算分量类型的一致性（相容性），必要时作相应的类型转换8/30/202435.1 5.1 语义分析概述语义分析概述n识别含义识别含义：确定程序中各构成成分组合到一起的含义，对可执行语句生成中间代码或目标代码* 语义分析往往是和中间代码生成紧密联系的n其他一些静态语义检查：n控制流检查控制流检查：如对于PASCAL语言，不允许从循环外跳转到循环内，C语言的Break引起控制离开最小包围的while、for等语句，检查是否这样的语句存在n唯一性检查唯一性检查：如标识符只能定义一次，枚举类型的元素不能重复等8/30/202445.1 5.1 语义分析概述语义分析概述n语义分析的输入是语法分析的输出（分析语义分析的输入是语法分析的输出（分析树），输出是中间代码，但同时它还完成树），输出是中间代码，但同时它还完成了很多语义处理工作（见上）了很多语义处理工作（见上）n语义分析的主流技术语义分析的主流技术 —— 语法制导翻译语法制导翻译技术技术8/30/202455.2 5.2 语法制导翻译语法制导翻译n文法符号的属性：文法符号的属性：n文法符号（Grammar Symbols）代表语言结构（Language Construct），如标识符、表达式、语句、程序n为每个文法符号文法符号引入一个属性（属性（attribute））集合集合，反映相应语言结构的语义信息语义信息，如标识符的类型、常量的值、变量的存储地址等8/30/20246n属性的类型（从分析过程中属性值的计算方法来分类）：5.2 5.2 语法制导翻译语法制导翻译1、综合属性综合属性（（Synthesized Attributes））：属性值是分析树中该结点的子结点的属性值的函数 2、继承属性继承属性（（Inherited Attributes））：属性值是分析树中该结点的父结点和和/或或兄弟结点的属性值的函数8/30/202475.2 5.2 语法制导翻译语法制导翻译n对于产生式 AX1 X2 …XnA AX X1 1X X2 2X Xn n……计算 A 的综合属性, S ( A ) : = f ( I ( X1 ) , … , I ( Xn ) )计算 Xj 的继承属性, T ( Xj ) : = f ( I ( A ) , ..., I ( Xn ) )n综合属性用于“自下而上”传递信息，继承属性用于“自上而下”传递信息8/30/202485.2 5.2 语法制导翻译语法制导翻译n非终结符（开始符号除外）既可有综合属性也可有继承属性n文法开始符号没有继承属性n终结符号只有综合属性，一般由词法分析器提供8/30/202495.2 5.2 语法制导翻译语法制导翻译n语法制导定义：语法制导定义：n为每一条产生式（A α）引入一套语义规则n规则形式：b := f (c1,c2,…,ck)nb 是 A 的综合属性，则c1,c2,…,ck是产生式文法符号的属性nb 是产生式右部某文法符号的继承属性，则c1,c2,…,ck是产生式文法符号的属性8/30/2024105.2 5.2 语法制导翻译语法制导翻译n虚（综合）属性 （Dummy synthesized attribute） ：n 针对语义动作（过程或语义子程序）n只是为了形式上的统一n语义规则可以计算属性值，也可以（语义动作）在符号表中登录信息、输出错误信息、进行类型检查、产生中间代码等8/30/2024115.2 5.2 语法制导翻译语法制导翻译n例1 P281 Fig.5.2 （只有综合属性）n虚属性n终结符号的属性 n某些非终结符加下标是为了区分一个产生式中同一非终结符的多次出现n例2 P283 Fig.5.4 （带有继承属性）8/30/2024125.2 5.2 语法制导翻译语法制导翻译n属性文法属性文法：语法制导定义对上下文无关文法进行了扩充，扩充后的文法称为属性文法（attribute grammar）。

8/30/2024135.2 5.2 语法制导翻译语法制导翻译n语法制导翻译语法制导翻译（（Syntax-Directed Translation））:n根据语法分析中产生式对应的语义规则语义规则进行翻译的方法称为语法制导翻译语法制导翻译n语法制导：语法制导：基于语法分析中用到的文法产生式n翻译：翻译：完成语义分析的各项功能，不仅指生成中间代码8/30/2024145.2 5.2 语法制导翻译语法制导翻译n属性之间的依赖关系属性之间的依赖关系n语义规则 b := f (c1,c2,…,ck)n只有在已知 c1,…,ck 值的基础上，才能计算属性值 bn称属性 b 依赖于属性 c1,…,ck8/30/2024155.2 5.2 语法制导翻译语法制导翻译n依赖图（依赖图（Dependency Graphs））:n有向边，a → b，表示属性 b 依赖于属性 an用来表示属性之间依赖关系的有向图（Directed Graph）称为依赖图依赖图8/30/2024165.2 5.2 语法制导翻译语法制导翻译n依赖图的构造算法：P284n考虑的是分析树中的结点n一个属性建立一个结点n为每个语义动作引入一个虚属性n例 Fig.5.68/30/2024175.2 5.2 语法制导翻译语法制导翻译n依赖图的例子：LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*Fig.5.3的依赖图n8/30/2024185.2 5.2 语法制导翻译语法制导翻译n依赖图的例子：nFig.5.7（Fig.5.5的依赖图）8/30/2024195.2 5.2 语法制导翻译语法制导翻译n属性计算顺序属性计算顺序n有向非循环图（directed acyclic graph）的拓扑排序（topological sort）：n图中所有结点的一个排列n若 mi→mj 是一有向边，则在结点序列中 mi 在 mj 的前面8/30/2024205.2 5.2 语法制导翻译语法制导翻译n例子：1234765拓扑排序：拓扑排序：7 6 5 4 3 2 1 7 5 6 4 3 2 1 4 7 6 3 5 2 1* 依赖图的任一拓扑排序是一个合理的属性计算顺序 8/30/2024215.2 5.2 语法制导翻译语法制导翻译n属性计算实例：nP286 Example 5.68/30/2024225.2 5.2 语法制导翻译语法制导翻译n属性计算的三种方法：属性计算的三种方法：n1、分析树法：（1）按基础文法构造句子（程序）的分析树（语法分析）（2）按分析树构造依赖图（3）对依赖图进行拓扑排序，得到语义规则的执行顺序（4）按上述顺序执行语义规则，计算属性值，得到句子的翻译结果* 如果依赖图存在回路，这种方法会失败8/30/2024235.2 5.2 语法制导翻译语法制导翻译n2、基于语义规则的方法（Rule-based methods）：n语法分析和属性计算分开，先构造分析树，然后按预先定义的策略遍历分析树来计算属性n语义规则的定义和计算顺序(翻译模式翻译模式)在编译器构造之前确定8/30/2024245.2 5.2 语法制导翻译语法制导翻译n分析树遍历策略的确定（构造编译器时）要考虑语义规则的定义及计算顺序，因此是基于规则的方法n优点：不构造依赖图，不对依赖图进行拓扑排序，提高了时空效率8/30/2024255.2 5.2 语法制导翻译语法制导翻译n3、忽略语义规则的方法（Oblivious methods）：n在进行语法分析的同时进行翻译，即边分析边计算属性，计算次序由分析方法确定而与语义规则无关n缺点：这样确定计算次序将限制能实现的语法制导定义的种类n优点：不构造依赖图，不对依赖图进行拓扑排序，提高了时空效率8/30/2024265.2 5.2 语法制导翻译语法制导翻译nS -属性定义属性定义（（S-attributed definitions）：）：n只含有综合属性的语法制导定义n例：P281 Fig.5.28/30/2024275.2 5.2 语法制导翻译语法制导翻译n只有综合属性时（以 P282 Fig.5.3 的依赖图为例）依赖图中有向边的走向和自底向上分析时建立分析树的顺序是一致的n因此，可以考虑在进行语法分析（自底向上）的同时进行翻译（执行语义规则）8/30/2024285.2 5.2 语法制导翻译语法制导翻译n具体实现具体实现：扩充 LR分析器，为栈中的每一个文法符号增加一个属性域，存放分析过程中该文法符号的综合属性值，当用产生式进行归约时，产生式左边文法符号入栈，其属性值由栈中正在归约的产生式右边符号的属性值计算8/30/2024295.2 5.2 语法制导翻译语法制导翻译n例子例子1：：nP294…… XX.x YY.y ZZ.z………… AA.a………………toptoptoptop8/30/2024305.2 5.2 语法制导翻译语法制导翻译n例子例子2：：P295-296 Fig.5.16 Fig.5.17nntop = top – r + 1 r是产生式右部符号个数PRODUCTIONPRODUCTION SEMANTIC RULE SEMANTIC RULEL L  E n E nprintprint(val[(val[toptop])])E E  E E1 1 + T + Tval[val[ntopntop] = val[] = val[toptop-2]+val[-2]+val[toptop] ] E E  T TT T  T T1 1 * F * Fval[val[ntopntop] = val[] = val[toptop-2]*-2]*val[val[toptop] ] T T  F FF F  (E) (E)val[val[ntopntop] = val[] = val[toptop-1]-1]F F  digit digit8/30/2024315.2 5.2 语法制导翻译语法制导翻译n** Fig.5.16 是 Fig.5.2 的一种具体实现方法8/30/2024325.2 5.2 语法制导翻译语法制导翻译nL -属性定义属性定义（（L-attributed definitions）：）：n是一种语法制导定义n对于产生式 A→X1X2…Xn 右部 Xj 的继承属性，它依赖于：1、 X1，X2，…，Xj-1 （ Xj左边的文法符号）的属性2、A 的继承属性n** L-属性定义包含 S-属性定义8/30/2024335.2 5.2 语法制导翻译语法制导翻译n例子：nP298 Fig.5.19（非L-属性定义）8/30/2024345.2 5.2 语法制导翻译语法制导翻译n翻译模式（翻译模式（translation scheme）：）：n将语义规则放到 { } 中，并插入到产生式右部的适当位置，以反映语义规则的计算顺序，这种书写形式称之为翻译模式翻译模式n翻译模式与语法制导定义的区别：翻译模式中指明了语义规则的执行顺序8/30/2024355.2 5.2 语法制导翻译语法制导翻译n例子：P298 例5.12n（5.1）是一个翻译模式n用此翻译模式去分析一个句子（9-5+2）n把语义动作作为终结符号8/30/202436ETR9{print(“9”){print(“9”)} }-T{print(“-{print(“-”)}”)}{print(“5”){print(“5”)} }{print(“+”){print(“+”)} }{print(“2”){print(“2”)} }52RT1 12 23 34 45 5n对分析树（Fig.5.20）进行深度优先遍历，执行语义动作，完成翻译工作（95-2+）n（5.1）是一个适合以深度优先顺序计算属性的翻译模式R+8/30/2024375.2 5.2 语法制导翻译语法制导翻译n为为 L-属性定义构造翻译模式：属性定义构造翻译模式：n适合以深度优先顺序计算属性的翻译模式需满足的条件：1、产生式右部文法符号的继承属性必须在这个符号以前的动作中计算出来；2、一个动作不能引用该动作右边符号的综合属性；3、产生式左部非终结符号的综合属性只有在其引用的所有属性都计算出来以后才能计算。

计算该属性的动作通常放在产生式右部的末尾8/30/2024385.2 5.2 语法制导翻译语法制导翻译n从 L-属性定义出发，构造一个满足要求的翻译模式 ** L-属性定义本身考虑到了满足这些条件n（第一条件）将计算产生式右边某文法符号的继承属性的语义规则插入到此符号之前n（第二条件）L-属性定义本身满足n（第三条件）将计算产生式左边非终结符号综合属性的语义规则放在产生式右端的末尾8/30/2024395.2 5.2 语法制导翻译语法制导翻译n例子：P300-301 例5.13nFig.5.22----语法制导定义（ L-属性定义）nFig.5.23----翻译模式8/30/202440PRODUCTION SEMANTIC RULES BB.ps = 10; S.ht = B.htB  B1 B2B1.ps = B.ps; B2.ps = B.ps;B.ht = max(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  textB.ht = text.h * B.psTRANSLATION SCHEMES {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.ht = text.h * B.ps }8/30/2024415.2 5.2 语法制导翻译语法制导翻译n分析一个句子：text sub text textSBB2B1textB3subB4texttext分析树分析树8/30/202442带语义动作的分析树带语义动作的分析树SB{B.ps:=10}{S.ht:=B.ht}{B1.ps:=B.ps}{B.ht:=max(B1.ht,B2.ht}{B2.ps:=B.ps}B1B2{B3.ps:=B1.ps}{B4.ps:=shrink(B1.ps)}{B1.ht:=disp(B3.ht,B4.ht}B4subB3text{B2.ht:=text.h*B2.ps}text{B3.ht:=text.h*B3.ps}text{B4.ht:=text.h*B4.ps}1 12 23 34 45 56 67 78 89 910101111* 深度优先计算属性深度优先计算属性8/30/2024438/30/202444。