《编译课件第八章》由会员分享，可在线阅读，更多相关《编译课件第八章（87页珍藏版）》请在金锄头文库上搜索。
1、第八章语法制导翻译和中间代码生成,8.1概述 8.2属性文法和语法制导翻译 8.3语义分析 8.4中间代码 8.5一些语句的翻译,本章要研究的编译程序阶段是计算编译过程所需的附加信息。这个阶段称作语义分析，因为它包括计算上下文无关文法和标准分析算法以外的信息，因此，它不被看成是语法。 语义分析可以分为两类。 第1类是程序的分析，要求根据编程语言的规则建立其正确性，并保证其正确执行。对于不同的语言来说，语言定义所要求的这一类分析的总量变化很大。 第2类是由编译程序执行的分析，用以提高翻译程序执行的效率。这一类分析通常包括对“最优化”或代码改进技术的讨论。 这两类分析也不是相互排斥的，如静态类型检
2、查这样的正确性要求能使编译程序产生更加有效的代码。,静态语义分析包括执行分析的描述( d e s c r i p t i o n ) 和使用合适的算法对分析的实现( i m p l e m e n t a t i o n )。 在语义分析中，情形不是那么清晰，其部分原因是没有用标准的方法(如B N F )来说明语言的静态语义；另一个原因是对于各种语言，静态语义分析的种类和总量的变化范围很大。 编译程序编写者过去常用的且实现得很好的一种描述语义分析方法是：属性文法,因为编译器完成的分析是静态(它在执行之前发生)定义的，这样，语义分析也可称作静态语义分析(static semantic analy
3、sis)。 在一个典型的静态类型的语言(如C语言)中，语义分析包括构造符号表、记录声明中建立的名字的含义、在表达式和语句中进行类型推断和类型检查以及在语言的类型规则作用域内判断它们的正确性。,编译中的语义处理是指两个功能： 第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。 第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。,静态语义分析通常包括： 类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.，编译程序必须报告不符合类型系
4、统的信息。 控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。 一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。 相关名字检查。有时，同一名字必须出现两次或多次。例如，Ada 语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。 名字的作用域分析,编译程序的语义处理工作 静态语义
5、审查 解释执行动态语义 （计算）生成代码.,8.1 属性文法,语义形式化语义建模 文法模型-属性文法 命令式或操作式模型 -操作语义学 应用式模型-指称语义学 公理式模型-公理语义学,操作语义,描述一段程序的含义是通过执行该段程序所改变的计算机（虚拟计算机）状态来反映。这个计算机的状态与程序执行时的状态相对应：包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。计算机里所有的寄存器的值和存储单元的值作为计算机的状态，用一组形式定义的操作来说明执行一条指令相应的状态怎样变化。 For (expr1;expr2;expr3) expr1; . Loop:if expr2=0 goto o
6、ut expr3; goto loop out: .,公理语义,一个语言的每个语法成分的含义定义为公理和演绎规则，用于推导出该成分执行的效果。 公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。 一般的记号 P S Q 如果在语句S执行前P为真，则在语句S执行并终止后Q为真。,演绎规则的例子 规则 前驱 后继 赋值：x:=expr P(expr)x:=exprP(x) While: P B S P P while B do S end P (not
7、 B) if-then-else B P S1 Q, (not B) P S2 Q P if B then S1 else S2Q,指称语义,指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数 语义函数： 程序设计语言的语义利用映射函数来证 明。,例： 二进制数语言 110或10101 语法实体 指称（自然数） 6 或 21 语义实体 二进制数文法 Numeral:=0 :=1 := Numeral 0 :=Numeral 1 自然数 Natrual=0,1,2,3, 语义函数 Valuation:NumeralNatural,Valuat
8、ion101 表示把Valuation施用于101 ValuationN - 把它施用于N 定义: Valuation（用四个方程)因为有四个形式numeral Valuation0 0 Valuation1 1 ValuationN0 2Valuation N ValuationN1 2Valuation N+1 所以： Valuation110=2 Valuation11 = 2 (2 Valuation1+1) =2 (2 1+1) =6,属性文法和语法制导翻译,虽然形式语义学(如指称语义学、公理语义学、操作语义学等)的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语
9、义处理的方法主要还是属性文法和语法制导翻译方法,属性文法,确定语言实体的属性( a t t r i b u t e )或特性，它们必须进行计算并写成属性等式(attribute equation)或语义规则(semantic rule)，并描述这些属性的计算如何与语言的文法规则相关。 这样的一组属性和等式称作属性文法(attribute grammar)。 属性文法对遵循语法制导语义(syntax-directed semantic)原理的语言最有用，它表明程序的语义内容与它的语法密切相关。所有的现代语言都有这个特性。,编译程序的编写者通常必须根据语言手册手工构造属性文法，因为语言设计者很少为
10、之提供。 更糟糕的是，由于坚持语言清晰的语法结构，属性文法的构造会有不必要的复杂性。 它是由编译过程中分析的时间选择引起的。如果语义分析可以推迟到所有的语法分析(以及抽象语法树的构造)完成之后进行，那么实现语义分析的任务就相当容易，其本质上由指定对语法树遍历的一个顺序组成，同时在遍历中每次遇到节点时进行计算。这就意味着编译程序必须是多遍的。另一方面，如果必须要求编译程序在一遍中完成所有的操作(包括代码生成)，那么语义分析的实现就更加会变成寻找计算语义信息的正确顺序和方法的特别的过程。,属性文法,属性文法(attribute grammar)是一个三元组: A=(G,V,F),其中 G:是一个上
11、下文无关文法 V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等 .属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。 F:关于属性的属性断言或一组属性的计算规则(称为语义规则) . 断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.,类型检查的属性文法,ET+T| T or T Tnum| true|false ET1 + T2 T1.type = int T2.type= int E.type :=int E T1 or T2 T1.type = boo
12、l T2.type= bool E.type :=bool T num T.type := int T true T.type := bool T false T.type := bool,属性有两种 继承的和综合的属性,属性通常分为两类：综合属性和继承属性。简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由计算器的参数提供。 AX1 X2 Xn A的综合属性,计算 S(A):=f(I(X1),I(Xn) Xj的继承属性,计算 T(
13、Xj):=f(I(A),. I(Xn) 1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性. 2)终结符只有综合属性.,在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为b:=f(c1,c2ck) 这里，f是一个函数，而且或者 （1）b是A的一个综合属性并且c1,c2ck是产生式右边文法符号的属性;或者 （2）b是产生式右边某个文法符号的一个继承属性并且c1,c2ck是A或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性b依赖于属性c1,c2ck 。,一个属性文法的例子: 非终结符E、T及F都有一个综合属性val,符号digit有一个
14、综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。,语 义 规 则,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,产 生 式,设表达式为35+4，则语义动作打印数值19,.,L,E.val=19,E.val=15,T.val=4,T.val=
15、15,F.val=4,T.val=3,F.val=3,F.val=5,digit.lexval=4,digit.lexval=5,digit.lexval=3,+,*,3*5+4的带注释的分析树,继承属性,一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。 例 描述说明语句中各种变量的类型信息的语义规则，这个例子里，继承属性L.in 在说明中为各个标识符提供类型信息。,产生式,语 义 规 则,D TL,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),句子int id1,id2的语法树，使用=表示属性的传递情况。,属性文法看作是允许为每个终结符和非终结符配备一些
