编译第六章语义分析.ppt

第 6 章 语义分析,学习目标: 掌握: 依赖图, 属性计算算法 理解: 属性文法, 合成和继承属性, S-属性文法, L-属性文法, 符号表,语义分析概述,1 语义 2 语义分析 3 语义分析的典型实现 4 语义分析的方法,1 语义,与被翻译过程的最终含义密切相关的信息 两种语义 静态语义 被静态定义，在执行前可以确定. 编译器实现静态语义分析 动态语义 只有在执行时才能确定,2 语义分析,要求根据编成语言的规则建立正确性，并保证其正确执行。 典型的语义分析有:,静态类型检查: 运算符的分量类型是否相同？ 赋值号的左右边类型是否相同？ 形参与实参类型是否相同？ 数组下标的类型是否为所允许的类型？ 函数说明中的函数类型和返回值的类型是否一致？,其他语义分析: VE中的V是不是变量，而且是数组类型？ V.i中的V是不是变量，而且是记录类型？i是不是该记录的域名？ 每个使用性标识符是否都有声明？有无标识符的重复声明？,3 语义分析的典型实现,构造符号表、记录声明中建立的名字的含义 在表达式和语句中进行类型推断和类型检查以及在语言的类型规则作用域内判断它们的正确性。,4 语义分析的方法,描述 属性文法 用来描述语义 实现 语法制导语义分析 程序的语义内容与它的语法紧密相关的,属性文法 属性文法包括一组属性和属性等式或语义规则 属性是必须进行计算的语言实体的属性 属性等式（或语义规则）描述这些属性的计算如何与语言的文法规则相关,6.1 属性和属性文法 6.2 属性计算算法 6.3 符号表 6.4 程序的语义分析,6.1 属性和属性文法,1 属性 定义 属性是编程语言结构的任意特性 属性的典型例子有: 变量的数据类型 表达式的值 存储器中变量的位置 程序的目标代码,2 属性文法,属性 属性直接与语言的文法符号相联系（终结符和非终结符） 如果X 是一个文法符号，a 是X的一个属性，那么我们把与X关联的 a 的值记作X.a,属性等式（或语义规则） 若有一个属性集合 a1 , . . . , ak 对于每个文法规则 X0X1 X2 . . . X n, 每个文法符号Xi 的属性值Xi .aj 与规则中其他文法符号的属性值是有关的。 属性等式形如 Xi .aj = fij (X0.a1 , . . . , X0.ak ,X1.a1 , . . . , X1.ak , . . . , Xn .a1 , . . . , Xn .ak ) 其中 fij 是一个数学函数,属性文法 属性a1,ak 的属性文法是对语言的所有文法规则的所有这类等式的集合 一般地，将属性文法写成表格形式,例1 无符号数的属性文法： 数的属性是它的值,使用字符串的语法树可以形象化地表示特殊符号串的属性等式的意义。,(val=3),(val=3),(val=4),(val=3*10+4=34),(val=5),(val=34*10+5=345),例 2 变量声明的属性文法： 变量的属性是数据类型,串 “float x,y” 的语法树显示了dtype属性,(dtype=real),(dtype=real),(dtype=real),(dtype=real),(dtype=real),例 3 表达式类型检查的属性文法： 表达式的属性是它的类型,可能出现在属性等式中的表达式类型 数值表达式、逻辑表达式以及一些其他种类的表达式 If-then-else 表达式, case 或 switch表达式 也可以是函数，函数的定义可以在别处给出，作为属性文法的补充的定义。,6.2 属性计算算法,将属性等式转换为计算规则的方式 属性在语法分析器构造语法树后计算 (6.2.2) 属性在语法分析时计算 (6.2.3),实现对应于属性文法的算法规则的问题 属性文法是一种抽象表示，可以将属性等式写成任何顺序而不会影响正确性，它们不指定属性计算的顺序 问题主要在于为赋值和属性分配寻找一个顺序，并确保当每次进行计算时使用的所有属性值都是有效的。 属性等式本身指示了属性计算时的顺序约束，我们使用 相关依赖图 表示这些约束来明确顺序的约束,6.2.1 相关依赖图和赋值顺序,相关依赖图 给定一个属性文法，每个文法规则有一个相关依赖图 每个文法符号的每个属性 Xi.aj 对应一个节点 对每个属性等式 Xi.aj=fij(,Xm.ak,) ，从右边的每个节点Xm.ak 到节点 Xi.aj有一条边(表示Xi.aj 对Xm.ak的依赖),由上下文无关文法得到的一个合法字符串的依赖图 就是字符串语法树中选择表示每个（非叶子）节点文法规则依赖图的联合。,例 1 无符号数的属性文法： 文法规则的依赖图: number1-number2 digit number1.val=number2.val*10+digit.val,number-digit number.val=digit.val,串 “345”的依赖图,例 2 变量声明的属性文法： 文法规则的依赖图: varlist1-id,varlist2 id.dtype=varlist1.dtype varlist2.dtype=varlist1.dtype,varlist-id id.dtype=varlist.dtype,decl-type varlist varlist.dtype=type.dtype,我们通常重叠在相应的文法规则的语法树片段上绘制相关依赖图，这就使和相关有关的文法规则更加清晰。,串 “float x,y”的依赖图,6.2.2 合成和继承属性,属性赋值依赖于分析树或语法树明确或不明确的遍历。 不同种类的遍历处理的属性相关，在项目和能力的种类上都不同。 必须根据它们具有的相关依赖种类对属性分类 合成属性 继承属性,1 合成属性,定义 一个属性是合成的，如果在语法树中它所有的相关都从子节点指向父节点。 等价地，一个属性a 是合成的，如果给定一个文法规则A-X1X2Xn, 左边仅有一个a 的相关属性等式，形如 A.a=f(x1.a1,X1.ak,Xn.a1,Xn.ak),例 1 无符号数的属性文法,val 属性是合成的,例 2 简单整数算术表达式的属性文法,val 属性是合成的。,S-属性文法 一个属性文法的所有属性是合成的，则这个文法叫S属性文法 例如 无符号数的属性文法 简单整数算术表达式的属性文法 都是 S属性文法,合成属性的计算 给定由分析程序构造的分析树或语法树 S属性文法的属性值可以通过对树进行简单的自底向上或后序遍历来计算，着可以用以下递归的属性赋值程序来表示：,procedure PostEval(T:treenode) begin for each child C of T do PostEval(C); compute all synthesized attributes of T; end;,2 继承属性,定义 一个属性不是合成，则称作继承属性 无论在分析树中从祖先到孙子的继承属性还是从同属的继承属性都有依赖。,继承属性的两种依赖图,例 1 变量声明的属性文法,dtype 属性是继承的,继承属性的计算 继承属性的计算可以通过对分析树或语法树的前序遍历或前序/中序遍历的组合来进行。 可以用下面的伪代码表示为： procedure PreEval(T:treenode); begin for each child C of T do compute all inherited attributes of C; PreEval(C); end;,注释: 与合成属性不同，子孙继承属性计算的顺序是重要的 因为在子孙的属性中继承属性可能有依赖关系。,例如 变量声明的属性文法为：,假设从文法明确构造了分析树 所有需要的节点dtype 属性的递归程序的伪代码如下：,procedure EvalType(T:treenode); begin case nodekind of T of decl: /decl-type varlist varlist.dtype=type.dtype EvalType(type child of T); vallist.dtype=type.dtype; EvalType(varlist child of T); type: /type-int type.dtype=integer /type- float type.dtype=real if child of T=int then T.dtype:=integer else T.dtype:=real;,varlist: /varlist-id,varlistid.dtype=varlist1.dtype varlist2.dtype=varlist1.dtype /varlist-idid.dtype=varlist.dtype assign T.dtype to first child of T; if third child of T is not nil then assign T.dtype to third child; EvalType(third child of T); end case; end EvalType;,串“float x,y” 的分析树及dtype 属性的依赖图 编号显示了遍历顺序,3 属性值的存储,属性值作为字段存储在语法树的节点中 例如,如果许多属性值是相同的或仅用于临时计算其他属性值，则使用语法树的空间在每个节点存储属性值就没有什么意义了。,例如：八进制和十进制数的属性文法 属性是 value 和 base,数 345o的属性计算,val=229,val=28*8+5=229,base=8,base=8,val=3*8+4=28,base=8,val=5,base=8,val=3,base=8,val=4,base=8,val=3,base=8,作为参数和返回值的属性 事实上，递归遍历程序用前序计算继承属性，而用后序计算合成属性 在子节点把继承属性作为参数传递给递归函数调用，并接收合成属性作为那些相同调用的返回值,例如: 八进制和十进制数的属性文法： Base是继承属性， val 是合成属性 属性计算的递归函数是：,function EvalWithBase(T:treenode;base:int):int var temp,temp2:int; begin case nodekind of T of base-num: /based-num-num basechar temp:=EvalWithBase(right child of T); return EvalWithBase(left child of T,temp);,num: /num1-num2 digit num-digit temp:=EvalWithBase(left child of T,base); if right child of T is not nill then temp2:=EvalWithBase(right child of T,base); if temperror and temp2error then return base*temp+temp2 else return error; else return temp;,digit: /digit-0 |1 |9 if base=8 and child of T=8 or 9 then error else return numval(child of T); end case; end EvalWithBase,basechar: /basechar-o | d if child of T=o then return 8 else return 10;,使用外部数据结构存储属性值 当属性值有重要的结构时，在翻译时可能专门需要，把属性值存储在语法树节点也是不合理的 在这些情况下，如查表、图以及其他一些数据结构对于获得属性值的正确活动和可用性都是有用的。 一种主要的数据结构是符号表，结合程序中声明的常量、变量和过程存储属性。,6.2.3 语法分析时属性的计算,在分析阶段的同时计算扩展属性，无须等到语法树的递归遍历进行对源代码的多遍处理。,例如 算术表达式的属性文法 EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*number T.val :T1.val * number.val Tnumber T.val :number.val ,自底向上的语法分析过程和串 “2+3*5”的分析树,当语法分析完成时，同时计算了属性值,1 语法分析时哪些能计算属性？,这取决于使用分析方法的能力和性质。 所有主要的分析方法都从左向右处理输入程序。 它等价于要求属性能通过从左向右遍历分析树进行赋值。 对于合成属性这不是一个限制，因为节点的子节点可以用任意顺序赋值。,但是对于继承属性，这就意味着在相关图中没有“向后”的依赖（在分析树中从右指向左）。 属性文法确保的这个特性称作L-属性（从左向右）。,L-属性 定义 属性 a1,ak 的属性文法是 L-属性, 如果对每个继承属性aj 和每个文法规则 X0-X1X2Xn aj 的相关等式都有以下形式： Xi.aj=fij(X0.a1,X0.ak,X1.a1,X1.ak,Xi-1.a1,Xi-1.ak) 也就是说，在Xi 处aj 的值只依赖于在文法规则中Xi 左边出现的符号X0,Xi-1 的属性 作为一个特例， S-属性文法是L-属性文法,3 语法分析时属性的计算,通过把继承属性转换成参数以及把合成属性转换成返回值，递归下降的分析程序可以对所有的属性赋值。 LR 分析程序适合于处理主要的合成属性。,递归下降分析时的属性计算 例如,ETE E+TE TFT T*FT F(E)i,“3+4+5” 的语法树：,“3+4+5” 的语义树：,/ETE E.tree=E.tree E.left=T.tree function E:syntaxTree; var temp:syntaxTree; begin temp:=T; return E(temp); end;,function E(treesofar:syntaxTree):syntaxTree var temp: syntaxTree; begin if TOKEN=+ then /E1-+TE2 E1.tree=E2.tree begin E2.left=mkOpNode(+,E1.left,T.tree) temp:=makeOpNode(+); match(+); leftChild(temp):=treesofar; rightChild(temp):=T; return E(temp) end; else /E- E.tree=E.left begin if TOKEN) and TOKEN$ then ERROR; return treesofar; end; end;,LR语法分析时合成属性的计算 由一个值栈存储合成属性 值栈将和分析栈并行操作 分析栈出现归约时，值栈发生属性等式的计算 移进看作是把记号值同时推进分析栈和值栈,L E print(E.val) EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*num T.val :T1.val * num.val Tnum T.val :num.val ,例如 :算术表达式的属性文法,GOTO,Action,输入串,栈值,分析栈,“2+3*5”的分析过程,LR分析中处理继承属性的技术 LR分析中继承前面计算的合成属性 与规则右边非终结符相关的动作可以把符号的合成属性使用到规则的左边,例如 产生式 A-BC C 有一个继承属性 i 和以某种方式依赖于B: C.i=f(B.s) 的合成属性s 通过在B和C之间引入一个-产生式安排值栈栈顶的存储，在识别C之前的C.i 值可以存进一个变量中：,例如,E.left 是继承属性，并依赖合成属性T.tree,