编译原理语义分析

1、2021-11-4西北工业大学软件与微电子学院 machunyan1o 课程内容课程内容 第第1 1章章 概论概论 第第2 2章章 词法分析词法分析 第第3 3章上下文无关文法章上下文无关文法 第第4 4章语法分析章语法分析n 第第5 5章语义分析章语义分析n 第第6 6章运行时环境章运行时环境n 第第7 7章代码生成章代码生成machunyan西北工业大学软件与微电子学院2第5章 语义分析 o 程序设计语言的语义分为静态语义和动态语程序设计语言的语义分为静态语义和动态语义两种。义两种。n 静态语义是指在编译阶段能够检查的语义；n 动态语义是指在目标程序运行阶段能够检查的语义。machunya

2、n西北工业大学软件与微电子学院3词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成源代码目标代码常数表符号表 错误处理器编译器逻辑结构的组成编译器逻辑结构的组成machunyan西北工业大学软件与微电子学院4o语义分析的任务：语义分析的任务：1. 计算各类语法成分的语义信息(属性信息)，一般将收集的语义信息存放到相应的信息表中，在编译程序中符号表是用来存放源程序中标示符相关属性(语义)信息的一种信息表。第5章 语义分析(续)o 语义分析的任务：语义分析的任务：n 静态语义检查举例：o类型检查：指类型相容问题的检查，如果操作符作用于不相容的操作数，则编译器应该报错。o上下文

3、有关问题的检查：当某个对象出现时，要求它必须在前面的某个适当位置已经出现过。o唯一性检查：要求某个对象只能被定义一次。o控制流检查：引起控制流从某个结构中跳转出来的语句，必须能够决定控制流转向的目标地址。oBreak和continue语句是否在循环结构中？o对于一个方法调用，实际参数的类型和实际参数的个数是否与方法的声明的参数特征相符？o数组下标引用是否超出范围？o数组下标是否是整数？2021-11-4西北工业大学软件与微电子学院 machunyan5第5章 语义分析(续)2021-11-4西北工业大学软件与微电子学院 machunyan6第5章 语义分析(续)machunyan西北工业大学软

4、件与微电子学院75.1 属性和属性文法n 5.2 符号表n 5.3 数据类型和类型检查文法符号语义信息的计算技术语义分析的两个主要方面第5章 语义分析machunyan西北工业大学软件与微电子学院8o 至今没有形式化的系统来描述语义，但至今没有形式化的系统来描述语义，但存在一种存在一种属性文法属性文法，将将语义信息语义信息和和程序程序设计语言的语法结构设计语言的语法结构联系起来。联系起来。n 补充说明合法程序的规格说明5.1 属性和属性文法machunyan西北工业大学软件与微电子学院9o 每个属性文法是一个三元式：每个属性文法是一个三元式： A=(G, V, F)n G是一个上下文无关文法；

5、n V是一个属性的有限集合；n F是一个与属性有关的语义规则的有限集合。5.1 属性和属性文法（续）n V： 每个文法符号(终结符号或非终结符号)都有一个属性集(语义信息)。o如果X是一个文法符号，与X关联的属性a的值记作X.a。o 文法符号关联的属性可以代表n 变量的数据类型n 表达式的值n 存储器中变量的位置n 程序的中间或目标代码片段n 数的有效位数n 等2021-11-4西北工业大学软件与微电子学院 machunyan105.1 属性和属性文法（续）machunyan西北工业大学软件与微电子学院11Xi.aj=fij(X0.a1,.,X0.ak，X1.a1,., X1.ak,.,Xn.

6、a1,.,Xn.ak)o F F: 每个产生式都有一个与文法符号属性相关的语义规则集合。对于上下文无关文法中的任一产生式X0X1X2.Xn，其语义规则定义格式如下：其中，a1,.,ak是与各文法关联的属性集合；fij是一个数学函数，表示文法符合Xi的第j个属性aj是如何计算得到的。o 所以，产生式的语义规则是产生式中所以，产生式的语义规则是产生式中相关文法符相关文法符号属性值的等式。号属性值的等式。5.1 属性和属性文法（续）p 属性属性a1,.,ak的的属性文法属性文法是是文法所有产生式的语文法所有产生式的语义规则的集合。义规则的集合。一般将属性文法写成表格形式，一般将属性文法写成表格形式，

7、每个产生式用相应语义规则列出，如下所示：每个产生式用相应语义规则列出，如下所示：machunyan西北工业大学软件与微电子学院12文法规则 语义规则产生式1 相关的属性等式 . .产生式n 相关的属性等式5.1 属性和属性文法（续）o 属性文法的作用？属性文法的作用？n 根据已求得的各产生式的语义规则，遍历语法分析的结果-语法树或分析树，计算任意句子的推导过程中各文法符号对应的属性值（例如：变量的数据类型、表达式的值、存储器中变量的位置、程序的目标代码、或数的有效位数等），n 根据属性值分析相关语义，或者将属性值存储在符号表中，以供编译的后续阶段使用。machunyan西北工业大学软件与微电子

8、学院135.1 属性和属性文法（续）machunyan西北工业大学软件与微电子学院14o 例例5.1：求解下述无符号数文法的：求解下述无符号数文法的val(十进制十进制值值)属性的属性的属性文法。属性文法。n numbernumber digit |digitn digit0|1|2|3|4| 5 |6|7|8|9o 文法定义的合法的句子举例：文法定义的合法的句子举例：n 345对应的分析树5.1 属性和属性文法（续）machunyan西北工业大学软件与微电子学院15数345对应的分析树machunyan西北工业大学软件与微电子学院16文法规则 语义规则number1number2 digit

9、number1.val = number2.val*10 + digit.valnumberdigit number.val =digit.valmachunyan西北工业大学软件与微电子学院17digit 0 digit.val = 0digit 1 digit.val = 1digit 2 digit.val = 2digit 3 digit.val = 3 . . . . . . 文法规则 语义规则o 属性文法的求解方法：属性文法的求解方法：n 给出一个句子最左推导对应的分析树，而且该句子的推导过程中基本涵盖各种语法规则（即产生式规则）的运用。n 根据该句子的分析树和已知文法符号的属性值

10、，概括出各节点属性值的计算规则，将该计算规则作为节点对应的产生式的语义规则，最后得到属性文法。machunyan西北工业大学软件与微电子学院185.1 属性和属性文法（续）machunyan西北工业大学软件与微电子学院19o 如果给定一个产生式AX1X2.Xn，相关属性等式满足：A.a=f(X1.a1,X1.ak,.，Xn .a1,Xn.ak)，则属性a是合成(综合)的，n 例如：无符号数文法的val(十进制值)属性n 从语法分析树角度看，如果一个节点(文法符号)的某一属性值由其子节点的属性值来计算，则称该属性为合成属性。5.1 属性和属性文法-合成属性machunyan西北工业大学软件与微电

11、子学院20o 一个属性文法中所有的属性都是合成的，就一个属性文法中所有的属性都是合成的，就称作称作S-属性文法属性文法(S-attributed grammar)。o 合成属性的计算合成属性的计算n 给定由语法分析程序构造的分析树或语法树，S-属性文法的属性值可以通过对树进行简单的自底向上或后序遍历来计算。5.1 属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院21void PostEval (T: treenode); for each child C of T do PostEval (C); compute all synthesized attributes of

12、 T;树遍历的合成属性的计算machunyan西北工业大学软件与微电子学院22例5.2：撰写下述简单整型算术表达式文法的val(十进制值)属性的属性文法。expexp+term|exp-term|termtermterm*factor|factor factor(exp)|number5.1 属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院23文法规则 语义规则exp1exp2+term exp1.val=exp2.val+ term.valexp1exp2-term exp1.val= exp2.val-term.valexpterm exp.val=term.val5

13、.1 属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院24term1term2*factor term1.val=term2.val*factor.valtermfactor term.val=factor.valfactor(exp) factor.val=exp.valfactornumber factor.val=number.val文法规则 语义规则5.1 属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院25*-42（34-3）*42 的抽象语法树343对于上述简单整型算术表达式文法，假设表达式(34-3)*42语法分析的结果如下：5.1 属

14、性和属性文法-合成属性machunyan西北工业大学软件与微电子学院26o 如果把分析树中对应该文法符号的节点看成是一条记录，如果把分析树中对应该文法符号的节点看成是一条记录，其中，那么其中，那么属性，属性，就相当于一个就相当于一个域的名字。上页抽象语法域的名字。上页抽象语法树的定义如下：树的定义如下：typedef enum Plus, Minus, Times OpKind;typedef enum OpKind, ConstKind ExpKind;typedef struct streenode ExpKind kind; OpKind op; struct streenode *lc

15、hild, *rchild; int val; STreeNode;typedef STreeNode *SyntaxTree;5.1 属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院27o 后序遍历语法树计算后序遍历语法树计算val属性的伪代码属性的伪代码：n 树节点的属性值由该节点所用产生式的语义规则来定义(计算)。n 后序遍历语法树.doc5.1 属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院28*-42343val=34val=3val=42val=34-3=31val=31*42=1302表达式(34-3)*42对应的加了注释的抽象语法树

16、如下：machunyan西北工业大学软件与微电子学院29o 从语法分析树角度看，一个节点的某一属性从语法分析树角度看，一个节点的某一属性值是由父结点和值是由父结点和/ /或兄弟结点的属性值来计或兄弟结点的属性值来计算，则该属性称为算，则该属性称为继承属性继承属性。o 继承属性的计算继承属性的计算可以通过对分析树或语法树可以通过对分析树或语法树的前序遍历或前序和中序遍历的组合来进行的前序遍历或前序和中序遍历的组合来进行, ,用伪代码表示：用伪代码表示：5.1 属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院30void PreEval(T: treenode);for ea

17、ch child C of T do compute all inherited attributes of C; PreEval ( C );继承属性的计算5.1 属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院31例5.3：对于文法decltype var-listtypeint|floatvar-listid,var-list|id试写出有关属性dtype(数据类型)的属性文法:5.1 属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院32文法规则 语义规则decltype var-listtypeinttypefloatvar-list.dty

18、pe = type.dtypetype.dtype = integertype.dtype = real5.1 属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院33o var-list1id,var-list2o var-listidid.dtype = var-list1.dtypevar-list2.dtype = var-list1.dtypeid.dtype=var-list.dtype文法规则 语义规则5.1 属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院34考虑符号串float x, y的分析树计算节点dtype属性的递归程序的伪代码如

19、下：ididdecltypevar-listvar-listfloat,(dtype=real)(dtype=real)(dtype=real)(dtype=real)(dtype=real)machunyan西北工业大学软件与微电子学院35void EvalType(T: treenode) case nodekind of T ofdecl : EvalType(firstchild of T );T.secondchild.dtype=T.firstchild .dtype;EvalType (secondchild of T );type : if child of T = intT.

20、dtype :=integer else T.dtype := real;machunyan西北工业大学软件与微电子学院36var-list: T.firstchild.dtype =T.dtype;if third child of T is not nil T.thirdchild.dtype =T.dtype;EvalType(third child of T );end case;o 是否任意文法符号的值都需要计算？是否任意文法符号的值都需要计算？n 为了语义分析，有的文法符号的属性值需要计算并保存（例如5.3中文法符号id 的type属性）；n 有的文法符号的属性值不需要保存，但需要

21、计算，这种情况，该文法符号属性作为中间变量，起到传递值的作用（例如5.3中文法符号var-list和type的type属性）；n 有的文法符号的属性值不需要计算（例如5.3中文法符号decl的type属性）。machunyan西北工业大学软件与微电子学院375.1 属性和属性文法-继承属性o 综合综合案例案例 文法文法GS：撰写计算十进制值：撰写计算十进制值val属性属性的属性文法，其中：如果除运算中的任一个操作的属性文法，其中：如果除运算中的任一个操作数是浮点数，则整个表达式就是浮点数，函数数是浮点数，则整个表达式就是浮点数，函数Float可以将整数转换为浮点数。可以将整数转换为浮点数。5.

22、1 属性和属性文法（续）o 5/2/2.0的分析树（该表达式的值计算结果应的分析树（该表达式的值计算结果应1.25而不是而不是1.0）2021-11-4西北工业大学软件与微电子学院 machunyan395.1 属性和属性文法（续）2021-11-4西北工业大学软件与微电子学院 machunyan40辅助属性辅助属性isFloat，首先判断整个表达式是，首先判断整个表达式是float类型还是类型还是int类型类型辅助属性辅助属性isFloat2021-11-4西北工业大学软件与微电子学院 machunyan42辅助属性辅助属性type， 其次调整除运算中每个操作数的数据类型其次调整除运算中每个

23、操作数的数据类型辅助属性辅助属性type， 其次调整除运算中每个操作数的数据类型其次调整除运算中每个操作数的数据类型计算属性计算属性val计算属性计算属性val计算十进制值val属性的完整的属性文法Div表示整数相除，/表示浮点数相除。machunyan西北工业大学软件与微电子学院47o 例例5.4 文法：文法：n based-numnum basecharn basechar o | dn numnum digit | digitn digit0|1|2|3|4|5|6|7|8|9o 撰写其属性撰写其属性val(十进制值十进制值)的属性文法：的属性文法：5.1 属性和属性文法-继承属性mac

24、hunyan西北工业大学软件与微电子学院48计算345o的十进制的值：machunyan西北工业大学软件与微电子学院49 继承属性(续)o 文法规则文法规则based-num num basechar Basechar obasechardo 语义规则语义规则based-num.val=num.valnum.base=basechar.basebasechar.base=8basechar.base=10machunyan西北工业大学软件与微电子学院50num1num2 digit if digit.val=error or num2.val=error then num1.val = err

25、or else num1.val =num2.val*num1.base+digit.val num2.base=num1.base digit.base=num1.base 文法规则 语义规则machunyan西北工业大学软件与微电子学院51numdigitdigit0 digit1.digit7 文法规则 语义规则num.val=digit.valdigit.base = num.basedigit.val=0digit.val=1.digit.val=7machunyan西北工业大学软件与微电子学院52digit8 if digit.base=8 then digit.val=error

26、 else digit.val= 8digit9 if digit.base=8 then digit.val= error else digit.val 9文法规则 语义规则machunyan西北工业大学软件与微电子学院53 继承属性(续)o 在包含在包含合成合成和和继承继承属性的属性文法（例如属性的属性文法（例如5.4）中，如果合成属性依赖于继承属性以）中，如果合成属性依赖于继承属性以及其它合成属性，但继承属性不依赖于任何及其它合成属性，但继承属性不依赖于任何合成属性，那么就可能在分析树或语法树的合成属性，那么就可能在分析树或语法树的一遍遍历中计算所有的属性。一遍遍历中计算所有的属性。o递

27、归遍历分析树或语法树计算合成和继承属性的函数伪代码如下页。machunyan西北工业大学软件与微电子学院54void CombinedEval (T: treenode); for each child C of T do compute all inherited attributes of C; CombinedEval ( C ); compute all synthesized attributes of T; 继承属性(续)o 属性的两种计算方法：属性的两种计算方法：n 语法分析结果-抽象语法树遍历的属性计算方法n 一遍语法分析的处理方法（即语法分析时属性的计算）2009-machu

28、nyan西北工业大学软件与微电子学院55 属性计算方法machunyan西北工业大学软件与微电子学院56树遍历的属性计算方法假设语法分析的结果分析树或语法树已经建立了，并且树中已带有终结符的相应属性，可以以某种次序遍历语法树，直至计算出所有属性，如果需要的话，可使用多次遍历。lGJC中的语义分析程序遍历抽象语法树，进行各种语义检查，是作为编译器中单独的一遍来完成的，源码主要包括Attr.java，Check.java。 属性计算方法(续)machunyan西北工业大学软件与微电子学院57一遍语法分析的处理方法（即语法分析时属性的计算）l与树遍历的属性计算文法不同，一遍语法分析的处理方法是在语法

29、分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算。 属性计算方法(续)o 语法分析时属性的计算方法与语法分析器的相语法分析时属性的计算方法与语法分析器的相互作用，它与下面两个因素密切相关：互作用，它与下面两个因素密切相关：n （1）所采用的语法分析方法n （2）属性的计算次序，语法分析方法都要求从左向右处理输入程序，等价于要求属性能通过从左向右遍历分析树进行赋值（下页引出L属性文法）。machunyan西北工业大学软件与微电子学院58语法分析时属性的计算o 属性属性a1,.,ak 的一个属性文法是的一个属性文法是L-属性属性( (L-attributed) )文法文法，如果满足

30、：如果满足：n 对每个继承属性aj和每个文法规则 X0X1X2Xn， aj的相关等式都有以下形式：Xi.aj=fij(X0.a1,.,X0.ak，Xi-1.a1,.,Xi-1.ak)o 即在Xi处aj的值只依赖于文法规则中Xi左边出现的符号X0 , . . . , Xi -1 的属性（例如：例5.3的dtype属性）machunyan西北工业大学软件与微电子学院59语法分析时属性的计算machunyan西北工业大学软件与微电子学院60语法分析时属性的计算举例o 给定一个给定一个L-属性文法属性文法，如果其继承属性不依赖，如果其继承属性不依赖于合成属性，于合成属性，递归下降的分析程序递归下降的分

31、析程序可以对所有可以对所有的属性赋值；的属性赋值；o 对于对于S-属性属性(合成属性合成属性)，通常使用自底向上的分，通常使用自底向上的分析方法，在建立每一个结点处使用语义规则来析方法，在建立每一个结点处使用语义规则来计算合成计算合成(综合综合)属性值；属性值；n 即在用哪个产生式进行归约后，就执行那个产生式的语义规则计算属性的值，从叶结点到根结点进行计算。n YACC（例如，课程设计，计算器）machunyan西北工业大学软件与微电子学院61 属性值可以作为参数和返回值o 许多属性值都相同，或者仅仅在计算其它属许多属性值都相同，或者仅仅在计算其它属性值时临时使用，则可将属性作为函数的参性值时

32、临时使用，则可将属性作为函数的参数或返回值，而数或返回值，而不是把它们作为字段存储在不是把它们作为字段存储在语法树节点的记录结构中语法树节点的记录结构中。p219machunyan西北工业大学软件与微电子学院62 使用扩展数据结构存储属性值o 如果不能方便地把属性值作为参数或返回值使用的情况下，把属性值存储在语法树节点也是不合理的；n 可以构建额外的数据结构符号表来维护属性值，符号表结合程序中声明的常量、变量、和过程来存储属性。machunyan西北工业大学软件与微电子学院63 使用扩展数据结构存储属性值(续)o 例如：对于简单声明的文法例如：对于简单声明的文法n decltype var-l

33、istn typeint|floatn var-listid,var-list|idn 可以将标示符的声明信息以标示符作为关键字插入并存储到符号表中，以供程序的其他部分翻译使用。o void insert(name:string;dtype:typekind);o 例例5.3的语义规则如何修改？的语义规则如何修改？machunyan西北工业大学软件与微电子学院64因为每个声明只有一个相关类型，所以就可以在处理过程中使用一个全局变量存储每个声明的常量dtype。语义规则如下：文法规则 语义规则decltype var-list typeint dtype=integermachunyan西北工业

34、大学软件与微电子学院65typefloat dtype=realvar-list1id,var-list2 insert(，dtype )var-listid insert(，dtype )相应的属性求值程序EvalType的伪代码：machunyan西北工业大学软件与微电子学院66void EvalType(T:treenode); case nodekind of T of decl:EvalType(first child of T );EvalType(second child of T); type:if child of T= intdtype:=int

35、eger; else dtype:=real;machunyan西北工业大学软件与微电子学院67var-list:insert(name of first child of T，dtype )if third child of T is not nil;EvalType(third child of T ); end case;machunyan西北工业大学软件与微电子学院685.1 属性和属性文法 5.2 符号表n 5.3 数据类型和类型检查文法符号语义信息的计算技术语义分析的两个主要方面第5章 语义分析machunyan西北工业大学软件与微电子学院691. 符号表的概念o 在编译程序工作过

36、程中，需要经常收集、记录在编译程序工作过程中，需要经常收集、记录和使用源程序中一些语法符号的有关类型和特和使用源程序中一些语法符号的有关类型和特征等相关信息，一般的方法是在编译过程中，征等相关信息，一般的方法是在编译过程中，建立并保持一些表格，在需要时进行查询或进建立并保持一些表格，在需要时进行查询或进一步扩展一步扩展(添加添加)。n 常用表格有：变量名表、常数名表、数组名表、过程或子程序名表、保留字表等，把这些表格统称为符号表或名字表或属性表。 machunyan西北工业大学软件与微电子学院701. 符号表的概念（续）符号表的概念（续）o 符号表符号表存储函数、变量、常量以及数据类型存储函数

37、、变量、常量以及数据类型等标识符相关的信息。符号表用于以下情况：等标识符相关的信息。符号表用于以下情况：n 在词法分析、语法分析和语义分析的过程中收集有关标识符的属性，并存于符号表中； 作为进行语法和语义的合法性检查的依据：同一个标识符可能在程序的不同地方出现，需要检查标识符在上下文中的一致性和合法性，而符号表正是进行这种检查的依据；machunyan西北工业大学软件与微电子学院711. 符号表的概念（续）符号表的概念（续）n作为目标代码生成阶段地址分配的依据：每个变量在目标代码生成时都需要确定其对应的存储地址，编译程序在完成了对变量的地址分配后，将其存于符号表中，可以通过符号表获取每个变量对

38、应的存储地址。o 一个编译系统中使用多少符号表，这是由编程一个编译系统中使用多少符号表，这是由编程者根据需要来确定，可以将所有符号放到一张者根据需要来确定，可以将所有符号放到一张统一的表中，也可以按类分成若干表，一般将统一的表中，也可以按类分成若干表，一般将不同种类的单词不同种类的单词(符号符号)分类放到若干表中。分类放到若干表中。machunyan西北工业大学软件与微电子学院72o 一个符号表包括若干登记项，每一项除了包一个符号表包括若干登记项，每一项除了包括符号的名字外，还要填入其它信息括符号的名字外，还要填入其它信息(属性属性域域) ，即每一项的形式为：，即每一项的形式为：n 属性栏一般

39、由若干子栏(或域)组成，用来记录与该项目名字相对应的各种属性之值和特征。名字栏属性栏2.符号表的内容machunyan西北工业大学软件与微电子学院73o 每个名字的属性信息包括：每个名字的属性信息包括：n 名字的种类：常数、变量、数组、函数、标号n 名字的类型：整型、实型、字符型、布尔型n 名字的出现特征：定义性出现、使用性出现n 给名字分配的存储单元地址n 与该名字的语义有关的其它信息：数组的维数、下标的类型、过程或函数的参数及参数类型等。2.符号表的内容(续)machunyan西北工业大学软件与微电子学院74o编译程序在整个编译期间，符号表中所登记的信息编译程序在整个编译期间，符号表中所登

40、记的信息可能在编译的不同阶段使用，对于符号表的操作大可能在编译的不同阶段使用，对于符号表的操作大致可归纳为如下致可归纳为如下5 5类：类：n对给定的名字，判定此名字是否已在表中；n向表中填入一个新的名字；n对给定名字，访问它在表中的某些相关信息；n对给定名字，在表中填写或更新它的某些信息；1)从表中删除一个或一组无用的项；2.符号表的内容(续)machunyan西北工业大学软件与微电子学院75 符号表的数据结构 在编译器中，符号表应该采用何种目录数据结构进行实现？这个问题同样没有一个统一的答案。不同的数据结构有不同的时间复杂度、空间复杂度以及编程复杂度，几种最常见的选择有： 线性链表、各种搜索

41、树结构(二叉搜索树、AVL树、B树)以及哈希表( hash表)等。machunyan西北工业大学软件与微电子学院76 符号表的数据结构o 线性链表：线性链表：符号表里所有的符号都用一条链表串起来,插入一个新的符号只需将这个符号放在链表的表头,时间效率为O(1)；在链表里查找或删除一个符号需要对其进行遍历，时间效率为O(n)；machunyan西北工业大学软件与微电子学院77 符号表的数据结构o 平衡二叉树o在一个典型的平衡二叉树实现（例如AVL树、红黑树、伸展树等）上查找一个符号的时间效率为O(logn);插入一个符号相当于进行一次失败的查找找到待插入的位置，时间效率同样为O(logn)；删除

42、一个符号可能需要做更多的维护操作，但其时间效率仍然维持在O(logn)级别。machunyan西北工业大学软件与微电子学院78 符号表的数据结构o 哈希表（散列表）代表了一个数据结构可以达到的搜索效率的极致，一个好的哈希表实现可以让插入、查找和删除的平均时间效率都达到O(1)。同时，代码实现简单：o 申请一个大数组、计算一个哈希函数的值、然后根据这个值将该符号放到数组相应下标的位置即可。一个最简单的hash函数只需要把符号名中的所有字符相加，然后对符号表的大小取模。machunyan西北工业大学软件与微电子学院79o 在符号表实现中使用的哈希函数将在符号表实现中使用的哈希函数将字符串字符串(标

43、识符名标识符名)转换成转换成0.size-1范围内的一个整范围内的一个整数，一般通过数，一般通过3步。步。n 首先，字符串中的每个字符转换成一个非负整数。n 然后，这些整数用一定的方法组合形成一个整数。n 最后，把结果整数调整到0.size-1范围内。 符号表的数据结构(续)machunyan西北工业大学软件与微电子学院80 符号表的数据结构(续)o 将字符串将字符串x1x2x3x4x5xn映射为存储地址映射为存储地址hn 假设ci是第i个字符的数字值；n乘法因子的一种合理的选择是2的幂，如16或128，这样乘法可以通过移位来完成。 nh的计算公式如上。o symtab.c nint hash

44、 ( char * key )machunyan西北工业大学软件与微电子学院81符号表的哈希函数的实现：static int hash ( char *key ) int temp = 0; int i = 0; while (keyi != 0) temp = (temp SHIFT) + keyi) % SIZE; +i; return temp;machunyan西北工业大学软件与微电子学院82哈希表如何解决冲突是一个重要的问题编译器结构最好的方案对应于分离链表(separate chaining)。“桶”数组的实际大小要选择一个素数，实践证明这将使一般的哈希函数运行得更好。machun

45、yan西北工业大学软件与微电子学院83 变量声明对符号表行为的影响变量声明对符号表实现的影响是说明的变量声明对符号表实现的影响是说明的作用域作用域。编程语言中的编程语言中的作用域作用域规则变化很广，但对许多语规则变化很广，但对许多语言都有几条公共的规则。言都有几条公共的规则。n 使用前声明(declaration before use)：它允许符号表在语法分析期间建立，当在代码中遇到对名字的引用时进行查找；如果查找失败，就出现声明错误，编译器给出相应的出错消息。machunyan西北工业大学软件与微电子学院84n 块结构(block structure)：一种语言是块结构(block stru

46、ctured)的，如果它允许在一个作用域块的内部嵌入其它块。 如果一个块中声明的作用域限制在本块以及本块包含的其它块，一般服从最近嵌套规则(most closely nested rule)，即为同一个名字给定几个不同的说明，被引用的说明是最接近引用的那个嵌套块。 变量声明对符号表行为的影响（续）machunyan西北工业大学软件与微电子学院85int i,j;int f (int size) char i, temp;. . . double j;. . . char * j;. . . . .说明嵌套作用域的C代码片段machunyan西北工业大学软件与微电子学院86o 实现嵌套作用域的方

47、案一：实现嵌套作用域的方案一：n 为了实现嵌套作用域和最近嵌套规则，符号表插入操作不必改写前面的声明，再插入新的声明即可，这样查找操作只能找到名字最近插入的声明。n 类似地，删除操作不应删除与这个名字相应的所有声明，只需删除最近的一个，而显示前面任何的声明。 变量声明对符号表行为的影响（续）machunyan西北工业大学软件与微电子学院87处理f的函数体说明之后machunyan西北工业大学软件与微电子学院88处理f的函数体内第2层嵌套的复合语句的说明之后machunyan西北工业大学软件与微电子学院89退出f的函数体之后(删除其说明)machunyan西北工业大学软件与微电子学院90o 实现

48、嵌套的作用域的实现嵌套的作用域的方案二：方案二：n 为每个作用域建立一个新的符号表，再从内到外把它们链接在一起，这样如果查找操作在当前表中没有找到名字，就自动用附上的表继续搜索。machunyan西北工业大学软件与微电子学院91machunyan西北工业大学软件与微电子学院92o TINY没有作用域信息，所有的变量都是整型，没有作用域信息，所有的变量都是整型， 所以所以TINY符号表不需要保存这些信息。然而，在代码产生符号表不需要保存这些信息。然而，在代码产生期间，变量需要分配存储器地址，所以符号表存储这期间，变量需要分配存储器地址，所以符号表存储这些变量的偏移地址。些变量的偏移地址。o 为使

49、符号表更加有用，还使用符号表产生一个链表，为使符号表更加有用，还使用符号表产生一个链表，显示被访问变量的行号。显示被访问变量的行号。o 符号表的代码包含在符号表的代码包含在symtab.h和和symtab.c文件中。文件中。TINY语言符号表machunyan西北工业大学软件与微电子学院93hashTableSIZE BucketListRec LineListRec name lines memloc next lineno next machunyan西北工业大学软件与微电子学院94Java语言符号表语言符号表o 在在GJC中：中：n Symbol.java定义了GJC中使用的符号。o 一

50、个符号包括符号的种类和类型等信息，它们分别在Kind.java和Type.java中定义。n Scope.java完成了上下文管理的功能(方案2)。 machunyan西北工业大学软件与微电子学院95 5.1 属性和属性文法 5.2 符号表 5.3 数据类型和类型检查文法符号语义信息的计算技术语义分析的两个主要方面第5章 语义分析machunyan西北工业大学软件与微电子学院965.3 数据类型和类型检查o 编译器的主要任务之一是数据类型信息的计算和维护编译器的主要任务之一是数据类型信息的计算和维护( (类型推论类型推论( (type inference)以及使用这些信息确保程序以及使用这些信

51、息确保程序的每一部分在语言的类型规则作用下有意义的每一部分在语言的类型规则作用下有意义( (类型检查类型检查( (type checking)。n 由编译器完成的检查称为静态检查，在大多数传统语言中，如Pascal、C和Ada，类型信息主要是静态的，主要在程序执行之前进行正确性检查。n 在目标程序运行时完成的检查则称为动态检查。原则上，如果目标代码将每个元素的类型和其值保存在一起，则任何检查都可以动态完成。machunyan西北工业大学软件与微电子学院975.3 数据类型和类型检查(续)o 类型检查：n 类型检查器将验证结构的类型是否与上下文所期望的类型匹配；n 类型检查器必须能够验证指针地址

52、访问只作用于指针，下标运算只作用于数组，用户自定义的函数只能用于有正确参数个数及参数类型等情况。machunyan西北工业大学软件与微电子学院98类型等价例如，当对一个表达式或函数调用的形式参数和实在参数进行类型检查时，通常必须进行类型的比较以确定它们是否与给定的上下文相匹配。编译器有一个语义分析程序：Boolean typeEqual(t1,t2:TypeExp);该语义分析程序接受两个类型表达式，如果根据语言的类型等价规则(C语言和Java举例)它们表示相同的类型就返回true，否则返回false。machunyan西北工业大学软件与微电子学院99下面对一个简单语言的语义分析动作方面的类型检查器进行描述，该语言的语法描述如下：var-decl id:type-exp type-expinttype-expbooltype-exp1arraynum of type-exp2exp1exp2+exp3exp1exp2 or exp3exp1exp2exp3expnumexptrueexpfalseexpidstmtif exp then stmtstmt id:=expmachunyan西北工业大学软件与微电子学院100o 符合上述语法的合法的变量声明举例：符合上述语法的合法