语法制导翻译和中间代码生成

1、武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成【课前思考课前思考】 回顾第一章介绍的编译过程，理解语义分析回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。在编译过程中的位置和作用。“属性文法属性文法”的概念及应用。的概念及应用。 “语法制导翻译语法制导翻译”的概念及应用。的概念及应用。什么是中间代码（中间表示），为什么要中什么是中间代码（中间表示），为什么要中间代码？间代码？ 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌【学习目标学习目标】 明确语义分析在编译过程所处的阶段和作用。明

2、确语义分析在编译过程所处的阶段和作用。 掌握属性文法的基本概念。掌握属性文法的基本概念。 使用属性文法和语法制导翻译方法描述具体的语使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。义分析和产生中间代码。主要是要让同学们了解：主要是要让同学们了解：)语义的描述方式；语义的描述方式；)语义的处理方法。语义的处理方法。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌【本章重点本章重点】1.1.几种典型的中间代码（语言）的形式几种典型的中间代码（语言）的形式; ;2.2.语义的描述方法语义的描述方法 着重介绍一种形式化的语义描述方法着重介绍一种形式化的语义描述方法属性文法属

3、性文法; ;3.3.语义的处理方法语义的处理方法 着重介绍语法制导的翻译法着重介绍语法制导的翻译法包括它的两种具体包括它的两种具体形式：语法制导的定义和翻译方案形式：语法制导的定义和翻译方案 。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 编译程序的任务是把源程序翻译成目标程序，这编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应管它们的语法结构完全不同，但它们所表达的结果应完全相同。完全相同。通常，在词法分析程序和语法分析程序对源程序通常，在词法分

4、析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。语法树或该结构的某种表示，再进行语义处理。8.0 概述概述第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌第一，审查每个语法结构的静态语义，即验证第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个语法结构合法的程序是否真正有意义。有时

5、把这个工作称为静态语义分析或静态审查。工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成中间表示形式（中间代码），或者将源程序翻译成目标代码。目标代码。本章引入属性文法和语法制导翻译方法的基本本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式，最后讨论一思想，介绍几种典型的中间代码形式，最后讨论一些语法成分的翻译工作。些语法成分的翻译工作。编译中的语义处理是指两个功能：编译中的语义

6、处理是指两个功能：武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌8.1 属性文法属性文法(attribute grammar)属性文法属性文法( (也称属性翻译文法也称属性翻译文法) )是是KnuthKnuth在在19681968年首年首先提出的。先提出的。它是在上下文无关文法的基础上，为每个文法符它是在上下文无关文法的基础上，为每个文法符号号( (终结符或非终结符终结符或非终结符) )配备若干相关的配备若干相关的“特性特性”（称（称为属性）。为属性）。这些属性代表与文法符号相关信息，例如它的类这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。型、值、代

7、码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。工的过程即是语义处理的过程。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌为文法的每个产生式配备的一组属性的计算规则，为文法的每个产生式配备的一组属性的计算规则，称为称为语义规则语义规则。 所谓属性，其涉及的概念比较广泛，常用以描所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到述事物或人的特征、性质，品质等等。比如，谈到一个物体，可以用一个物体，可以用“形状、功能、颜色形状、功能、颜色”描述它，描述它，谈起某人

8、，可以用谈起某人，可以用“性别、身高、年龄性别、身高、年龄”来介绍他。来介绍他。对编译程序使用的语法树的结点，可以用对编译程序使用的语法树的结点，可以用 类型类型 、 值值 或或 存储位置存储位置 来描述它。来描述它。 一个属性文法包含一个上下文无关文法和一系列一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。语义规则，这些语义规则附在文法的每个产生式上。所谓所谓语法制导的翻译语法制导的翻译指的是在语法分析过程中，指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。完成这些语义规则描述的动作，从而实现语义处理。武汉理工大学计算机科学系陈天

9、煌武汉理工大学计算机科学系陈天煌8.1.1 属性文法定义属性文法定义定义定义1： 形式上讲，属性文法是一个三元组形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中：其中：G:是一个上下文无关文法；是一个上下文无关文法；V:是一个有穷的属性集是一个有穷的属性集,每个属性与文法的一个终结符每个属性与文法的一个终结符或非终结符相联或非终结符相联,这些属性代表与文法符号相关信息；这些属性代表与文法符号相关信息；F:是一组关于属性的属性断言或一组属性的计算规则是一组关于属性的属性断言或一组属性的计算规则(称为语义规则称为语义规则) 。 断言或语义规则与一个产生式相断言或语义规则与一个产生式相联

10、联,只引用该产生式左端或右端的终结符或非终结符只引用该产生式左端或右端的终结符或非终结符相联的属性。相联的属性。 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例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.tintET1orT2 T1.tboolAND T2.tboolTnum T.t intTtrue T.t b

11、oolTfalse T.t bool 图图8.1 类型检查的属性文法类型检查的属性文法 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌属性文法记号中常使用属性文法记号中常使用N.tN.t的形式表示与非终结符的形式表示与非终结符N N相联相联的属性的属性t t。比如可把对上面表达式的类型检查的属性文法写成。比如可把对上面表达式的类型检查的属性文法写成图图8.18.1的形式。与每个非终结符的形式。与每个非终结符T T相联的有属性相联的有属性t t，t t要么是要么是intint，要么是要么是boolbool。与非终结符。与非终结符E E的产生式相联的语义规则指明：两的产生式相联的语义

12、规则指明：两个个T T的属性必须相同。的属性必须相同。图图8.28.2的（的（b b）是图）是图8.2(a)8.2(a)语法树结点带有语义信息的表语法树结点带有语义信息的表示。示。 图图8.2 静态语义审查静态语义审查 ETT+34（a）ETT+34（b）T2. .t=intT1. .t=intT1. .t= T2. .t 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌定义定义2 2：一个属性文法是一个三元组：一个属性文法是一个三元组：A=(G,V,F ),A=(G,V,F ),其中其中uG -G -基础文法（基础文法（一个上下文无关文法一个上下文无关文法）uV -V -每个文法

13、符号有一组属性每个文法符号有一组属性uF -F -每个文法产生式每个文法产生式A A有一组形式为有一组形式为b b:=:=f f( (c c1 1, ,c c2 2,c ck k) )的语义规则，其中的语义规则，其中f f 是函数，是函数，b b和和c c1 1, ,c c2 2,c ck k是该产生式文法符号的属性。是该产生式文法符号的属性。 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 属性文法中的属性分成两类：继承属性和综合属属性文法中的属性分成两类：继承属性和综合属性。性。简单地说，综合属性用简单地说，综合属性用 自下而上自下而上 传递信息，而传递信息，而继承属性用于继

14、承属性用于 自上而下自上而下 传递信息。传递信息。 u综合属性（综合属性（synthesized attribute）：如果）：如果b是是A的的属性，属性，c1 , c2 , , ck是产生式右部文法符号的属性或是产生式右部文法符号的属性或A的其它属性，则称的其它属性，则称b是文法符号是文法符号A的综合属性。的综合属性。u继承属性继承属性(inherited attribute)：如果：如果b是产生式右是产生式右部某个文法符号部某个文法符号X的属性，并且的属性，并且c1,c2,ck是是A或产生或产生式右部文法符号的属性，则称式右部文法符号的属性，则称b是文法符号是文法符号X的继承的继承属性。属

15、性。每个文法产生式每个文法产生式A有一组形式为有一组形式为b:=f(c1,c2,ck)的语义规则，的语义规则，其中其中f 是函数，是函数，b和和c1,c2,ck是该产生式文法符号的属性是该产生式文法符号的属性武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌属性文法的主要思想是：属性文法的主要思想是：1.对每个文法符号引入相关的属性符号；对每个文法符号引入相关的属性符号；2.对于每个产生式设置一组计算属性值的属性规则（语对于每个产生式设置一组计算属性值的属性规则（语义规则），其形式为：义规则），其形式为：b：= f(c1, c2, , ck ) 即：属性变量：即：属性变量：=这里这里

16、 f是一个函数，且对于产生式是一个函数，且对于产生式A ，(1) b或者是或者是A的一个综合属性并且的一个综合属性并且c1,c2,，ck是产生式是产生式右边文法符号的属性；右边文法符号的属性；(2) b或者是产生式右边某个文法符号的一个继承属性并或者是产生式右边某个文法符号的一个继承属性并且且c1,c2,，ck是是A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性在两种情况下，我们都说属性b依赖于属性依赖于属性c1,c2,，ck。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌即：属性规则中的左部即：属性规则中的左部b能写那些属性变量是有

17、规定的，能写那些属性变量是有规定的，只能为下述两种变量：只能为下述两种变量：产生式左部符号的综合属性变量；产生式左部符号的综合属性变量；产生式右部符号的继承属性变量。产生式右部符号的继承属性变量。2.对于每个产生式设置一组计算属性值的属性规则（语义规则对于每个产生式设置一组计算属性值的属性规则（语义规则），其形式为：），其形式为： b：= f(c1, c2, , ck ) 即属性变量：即属性变量：=，这里，这里 f是一个函数，且对于产生式是一个函数，且对于产生式A A ，(1) b1) b或者是或者是A A的一个综合属性并且的一个综合属性并且c c1 1,c,c2 2，c ck k是产生式右边

18、文是产生式右边文法符号的属性；法符号的属性；(2) b(2) b或者是产生式右边某个文法符号的一个继承属性并且或者是产生式右边某个文法符号的一个继承属性并且c c1 1,c,c2 2，c ck k是是A A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。在两种情况下，我们都说属性在两种情况下，我们都说属性b b依赖于属性依赖于属性c c1 1,c,c2 2，c ck k。 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌继承属性的求值规则：继承属性的求值规则： 产生式左部非终结符号的继承属性值产生式左部非终结符号的继承属性值取取（来自于）（来自于）前面前面产生式右部

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

20、产生式左部非终结符号的综合属性值产生式左部非终结符号的综合属性值用用该产生式左部符该产生式左部符号的继承属性或某个右部符号的属性进行计算；号的继承属性或某个右部符号的属性进行计算；武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌8.1.2 属性的确定属性的确定 写属性文法，首先应确定对于每个文法符号都有哪些属写属性文法，首先应确定对于每个文法符号都有哪些属性，然后给每个属性起个名字，接着确定每个属性的类别。性，然后给每个属性起个名字，接着确定每个属性的类别。 要特别强调的是：要特别强调的是：（1）终结符只有综合属性终结符只有综合属性，它们的值由词法分析器提供；，它们的值由词法分析器

21、提供；（2）非终结符既可有综合属性也可有继承属性，文法开始非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值要在计算（整符号的所有继承属性作为属性计算前的初始值要在计算（整个处理）开始时指定。个处理）开始时指定。 正确确定综合属性和继承属性是非常重要的，究竟哪些属正确确定综合属性和继承属性是非常重要的，究竟哪些属性确定为综合属性，哪些属性确定为继承属性，并没有固定的性确定为综合属性，哪些属性确定为继承属性，并没有固定的模式。模式。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例8.2 8.2 简单算术表达式求值的语义描述。简单算术表达式求值的

22、语义描述。产生式产生式 语义规则语义规则 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在该描述中，大多数非终结符都有一个属性：一个整数值的称作在该描述中，大多数非终结符都有一个属性：一个整数值的称作valval的的属性。属性。按照语义规则对每个产生式来说，它的左部按照语义规则对每个产生式来说，它的左部E E，T T，F F的属

23、性值的计算来的属性值的计算来自它右部的非终结符，这种属性称作综合属性。自它右部的非终结符，这种属性称作综合属性。单词单词digitdigit仅有综合属性，它的值是由词法分析程序提供的。仅有综合属性，它的值是由词法分析程序提供的。和产生式和产生式LELE相联的语义规则是一个过程，打印由相联的语义规则是一个过程，打印由E E产生的表达式的值。产生的表达式的值。我们可以理解为我们可以理解为L L的属性是空的或是虚的。的属性是空的或是虚的。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例 8.38.3 描述说明语句中各种变量的类型信息的语义规则。描述说明语句中各种变量的类型信息的语义规

24、则。 产生式产生式 语义规则语义规则（1）DTL L.in T.type（2）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） 例例8.38.3中的文法定义了一种说明语句，该说明语句的形式是由关键字中的文法定义了一种说明语句，该说明语句的形式是由关键字intint或或realreal开头，后面是一个标识符表，每个标识符用逗号隔开。开头，后面是一个标识符表，每个标识符用逗号隔开。非终结符非终结符T T有一个综合属性有一个综

25、合属性typetype，它的值由关键字决定（，它的值由关键字决定（intint或或realreal）。）。与产生式与产生式DTLDTL相联的语义规则相联的语义规则L.inL.inT.typeT.type将将L.in(L.in(继承属性继承属性) )的属性的属性值置为该说明语句指定的类型。属性值置为该说明语句指定的类型。属性L.inL.in将被沿着语法树传递到下边的结将被沿着语法树传递到下边的结点使用，与点使用，与L L产生式相联的规则里使用了它。产生式相联的规则里使用了它。 这个例子里，继承属性这个例子里，继承属性L.in在说明中为各个标识符提供类型信息。在说明中为各个标识符提供类型信息。 武

26、汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌图图8.48.4是句子是句子int idint id1 1,id,id2 2的语法树，使用的语法树，使用表示属性表示属性的传递情况。在语法树中，一个结点的继承属性由此结点的的传递情况。在语法树中，一个结点的继承属性由此结点的父结点和父结点和/ /或兄弟结点的某些属性确定。与或兄弟结点的某些属性确定。与L L产生式相联的语产生式相联的语义规则中有一个过程调用义规则中有一个过程调用addtypeaddtype，过程，过程addtypeaddtype的功能是把的功能是把每个标识符的类型信息登录在符号表的相关项中。每个标识符的类型信息登录在符号

27、表的相关项中。 图图 8.4 属性信息传递情况属性信息传递情况 D T L Lintid1，Id2武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌8.1.3 属性计算规则的确定属性计算规则的确定一般说来，一般说来，对产生式右部符号的继承属性和产生式左部符号对产生式右部符号的继承属性和产生式左部符号的综合属性都必须提供一个计算规则。属性计算的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内这有助于在产生式范围内“封装封装”属性的依赖性。属性的依赖性。然而，对产生式左部符号的继承属性和

28、产生式右然而，对产生式左部符号的继承属性和产生式右部符号的综合属性不由所给的产生式的属性计算部符号的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。算或者由属性计算器的参数提供。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌属性文法看作是允许为每个终结符和非终结符配备一些属性文法看作是允许为每个终结符和非终结符配备一些属性的文法。它既能描述程序设计语言的语法，又为语义处属性的文法。它既能描述程序设计语言的语法，又为语义处理提供了方便。理提供了方便。属性文法里的属性有不同的类型，可以

29、象变量一样地被属性文法里的属性有不同的类型，可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值计算与语法分析赋值。赋值规则附加于语法规则之上。赋值计算与语法分析同时进行，赋值计算过程就是语义处理过程。同时进行，赋值计算过程就是语义处理过程。在推导或者归约的时候，诸属性的值被计算并通过赋值在推导或者归约的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传，有的从右边规则层层传递。有的从语法规则左边向右边传，有的从右边向左边传。语法推导树最后完成时，就得到开始符号的属性向左边传。语法推导树最后完成时，就得到开始符号的属性值。也就是整个源程序的语义。值。也就是整个源程序的

30、语义。 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌中间代码，也称中间语言，是复杂性介于源程序中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。语言和机器语言的一种表示形式。为什么有的编译程序直接生成目标代码，有的编为什么有的编译程序直接生成目标代码，有的编译程序采用中间代码。译程序采用中间代码。一般，快速编译程序直接生成目标代码，没有将一般，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，但是为了使编译程序结构在逻辑上更为简单明确，常采用中间代码。常采用中

31、间代码。这样可以将与机器相关的某些实现细节置于代码这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。化工作使得代码优化比较容易实现。 8.2 中间代码（语言）中间代码（语言）武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 中间代码（语言）是一种特殊结构的语言，编中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元常见的有逆波兰式（后缀式）、三地址代

32、码（三元式、四元式）和树形表示（抽象语法树）、式、四元式）和树形表示（抽象语法树）、DAG表表示。示。8.2.1 逆波兰式（后缀式）逆波兰式（后缀式） 逆波兰式是最简单的一种中间代码表示形式，逆波兰式是最简单的一种中间代码表示形式，早在编译程序出现之前，它主要用于表示算术表达早在编译程序出现之前，它主要用于表示算术表达式，是波兰逻辑学家卢卡西维兹式，是波兰逻辑学家卢卡西维兹(J.Lukasiewicz)于于1929年发明的。后来人们为了纪念他年发明的。后来人们为了纪念他 ，就把这种后，就把这种后缀表示取名为逆波兰式。缀表示取名为逆波兰式。 逆波兰式最早是用于表示表达式的逆波兰式最早是用于表示表

33、达式的,后来计算机后来计算机科学家把它应用于表示程序语言的各种语法成分。科学家把它应用于表示程序语言的各种语法成分。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌（一）特点（一）特点 首先我们考察算术表达式（中缀式）的计值顺序首先我们考察算术表达式（中缀式）的计值顺序.例例8.4 中缀式的计值顺序见图中缀式的计值顺序见图8.5。 中缀式计值三个特点：中缀式计值三个特点：（1）运算对象分别放在运算符（双目运算符）的两边；）运算对象分别放在运算符（双目运算符）的两边；（2）计值顺序是根据运算符的优先级别及结合性确定，）计值顺序是根据运算符的优先级别及结合性确定，使用括号可以改变计值顺

34、序；使用括号可以改变计值顺序；（3）运算符的排列顺序不等价于计值顺序。）运算符的排列顺序不等价于计值顺序。图图8.5 中缀式的计值顺序例中缀式的计值顺序例a + b * ( c + d * ( e f ) )a + b * ( c + d * ( e f ) )武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌（1）不考虑运算符的优先关系，又不使用括号；）不考虑运算符的优先关系，又不使用括号；（2）运算符的排列顺序就是计值顺序；）运算符的排列顺序就是计值顺序；（3）运算对象放在运算符的前面。）运算对象放在运算符的前面。这种表示称为逆波兰式，也称做后缀式。这种表示称为逆波兰式，也称做后

35、缀式。中缀式虽然是人们习惯的表示，但对于计算机来说，处中缀式虽然是人们习惯的表示，但对于计算机来说，处理起来很不方便，如果我们采用一种表示方法：理起来很不方便，如果我们采用一种表示方法：如上例：如上例：a b ( c d ( e f ) )其逆波兰式为：其逆波兰式为：a b c d e f 这种后缀表示法虽然不符合人们的习惯，但它极易被计算机这种后缀表示法虽然不符合人们的习惯，但它极易被计算机来处理。由于后缀式表示上的简洁和计值的方便，特别适用来处理。由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体于解释执行的程序设计语言的中间表示，也方便具有堆

36、栈体系的计算机的目标代码生成。系的计算机的目标代码生成。 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌(二二)定义定义逆波兰式（逆波兰式（后缀后缀式）的一般形式为：式）的一般形式为：若若 是一个是一个K元运算符（元运算符（ K 1） ，它对其运算对象，它对其运算对象e1,e2, ,ek作用的结果被表示为：作用的结果被表示为： e1 e2 ek 表达式表达式E E的后缀表示的递归定义：的后缀表示的递归定义：（1 1）如果）如果E E是变量或常数，那么是变量或常数，那么E E的后缀表示是的后缀表示是E E本身；本身；（2 2）如果）如果E E是形如是形如E E1 1 op Eop

37、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），那么），那么E E的后缀表示就是的后缀表示就是E E1 1的后缀表示。的后缀表示。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌（三）转换（中缀式（三）转换（中缀式 后缀式）后缀式）转换算法：转换算

38、法： 转换规则：设转换规则：设E E为给定的中缀式，我们用为给定的中缀式，我们用表示表示E E的后的后缀式，则有：缀式，则有： E E | ； ； a, a,其中其中a a表示表示变量或常数变量或常数 。 对于给定的中缀式首先找出最后被计算的运算符，并把对于给定的中缀式首先找出最后被计算的运算符，并把此运算符作为上述式中的此运算符作为上述式中的 ，使用上述规则转换之；，使用上述规则转换之； 对对中缀式的剩余部分重复上述过程，直至中缀式的每个中缀式的剩余部分重复上述过程，直至中缀式的每个量均被处理到为止。量均被处理到为止。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌把一般表达式翻

39、译为后缀式是很容易的。把一般表达式翻译为后缀式是很容易的。表表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表示任意二元操作符，表示任意二元操作符，“|”表示后缀形式的表示后缀形式的并置并置。 武汉理工大学计算机科学系陈天煌武汉

40、理工大学计算机科学系陈天煌解：解：E TR 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)print(+) numprint(2) print( )输出：输出：print(8)print(5)print(+)print(2)print( ) 即：即： 8 5 +

41、 2 例例8.5 有下面翻译模式：有下面翻译模式：ETRRT print（）R1|T print（）R1| Tnum print（num.val）把中缀表达式把中缀表达式8+5 2翻译成后缀表达式。翻译成后缀表达式。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌后缀式后缀式很容易扩充到表达式以外的范围。只要很容易扩充到表达式以外的范围。只要遵守运算对象后直接紧跟它们的运算符的规则即可。遵守运算对象后直接紧跟它们的运算符的规则即可。赋值语句的后缀表示：如有赋值语句的后缀表示：如有aab + cb + c，则有则有 a b c + a b c + 转向语句转向语句GOTO LGOTO

42、 L的后缀表示为的后缀表示为“L jumpL jump”，运算对象运算对象L L为语句标号，运算符为语句标号，运算符jumpjump表示转到表示转到某个标号。某个标号。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌数组元素数组元素AA下标表达式下标表达式1 1，下标表达下标表达式式n n 的后缀表示可表示为：的后缀表示可表示为：下标表达式下标表达式1 1下标表达式下标表达式2 2 下标下标表达式表达式n nA subsA subs，运算符，运算符SubsSubs表示求数组的下标。表示求数组的下标。 当然，这些扩充的后缀表示的计值远比后缀表达当然，这些扩充的后缀表示的计值远比后缀表

43、达式的计值复杂得多，要注意对扩展的运算符的含义正式的计值复杂得多，要注意对扩展的运算符的含义正确处理。确处理。条件语句条件语句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看成三目运算符，用￥来表示。看成三目运算符，用￥来表示。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌8.2.2 三地址代码三地址代码一般形式：一般形式：x x := := y op zy op z如表达式如表达式x x + + y y z z

44、 翻译成的三地址代码序列是翻译成的三地址代码序列是 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 relopx relop y y goto L goto L 过程调用过程调用 param param x x 和和call p , call p , n n 过程返回过程返回 returnre

45、turn 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武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌三地址代码有三地址代码有四元式、三元式等形式四元式、三元式等形式三地址代码可看成中间代码的一种抽象形式。三地址代码可看成中间代码的一种抽象形式。编译程序中，三地址代码语句的具体实现可以用记录编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。表示，记录中

46、包含表示运算符和操作数的域。三地址代码通常有三种表示方法：四元式、三元式、三地址代码通常有三种表示方法：四元式、三元式、间接三元式。间接三元式。 四元式结构形式四元式结构形式: (OP，ARG1，ARG2，RESULT)算符算符左运算对象左运算对象右运算对象右运算对象运算结果运算结果三元式结构形式三元式结构形式: 编号编号 (OP，ARG1，ARG2)武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例8.6 有中缀式有中缀式a:b*cb*c，求其等价的四元式和三元式。，求其等价的四元式和三元式。 四元式四元式 三元式三元式 算符算符 左对象左对象 右对象右对象 结果量结果量 编号

47、编号 算符算符 左对象左对象 右对象右对象 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) b (3) T2 T4 T5 (5) T2 T4 T5 (5) (4) (2) (4) (2) T5 a (6

48、) assign (5) a T5 a (6) assign (5) a 图图8.6 四元式、三元式四元式、三元式结构结构武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌8.2.3 8.2.3 图形表示图形表示抽象语法树抽象语法树是一种图形化的中间表示，它的每是一种图形化的中间表示，它的每一个叶结点都表示诸如常量或变量这样的运算对象，一个叶结点都表示诸如常量或变量这样的运算对象，而它的内部结点则表示运算符；它不同于前述的语而它的内部结点则表示运算符；它不同于前述的语法树，它展示了一个操作过程并同时描述了源程序法树，它展示了一个操作过程并同时描述了源程序的自然层次结构；的自然层次结构

49、；DAG（有向无环图）（有向无环图）以更紧凑的方式给出了同以更紧凑的方式给出了同样的信息（即对于相同的语法成分只给出一次），样的信息（即对于相同的语法成分只给出一次），在图中其结点的含义同抽象语法树。在图中其结点的含义同抽象语法树。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌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 + c

50、b + c d ) + cd ) + c d d的两种图形表示的两种图形表示见图见图8.88.8。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 抽象语法树是分析树的浓缩表示抽象语法树是分析树的浓缩表示：算符和关键字是算符和关键字是作为内部结点出现的。作为内部结点出现的。 语法制导翻译可以基于分析树，也可以基于抽象语语法制导翻译可以基于分析树，也可以基于抽象语法树法树 抽象语法树的例子：抽象语法树的例子：if-then-elseBS1S2+*258图图8.9 抽象语法树的例子抽象语法树的例子 抽象语法树抽象语法树武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 构造抽

51、象语法树的语法制导定义构造抽象语法树的语法制导定义 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 T1* *F E.nptr := T.nptr E T E.nptr := mknode( +, E1.nptr, T.nptr) E E1 + T 语语 义义 规规 则则产产 生生 式式图图8.10 抽象语法树的语法制导定义

52、例子抽象语法树的语法制导定义例子武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例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.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridn

53、umididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(b) a+5*b的抽象语法树的抽象语法树武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌T.nptrE.nptrT.nptrE.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(c) a+5*b的抽象语法树的抽象语法树武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌E.nptrT.nptrF.nptrE.n

54、ptrT.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(d) a+5*b的抽象语法树的抽象语法树武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌T.nptrE.nptrT.nptrE.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(e) a+5*b的抽象语法树的抽象语法树武汉理工大学计算机科学系陈天煌武汉

55、理工大学计算机科学系陈天煌指向符号表中指向符号表中b的入口的入口E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口图图8.11(f) a+5*b的抽象语法树的抽象语法树武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(g)

56、a+5*b的抽象语法树的抽象语法树武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(h) a+5*b的抽象语法树的抽象语法树武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的

57、入口的入口指向符号表中指向符号表中b的入口的入口图图8.11(i) a+5*b的抽象语法树的抽象语法树武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌8.3 8.3 语法制导翻译语法制导翻译编译程序的整个任务就是把源程序翻译为目标程序。编译程序的整个任务就是把源程序翻译为目标程序。实际上可以把每个编译阶段都看作是完成一定翻译任务实际上可以把每个编译阶段都看作是完成一定翻译任务的处理过程：的处理过程：词法分析阶段把字符流翻译为单词流，语法分析阶段把词法分析阶段把字符流翻译为单词流，语法分析阶段把单词流翻译为语法树，语义分析和代码生成阶段把语法树翻单词流翻译为语法树，语义分析和代码生成

58、阶段把语法树翻译为汇编代码或者机器代码等等。译为汇编代码或者机器代码等等。 定义（语法制导翻译）：定义（语法制导翻译）：为文法中每个产生式配备一组语义规则，并且在语法为文法中每个产生式配备一组语义规则，并且在语法分析过程中，每分析过程中，每当进行推导或归约时同步当进行推导或归约时同步执行执行附加在所使附加在所使用的产生式上的语义规则描述的动作用的产生式上的语义规则描述的动作（语义子程序）（语义子程序），从，从而实现语义处理。而实现语义处理。这种翻译的办法称作语法制导翻译。这种翻译的办法称作语法制导翻译。 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例8.98.9：把中缀算术表

59、达式翻译为后缀表示形式，给出如下：把中缀算术表达式翻译为后缀表示形式，给出如下语义描述：语义描述： 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分别表示其相应的后缀式，分别表示其相应的后缀式，|表示后缀式的连接。表示后缀式的连接。 如果对于输入串如果对于输入串a+b*c采用最左推导，其形成的推导过采用最左推导，其

60、形成的推导过程为：程为： 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+bT, a|