《 语法制导翻译和中间代码生成new》由会员分享，可在线阅读，更多相关《 语法制导翻译和中间代码生成new（131页珍藏版）》请在金锄头文库上搜索。
1、第八章 语法制导翻译和中间代码生成,【课前思考】 回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。 “属性文法”的概念及应用。 “语法制导翻译”的概念及应用。 什么是中间代码（中间表示），为什么要中间代码？,【学习目标】,明确语义分析在编译过程所处的阶段和作用。 掌握属性文法的基本概念。 使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。主要是要让同学们了解： )语义的描述方式； )语义的处理方法。,【本章重点】,1.几种典型的中间代码（语言）的形式; 2.语义的描述方法着重介绍一种形式化的语义描述方法属性文法; 3.语义的处理方法着重介绍语法制导的翻译法包括它的
2、两种具体形式：语法制导的定义和翻译方案 。,编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。 通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。,8.0 概述,第八章 语法制导翻译和中间代码生成,第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。 第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源
3、程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。 本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式，最后讨论一些语法成分的翻译工作。,编译中的语义处理是指两个功能：,8.1 属性文法(attribute grammar),属性文法(也称属性翻译文法)是Knuth在1968年首先提出的。 它是在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的“特性”（称为属性）。 这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。 属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。,为文法的每
4、个产生式配备的一组属性的计算规则，称为语义规则，称为语义规则。,所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到一个物体，可以用“颜色“描述它，谈起某人，可以使用“有幽默感“来形容他。对编译程序使用的语法树的结点，可以用“类型“、“值“或“存储位置“来描述它。,一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。,所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。,8.1.1 属性文法定义,定义1：形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中： G:是一个上下文无关文法
5、； V:有穷的属性集,每个属性与文法的一个终结符或非终结符相联,这些属性代表与文法符号相关信息； F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。 断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。,定义2：,一个属性文法是一个三元组：A=(G,V,F ),其中 G -基础文法（一个上下文无关文法） V -每个文法符号有一组属性 F -每个文法产生式A有一组形式为b:=f(c1,c2,ck)的语义规则，其中f 是函数，b和c1,c2,ck是该产生式文法符号的属性。,属性文法中的属性分成两类：继承属性和综合属性。,简单地说，综合属性用“自下而上“
6、传递信息，而继承属性用于“自上而下“传递信息。,综合属性（synthesized attribute）：如果b是A的属性，c1 , c2 , , ck是产生式右部文法符号的属性或A的其它属性，则称b是文法符号A的综合属性。 继承属性(inherited attribute)：如果b是产生式右部某个文法符号X的属性，并且c1,c2,ck是A或产生式右部文法符号的属性，则称b是文法符号X的继承属性。,每个文法产生式A有一组形式为b:=f(c1,c2,ck)的语义规则，其中f 是函数，b和c1,c2,ck是该产生式文法符号的属性,属性文法的主要思想是：,1.对每个文法符号引入相关的属性符号； 2.对
7、于每个产生式设置一组计算属性值的属性规则（语义规则），其形式为：b：= f(c1, c2, , ck ) 即：属性变量：= 这里 f是一个函数，且对于产生式A ， (1) b或者是A的一个综合属性并且c1,c2,，ck是产生式右边文法符号的属性； (2) b或者是产生式右边某个文法符号的一个继承属性并且c1,c2,，ck是A或产生式右边任何文法符号的属性。在两种情况下，我们都说属性b依赖于属性c1,c2,，ck。,即：属性规则中的左部b能写那些属性变量是有规定的，只能为下述两种变量： 产生式左部符号的综合属性变量； 产生式右部符号的继承属性变量。,2.对于每个产生式设置一组计算属性值的属性规则
8、（语义规则），其形式为： b：= f(c1, c2, , ck ) 即属性变量：=，这里 f是一个函数，且对于产生式A ， (1) b或者是A的一个综合属性并且c1,c2，ck是产生式右边文法符号的属性； (2) b或者是产生式右边某个文法符号的一个继承属性并且c1,c2，ck是A或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性b依赖于属性c1,c2，ck。,继承属性的求值规则： 产生式左部非终结符号的继承属性值取（来自于）前面产生式右部该符号已有的继承属性值； 产生式右部符号的继承属性值用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算。,体现自顶向下，自左向右
9、的求值特性,体现自底向上，自右向左的求值特性,综合属性的求值规则： 产生式右部非终结符号的综合属性值取（来自于）其下面产生式左部同名非终结符号的综合属性值； 产生式左部非终结符号的综合属性值用该产生式左部符号的继承属性或某个右部符号的属性进行计算；,例8.1 有文法G为： ET1 + T2|T1 or T2 Tnum|true|false 对输入串3+4的类型检查的属性文法如图8.1。,ET1+T2 T1.tint AND T2.tint ET1orT2 T1.tbool AND T2.tbool Tnum T.tint Ttrue T.tbool Tfalse T.tbool,图8.1 类型
10、检查的属性文法,属性文法记号中常使用N.t的形式表示与非终结符N相联的属性t。比如可把对上面表达式的类型检查的属性文法写成图8.1的形式。与每个非终结符T相联的有属性t，t要么是int，要么是bool。与非终结符E的产生式相联的语义规则指明：两个T的属性必须相同。 图8.2的（b）是图8.2(a)语法树结点带有语义信息的表示。,图8.2 静态语义审查,8.1.2 属性的确定,写属性文法，首先应确定对于每个文法符号都有哪些属性，然后给每个属性起个名字，接着确定每个属性的类别。要特别强调的是： （1）终结符只有综合属性，它们的值由词法分析器提供； （2）非终结符既可有综合属性也可有继承属性，文法开
11、始符号的所有继承属性作为属性计算前的初始值要在计算（整个处理）开始时指定。,正确确定综合属性和继承属性是非常重要的，究竟哪些属性确定为综合属性，哪些属性确定为继承属性，并没有固定的模式。,例8.2 简单算术表达式求值的语义描述。,产生式 语义规则 LE print(E.val) E E1 + T E. val E1. val+ T. val ET E. val T. val T T1 * F T. val T1. val * F. val TF T . val F. val F（E） F . val E. val Fdigit F . val digit.lexval,在该描述中，大多数非终结
12、符都有一个属性：一个整数值的称作val的属性。 按照语义规则对每个产生式来说，它的左部E，T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性。 单词digit仅有综合属性，它的值是由词法分析程序提供的。 和产生式LE相联的语义规则是一个过程，打印由E产生的表达式的值。我们可以理解为L的属性是空的或是虚的。,例 8.3 描述说明语句中各种变量的类型信息的语义规则。,产生式 语义规则 （1）DTL L.inT.type （2）Tint T.Typeinteger （3）Treal T.Typereal （4）LL1，id L1.inL.in;addtype（id.entry，L.in）
13、 （5）Lid addtype（id.entry，L.in）,例8.3中的文法定义了一种说明语句，该说明语句的形式是由关键字int或real开头，后面是一个标识符表，每个标识符用逗号隔开。 非终结符T有一个综合属性type，它的值由关键字决定（int或real）。与产生式DTL相联的语义规则L.inT.type将L.in(继承属性)的属性值置为该说明语句指定的类型。属性L.in将被沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了它。 这个例子里，继承属性L.in在说明中为各个标识符提供类型信息。,图8.4是句子int id1,id2的语法树，使用表示属性的传递情况。在语法树中，一个
14、结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。与L产生式相联的语义规则中有一个过程调用addtype，过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中。,图 8.4 属性信息传递情况,8.1.3 属性计算规则的确定,一般说来， 对产生式右部符号的继承属性和产生式左部符号的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。 然而，对产生式左部符号的继承属性和产生式右部符号的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。,属性
15、文法看作是允许为每个终结符和非终结符配备一些属性的文法。它既能描述程序设计语言的语法，又为语义处理提供了方便。,属性文法里的属性有不同的类型，可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行，赋值过程就是语义处理过程。在推导或者归约的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的属性值。也就是整个源程序的语义。,中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。 为什么有的编译程序直接生成目标代码，有的编译程序采用中间代码。 一般，快速编译程序直接生成目标代码，没有
16、将中间代码翻译成目标代码的额外开销。 但是为了使编译程序结构在逻辑上更为简单明确，常采用中间代码。 这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。,8.2 中间代码（语言）,中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG表示。 8.2.1 逆波兰式（后缀式）逆波兰式是最简单的一种中间代码表示形式，早在编译程序出现之前，它主要用于表示算术表达式，是波兰逻辑学家卢卡西维兹(J.Lukasiewicz)于1929年发明的。后来人们为了纪念他 ，就把这种后缀表示取名为逆波兰式。逆波兰式最早是用于表示表达式的,后来计算机科学家把它应用于表示程序语言的各种语法成分。,
