编译原理清华大学第8章 语法制导翻译及中间代码生成

1、第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成【课前思考课前思考】 回顾第一章介绍的编译过程，理解语义分析回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。在编译过程中的位置和作用。“属性文法属性文法”的概念及应用。的概念及应用。 “语法制导翻译语法制导翻译”的概念及应用。的概念及应用。什么是中间代码（中间表示），为什么要中什么是中间代码（中间表示），为什么要中间代码？间代码？ 【学习目标学习目标】明确语义分析在编译过程所处的阶段和作用。明确语义分析在编译过程所处的阶段和作用。掌握属性文法的基本概念。掌握属性文法的基本概念。使用属性文法和语法制导翻译方法描述具

2、体的语使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。义分析和产生中间代码。主要是了解：主要是了解：)语义的描述方式；语义的描述方式；)语义的处理方法。语义的处理方法。【本章重点本章重点】(1)(1)几种典型的中间代码（语言）的形式几种典型的中间代码（语言）的形式; ;(2)(2)语义的描述方法语义的描述方法: : 一种形式化的语义描述方法一种形式化的语义描述方法属性文法属性文法; ;(3)(3)语义的处理方法语义的处理方法: : 语法制导的翻译法语法制导的翻译法包括它的两种具体形包括它的两种具体形式：语法制导的翻译和翻译方案式：语法制导的翻译和翻译方案 。编译程序的任务是把源

3、程序翻译成目标程序，这编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应管它们的语法结构完全不同，但它们所表达的结果应完全相同。完全相同。通常，在词法分析程序和语法分析程序对源程序通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后的语法结构进行分析之后:或者由语法分析程序直接调用相应的语义子程序或者由语法分析程序直接调用相应的语义子程序进行语义处理进行语义处理;或者首先生成语法树或该结构的某种表示，再进或者首先生成语法树或该结构的某种表示，再进行语义处

4、理。行语义处理。8.0 概述概述第一，审查每个语法结构的静态语义，即验证第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。工作称为静态语义分析或静态审查。 静态语义分析通常包括：静态语义分析通常包括： 类型检查类型检查 控制流检查控制流检查 一致性检查一致性检查 相关名字检查相关名字检查 名字的作用域分析名字的作用域分析第二，如果静态语义正确，语义处理则要执行第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种真正的翻译，即，或者将源程序翻译成程序的一种

5、中间表示形式（中间代码），或者将源程序翻译成中间表示形式（中间代码），或者将源程序翻译成目标代码。目标代码。编译中的语义处理是指两个功能：编译中的语义处理是指两个功能：中间代码，也称中间语言，是复杂性介于源程中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。序语言和机器语言的一种表示形式。为什么有的编译程序直接生成目标代码，有的为什么有的编译程序直接生成目标代码，有的编译程序采用中间代码。编译程序采用中间代码。一般，快速编译程序直接生成目标代码，没有一般，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。将中间代码翻译成目标代码的额外开销。但是为了使编

6、译程序结构在逻辑上更为简单明但是为了使编译程序结构在逻辑上更为简单明确，常采用中间代码。确，常采用中间代码。这样可以将与机器相关的某些实现细节置于代这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进码生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。行优化工作使得代码优化比较容易实现。 8.1 属性文法属性文法(attribute grammar)属性文法属性文法( (也称属性翻译文法也称属性翻译文法) )是是 Donald Ervin Knuth 在在19681968年首先提出的。年首先提出的。它是在上下文无关文法的基础上，为每个

7、文法符它是在上下文无关文法的基础上，为每个文法符号号( (终结符或非终结符终结符或非终结符) )配备若干相关的配备若干相关的“特性特性”（称（称为属性）。为属性）。这些属性代表与文法符号相关信息，例如它的类这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。规则，称为语义规则。 所谓属性，其涉及的

8、概念比较广泛，常用以描所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到述事物或人的特征、性质，品质等等。比如，谈到一个物体，可以用一个物体，可以用 颜色颜色 描述它，谈起某人，可以描述它，谈起某人，可以使用使用 有幽默感有幽默感 来形容他。对编译程序使用的语法来形容他。对编译程序使用的语法树的结点，可以用树的结点，可以用 类型类型 、 值值 或或 存储位置存储位置 来描来描述它。述它。 一个属性文法包含一个上下文无关文法和一系列一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。语义规则，这些语义规则附在文法的每个产生式上

9、。所谓语法制导的翻译指的是在语法分析过程中，所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。完成这些语义规则描述的动作，从而实现语义处理。8.1.1 属性文法定义属性文法定义定义定义1： 形式上讲，属性文法是一个三元组形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中：其中：G:是一个上下文无关文法；是一个上下文无关文法；V:有穷的属性集有穷的属性集,每个属性与文法的一个终结符或非终每个属性与文法的一个终结符或非终结符相连结符相连,这些属性代表与文法符号相关信息；这些属性代表与文法符号相关信息；F:关于属性的属性断言或一组属性的计算规则关于属性

10、的属性断言或一组属性的计算规则(称为语称为语义规则义规则) 。 断言或语义规则与一个产生式相联断言或语义规则与一个产生式相联,只引只引用该产生式左端或右端的终结符或非终结符相联的用该产生式左端或右端的终结符或非终结符相联的属性。属性。 定义定义2 2：一个属性文法是一个三元组：一个属性文法是一个三元组：A=(G,V,F ),A=(G,V,F ),其中其中uG -G -基础文法（基础文法（一个上下文无关文法一个上下文无关文法）uV -V -每个文法符号有一组属性每个文法符号有一组属性uF -F -每个文法产生式每个文法产生式 A A 有一组形式为有一组形式为b b:=:=f f( (c c1 1

11、, ,c c2 2,c ck k) )的语义规则，的语义规则，其中其中f f 是函数，是函数，b b和和c c1 1, ,c c2 2,c ck k是该产生式文法符号是该产生式文法符号的属性。的属性。 属性文法中的属性分成两类：继承属性和综合属属性文法中的属性分成两类：继承属性和综合属性。性。简单地说，综合属性用简单地说，综合属性用“自下而上自下而上 传递信息，传递信息，而继承属性用于而继承属性用于 自上而下自上而下 传递信息。传递信息。 u综合属性（综合属性（synthesized attribute）：如果）：如果b是是A的的属性，属性，c1 , c2 , , ck是产生式右部文法符号的属

12、性是产生式右部文法符号的属性或或A的其它属性，则称的其它属性，则称b是文法符号是文法符号A的综合属性。的综合属性。u继承属性继承属性(inherited attribute)：如果：如果b是产生式右是产生式右部某个文法符号部某个文法符号X的属性，并且的属性，并且c1,c2,ck是是A或产或产生式右部文法符号的属性，则称生式右部文法符号的属性，则称b是文法符号是文法符号X的继的继承属性。承属性。属性文法的主要思想是：属性文法的主要思想是：.对每个文法符号引入相关的属性符号；对每个文法符号引入相关的属性符号；.对于每个产生式写出计算属性值的属性规则（语义规对于每个产生式写出计算属性值的属性规则（语

13、义规则），其形式为：则），其形式为：b：= f(c1, c2, , ck ) 即：属性变量：即：属性变量：=这里这里 f是一个函数，且对于产生式是一个函数，且对于产生式A ，(1) b或者是或者是A的一个综合属性并且的一个综合属性并且c1,c2,，ck是产生式是产生式右边文法符号的属性；右边文法符号的属性；(2) b或者是产生式右边某个文法符号的一个继承属性并或者是产生式右边某个文法符号的一个继承属性并且且c1,c2,，ck是是A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性在两种情况下，我们都说属性b依赖于属性依赖于属性c1,c2,，ck。继承属

14、性的求值规则：继承属性的求值规则：产生式左部非终结符号的继承属性值取前面产生式右部产生式左部非终结符号的继承属性值取前面产生式右部该符号已有的继承属性值；该符号已有的继承属性值； 产生式右部符号的继承属性值用该产生式左部符号的继产生式右部符号的继承属性值用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算。承属性或出现在该符号左部的符号的属性值进行计算。体现自顶向下，自体现自顶向下，自左向右的求值特性左向右的求值特性体现自底向上，自体现自底向上，自右向左的求值特性右向左的求值特性综合属性的求值规则：综合属性的求值规则：产生式右部非终结符号的综合属性值取其下部产生式或产生式右部非

15、终结符号的综合属性值取其下部产生式或左部同名非终结符号的综合属性值；左部同名非终结符号的综合属性值； 产生式左部非终结符号的综合属性值用该产生式左部符产生式左部非终结符号的综合属性值用该产生式左部符号的继承属性或某个右部符号的属性进行计算；号的继承属性或某个右部符号的属性进行计算；例例8.1 8.1 有文法有文法G G为：为：ETET1 1 + T + T2 2|T|T1 1 or Tor T2 2Tnum|true|false Tnum|true|false 对输入串对输入串3+43+4的的类型检查的属性文法类型检查的属性文法如图如图8.18.1。 ET1+T2 T1.tintANDT2.t

16、intET1orT2 T1.tboolAND T2.tboolTnum T.t intTtrue T.t boolTfalse T.t bool 图图8.1 类型检查的属性文法类型检查的属性文法 属性文法记号中常使用属性文法记号中常使用N.tN.t的形式表示与非终结符的形式表示与非终结符N N相联相联的属性的属性t t。与非终结符与非终结符E E的产生式相联的语义规则指明：两个的产生式相联的语义规则指明：两个T T的属的属性必须相同。性必须相同。图图8.2 静态语义审查静态语义审查 ETT+34（a）ETT+34（b）T2. .t=intT1. .t=intT1. .t= T2. .t 图图8

17、.2(b) 是是 图图8.2(a)语法树结点带有语义信息的表示。语法树结点带有语义信息的表示。 8.1.2 属性的确定属性的确定 写属性文法，首先应确定对于每个文法符号都有哪些属写属性文法，首先应确定对于每个文法符号都有哪些属性，然后给每个属性起个名字，接着确定每个属性的类别。性，然后给每个属性起个名字，接着确定每个属性的类别。 特别强调：特别强调：（1）终结符只有综合属性，它们的值由词法分析器提供；）终结符只有综合属性，它们的值由词法分析器提供；（2）非终结符既可有综合属性也可有继承属性，文法开始非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值要在计算（

18、整符号的所有继承属性作为属性计算前的初始值要在计算（整个处理）开始时指定。个处理）开始时指定。 正确确定综合属性和继承属性是非常重要的，究竟哪些属正确确定综合属性和继承属性是非常重要的，究竟哪些属性确定为综合属性，哪些属性确定为继承属性，并没有固定的性确定为综合属性，哪些属性确定为继承属性，并没有固定的模式。模式。 每个文法符号表示一类语法对象，而每个语法对象都有自己每个文法符号表示一类语法对象，而每个语法对象都有自己的功能。的功能。 图图8.3表示表示E有两个属性，其一是值环境，其二是结果值。它有两个属性，其一是值环境，其二是结果值。它们的属性名分别为们的属性名分别为Env和和Value，其

19、中，其中Env是需要由外部给的，是需要由外部给的， Value则由自己计算出来，而且一旦给定则由自己计算出来，而且一旦给定Env值，则值，则Value的值就的值就被确定。被确定。 这时将属性这时将属性Env定义为继承属性，而属性定义为继承属性，而属性Value则要定义为综则要定义为综合属性。合属性。 EEnvValue图图8.3 E的属性的属性 比如，比如，E表示由整常数和整型变量组成的表达式，则表示由整常数和整型变量组成的表达式，则E的功的功能是给出一个变量求值的环境，且输出一个整型值。能是给出一个变量求值的环境，且输出一个整型值。因此，可以称继承属性为输入属性，而称综合属性为输出因此，可以

20、称继承属性为输入属性，而称综合属性为输出属性。属性。 例例8.2 8.2 简单算术表达式求值的语义描述。简单算术表达式求值的语义描述。产生式产生式 语义规则语义规则 LE print(E.val)E E1 + T E. val E1. val+ T. valET E. val T. valT T1 * F T. val T1. val * F. val TF T . val F. valF（E） F . val E. valFdigit F . val digit.lexval按照语义规则对每个产生式来说，它的左部按照语义规则对每个产生式来说，它的左部E E，T T，F F的属性值的计算来的属

21、性值的计算来自它右部的非终结符，这种属性称作综合属性。自它右部的非终结符，这种属性称作综合属性。单词单词digitdigit仅有综合属性，它的值是由词法分析程序提供的。仅有综合属性，它的值是由词法分析程序提供的。和产生式和产生式LELE相联的语义规则是一个过程，打印由相联的语义规则是一个过程，打印由E E产生的表达式的值。产生的表达式的值。我们可以理解为我们可以理解为L L的属性是空的或是虚的。的属性是空的或是虚的。例例 8.38.3 描述说明语句中各种变量的类型信息的语义规则。描述说明语句中各种变量的类型信息的语义规则。 产生式产生式 语义规则语义规则（1）DTL L.in T.type（2

22、）Tint T.Type integer（3）Treal T.Type real（4）LL1，id L1.in L.in; addtype（id.entry，L.in）（5）Lid addtype（id.entry，L.in） 非终结符非终结符T T有一个综合属性有一个综合属性typetype，它的值由关键字决定（，它的值由关键字决定（intint或或realreal）。与产生）。与产生式式DTLDTL相联的语义规则相联的语义规则L.inL.inT.typeT.type将将L.inL.in的属性值置为该说明语句指定的类的属性值置为该说明语句指定的类型。属性型。属性L.inL.in将被沿着语法树

23、传递到下边的结点使用，与将被沿着语法树传递到下边的结点使用，与L L产生式相联的规则里使产生式相联的规则里使用了它。用了它。 这个例子里，继承属性在说明中为各个标识符提供类型信息。这个例子里，继承属性在说明中为各个标识符提供类型信息。 图图8.48.4是句子是句子int idint id1 1,id,id2 2的语法树，使用的语法树，使用表示属性的表示属性的传递情况。传递情况。图图 8.4 属性信息传递情况属性信息传递情况 D T L Lintid1，Id28.2 中间代码（语言）中间代码（语言） 中间代码（语言）是一种特殊结构的语言，编中间代码（语言）是一种特殊结构的语言，编译程序所使用的中

24、间代码有多种形式。按其结构分译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、式、四元式）和树形表示（抽象语法树）、DAG表表示。示。8.2.1 逆波兰式（后缀式）逆波兰式（后缀式） 逆波兰式最早是用于表示表达式的逆波兰式最早是用于表示表达式的,后来计算机后来计算机科学家把它应用于表示程序语言的各种语法成分。科学家把它应用于表示程序语言的各种语法成分。（一）特点（一）特点 首先我们考察算术表达式（中缀式）的计值顺序首先我们考察算术表达式（中缀式）的计值顺序.例例8.4 中缀式

25、的计值顺序见图中缀式的计值顺序见图8.5。 中缀式计值三个特点：中缀式计值三个特点：（1）运算对象分别放在运算符（双目运算符）的两边；）运算对象分别放在运算符（双目运算符）的两边；（2）计值顺序是根据运算符的优先级别及结合性确定，）计值顺序是根据运算符的优先级别及结合性确定，使用括号可以改变计值顺序；使用括号可以改变计值顺序；（3）运算符的排列顺序不等价于计值顺序。）运算符的排列顺序不等价于计值顺序。图图8.5 中缀式的计值顺序例中缀式的计值顺序例a + b * ( c + d * ( e f ) )a + b * ( c + d * ( e f ) )后缀式计值三个特点：后缀式计值三个特点：

26、（1）不考虑运算符的优先关系，又不使用括号；）不考虑运算符的优先关系，又不使用括号；（2）运算符的排列顺序就是计值顺序；）运算符的排列顺序就是计值顺序；（3）运算对象放在运算符的前面。）运算对象放在运算符的前面。例：例：a b ( c d ( e f ) )其逆波兰式为：其逆波兰式为：a b c d e f (二二)定义定义逆波兰式（逆波兰式（后缀后缀式）的一般形式为：式）的一般形式为：若若 是一个是一个K元运算符（元运算符（ K 1） ，它对其运算对象，它对其运算对象e1,e2, ,ek作用的结果被表示为：作用的结果被表示为： e1 e2 ek 表达式表达式E E的后缀表示的递归定义：的后缀

27、表示的递归定义：（1 1）如果）如果E E是变量或常数，那么是变量或常数，那么E E的后缀表示是的后缀表示是E E本身；本身；（2 2）如果）如果E E是形如是形如E E1 1 op Eop E2 2的表达式，其中的表达式，其中opop是任意的二元运是任意的二元运算符，那么算符，那么E E的后缀表示是的后缀表示是E E1 1 | E| E2 2 | op ,| op ,其中；其中；E E1 1 和和E E2 2 分别是分别是E E1 1和和 E E2 2的后缀表示，的后缀表示，| | 称为称为连接连接 （并置）运（并置）运算符；算符；（3 3）如果）如果E E是形如（是形如（E E1 1），那

28、么），那么E E的后缀表示就是的后缀表示就是E E1 1的后缀表示。的后缀表示。（三）转换（中缀式（三）转换（中缀式 后缀式）后缀式）转换算法：转换算法： 转换规则：设转换规则：设E E为给定的中缀式，我们用为给定的中缀式，我们用表示表示E E的后的后缀式，则有：缀式，则有： E E | ； ； a, a,其中其中a a表示表示变量或常数变量或常数 。 对于给定的中缀式首先找出最后被计算的运算符，并把对于给定的中缀式首先找出最后被计算的运算符，并把此运算符作为上述式中的此运算符作为上述式中的 ，使用上述规则转换之；，使用上述规则转换之； 对对中缀式的剩余部分重复上述过程，直至中缀式的每个中缀式

29、的剩余部分重复上述过程，直至中缀式的每个量均被处理到为止。量均被处理到为止。表表8.1 把表达式翻译为后缀式的语义规则描述把表达式翻译为后缀式的语义规则描述 产产 生生 式式 语语 义义 规规 则则EE1 op E2 E.code =E1.code |E2.code | opE（E1） E.code =E1.codeEid E. .code=id 表表8.1给出了把表达式翻译为后缀式的语义规则描述，给出了把表达式翻译为后缀式的语义规则描述，其中其中E.code表示表示E后缀形式，后缀形式，op表示任意二元操作符，表示任意二元操作符，“|”表示后缀形式的连接。表示后缀形式的连接。 例例8.5 有

30、下面翻译模式：有下面翻译模式：ETRRT print（）R1|T print（）R1| Tnum print（num.val）把中缀表达式把中缀表达式8+5 2翻译成后缀表达式。翻译成后缀表达式。解：解：E T R numprint (8)Rnumprint(8)+Tprint(+)R1numprint(8)+numprint(5)print(+) R1numprint(8)+numprint(5)print(+) Tprint( ) R1numprint(8)+numprint(5)print(+) numprint(2) print( ) R1numprint(8)+numprint(5)

31、print(+) numprint(2) print( )输出：输出：print(8)print(5)print(+)print(2)print( ) 即：即： 8 5 + 2 后缀式后缀式很容易扩充到表达式以外的范围。只要很容易扩充到表达式以外的范围。只要遵守运算对象后直接紧跟它们的运算符的规则即可。遵守运算对象后直接紧跟它们的运算符的规则即可。赋值语句的后缀表示：如有赋值语句的后缀表示：如有aab + cb + c，则有则有 a b c + a b c + 转向语句转向语句GOTO LGOTO L的后缀表示为的后缀表示为“L jumpL jump”，运算对象运算对象L L为语句标号，运算符

32、为语句标号，运算符jumpjump表示转到表示转到某个标号。某个标号。数组元素数组元素AA下标表达式下标表达式1 1，下标表达下标表达式式n n 的后缀表示可表示为：的后缀表示可表示为：下标表达式下标表达式1 1下标表达式下标表达式2 2 下标下标表达式表达式n nA subsA subs，运算符，运算符SubsSubs表示求数组的下标。表示求数组的下标。 条件语句条件语句if E then Sif E then S1 1 else S else S2 2的后缀表示可表的后缀表示可表示为：示为： E SE S1 1 S S2 2 ￥，把把if-then-elseif-then-else看成三目

33、运算符，用￥来表示。看成三目运算符，用￥来表示。8.2.2 三地址代码三地址代码一般形式：一般形式：x x := := y op zy op z如表达式如表达式x x + + y y z z 翻译成的三地址代码序列是翻译成的三地址代码序列是 t t1 1 := := y y z z t t2 2 := := x x + + t t1 1 常用的三地址表示常用的三地址表示: : 赋值语句赋值语句 x x := := y op zy op z， x x := := op yop y， x x := := y y 无条件转移无条件转移 goto Lgoto L 条件转移条件转移 if if x re

34、lopx relop y y goto L goto L 过程调用过程调用 param param x x 和和call p , call p , n n 过程返回过程返回 returnreturn y y 索引赋值索引赋值 x x := := y y i i 和和 x x i i := := y y 地址和指针赋值地址和指针赋值 x x := & := &y y，x x := := y y和和 x x := := y y四元式、三元式、间接三元式四元式、三元式、间接三元式三地址代码可看成中间代码的一种抽象形式。三地址代码可看成中间代码的一种抽象形式。编译程序中，三地址代码语句

35、的具体实现可以用记录编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。表示，记录中包含表示运算符和操作数的域。三地址代码通常有三种表示方法：四元式、三元式、三地址代码通常有三种表示方法：四元式、三元式、间接三元式。间接三元式。 四元式结构形式四元式结构形式: (OP，ARG1，ARG2，RESULT)算符左运算对象右运算对象运算结果三元式结构形式三元式结构形式: 编号编号 (OP，ARG1，ARG2)间接三元式：间接三元式：由间接三元式序列和间接码表组成。由间接三元式序列和间接码表组成。例例8.6 有中缀式有中缀式a:b*cb*c，求其等价的四元式和三元式。

36、，求其等价的四元式和三元式。 四元式四元式 三元式三元式 算符算符 左对象左对象 右对象右对象 结果量结果量 编号编号 算符算符 左对象左对象 右对象右对象 op arg1 arg2 result op arg1 arg2op arg1 arg2 result op arg1 arg2 minus c T1 (1) minus c minus c T1 (1) minus c b T1 T2 (2) b T1 T2 (2) b (1) b (1) minus c T3 (3) minus c minus c T3 (3) minus c b T3 T4 (4) b T3 T4 (4) b (3

37、) b (3) T2 T4 T5 (5) T2 T4 T5 (5) (4) (2) (4) (2) T5 a (6) assign a T5 a (6) assign a 图图8.6 四元式、三元式四元式、三元式结构结构例例8.7 有中缀式有中缀式A + B * ( C - D ) + E / ( C - D ) N ，求其等价的几种不同，求其等价的几种不同的三地址代码序列的形式。的三地址代码序列的形式。四元式：四元式：（1）（）（ CDT1）（2）（）（*BT1T2）（3）（）（+AT2T3）（4）（）（ C DT4）（5）（）（T4NT5）（6）（）（/ ET5T6）（7）（）（+ T3T

38、6T7）三元式：三元式：（1）（）（C D）（2）（）（* B （1）（3）（）（+ A （2）（4）（）（C D）（5）（）（ （4） N）（6）（）（/ E （5）（7）（）（+ （3）（）（6） 间接三元式：间接三元式序列间接三元式：间接三元式序列（1）（）（ C D）（2）（）（* B（1）（3）（）（+ A（2）（4）（）（ （1）N）（5）（）（/ E（4）（6）（）（+ （3） （5）间接码表间接码表（1）（2）（3）（1）（4）（5）（6） 间接码表表示了执行三元式间接码表表示了执行三元式的顺序。的顺序。 图图8.7 几种不同的三地址代码序列几种不同的三地址代码序列8.2.3

39、8.2.3 图形表示图形表示抽象语法树是一种图形化的中间表示，它的每抽象语法树是一种图形化的中间表示，它的每一个叶结点都表示诸如常量或变量这样的运算对象，一个叶结点都表示诸如常量或变量这样的运算对象，而它的内部结点则表示运算符；它不同于前述的语而它的内部结点则表示运算符；它不同于前述的语法树，它展示了一个操作过程并同时描述了源程序法树，它展示了一个操作过程并同时描述了源程序的自然层次结构；的自然层次结构；DAG（有向无环图）以更紧凑的方式给出了同（有向无环图）以更紧凑的方式给出了同样的信息（即对于相同的语法成分只给出一次），样的信息（即对于相同的语法成分只给出一次），在图中其结点的含义同抽象语

40、法树。在图中其结点的含义同抽象语法树。assigna+ bcdcd minus(a)抽象语法树抽象语法树assigna+ bcd minus(b)DAG(b)DAG 图图8.8 a := (8.8 a := ( b + cb + c d ) + cd ) + c d d的图形表示的图形表示例：表达式例：表达式a := (a := ( b + cb + c d ) + cd ) + c d d的两种图形表示的两种图形表示见图见图8.88.8。 抽象语法树是分析树的浓缩表示抽象语法树是分析树的浓缩表示：算符和关键字是算符和关键字是作为内部结点出现的。作为内部结点出现的。 语法制导翻译可以基于分析树

41、，也可以基于抽象语语法制导翻译可以基于分析树，也可以基于抽象语法树法树 抽象语法树的例子：抽象语法树的例子：if-then-elseBS1S2+*258图图8.9 抽象语法树的例子抽象语法树的例子 抽象语法树抽象语法树 构造抽象语法树的语法制导定义构造抽象语法树的语法制导定义 F.nptr := mkleaf (num, num.val) F num F.nptr := mkleaf (id, id.entry) F id F.nptr := E.nptr F (E) T.nptr := F.nptr T F T.nptr := mknode( * *, T1.nptr, F.nptr) T

42、T1* *F E.nptr := T.nptr E T E.nptr := mknode( +, E1.nptr, T.nptr) E E1 + T 语语 义义 规规 则则产产 生生 式式图图8.10 抽象语法树的语法制导定义例子抽象语法树的语法制导定义例子例例8.8 a+5* *b的抽象语法树的构造的抽象语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(a) a+5*b的抽象语法树的抽象语法树 E.

43、nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(b) a+5*b的抽象语法树的抽象语法树E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(c) a+5*b的抽象语法树的抽象语法树E.nptrT.nptrE.nptrT.nptrF.np

44、tridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(d) a+5*b的抽象语法树的抽象语法树E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(e) a+5*b的抽象语法树的抽象语法树E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptrid

45、numididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(f) a+5*b的抽象语法树的抽象语法树E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(g) a+5*b的抽象语法树的抽象语法树E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向

46、符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(h) a+5*b的抽象语法树的抽象语法树E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(i) a+5*b的抽象语法树的抽象语法树8.3 8.3 语法制导翻译语法制导翻译编译程序的整个任务就是把源程序翻译为目标程序。编译程序的整个任务就是把源程序翻译为目标程序。实际上可以把每个编译阶段都看作是完成一定翻译任务实际上可以把每个编译阶段都看作是

47、完成一定翻译任务的处理过程：的处理过程：词法分析阶段把字符流翻译为单词流，语法分析阶段把词法分析阶段把字符流翻译为单词流，语法分析阶段把单词流翻译为语法树，目标代码生成阶段把语法树翻译为汇单词流翻译为语法树，目标代码生成阶段把语法树翻译为汇编语言等等。编语言等等。 语法制导翻译：语法制导翻译：在语法分析过程中，随着分析的步步进展，每当进行在语法分析过程中，随着分析的步步进展，每当进行推导或归约时，同步的去执行每个产生式所附带的语义规推导或归约时，同步的去执行每个产生式所附带的语义规则描述的语义动作（或语义子程序），这样进行翻译的办则描述的语义动作（或语义子程序），这样进行翻译的办法称作语法制导

48、翻译。法称作语法制导翻译。 例例8.98.9：把中缀算术表达式翻译为后缀表示形式，给出如下：把中缀算术表达式翻译为后缀表示形式，给出如下语义描述：语义描述： ET + E1 E.code=T.code| E1.code|+ ET E.code=T.code TF * T1 T.code=F.code|T1.code| * TF T.code =F.code F（E） F.code = E.code Fa F.code = a 其中使用其中使用E.code，T.code和和F.code分别表示其相应的后缀式，分别表示其相应的后缀式，|表示后缀式的连接。如果对于输入串表示后缀式的连接。如果对于输入

49、串a+b*c采用最左分采用最左分析，其形成的推导过程为：析，其形成的推导过程为： E T+E F+E a+E a+T a+T* F a+F*F a+b*F a+b*c 把语义规则计算带入推导过程中，用把语义规则计算带入推导过程中，用(，)表示拓广的句表示拓广的句型型,其中其中是句型，是句型，是翻译的输出形式，则有：是翻译的输出形式，则有：(E , E.code) (T+E, T.code|E.code|+ ) (F+E, F.code|E.code|+ ) (a+E, a|E.code|+ ) (a+T, a|T.code|+ ) (a+FT, a|F.code|T.code|+ ) (a+b

50、T, a|b|T.code|+ ) (a+bF, a|b|F.code|+ ) (a+b*c, a|b|c| |+ ) 去掉去掉a|b|c| | +中的连结符，得到中缀表达式中的连结符，得到中缀表达式a+bc的的后缀式后缀式a b c + 。 E T+E F+E a+E a+T a+T* F a+F*F a+b*F a+b*c 8.3.1 8.3.1 基于属性文法的处理方法基于属性文法的处理方法处理方法：处理方法：1 1）多遍扫描多遍扫描依赖图依赖图树遍历树遍历2）一遍扫描）一遍扫描基于属性文法的处理过程基于属性文法的处理过程(理论上理论上):输入串输入串语法树语法树 依赖图依赖图 计算语义规

51、则顺序计算语义规则顺序语法分析树遍历语法分析树遍历执行语义规则执行语义规则语义规则的计算可能产生代码，在符号表中存取信息，语义规则的计算可能产生代码，在符号表中存取信息，给出出错信息或执行其它动作。对输入串的翻译也就是根给出出错信息或执行其它动作。对输入串的翻译也就是根据语义规则进行计算的结果。据语义规则进行计算的结果。8.3.2 8.3.2 属性依赖图属性依赖图依赖图是一个有向图，用于描述分析树中的属性和属性之依赖图是一个有向图，用于描述分析树中的属性和属性之间的相互依赖关系。间的相互依赖关系。依赖图构造算法：依赖图构造算法：for 语法树中每一结点n do for 结点n的文法符号的每一个

52、属性a do 为a在依赖图中建立一个结点；for 语法树中每一个结点n do for 结点n所用产生式对应的每一个语义规则 b:=f(c1，c2，ck) do for i:=1 to k do 从ci结点到b结点构造一条有向边；注注:在构造依赖图之前在构造依赖图之前,要为每一个过程调用的语义规则引入一个虚综要为每一个过程调用的语义规则引入一个虚综合属性，即在依赖图中构造一个结点。这样，若属性合属性，即在依赖图中构造一个结点。这样，若属性b依赖于属性依赖于属性c，则从则从c的结点有一条有向边连接到的结点有一条有向边连接到b的结点。的结点。 例例8.10：有属性文法见表：有属性文法见表8.2，构造

53、，构造int id1, id2, id3的分析的分析树依赖图。树依赖图。产产 生生 式式 语语 义义 规规 则则 D TL L.in := T.type T int T. type := integer T real T. type := real L L1, id L1.in := L.in; addtype (id.entry, L.in ) L id addtype (id.entry, L.in ) 表表8.2 说明语句的属性文法说明语句的属性文法 表表8.2 说明语句的属性文法说明语句的属性文法 图图 8.12(a) int id1, id2, id3的的注释分析树注释分析树产产 生

54、生 式式 语语 义义 规规 则则 D TL L.in := T.type T int T. type := integer T real T. type := real L L1, id L1.in := L.in; addtype (id.entry, L.in ) L id addtype (id.entry, L.in ) 先构造先构造int id1, id2, id3的语法树见的语法树见图图8.12 (a)所示。所示。 再构造再构造int id1, id2, id3的分析树的依赖图的分析树的依赖图(结点结点用数字表示用数字表示)见图见图8.12b。 D TL L.in := T.typ

55、eD intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 typeaddtype (id.entry, L.in )图图 8.12(b) int id1, id2, id3的依赖图的依赖图8.3.3 语义规则的计算次序语义规则的计算次序 1）拓扑排序）拓扑排序 从依赖图的拓扑排序中我们可以得到计算语义规则的次从依赖图的拓扑排序中我们可以得到计算语义规则的次序，用这个顺序来计算语义规则就得到了输入串的翻译。序，用这个顺序来计算语义规则就得到了输入串的翻译。拓扑排序：结点的一种排序，使得有向边只会从该次序中拓扑排序：结点的一种排序，使得

56、有向边只会从该次序中先出现的结点指向后出现的结点。先出现的结点指向后出现的结点。 例：图例：图8.12 (b)的拓扑排序为：的拓扑排序为：1，2，3，4，5，6，7，8，9，10 。一个依赖图的任何拓扑排序都给出了语法树中结点的语一个依赖图的任何拓扑排序都给出了语法树中结点的语义规则计算的有效顺序。义规则计算的有效顺序。根据例根据例8.10的拓扑排序我们可得到下列语义规则计算顺序的拓扑排序我们可得到下列语义规则计算顺序（其中（其中an代表图中与序号代表图中与序号n的结点有关的属性的结点有关的属性)：a4:=int;a5:=a4;addtype(id1，entry，a5);a7:=a5;addt

57、ype(id2，entry，a7);a9:=a7;addtype(id3，entry，a9);通过这些语义规则的计算将把类型值通过这些语义规则的计算将把类型值int填入到每个标识符填入到每个标识符对应的符号表项中去对应的符号表项中去也就是说，在拓扑排序中，在一个结点上，语义规则也就是说，在拓扑排序中，在一个结点上，语义规则b:=f(c1,c2,ck)中属性中属性c1,c2,ck 在计算在计算b之时是可用的。既之时是可用的。既属性属性b依赖于属性依赖于属性c1,c2,ck 。2）属性的计算过程）属性的计算过程图图8.12 (a) int id1, id2, id3的语法树的语法树 DintT,i

58、d3LLLid2id1, 属性计算有树遍历和一遍扫描两种方法。属性计算有树遍历和一遍扫描两种方法。 树遍历：构造输入的语法树见图树遍历：构造输入的语法树见图8.12 (a)，2）属性的计算过程）属性的计算过程DintT.type = integer,id3L.in = integerL.in = integerL.in = integerid2id1,图图 8.13int id1, id2, id3的注释分析树的注释分析树构造带有属性分析树见图构造带有属性分析树见图8.13。属性计算有树遍历和一遍扫描两种方法。属性计算有树遍历和一遍扫描两种方法。树遍历：构造输入的语法树见图树遍历：构造输入的语

59、法树见图8.12(a)，用深度优先遍历该分析树。用深度优先遍历该分析树。还可以采用一遍扫描的处理方法来计算属性值。还可以采用一遍扫描的处理方法来计算属性值。 一遍扫描的处理方法不同于树遍历的方法，它一遍扫描的处理方法不同于树遍历的方法，它不需要构造实际语法树，而是在语法分析的同时计不需要构造实际语法树，而是在语法分析的同时计算属性值。算属性值。如果需要的话，可以进行多次遍历，直至计算如果需要的话，可以进行多次遍历，直至计算出所有属性。出所有属性。3） 树遍历的属性计算方法树遍历的属性计算方法现在我们来考虑如何通过树遍历的方法计算属现在我们来考虑如何通过树遍历的方法计算属性的值。性的值。通过树遍

60、历计算属性值的方法有多种。这些方通过树遍历计算属性值的方法有多种。这些方法都假设语法树已经建立起了，并且树中已带有开法都假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有然后以某种次序遍历语法树，直至计算出所有属性。属性。最常用的遍历方法是深度优先，从左到右的遍最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称历方法。如果需要的话，可使用多次遍历（或称遍）。遍）。下面算法可对任何无循环的属性文法进行计算。下面算法可对任何无循环的属性文法进行计算。 While 还有未被计算的属性