《编译原理语义分析概要》由会员分享，可在线阅读，更多相关《编译原理语义分析概要（110页珍藏版）》请在金锄头文库上搜索。
1、2019/11/3,西北工业大学软件与微电子学院 machunyan,1,课程内容 第1章 概论 第2章 词法分析 第3章上下文无关文法 第4章语法分析 第5章语义分析 第6章运行时环境 第7章代码生成,machunyan,西北工业大学软件与微电子学院,2,第5章 语义分析,程序设计语言的语义分为静态语义和动态语义两种。 静态语义是指在编译阶段能够检查的语义； 动态语义是指在目标程序运行阶段能够检查的语义。,machunyan,西北工业大学软件与微电子学院,3,词法分析程序,语法分析程序,语义分析程序,中间代码生成,代码优化程序,目标代码生成,源 代 码,目 标 代 码,常数表,符号表,错误处
2、理器,编译器逻辑结构的组成,machunyan,西北工业大学软件与微电子学院,4,语义分析的任务： 计算各类语法成分的语义信息(属性信息)，一般将收集的语义信息存放到相应的信息表中，在编译程序中符号表是用来存放源程序中标示符相关属性(语义)信息的一种信息表。,第5章 语义分析(续),语义分析的任务： 静态语义检查举例： 类型检查：指类型相容问题的检查，如果操作符作用于不相容的操作数，则编译器应该报错。 上下文有关问题的检查：当某个对象出现时，要求它必须在前面的某个适当位置已经出现过。 唯一性检查：要求某个对象只能被定义一次。 控制流检查：引起控制流从某个结构中跳转出来的语句，必须能够决定控制流
3、转向的目标地址。 Break和continue语句是否在循环结构中？ 对于一个方法调用，实际参数的类型和实际参数的个数是否与方法的声明的参数特征相符？ 数组下标引用是否超出范围？ 数组下标是否是整数？,2019/11/3,西北工业大学软件与微电子学院 machunyan,5,第5章 语义分析(续),2019/11/3,西北工业大学软件与微电子学院 machunyan,6,第5章 语义分析(续),machunyan,西北工业大学软件与微电子学院,7,5.1 属性和属性文法,5.2 符号表,5.3 数据类型和类型检查,文法符号语义信息的计算技术,语义分析的两个主要方面,第5章 语义分析,machu
4、nyan,西北工业大学软件与微电子学院,8,至今没有形式化的系统来描述语义，但存在一种属性文法，将语义信息和程序设计语言的语法结构联系起来。 补充说明合法程序的规格说明,5.1 属性和属性文法,machunyan,西北工业大学软件与微电子学院,9,每个属性文法是一个三元式： A=(G, V, F) G是一个上下文无关文法； V是一个属性的有限集合； F是一个与属性有关的语义规则的有限集合。,5.1 属性和属性文法（续）,V： 每个文法符号(终结符号或非终结符号)都有一个属性集(语义信息)。 如果X是一个文法符号，与X关联的属性a的值记作X.a。 文法符号关联的属性可以代表 变量的数据类型 表达
5、式的值 存储器中变量的位置 程序的中间或目标代码片段 数的有效位数 等,2019/11/3,西北工业大学软件与微电子学院 machunyan,10,5.1 属性和属性文法（续）,machunyan,西北工业大学软件与微电子学院,11,Xi.aj=fij(X0.a1,.,X0.ak，X1.a1,., X1.ak,.,Xn.a1,.,Xn.ak),F: 每个产生式都有一个与文法符号属性相关的语义规则集合。对于上下文无关文法中的任一产生式X0X1X2.Xn，其语义规则定义格式如下： 其中，a1,.,ak是与各文法关联的属性集合；fij是一个数学函数，表示文法符合Xi的第j个属性aj是如何计算得到的。
6、 所以，产生式的语义规则是产生式中相关文法符号属性值的等式。,5.1 属性和属性文法（续）,属性a1,.,ak的属性文法是文法所有产生式的语义规则的集合。一般将属性文法写成表格形式，每个产生式用相应语义规则列出，如下所示：,machunyan,西北工业大学软件与微电子学院,12,文法规则 语义规则 产生式1 相关的属性等式 . . 产生式n 相关的属性等式,5.1 属性和属性文法（续）,属性文法的作用？ 根据已求得的各产生式的语义规则，遍历语法分析的结果-语法树或分析树，计算任意句子的推导过程中各文法符号对应的属性值（例如：变量的数据类型、表达式的值、存储器中变量的位置、程序的目标代码、或数的
7、有效位数等）， 根据属性值分析相关语义，或者将属性值存储在符号表中，以供编译的后续阶段使用。,machunyan,西北工业大学软件与微电子学院,13,5.1 属性和属性文法（续）,machunyan,西北工业大学软件与微电子学院,14,例5.1：求解下述无符号数文法的val(十进制值)属性的属性文法。 numbernumber digit |digit digit0|1|2|3|4| 5 |6|7|8|9 文法定义的合法的句子举例： 345对应的分析树,5.1 属性和属性文法（续）,machunyan,西北工业大学软件与微电子学院,15,数345对应 的分析树,machunyan,西北工业大学
8、软件与微电子学院,16,文法规则 语义规则,number1number2 digit,number1.val = number2.val*10 + digit.val,numberdigit,number.val =digit.val,machunyan,西北工业大学软件与微电子学院,17,digit 0 digit.val = 0 digit 1 digit.val = 1 digit 2 digit.val = 2 digit 3 digit.val = 3 . . . . . .,文法规则 语义规则,属性文法的求解方法： 给出一个句子最左推导对应的分析树，而且该句子的推导过程中基本涵盖各
9、种语法规则（即产生式规则）的运用。 根据该句子的分析树和已知文法符号的属性值，概括出各节点属性值的计算规则，将该计算规则作为节点对应的产生式的语义规则，最后得到属性文法。,machunyan,西北工业大学软件与微电子学院,18,5.1 属性和属性文法（续）,machunyan,西北工业大学软件与微电子学院,19,如果给定一个产生式AX1X2.Xn，相关属性等式满足：A.a=f(X1.a1,X1.ak,.，Xn .a1,Xn.ak)，则属性a是合成(综合)的， 例如：无符号数文法的val(十进制值)属性 从语法分析树角度看，如果一个节点(文法符号)的某一属性值由其子节点的属性值来计算，则称该属性
10、为合成属性。,5.1 属性和属性文法-合成属性,machunyan,西北工业大学软件与微电子学院,20,一个属性文法中所有的属性都是合成的，就称作S-属性文法(S-attributed grammar)。 合成属性的计算 给定由语法分析程序构造的分析树或语法树，S-属性文法的属性值可以通过对树进行简单的自底向上或后序遍历来计算。,5.1 属性和属性文法-合成属性,machunyan,西北工业大学软件与微电子学院,21,void PostEval (T: treenode); for each child C of T do PostEval (C); compute all synthesiz
11、ed attributes of T; ,树遍历的合成属性的计算,machunyan,西北工业大学软件与微电子学院,22,例5.2：撰写下述简单整型算术表达式文法的val(十进制值)属性的属性文法。 expexp+term|exp-term|term termterm*factor|factor factor(exp)|number,5.1 属性和属性文法-合成属性,machunyan,西北工业大学软件与微电子学院,23,文法规则 语义规则 exp1exp2+term exp1.val=exp2.val+ term.val,exp1exp2-term exp1.val= exp2.val-te
12、rm.val,expterm exp.val=term.val,5.1 属性和属性文法-合成属性,machunyan,西北工业大学软件与微电子学院,24,term1term2*factor term1.val=term2.val*factor.val,termfactor term.val=factor.val,factor(exp) factor.val=exp.val,factornumber factor.val=number.val,文法规则 语义规则,5.1 属性和属性文法-合成属性,machunyan,西北工业大学软件与微电子学院,25,*,-,42,（34-3）*42 的抽象语法
13、树,34,3,对于上述简单整型算术表达式文法，假设表达式(34-3)*42语法分析的结果如下：,5.1 属性和属性文法-合成属性,machunyan,西北工业大学软件与微电子学院,26,如果把分析树中对应该文法符号的节点看成是一条记录，其中，那么属性，就相当于一个域的名字。上页抽象语法树的定义如下：,typedef enum Plus, Minus, Times OpKind; typedef enum OpKind, ConstKind ExpKind; typedef struct streenode ExpKind kind; OpKind op; struct streenode *l
14、child, *rchild; int val; STreeNode; typedef STreeNode *SyntaxTree;,5.1 属性和属性文法-合成属性,machunyan,西北工业大学软件与微电子学院,27,后序遍历语法树计算val属性的伪代码： 树节点的属性值由该节点所用产生式的语义规则来定义(计算)。 后序遍历语法树.doc,5.1 属性和属性文法-合成属性,machunyan,西北工业大学软件与微电子学院,28,*,-,42,34,3,val=34,val=3,val=42,val=34-3=31,val=31*42=1302,表达式(34-3)*42对应的加了注释的抽象
15、语法树如下：,machunyan,西北工业大学软件与微电子学院,29,从语法分析树角度看，一个节点的某一属性值是由父结点和/或兄弟结点的属性值来计算，则该属性称为继承属性。 继承属性的计算可以通过对分析树或语法树的前序遍历或前序和中序遍历的组合来进行,用伪代码表示：,5.1 属性和属性文法-继承属性,machunyan,西北工业大学软件与微电子学院,30,void PreEval(T: treenode); for each child C of T do compute all inherited attributes of C; PreEval ( C ); ,继承属性的计算,5.1 属性和属性文法-继承属性,machunyan,西北工业大学软件与微电子学院,31,例5.3：对于文法 decltype var-list typeint|float var-listid,var-list|id 试写出有关属性dtype(数据类型)的属性文法:,5.1 属性和属性文法-继承属性,machunyan,西北工业大学软件与微电子学院,32,文法规则 语义规则,decltype var-list typeint typefloat,var-list.dtype
