《编译原理语义分析讲述》由会员分享，可在线阅读，更多相关《编译原理语义分析讲述（110页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学软件与微电子学院machunyan1o课程内容第1章概论第2章词法分析第3章上下文无关文法第4章语法分析n第5章语义分析n第6章运行时环境n第7章代码生成machunyan西北工业大学软件与微电子学院2第5章语义分析o程序设计语言的语义分为静态语义和动态语义两种。n静态语义是指在编译阶段能够检查的语义；n动态语义是指在目标程序运行阶段能够检查的语义。machunyan西北工业大学软件与微电子学院3词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成源代码目标代码常数表符号表错误处理器编译器逻辑结构的组成machunyan西北工业大学软件与微电子学院4o语义分析的
2、任务：1.计算各类语法成分的语义信息(属性信息)，一般将收集的语义信息存放到相应的信息表中，在编译程序中符号表是用来存放源程序中标示符相关属性(语义)信息的一种信息表。第5章语义分析(续)o语义分析的任务：2.静态语义检查举例：o类型检查：指类型相容问题的检查，如果操作符作用于不相容的操作数，则编译器应该报错。o上下文有关问题的检查：当某个对象出现时，要求它必须在前面的某个适当位置已经出现过。o唯一性检查：要求某个对象只能被定义一次。o控制流检查：引起控制流从某个结构中跳转出来的语句，必须能够决定控制流转向的目标地址。oBreak和continue语句是否在循环结构中？o对于一个方法调用，实际
3、参数的类型和实际参数的个数是否与方法的声明的参数特征相符？o数组下标引用是否超出范围？o数组下标是否是整数？西北工业大学软件与微电子学院machunyan5第5章语义分析(续)西北工业大学软件与微电子学院machunyan6第5章语义分析(续)machunyan西北工业大学软件与微电子学院75.1属性和属性文法n5.2符号表n5.3数据类型和类型检查文法符号语义信息的计算技术语义分析的两个主要方面第5章语义分析machunyan西北工业大学软件与微电子学院8o至今没有形式化的系统来描述语义，但存在一种属性文法，将语义信息和程序设计语言的语法结构联系起来。n补充说明合法程序的规格说明5.1属性和
4、属性文法machunyan西北工业大学软件与微电子学院9o每个属性文法是一个三元式：A=(GVF)nG是一个上下文无关文法；nV是一个属性的有限集合；nF是一个与属性有关的语义规则的有限集合。5.1属性和属性文法（续）nV：每个文法符号(终结符号或非终结符号)都有一个属性集(语义信息)。o如果X是一个文法符号，与X关联的属性a的值记作X.a。o文法符号关联的属性可以代表n变量的数据类型n表达式的值n存储器中变量的位置n程序的中间或目标代码片段n数的有效位数n等西北工业大学软件与微电子学院machunyan105.1属性和属性文法（续）machunyan西北工业大学软件与微电子学院11Xi.aj
5、=fij(X0.a1.X0.ak，X1.a1.X1.ak.Xn.a1.Xn.ak)oF:每个产生式都有一个与文法符号属性相关的语义规则集合。对于上下文无关文法中的任一产生式X0X1X2.Xn，其语义规则定义格式如下：其中，a1.ak是与各文法关联的属性集合；fij是一个数学函数，表示文法符合Xi的第j个属性aj是如何计算得到的。o所以，产生式的语义规则是产生式中相关文法符号属性值的等式。5.1属性和属性文法（续）p属性a1.ak的属性文法是文法所有产生式的语义规则的集合。一般将属性文法写成表格形式，每个产生式用相应语义规则列出，如下所示：machunyan西北工业大学软件与微电子学院12文法规
6、则语义规则产生式1相关的属性等式.产生式n相关的属性等式5.1属性和属性文法（续）o属性文法的作用？n根据已求得的各产生式的语义规则，遍历语法分析的结果-语法树或分析树，计算任意句子的推导过程中各文法符号对应的属性值（例如：变量的数据类型、表达式的值、存储器中变量的位置、程序的目标代码、或数的有效位数等），n根据属性值分析相关语义，或者将属性值存储在符号表中，以供编译的后续阶段使用。machunyan西北工业大学软件与微电子学院135.1属性和属性文法（续）machunyan西北工业大学软件与微电子学院14o例5.1：求解下述无符号数文法的val(十进制值)属性的属性文法。nnumbernum
7、berdigit|digitndigit0|1|2|3|4|5|6|7|8|9o文法定义的合法的句子举例：n345对应的分析树5.1属性和属性文法（续）machunyan西北工业大学软件与微电子学院15数345对应的分析树machunyan西北工业大学软件与微电子学院16文法规则语义规则number1number2digitnumber1.val=number2.val10+digit.valnumberdigitnumber.val=digit.valmachunyan西北工业大学软件与微电子学院17digit0digit.val=0digit1digit.val=1digit2digit.
8、val=2digit3digit.val=3.文法规则语义规则o属性文法的求解方法：n给出一个句子最左推导对应的分析树，而且该句子的推导过程中基本涵盖各种语法规则（即产生式规则）的运用。n根据该句子的分析树和已知文法符号的属性值，概括出各节点属性值的计算规则，将该计算规则作为节点对应的产生式的语义规则，最后得到属性文法。machunyan西北工业大学软件与微电子学院185.1属性和属性文法（续）machunyan西北工业大学软件与微电子学院19o如果给定一个产生式AX1X2.Xn，相关属性等式满足：A.a=f(X1.a1X1.ak.，Xn.a1Xn.ak)，则属性a是合成(综合)的，n例如：无
9、符号数文法的val(十进制值)属性n从语法分析树角度看，如果一个节点(文法符号)的某一属性值由其子节点的属性值来计算，则称该属性为合成属性。5.1属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院20o一个属性文法中所有的属性都是合成的，就称作S-属性文法(S-attributedgrammar)。o合成属性的计算n给定由语法分析程序构造的分析树或语法树，S-属性文法的属性值可以通过对树进行简单的自底向上或后序遍历来计算。5.1属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院21voidPost(T:treenode)foreachchildCofTd
10、oPost(C)computeallsynthesizedattributesofT树遍历的合成属性的计算machunyan西北工业大学软件与微电子学院22例5.2：撰写下述简单整型算术表达式文法的val(十进制值)属性的属性文法。expexp+term|exp-term|termtermtermfactor|factorfactor(exp)|number5.1属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院23文法规则语义规则exp1exp2+termexp1.val=exp2.val+term.valexp1exp2-termexp1.val=exp2.val-te
11、rm.valexptermexp.val=term.val5.1属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院24term1term2factorterm1.val=term2.valfactor.valtermfactorterm.val=factor.valfactor(exp)factor.val=exp.valfactornumberfactor.val=number.val文法规则语义规则5.1属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院25-42（34-3）42的抽象语法树343对于上述简单整型算术表达式文法，假设表达式(34-3)
12、42语法分析的结果如下：5.1属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院26o如果把分析树中对应该文法符号的节点看成是一条记录，其中，那么属性，就相当于一个域的名字。上页抽象语法树的定义如下：typedefenumPlusMinusTimesOpKindtypedefenumOpKindConstKindExpKindtypedefstructstreenodeExpKindkindOpKindopstructstreenodelchildrchildintvalSTreeNodetypedefSTreeNodeSyntaxTree5.1属性和属性文法-合成属性ma
13、chunyan西北工业大学软件与微电子学院27o后序遍历语法树计算val属性的伪代码：n树节点的属性值由该节点所用产生式的语义规则来定义(计算)。n后序遍历语法树.doc5.1属性和属性文法-合成属性machunyan西北工业大学软件与微电子学院28-42343val=34val=3val=42val=34-3=31val=3142=1302表达式(34-3)42对应的加了注释的抽象语法树如下：machunyan西北工业大学软件与微电子学院29o从语法分析树角度看，一个节点的某一属性值是由父结点和或兄弟结点的属性值来计算，则该属性称为继承属性。o继承属性的计算可以通过对分析树或语法树的前序遍历
14、或前序和中序遍历的组合来进行用伪代码表示：5.1属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院30voidPre(T:treenode)foreachchildCofTdocomputeallinheritedattributesofCPre(C)继承属性的计算5.1属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院31例5.3：对于文法decltypevar-listtypeint|floatvar-listidvar-list|id试写出有关属性dtype(数据类型)的属性文法:5.1属性和属性文法-继承属性machunyan西北工业大学软件与微
15、电子学院32文法规则语义规则decltypevar-listtypeinttypefloatvar-list.dtype=type.dtypetype.dtype=integertype.dtype=real5.1属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院33ovar-list1idvar-list2ovar-listidid.dtype=var-list1.dtypevar-list2.dtype=var-list1.dtypeid.dtype=var-list.dtype文法规则语义规则5.1属性和属性文法-继承属性machunyan西北工业大学软件与微电子学院
16、34考虑符号串floatxy的分析树计算节点dtype属性的递归程序的伪代码如下：ididdecltypevar-listvar-listfloat(dtype=real)(dtype=real)(dtype=real)(dtype=real)(dtype=real)machunyan西北工业大学软件与微电子学院35voidType(T:treenode)casenodekindofTofdecl:Type(firstchildofT)T.secondchild.dtype=T.firstchild.dtypeType(secondchildofT)type:ifchildofT=intT.dtype:=integerelseT.dtype:=realmachunyan西北工业大学软件与微电子学院36var-list:T.firstchild.dtype=T.dtypeifthirdchildofTisnotnilT.third
