语义分析-语义处理概述

1、语义分析-语义处理概述 第八章第八章 语义分析语义分析 8.1 语义处理概述语义处理概述 8.2 属性文法和语法制导翻译属性文法和语法制导翻译 8.3 中间代码的形式中间代码的形式 8.4 中间代码生成中间代码生成(典型语句的翻译典型语句的翻译) 8.4 语义分析-语义处理概述 源语言程序源语言程序 中间代码中间代码 汇编代码汇编代码 词法分析词法分析 语义分析语义分析 语法分析语法分析 中间代码生成中间代码生成 代码生成代码生成 在编译中的逻辑阶段在编译中的逻辑阶段 前端处理前端处理 后端处理后端处理 语义处理语义处理 8.18.1语义处理语义处理（语义分析和中间代码生成）（语义分析和中间代

2、码生成） 语义分析-语义处理概述 源语言程序源语言程序 汇编代码汇编代码 词法分析词法分析 语义分析语义分析 语法分析语法分析 代码生成代码生成 前端处理前端处理后端处理后端处理 语义处理 语义处理 8.18.1语义处理（语义分析）语义处理（语义分析） 语义分析-语义处理概述 语义处理的任务语义处理的任务 4静态语义检查 静态语义：语法规则的良形式条件 静态语义检查：审查静态语义 4动态语义处理 动态语义：程序单元执行的操作 动态语义处理：生成(中间/目标)代码 语义分析-语义处理概述 语义语义处理处理的实现的实现 4属性文法：描述语义规则。 4语法制导翻译：在语法分析的同时，执 行语义规则描

3、述的动作： 检查静态语义 生成中间代码/目标代码 语义分析-语义处理概述 语义处理语义处理的环境：符号表的环境：符号表 4为语义分析提供类型、作用域等信息。 4为代码生成提供类型、作用域、存储类 别、存储（相对）位置等信息。 语义分析-语义处理概述 归纳：语义分析（静态语义处理）归纳：语义分析（静态语义处理） （1）类型检查。验证程序中执行的每个操作是否遵守语言的类型）类型检查。验证程序中执行的每个操作是否遵守语言的类型 系统的过程系统的过程.，编译程序必须报告不符合类型系统的信息。，编译程序必须报告不符合类型系统的信息。 （2）控制流检查。控制流语句必须使控制转移到合法的地方。例）控制流检查

4、。控制流语句必须使控制转移到合法的地方。例 如，在如，在C语言中语言中break语句使控制跳离包括该语句的最小语句使控制跳离包括该语句的最小while、for 或或switch语句。如果不存在包括它的这样的语句，则就报错。语句。如果不存在包括它的这样的语句，则就报错。 （3）一致性检查。在很多场合要求对象只能被定义一次。例如）一致性检查。在很多场合要求对象只能被定义一次。例如 Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一语言规定同一标识符在一个分程序中只能被说明一次，同一 case语句的标号不能相同，枚举类型的元素不能重复出现等等。语句的标号不能相同，枚举类型的元素不能重复

5、出现等等。 （4）相关名字检查。有时，同一名字必须出现两次或多次。例如，）相关名字检查。有时，同一名字必须出现两次或多次。例如， Ada 语言程序中，循环或程序块可以有一个名字，出现在这些结构语言程序中，循环或程序块可以有一个名字，出现在这些结构 的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。 （5）名字的作用域分析）名字的作用域分析 语义分析-语义处理概述 归纳：语义分析（通俗说法）归纳：语义分析（通俗说法） 给你一段文字英文，已经完成语法分 析，要你进行语义分析。(自然语言的语义 分析) 静态语义部分：该单词是否是词典中

6、 的单词,确定每个单词的具体含义(查字典)， 判断是否有不符合逻辑的含义（词与词之 间是否搭配，apple eats a boy）。 动态语义部分：生成汉语翻译，对需 要调整句子结构的进行调整等等。 语义分析-语义处理概述 类型检查程序的设计类型检查程序的设计( (可选可选) ) 1.辨认语言中可用的类型 2.辨认具有类型的语言结构 3.辨认语言的语义规则 基础 类型的基本概念 语义分析-语义处理概述 类型的基本概念类型的基本概念( (可选可选) ) 4数据类型的三要素： 用于区别这种数据类型的数据对象的属性 这种类型数据对象可以具有的值 可以施用在这种类型的数据对象上的操作 4数据类型分为：

7、 基本(初等)数据类型：数值数据,逻辑数据,字 符数据,指针类型等。 复合数据类型：数组、结构、表、栈、树等。 抽象数据类型:Ada的包(Package),C+的类 (Class)等。 语义分析-语义处理概述 类型的等价关系和相容关系类型的等价关系和相容关系( (可选可选) ) 等价关系 如果在任何场合下，类型A和类型B的表达 式都可以互相替代，则称类型A与类型B等 价。 4相容关系 如果在类型A的表达式出现的任何场合下， 都可以用类型B的表达式替换，则称类型B 相容于类型A。 语义分析-语义处理概述 声明和定义声明和定义( (可选可选) ) 4声明： 程序通过声明语句把标识符的名称、类型和

8、作用域等信息传递给编译器。 声明语句本身传递名字和类型信息，声明语 句的位置传递作用域信息。 4定义： 变量、类的声明就是定义。 函数可以先声明一个原型，在定义中再给出 实现的代码。 语义分析-语义处理概述 强类型语言和弱类型语言强类型语言和弱类型语言 ( (可选可选) ) 强类型语言 标识符必须先声明后才能使用。 标识符的类型信息在编译时是已知的。 例如：PASCAL, C 4弱类型语言 标识符不声明就可以直接引用。 标识符的类型信息在编译时不能确定，在运 行时推测得到。 例如：Lisp，ML 语义分析-语义处理概述 运算符运算符( (函数函数) )的重载与多态函数的重载与多态函数( (可选

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

10、域( (可选可选) ) 作用域类型: 4Global scope 在任何函数和类定义之外的区域。 所声明的标识符具有全局作用域。 4Class scope 特指类定义的作用域。 所声明的类类型具有全局作用域。 所声明的类成员具有类作用域。 4Function scope 特指函数形参表中参数的作用域。 所声明的函数具有全局作用域,或类作用域,或其它局部作用域。 所声明的形参具有函数作用域。 4Local scope 由定界符 /begin end分隔，定义在过程(函数)体或其它局部作用域 (分程序)内。 所声明的标识符具有局部作用域。 语义分析-语义处理概述 分程序结构语言的作用域规则分程序结

11、构语言的作用域规则( (可选可选) ) 4当前开放的作用域中的标识符才能够被访问； 4在同一作用域中，不允许声明同名的标识符； 4在不同的作用域中，内层声明的标识符将遮蔽外 层声明的同名标识符，使其变为不可见的。 int a； chara； floata； a 引用引用char a; 4函数形参表中的变量在函数体中是可见的； int a; floatfunc（float a，float b） a a引用引用float a;float a; 语义分析-语义处理概述 分程序结构语言作用域举例分程序结构语言作用域举例( (可选可选) ) (1) main() (2) int a; (3) (4) (

12、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中可见中可见 程序运行到第程序运行到

13、第12行时：行时： scope 4是当前作用域；是当前作用域； scope 1, 2, 4是开放的作用域；是开放的作用域； scope 3是关闭的作用域。是关闭的作用域。 scope 4 语义分析-语义处理概述 8.28.2属性文法和语法制导翻译属性文法和语法制导翻译 1、属性文法概述 2、基于属性文法的处理方法 3、S-属性文法和自下而上翻译 4、L-属性文法在自下而上分析中实现 以上也是在实际应用中比较流行的语义描述和语义处理 的方法 语义分析-语义处理概述 语义形式化语义形式化( (语义建模语义建模) ) 形式语义学(如指称语义学、公理语义学、 操作语义学等)的研究已取得了许多重大的进展

14、 文法模型-属性文法 命令式或操作式模型-操作语义学 应用式模型-指称语义学 公理式模型-公理语义学 语义分析-语义处理概述 程序设计语言的语义程序设计语言的语义 静态语义静态语义 是对程序约束的描述，这些约束无法通过抽象语 法规则来妥善地描述，实质上就是语法规则的良形式条 件，它可以分为类型规则和作用域/可见性规则两大类。 如：类型相容性、变量先声明后引用、名称相关要求 动态语义动态语义 程序单位描述的计算 编译程序的语义处理工作 静态语义审查静态语义审查 执行动态语义执行动态语义（计算）生成代码. 语语 法法 分分 析析 后后 的的 源源 程程 序 序 语义处理语义处理 语义分析-语义处理

15、概述 8.2.18.2.1属性文法属性文法 通常就是高级语言代码 属性文法(attribute grammar)是一个三元组： A=(G,V,F),其中 G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一个终结符或 非终结符相连，这些属性代表与文法符号相关信 息，如它的类型、值、代码序列、符号表内容等 等。属性与变量一样属性与变量一样，可以进行计算和传递。属 性加工的过程即是语义处理的过程。 F:关于属性的属性断言或一组属性的计算规则(称 为语义规则语义规则) . 断言或语义规则与一个产生式相联, 引用该产生式左端或右端的终结符或非终结符相 联的属性。 语义分析-语义处理概述 属性

16、通常分为两类：属性通常分为两类：综合属性和继承属性 简单地说，综合属性用于“自下而上”传递信息，而继承 属性用于“自上而下”传递信息。 属性文法中，对应于每个产生式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 的继承属性继承属性 在两种情况下，我

17、们都说属性b依赖于属性c1,c2ck. 1)非终结符既可有综合属性也可有继承属性，但文法开始 符号没有继承属性. 2)终结符只有综合属性,它们由词法程序提供. 语义分析-语义处理概述 属性计算规则属性计算规则 一般，对出现在产生式左边的继承属性和出现在产 生式右边的综合属性都必须提供一个计算规则。属性计属性计 算规则算规则中只能使用相应产生式中的文法符号的属性。 （？）然而，出现在产生式左边的继承属性和出 现在产生式右边的综合属性不由所给定的产生式的属性 计算规则进行计算，它们由其它产生式的属性规则计算 或者由属性计算器属性计算器的参数提供。 AX1 X2 Xn A的综合属性S(A)计算公式

18、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是在其他地方计算的。 语义分析-语义处理概述 语义规则的描述语义规则的描述 语义规则所描述的工作可以包括：属性计算、静态 语义检查、符号表操作、代码（中间）生成等等。 有些语义规则可能产生副作用（如产生代码），也 可能是个函数，通常把这样的语义规则写成过程调用或 过程段 语义

19、分析-语义处理概述 例子例子1 1：综合属性：综合属性 语 义 规 则 L E E E1+T E T T T1 * F T F F (E) F digit Print(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval 产 生 式 非终结符E、T及F都有一个综合属性val ，符号digit有一个综合 属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅 仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规 则定义了L的一个

20、虚属性。某些非终结符加上标是为了区分一个产生 式中同一非终结符多次出现。 (G,V,F) 分别是? 语义分析-语义处理概述 例子例子1 1 （续）（续） L E.val=19 E.val=15T.val=4 T.val=15F.val=4 T.val=3 F.val=3 F.val=5 digit.lexval=4 digit.lexval=5 digit.lexval=3 + * 3*5+4的带注释的分析树的带注释的分析树 设表达式为设表达式为35+4，则语义动作打印数值，则语义动作打印数值19 语义分析-语义处理概述 例子例子2 2：继承属性：继承属性 生 产 式 语 义 规 则 D TL

21、 T int T real L L1,id L id L.in:=T.type T.type:=integer T.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) 一个结点的继承属性值是由此结点的父结点和（/或） 兄弟结点的某些属性来决定的。 注：注：addtype(id.entry, L.in)把每个标识符的类型信息（把每个标识符的类型信息（L.in） 登录在符号表的相关项中登录在符号表的相关项中 语义分析-语义处理概述 例子例子2 2 （续）（续） D L.in= real L.in= real L.

22、in= real T.type=real real id2 id1 id3 . Real id1,id2,id3 每个每个L结点都带有继承属性的语法树结点都带有继承属性的语法树 ， ， 语义分析-语义处理概述 8.2.28.2.2基于属性文法的处理过程基于属性文法的处理过程 从概念上讲，基于属性文法的处理过程（即 语法制导翻译）通常是这样的：对单词符号串进 行语法分析，构造语法分析树，然后根据需要构 造属性依赖图,遍历语法树并在语法树的各结点 处按语义规则进行计算。 输入符号串 语法分析树 属性依赖图 语义规则的计算顺序 语义分析-语义处理概述 依赖图依赖图 由称为依赖图的一个有向图 描述分析

23、树中的继承属性 和属性中间的相互依赖关系。 依赖图的构造算法：依赖图的构造算法： 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结点构造一条有向边 语义分析-语义处理概述 依赖图的例子依赖图的例子 生 产 式 语 义 规 则 D TL T int T real L L1,id L id L.in:=T.type T.type:=integer T.type:=rea

24、l L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) 继承属性继承属性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

25、,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。 1. 每一个与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以前都是可用的。 属性文法属性文法说明的翻译是很精确的