语义分析

语义分析概述1语义2语义分析3语义分析的典型实现4语义分析的方法1语义与被翻译过程的最终含义密切相关的信息两种语义a)静态语义被静态定义，在执行前可以确定.编译器实现静态语义分析b)动态语义只有在执行时才能确定2语义分析要求根据编成语言的规则建立正确性，并保证其正确执行。典型的语义分析有:a)静态类型检查:运算符的分量类型是否相同？赋值号的左右边类型是否相同？形参与实参类型是否相同？数组下标的类型是否为所允许的类型？函数说明中的函数类型和返回值的类型是否一致？b)其他语义分析:V[E]中的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对于每个文法规则X0→X1X2...Xn,每个文法符号Xi的属性值Xi.aj与规则中其他文法符号的属性值是有关的。属性等式形如Xi.aj=fij(X0.a1,...,X0.ak,X1.a1,...,X1.ak,...,Xn.a1,...,Xn.ak)其中fij是一个数学函数属性文法属性a1,…,ak的属性文法是对语言的所有文法规则的所有这类等式的集合一般地，将属性文法写成表格形式文法规则语义规则规则1相关的属性等式…规则n相关的属性等式例1无符号数的属性文法：数的属性是它的值文法规则语义规则number1-number2digitnumber1.val=number2.val*10+digit.valnumber-digitnumber.val=digit.valdigit-0digit.val=0……digit-9digit.val=9使用字符串的语法树可以形象化地表示特殊符号串的属性等式的意义。3numbernumberdigitnumberdigitdigit45“345”的语法树显示了属性计算(val=3)(val=3)(val=4)(val=3*10+4=34)(val=5)(val=34*10+5=345)例2变量声明的属性文法：变量的属性是数据类型文法规则语义规则decl-typevarlistvarlist.dtype=type.dtypetype-inttype.dtype=integertype-floattype.dtype=realvarlist1-id,varlist2id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtypevar-list-idid.dtype=varlist.dtype串“floatx,y”的语法树显示了dtype属性decltypevarlistid(x)varlist,floatid(y)(dtype=real)(dtype=real)(dtype=real)(dtype=real)(dtype=real)例3表达式类型检查的属性文法：表达式的属性是它的类型文法规则语义规则E→T1+T2T1.t＝intANDT2.t＝intE→T1orT2T1.t＝boolANDT2.t＝boolT→numT.t:＝intT→trueT.t:＝boolT→falseT.t:＝bool可能出现在属性等式中的表达式类型数值表达式、逻辑表达式以及一些其他种类的表达式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-number2digit{number1.val=number2.val*10+digit.val}number1.valnumber2.valdigit.valnumber-digit{number.val=digit.val}number.valdigit.val串“345”的依赖图3numbernumberdigitnumberdigitdigit35number.valnumber.valdigit.valnumber.valdigit.valdigit.val例2变量声明的属性文法：文法规则的依赖图:varlist1-id,varlist2{id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtype}varlist.dtypeid.dtypevarlist.dtypevarlist-id{id.dtype=varlist.dtype}varlist.dtypeid.dtypedecl-typevarlist{varlist.dtype=type.dtype}type.dtypevarlist.dtype我们通常重叠在相应的文法规则的语法树片段上绘制相关依赖图，这就使和相关有关的文法规则更加清晰。串“floatx,y”的依赖图id(x)varlist,decltypevarlistfloatid(y)dtypedtypedtypedtypedtype6.2.2合成和继承属性属性赋值依赖于分析树或语法树明确或不明确的遍历。不同种类的遍历处理的属性相关，在项目和能力的种类上都不同。必须根据它们具有的相关依赖种类对属性分类合成属性继承属性1合成属性定义一个属性是合成的，如果在语法树中它所有的相关都从子节点指向父节点。等价地，一个属性a是合成的，如果给定一个文法规则A-X1X2…Xn,左边仅有一个a的相关属性等式，形如A.a=f(x1.a1,..X1.ak,…,Xn.a1,…Xn.ak)例1无符号数的属性文法文法规则语义规则number1-number2digitnumber1.val=number2.val*10+digit.valnumber-digitnumber.val=digit.valdigit-0digit.val=0……digit-9digit.val=9val属性是合成的例2简单整数算术表达式的属性文法文法规则语义规则E→E1+TE.val:＝E1.val+T.valE→TE.val:＝T.valT→T1*FT.val:＝T1.val*F.valT→FT.val:＝F.valF→(E)F.val:＝E.valF→numF.val:＝num.valval属性是合成的。S-属性文法一个属性文法的所有属性是合成的，则这个文法叫S属性文法例如无符号数的属性文法简单整数算术表达式的属性文法都是S属性文法合成属性的计算给定由分析程序构造的分析树或语法树S属性文法的属性值可以通过对树进行简单的自底向上或后序遍历来计算，这可以用以下递归的属性赋值程序来表示：procedurePostEval(T:treenode)beginforeachchildCofTdoPostEval(C);computeallsynthesizedattributesofT;end;2继承属性定义一个属性不是合成，则称作继承属性无论在分析树中从祖先到孙子的继承属性还是从同属的继承属性都有依赖。继承属性的两种依赖图aBaCaA(a)从祖先到子孙的继承aBaCA(b)同属之间的继承例1变量声明的属性文法dtype属性是继承的文法规则语义规则decl-typevarlistvarlist.dtype=type.dtypetype-inttype.dtype=integertype-floattype.dtype=realvarlist1-id,varlist2id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtypevar-list-idid.dtype=varlist.dtype继承属性的计算继承属性的计算可以通过对分析树或语法树的前序遍历或前序/中序遍历的组合来进行。可以用下面的伪代码表示为：procedurePreEval(T:treenode);beginforeachchildCofTdocomputeallinheritedattributesofC;PreEval(C);end;注释:与合成属性不同，子孙继承属性计算的顺序是重要的因为在子孙的属性中继承属性可能有依赖关系。例如变量声明的属性文法为：文法规则语义规则decl-typevarlistvarlist.dtype=type.dtypetype-inttype.dtype=integertype-floattype.dtype=realvarlist1-id,varlist2id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtypevar-list-idid.dtype=varlist.dtype假设从文法明确构造了分析树所有需要的节点dtype属性的递归程序的伪代码如下：procedureEvalType(T:treenode);begincasenodekindofTofdecl://decl-typevarlist{varlist.dtype=type.dtype}EvalType(typechildofT);varlist.dtype=type.dtype;EvalType(varlistchildofT);type://type-int{type.dtype=integer}//type-float{type.dtype=real}ifchildofT=intthenT.dtype:=integerelseT.dtype:=real;varlist://varlist-id,varlist{id.dtype=varlist1.dtypevarlist2.dtype=varlist1.dtype}//varlist-id{id.dtype=varlist.dtype}assignT.dtypetofirstchildofT;ifthirdchildofTisnotnilthenassig