编译原理第16讲(第八章).ppt

《编译原理第16讲(第八章).ppt》由会员分享，可在线阅读，更多相关《编译原理第16讲(第八章).ppt（38页珍藏版）》请在三一办公上搜索。

1、第八章 语义分析,8.1 语义处理概述8.2 属性文法和语法制导翻译8.3 中间代码的形式8.4 中间代码生成(典型语句的翻译)8.4 符号表,源语言程序,中间代码,汇编代码,词法分析,语义分析,语法分析,中间代码生成,代码生成,在编译中的逻辑阶段,前端处理,后端处理,语义处理,8.1语义处理（语义分析和中间代码生成）,源语言程序,汇编代码,词法分析,语义分析,语法分析,代码生成,前端处理,后端处理,语义处理,8.1语义处理（语义分析）,语义处理的任务,静态语义检查静态语义：语法规则的良形式条件静态语义检查：审查静态语义动态语义处理动态语义：程序单元执行的操作动态语义处理：生成(中间/目标)代

2、码,语义处理的实现,属性文法：描述语义规则。语法制导翻译：在语法分析的同时，执行语义规则描述的动作：检查静态语义生成中间代码/目标代码,语义处理的环境：符号表,为语义分析提供类型、作用域等信息。为代码生成提供类型、作用域、存储类别、存储（相对）位置等信息。,归纳：语义分析（静态语义处理）,（1）类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.，编译程序必须报告不符合类型系统的信息。（2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。（3）一致

3、性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。（4）相关名字检查。有时，同一名字必须出现两次或多次。例如，Ada 语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。（5）名字的作用域分析,归纳：语义分析（通俗说法）,给你一段文字英文，已经完成语法分析，要你进行语义分析。(自然语言的语义分析)静态语义部分：该单词是否是词典中的单词,确定每个单词的具体含义(查字典)，判断是否有不符合逻辑的含义（词与词之间是否搭配，

4、apple eats a boy）。动态语义部分：生成汉语翻译，对需要调整句子结构的进行调整等等。,类型检查程序的设计(可选),1.辨认语言中可用的类型2.辨认具有类型的语言结构3.辨认语言的语义规则基础 类型的基本概念,类型的基本概念(可选),数据类型的三要素：用于区别这种数据类型的数据对象的属性 这种类型数据对象可以具有的值 可以施用在这种类型的数据对象上的操作数据类型分为：基本(初等)数据类型：数值数据,逻辑数据,字符数据,指针类型等。复合数据类型：数组、结构、表、栈、树等。抽象数据类型:Ada的包(Package),C+的类(Class)等。,类型的等价关系和相容关系(可选),等价关系

5、如果在任何场合下，类型A和类型B的表达式都可以互相替代，则称类型A与类型B等价。相容关系如果在类型A的表达式出现的任何场合下，都可以用类型B的表达式替换，则称类型B相容于类型A。,声明和定义(可选),声明：程序通过声明语句把标识符的名称、类型和作用域等信息传递给编译器。声明语句本身传递名字和类型信息，声明语句的位置传递作用域信息。定义：变量、类的声明就是定义。函数可以先声明一个原型，在定义中再给出实现的代码。,强类型语言和弱类型语言(可选),强类型语言标识符必须先声明后才能使用。标识符的类型信息在编译时是已知的。例如：PASCAL,C弱类型语言标识符不声明就可以直接引用。标识符的类型信息在编译

6、时不能确定，在运行时推测得到。例如：Lisp，ML,运算符(函数)的重载与多态函数(可选),重载运算符（overloading operator）是指该符号有多个含义,但根据上下文可以确定唯一的运算。如是重载符号，在AB中，当A和B为整数、实数、复数或者矩阵时，运算符执行不同类型的运算.当出现重载运算符时，要确定它所表示的唯一的意义，即进行运算符识别并检查运算符的操作数。多态函数(过程)-函数(过程)允许参数的类型变化.多态函数(过程)的特点是，每次被调用时，传递过来的参数可以具有不同类型。,作用域分析(可选),分程序结构的作用域规则作用域分析的实现,作用域(可选),作用域类型:Global

7、scope在任何函数和类定义之外的区域。所声明的标识符具有全局作用域。Class scope特指类定义的作用域。所声明的类类型具有全局作用域。所声明的类成员具有类作用域。Function scope特指函数形参表中参数的作用域。所声明的函数具有全局作用域,或类作用域,或其它局部作用域。所声明的形参具有函数作用域。Local scope由定界符/begin end分隔，定义在过程(函数)体或其它局部作用域(分程序)内。所声明的标识符具有局部作用域。,分程序结构语言的作用域规则(可选),当前开放的作用域中的标识符才能够被访问；在同一作用域中，不允许声明同名的标识符；在不同的作用域中，内层声明的标识

8、符将遮蔽外层声明的同名标识符，使其变为不可见的。int a；chara；floata；a 引用char a;函数形参表中的变量在函数体中是可见的；int a;floatfunc（float a，float b）a引用float a;,分程序结构语言作用域举例(可选),(1)main()(2)int a;(3)(4)(5)bool a;(6)(7)(8)double a;(9)(10)a(14)(15)(16),scope 3,scope 2,scope 1,scope 1:(1)-(16)scope 2:(4)-(14)嵌套于scope 1中 scope 3:(7)-(10)嵌套于scope

9、2中 scope 4:(11)-(12)嵌套于scope 2中 a(int)在scope 1中可见；a(bool)在scope 2,4中可见；a(double)在scope 3中可见程序运行到第12行时：scope 4是当前作用域；scope 1,2,4是开放的作用域；scope 3是关闭的作用域。,scope 4,8.2属性文法和语法制导翻译,1、属性文法概述2、基于属性文法的处理方法3、S-属性文法和自下而上翻译4、L-属性文法在自下而上分析中实现以上也是在实际应用中比较流行的语义描述和语义处理的方法,语义形式化(语义建模),形式语义学(如指称语义学、公理语义学、操作语义学等)的研究已取得

10、了许多重大的进展文法模型-属性文法命令式或操作式模型-操作语义学应用式模型-指称语义学公理式模型-公理语义学,程序设计语言的语义,静态语义 是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域/可见性规则两大类。如：类型相容性、变量先声明后引用、名称相关要求动态语义 程序单位描述的计算编译程序的语义处理工作 静态语义审查 执行动态语义（计算）生成代码.,8.2.1属性文法,通常就是高级语言代码,属性文法(attribute grammar)是一个三元组：A=(G,V,F),其中 G:是一个上下文无关文法V:有穷的属性集,每个属

11、性与文法的一个终结符或非终结符相连，这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。F:关于属性的属性断言或一组属性的计算规则(称为语义规则).断言或语义规则与一个产生式相联,引用该产生式左端或右端的终结符或非终结符相联的属性。,属性通常分为两类：综合属性和继承属性,简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为b:=f(c1,c2ck)。f是一个函数，b和c1,c2ck是该产生式文法符号的

12、属性.并且（1）如果b是A的一个属性，c1,c2ck是产生式右部文法符号的属性（或A的其他属性）,则称b是A的综合属性（2）如果 b是产生式右部某个文法符号X的一个属性,并且c1,c2ck是A（或产生式右边任何文法符号）的属性,则称b是文法符号X 的继承属性在两种情况下，我们都说属性b依赖于属性c1,c2ck.1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性.2)终结符只有综合属性,它们由词法程序提供.,属性计算规则,一般，对出现在产生式左边的继承属性和出现在产生式右边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。（？）然而，出现在产

13、生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。AX1 X2 XnA的综合属性S(A)计算公式 S(A):=f(I(X1),I(Xn)Xj的继承属性T(Xj)计算公式 T(Xj):=f(I(A),.I(Xn)如：非终结符A,B和C，其中A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d。对产生式A-BC可能有语义规则 C.d:=B.c+1和A.b:=A.a+B.c 而属性A.a和 B.c是在其他地方计算的。,语义规则的描述,语义规则所描述的工作可以包括：属性计算、静态语义检查、符号

14、表操作、代码（中间）生成等等。有些语义规则可能产生副作用（如产生代码），也可能是个函数，通常把这样的语义规则写成过程调用或过程段,例子1：综合属性,非终结符E、T及F都有一个综合属性val，符号digit有一个综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现。,(G,V,F)分别是?,例子1（续）,设表达式为35+4，则语义动作打印数值19,例子2：继承属性,一个结点的继承属性值是由此结点的父结点和（/或）兄弟结点的某些属性来决定的。,注

15、：addtype(id.entry,L.in)把每个标识符的类型信息（L.in）登录在符号表的相关项中,例子2（续）,D,L.in=real,L.in=real,L.in=real,T.type=real,real,id2,id1,id3,.,Real id1,id2,id3每个L结点都带有继承属性的语法树,，,，,8.2.2基于属性文法的处理过程,从概念上讲，基于属性文法的处理过程（即语法制导翻译）通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算。输入符号串 语法分析树 属性依赖图 语义规则的计算顺序,依赖图

16、,由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。依赖图的构造算法：for 分析树中每一个结点n do for 结点的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for 分析树中每一个结点n do for 结点n所用产生式对应的每一个语义规则 b:=f(c1,c2,ck)do for i:=1 to k do 从ci结点到b结点构造一条有向边,依赖图的例子,继承属性L.in,依赖图的例子（依赖图的表示）,5,6,7,8,9,10,T,4,D,L,L,L,Real,type,in,in,in,3 entry,2 entry,1 entry,id3,id2,

17、id1,Real id1,id2,id3分析树的依赖图(图中的结点用数字表示),依赖图的例子（依赖图的说明）,Real id1,id2,id3分析树的依赖图的说明依赖图中的结点由数字来标识。从代表T.type的结点4有一条有向边连到代表L.in的结点5，因为根据产生式DTL的语义规则L.in:=T.type,可知L.in依赖于T.type.根据产生式L L1,id的语义规则L1.in:=L.in，可知L1.in依赖于L.in，所以有两条向下的有向边分别进入结点7和9。每一个与L产生式有关的语义规则addtype(id.Entry,L.in)都产生一个虚属性，结点 6、8和10都是为这些虚属性构

18、造的。,属性的计算顺序,一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,mk，使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。一个依赖图的任何拓扑排序，都给出一个分析树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，对一个结点，语义规则b:=f(c1,c2,ck)中的属性c1,c2,ck在计算b以前都是可用的。属性文法说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树，依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序，用这个顺序来计算语义规则就得到输入符号串的

19、翻译。,良定义的属性文法,很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的循环依赖关系。如，p、c1、c2都是属性，若有下求值规则：p:=f1(c1)、c1:=f2(c2)、c2:=f3(p)时，就无法对p求值。如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。,依赖图的例子（属性计算顺序）,再考查例子 Real id1,id2,id3分析树的依赖图 每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可

20、以得到下列程序，用an来代表依赖图中与序号n的结点有关的属性：a4:=reala5:=a4 addtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7)a9:=a7 addtype(id1.entry,a9)这些语义规则的计算将把real类型填入到每个标识符对应的符号表项中。,属性的计算方法,树遍历的属性计算方法设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。一遍扫描的处理方法 与树遍历的属性计算文法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且并无需构造实际的语法树。因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：（1）所采用的语法分析方法（2）属性的计算次序。,在某些情况下可用一遍扫描实现属性文法的语义规则计算。也就是说在语法分析的同时完成语义规则的计算，无须明显地构造语法树或构造属性之间的依赖图。因为单遍实现对于编译效率非常重要,