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

第八章 语义分析,8.1 语义处理概述 8.2 属性文法和语法制导翻译 8.3 中间代码的形式 8.4 中间代码生成(典型语句的翻译) 8.4 符号表,源语言程序,中间代码,汇编代码,词法分析,语义分析,语法分析,中间代码生成,代码生成,在编译中的逻辑阶段,前端处理,后端处理,语义处理,8.1语义处理（语义分析和中间代码生成）,源语言程序,汇编代码,词法分析,语义分析,语法分析,代码生成,前端处理,后端处理,语义处理,8.1语义处理（语义分析）,语义处理的任务,静态语义检查 静态语义：语法规则的良形式条件 静态语义检查：审查静态语义 动态语义处理 动态语义：程序单元执行的操作 动态语义处理：生成(中间/目标)代码,语义处理的实现,属性文法：描述语义规则。 语法制导翻译：在语法分析的同时，执行语义规则描述的动作： 检查静态语义 生成中间代码/目标代码,语义处理的环境：符号表,为语义分析提供类型、作用域等信息。 为代码生成提供类型、作用域、存储类别、存储（相对）位置等信息。,归纳：语义分析（静态语义处理）,（1）类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.，编译程序必须报告不符合类型系统的信息。 （2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。 （3）一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。 （4）相关名字检查。有时，同一名字必须出现两次或多次。例如，Ada 语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。 （5）名字的作用域分析,归纳：语义分析（通俗说法）,给你一段文字英文，已经完成语法分析，要你进行语义分析。(自然语言的语义分析) 静态语义部分：该单词是否是词典中的单词,确定每个单词的具体含义(查字典)，判断是否有不符合逻辑的含义（词与词之间是否搭配，apple eats a boy）。 动态语义部分：生成汉语翻译，对需要调整句子结构的进行调整等等。,类型检查程序的设计(可选),1.辨认语言中可用的类型 2.辨认具有类型的语言结构 3.辨认语言的语义规则 基础 类型的基本概念,类型的基本概念(可选),数据类型的三要素： 用于区别这种数据类型的数据对象的属性 这种类型数据对象可以具有的值 可以施用在这种类型的数据对象上的操作 数据类型分为： 基本(初等)数据类型：数值数据,逻辑数据,字符数据,指针类型等。 复合数据类型：数组、结构、表、栈、树等。 抽象数据类型:Ada的包(Package),C+的类(Class)等。,类型的等价关系和相容关系(可选),等价关系 如果在任何场合下，类型A和类型B的表达式都可以互相替代，则称类型A与类型B等价。 相容关系 如果在类型A的表达式出现的任何场合下，都可以用类型B的表达式替换，则称类型B相容于类型A。,声明和定义(可选),声明： 程序通过声明语句把标识符的名称、类型和作用域等信息传递给编译器。 声明语句本身传递名字和类型信息，声明语句的位置传递作用域信息。 定义： 变量、类的声明就是定义。 函数可以先声明一个原型，在定义中再给出实现的代码。,强类型语言和弱类型语言 (可选),强类型语言 标识符必须先声明后才能使用。 标识符的类型信息在编译时是已知的。 例如：PASCAL, C 弱类型语言 标识符不声明就可以直接引用。 标识符的类型信息在编译时不能确定，在运行时推测得到。 例如：Lisp，ML,运算符(函数)的重载与多态函数(可选),重载运算符（overloading operator）是指该符号有多个含义,但根据上下文可以确定唯一的运算。如是重载符号，在AB中，当A和B为整数、实数、复数或者矩阵时，运算符执行不同类型的运算.当出现重载运算符时，要确定它所表示的唯一的意义，即进行运算符识别并检查运算符的操作数。 多态函数(过程)-函数(过程)允许参数的类型变化.多态函数(过程)的特点是，每次被调用时，传递过来的参数可以具有不同类型。,作用域分析(可选),分程序结构的作用域规则 作用域分析的实现,作用域(可选),作用域类型: Global scope 在任何函数和类定义之外的区域。 所声明的标识符具有全局作用域。 Class scope 特指类定义的作用域。 所声明的类类型具有全局作用域。 所声明的类成员具有类作用域。 Function scope 特指函数形参表中参数的作用域。 所声明的函数具有全局作用域,或类作用域,或其它局部作用域。 所声明的形参具有函数作用域。 Local scope 由定界符 /begin end分隔，定义在过程(函数)体或其它局部作用域(分程序)内。 所声明的标识符具有局部作用域。,分程序结构语言的作用域规则(可选),当前开放的作用域中的标识符才能够被访问； 在同一作用域中，不允许声明同名的标识符； 在不同的作用域中，内层声明的标识符将遮蔽外层声明的同名标识符，使其变为不可见的。 int a； char a； float a； a 引用char a; 函数形参表中的变量在函数体中是可见的； int a; float func（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 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-属性文法在自下而上分析中实现 以上也是在实际应用中比较流行的语义描述和语义处理的方法,语义形式化(语义建模),形式语义学(如指称语义学、公理语义学、操作语义学等)的研究已取得了许多重大的进展 文法模型-属性文法 命令式或操作式模型-操作语义学 应用式模型-指称语义学 公理式模型-公理语义学,程序设计语言的语义,静态语义 是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域/可见性规则两大类。 如：类型相容性、变量先声明后引用、名称相关要求 动态语义 程序单位描述的计算 编译程序的语义处理工作 静态语义审查 执行动态语义（计算）生成代码.,8.2.1属性文法,通常就是高级语言代码,属性文法(attribute grammar)是一个三元组： A=(G,V,F),其中 G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连，这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。 F:关于属性的属性断言或一组属性的计算规则(称为语义规则) . 断言或语义规则与一个产生式相联,引用该产生式左端或右端的终结符或非终结符相联的属性。,属性通常分为两类：综合属性和继承属性,简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。 属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为b:=f(c1,c2ck)。f是一个函数，b和c1,c2ck是该产生式文法符号的属性. 并且 （1）如果b是A的一个属性，c1,c2ck是产生式右部文法符号的属性（或A的其他属性）,则称b是A的综合属性 （2）如果 b是产生式右部某个文法符号X的一个属性,并且c1,c2ck是A（或产生式右边任何文法符号）的属性,则称b是文法符号X 的继承属性 在两种情况下，我们都说属性b依赖于属性c1,c2ck. 1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性. 2)终结符只有综合属性,它们由词法程序提供.,属性计算规则,一般，对出现在产生式左边的继承属性和出现在产生式右边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。 （？）然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。 AX1 X2 Xn A的综合属性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是在其他地方计算的。,语义规则的描述,语义规则所描述的工作可以包括：属性计算、静态语义检查、符号表操作、代码（中间）生成等等。 有些语义规则可能产生副作用（如产生代码），也可能是个函数，通常把这样的语义规则写成过程调用或过程段,例子1：综合属性,非终结符E、T及F都有一个综合属性val ，符号digit有一个综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现。,(G,V,F)分别是?,例子1 （续）,设表达式为35+4，则语义动作打印数值19,例子2：继承属性,一个结点的继承属性值是由此结点的父结点和（/或）兄弟结点的某些属性来决定的。,注：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基于属性文法的处理过程,从概念上讲，基于属性文法的处理过程（即语法制导翻译）通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算。 输入符号串 语法分析树 属性依赖图 语义规则的计算顺序,依赖图,由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。 依赖图的构造算法： 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,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都是为这些虚属性构造的。,属性的计算顺序,一个有向非循环图的拓扑序是图中结点的任何顺序m1, m2, , mk，使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。 一个依赖图的任何拓扑排序，都给出一个分析树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，对一个结点，语义规则b:=f(c1,c2,ck)中的属性c1,c2,ck在计算b以前都是可用的。 属性文法说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树，依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序，用这个顺序来计算语义规则就得到输入符号串的翻译。,良定义的属性文法,很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的循环依赖关系。如，p、c1、c2都是属性，若有下求值规则： p: = f1(c1)、c1: = f2(c2)、c2: = f3(p)时，就无法对p求值。如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。,依赖图的