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

语法制导翻译和中间代码生成第1页，课件共55页，创作于2023年2月代码优化静态存储分配目标代码生成789第2页，课件共55页，创作于2023年2月第5章语法制导翻译和中间代码生成自动机第3页，课件共55页，创作于2023年2月编译中的语义处理是两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间边式形式（中间代码），要么生成实际的目标代码。第4页，课件共55页，创作于2023年2月§5.1属性文法

属性文法的形式定义：一个属性文法形式上可定义为一个三元组A，A=（G，V，F）。其中G表示一个上下文无关文法；V表示属性的有穷集；F表示有关属性的断言或谓词的有穷集。

属性可以分为综合属性和继承属性两类。综合属性一般用于自下而上传递信息，而继承属性常常用于自上而下传递信息。

第5页，课件共55页，创作于2023年2月

简单算术表达式求值的属性文法。

规则语义规则1.S→Eprint（E.val）2.E→E1＋TE.val:=E1.val＋T.val3.E→TE.va1:=T.valv4.T→T1FT.val:=T1.valF.val5.T→T1T.val:=T1.val6.F→（E）F.val:=E.val7.F→digitF.val:=digit.lexval

例5.1

：第6页，课件共55页，创作于2023年2月此例中，每一个非终结符都有一个表示整数值的属性val，如E.va1，表示E的整数值。按照语义规则，每个规则的左部符号如E，T，F等的属性值的计算取决于各自相应的右部非终结符，我们把这种属性称为综合属性。单词digit仅有综合属性，它的值是由词法分析程序提供的。与规则S→E关联的语义规则是一个过程print（E.vd），其功能是打印由E产生的表达式的值。对于在语义规则中并没有出现文法符号S，我们认为其属性是虚的或者空的。

第7页，课件共55页，创作于2023年2月

说明语句中各种变量的类型信息的语义描述。规则语义规则1.D→TLL.in:=T.type2.T→intT.type:=integer3.T→realT.type:=real4.L→L1，idL1.in:=L.inaddtype（id.entry，L.in）5.L→idaddtype（id.entry，L.in）例5.2

：第8页，课件共55页，创作于2023年2月与例中对应的原文法可以表示为1.D→intL｜realL2.L→L，id｜id下图是句子intid1，id2的语法树。用“→”表示属性信息的传递情况。DTLLint，id1id2属性信息的传递情况第9页，课件共55页，创作于2023年2月§5.2语法制导翻译概述

语法制导翻译技术分为自底向上语法制导翻译和自顶向下语法制导翻译。下面以LR语法制导翻译为例，讨论如何具体实现语法制导翻译。假定有输入串3＋45，这是一个简单的算术表达式，相应的文法及各产生式的语义规则见例5.1。表达式3＋45的语法制导翻译法求值过程第10页，课件共55页，创作于2023年2月语法树描述图E.val:=335E.val:=234E.val:20E.val:=5E.val:=4+

Sny.valYSn-1x.valX┋┋┋S0-#状态栈语义值栈文法符号符号栈扩充的LR分析栈

第11页，课件共55页，创作于2023年2月状态actiongoto＋（）d#ETF0

s4

s5

1231

s6

acc

2s7r2

r2

r2

3r4r4

r4

r4

4

s4

s5

8235r6r6

r6

r6

6

s4

s5

937

s4

s5

108

s6

s11

9s7r1

r1

r1

10r3r3

r3

r3

11r5r5

r5

r5

LR分析表

第12页，课件共55页，创作于2023年2月步骤状态栈语义栈符号栈剩余串主要动作10-#3＋45#

205--#3＋45#

303-3#F＋45#r6402-3#T＋45#r4501-3#E＋45#r26016-3-#E＋5#

70165-3--#E＋45#

80163-3-4#E＋F5#r690169-3-4#E＋T5#r41001697-3-4-#E＋T5#

11016975-3-4--#E＋T5#

120169（10）-3-4-5#E＋TF

r6130169-3-20#E＋T#r31401-23#E#r115

acc表达式3＋45的语法语义分析和计值过程

第13页，课件共55页，创作于2023年2月§5.3中间语言所谓中间语言，也称中间代码，是复杂性介于源程序语言和机器语言的一种记号系统。一般来说，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，使生成的的目标代码更为高效，通常采用中间语言。编译程序所使用的中间语言形式较多。常见的逆波兰式、三元式、四元式和树形表示等。第14页，课件共55页，创作于2023年2月逆波兰式是最简单的一种中间语言形式，用逆波兰式表示的表达式也称做后缀式。它的特点是将运算对象写在前面，把运算符号写在后面，比如把x＋y写成xy＋，把xy写成xy。对于简单表达式E，相应的逆波兰式E′遵循下面的转换规则：表达式逆波兰式

EE′(E)E′5.3.1逆波兰式第15页，课件共55页，创作于2023年2月

－EE@（负号“－”是一元运算符，为了区别于减号“－”，通常写成@）

E1opE2E1′E2′op如，表达式x＋y

z的逆波兰式为xyz＋；赋值语句x:=x

y－y/z的逆波兰式为xxyyz/－:=。用逆波兰式表示表达式，其最大的优点是第16页，课件共55页，创作于2023年2月从左至右扫描该算术表达式的逆波兰式：每碰到运算对象，就把它推进栈；碰到运算符，若该运算符是k目运算符，则对找顶部的k个运算对象实施该运算，并用运算结果代替这k个运算对象并入钱。这样，当将整个后缀式扫描完毕，该表达式的结果也就计算出来了。第17页，课件共55页，创作于2023年2月t1:=－xxt1yzt2:=yzt1t2t3:=t1＋t2同时y、z入栈t3逆波兰式的计值过程算术表达式－x＋yz的逆波兰式为x@yz＋，在栈中的计值过程如图所示。

例5.3

：第18页，课件共55页，创作于2023年2月三元式是中间语言的另一种形式，每个三元式由三个部分组成:算符op，运算对象arg1，运算对象arg2。三元式的一般格式为：（i）（op，arg1，arg2）。其中（i）为序号。如表达式－ab＋cd可用三元式表示为：（1）（@，a，－）（2）（，（1），b）（3）（，c，d）5.3.2三元式和树形表示第19页，课件共55页，创作于2023年2月（4）（＋，（2），（3））“－”是一目运算符（这里用@表示），用来使a取反，只需选用一个运算对象，不妨规定只用arg1，至于多目算符，可采用多个相继的三元式表示。2.树形表示树形表示实际上是三元式的另一种表示形式，例如，表达式－ab＋cd可用如下树形表示如下。第20页，课件共55页，创作于2023年2月间接三元式为了尽量不改变三元式表，可以另设一张间接码表来表示有关三元式在三元式表的计值顺序。用这种方法获得的中间代码称为间接三元式。－ab＋cd的树形表示＋ab-dc第21页，课件共55页，创作于2023年2月例如，表达式a:=x＋yzb:=t－yz的间接三元式表示如图所示。

三元式列表间接码表（1）（，y，z）（2）（＋，x，（1））（3）（:=，a，（2））（4）（－，t，（1））（5）（:=，—，（4））

（1）（2）（3）（1）（4）（5）间接三元式表示

第22页，课件共55页，创作于2023年2月采用这种表示方法，当编译程序产生一个三元式时，就查看三元式表中是否存在该三元式，若存在，则不再重复填入三元式表，而只是将该三元式的序号填入三元码标中。如上例中的三元式（1）（，y，z），其序号（1）在间接码表中出现了两次，而该三元式在三元式表中实际只出现一次。

第23页，课件共55页，创作于2023年2月1.四元式在编译过程产生的各种中间语言中，四元式是比较普遍采用的一种形式。与三元式类似，四元式由四个部分组成，算符op，运算对象arg1和arg2，运算结果t。四元式的一般格式为：（i）（op，arg1，arg2，t）其中，（i）为序号，运算对象和运算结果可以是用户自己定义的变量，也可以是编译程5.3.3四元式和三地址码第24页，课件共55页，创作于2023年2月序引进的临时变量，运算对象还可以是常数。例如a:=b＋cd的四元式表示如下:

（1）（，c，d，t1）（2）（＋，b，t1，t2）（3）（:=，t2，—，a）

四元式和三元式在形式上很相似，不同之处主要在于对中间结果的引用方式。也就是说，四元式之间的联系是通过引入临时变量来实现，而三元式则是通过三元式编号来传递中间结果的。

第25页，课件共55页，创作于2023年2月2.三地址码就像树形表示和三元式一样，三地址代码也可以看成是四元式的另一种表示方式，它比四元式更直观、更易于理解。三地址码的一般格式为t:=arg1oparg2其中t，arg1，arg2，op的含义与四元式同。这其实就是一个赋值语句，只是与赋值语句不同的是：在三地址码中赋值符号的右边最多只能有一个运算符。第26页，课件共55页，创作于2023年2月§5.4自底向上语法制导翻译

语法制导翻译分为自底向上和自底向下两种。自底向上语法制导翻译方法就是在自底向上语法分析过程中逐步执行语义规则。也就是在每次归约的同时执行相应的语义动作。

简单算术表达式和赋值语句是指不含数组元素、记录等复杂数据结构的算术表达式和赋值语句。5.4.1简单算术表达式和赋值语句的翻译第27页，课件共55页，创作于2023年2月布尔表达式也叫逻辑表达式，是由布尔运算符和具有逻辑值的运算对象构成。布尔运算符有三个，即not、and和or（或者表示为、和）。布尔运算符的优先顺序（从高到低）为、和，和服从左结合，为一目运算符。具有逻辑值的运算对象可以是逻辑表达式，也可以式关系表达式或者常量。关系表达式是最简单的逻辑表达式，运算对象为算术表达式。关系运算符有＞、＜、＝、5.4.2布尔表达式的翻译第28页，课件共55页，创作于2023年2月≥、≤、≠等等，关系运算符的优先级相同，但运算优先级较低。在程序设计语言中，布尔表达式的作用有两个方面，其一是计算布尔值，其二是作为控制流语句（如ifEthenS1elseS2，whileEdo等）中的条件表达式，用来控制程序转向。计算布尔表达式的计值方法一般有两种，第一种方法是与算术表达式的计值方法相同，即按照表达式的运算顺序，逐步计算出各个第29页，课件共55页，创作于2023年2月部分的值，最后得出整个表达式的值。下面我们用1表示逻辑值true，用0表示逻辑值false，那么布尔表达式1or（0andnot0）and1的计值过程为:1or（0andnot0）and1=1or（0and1）and1=1or0and1=1or0=1

第二种计算方法是采取优化措施，只计算部分表达式，如要计算E1orE2，若计算出E1的值为1，那么E2值就无需计算，因为不管E2的值如何，E1orE2的值都为1。第30页，课件共55页，创作于2023年2月当然，对布尔表达式采用不同的计值方法，与之相应的翻译方法也不同。按照布尔表达式的第一种计值方法。布尔表达式E1orE2andnotE3翻译成的四元式序列可以表示为（1）tl:=notE3（2）t2:=E2andtl（3）t3:=E1ort2

如果E1是一个关系表达式，如A＞B，那么我们可以把它看成与之等价的条件语句第31页，课件共55页，创作于2023年2月ifA＞Bthen1else0来进行处理，翻译成的四元式序列为：（l）ifa＞bgoto（4）（2）t:=0（3）goto（5）（4）t:=1（5）…

其中用临时变量t存放布尔表达式a＞b的值，（5）为后续的四元式序号。

第32页，课件共55页，创作于2023年2月当布尔表达式出现在控制语句（如if-then；if-then-else和while-do等）中用做条件控制时，布尔表达式的作用就不仅仅是计值了，更重要的是决定程序控制流的转向。三种控制语句的语法及其代码结构如下控制结构语法if-thenifEthenS1if-then-elseifEthenS1elseS2while-dowhileEdoS1第33页，课件共55页，创作于2023年2月布尔表达式E的值（真或假）决定着控制流的转向，我们把E取真值和取假值时的两个出口分别叫做真出口和假出口，出口的目标分别叫E.true和E.false。三种控制语句的代码结构E的代码S1的代码E的代码S1的代码S2的代码E的代码S1的代码TFFFTT

if-then

if-then-else

while-do第34页，课件共55页，创作于2023年2月那么，对于E为aropb的形式生成代码为:ifaropbgotoE.truegotoE.false值得注意的是，对于E为E1orE2的形式的情况，如果E1为真，则E为真，即E1的真出口和E的真出口一样，无需考虑E2；如果E1为假，就必须计算E2的值，这时E1的假出口就是E2代码的第一个四元式标号，这时E2和E具有相同的真、假出口。

第35页，课件共55页，创作于2023年2月例5.4：

布尔表达式a<borc>d可以翻译为如下四元式序列:（1）ifa<bgotoE.true（2）goto（3）（3）ifc>dgotoE.truegotoE.false例5.4：分析语句ifa<borc>dthenS1elseS2

分析可知，当a<b为真时，可直接执行S1语句序列，不需要再考虑c>d；但是，若a<b为假时，则第36页，课件共55页，创作于2023年2月需要计算c>d是否为真，若c>d为真，则执行S1语句序列，若c>d为假，则执行S2语句序列。所以，当a<b与c>d分别为真时，程序控制流的转向是一致的，即具有相同真出口。根据上述分析可得到如下四元式：（1）ifa<bgoto（5）（2）goto（3）（3）ifc>dgoto（5）（4）goto（p＋1）（5）（关于S1的四元式序列）……（p）goto（q）第37页，课件共55页，创作于2023年2月（p＋1）（关于S2的四元式序列）……（q）（控制语句的后继四元式序列）分析可知，上述（5）是整个布尔表达式的真出口，但是在生成（1）（3）的时候，地址（5）是未知的，必须要等到将整个布尔表达式的四元式产生完毕后才知道。所以这个地址需要回填。同理，（p＋1）是假出口，在生成（4）的时候该地址也是未知的，因此也需要回填。为了记录需要回填地址的四元式，通常采用“拉链”的办法：把需要回填E.true和E.false的四元式分别形成一条链，分别叫做“真”链和“假”链。

第38页，课件共55页，创作于2023年2月考虑上述四元式序列中，真链的形成过程：（1）ifa<bgotoE.true……（3）ifc>dgotoE.true……则拉链如下（1）ifa<bgoto（0）……（3）ifc>dgoto（1）其中，地址（3）称作链首，0作为链尾标志，即地址（1）为链尾。第39页，课件共55页，创作于2023年2月在语法制导翻译中，为及时回填四元式中真假出口信息，需用到下列数据结构1.用E.true和E.false分别表示"真"链和"假"链；用next指向下一四元式的地址，next的初值为1，每生成一个四元式，其值自动累加1。2.用变量E.scode表示表达式E的第一个四元式序号。3.函数backpatch（p，t），功能是把p所链接的每个四元式的第四区段回填为t。4.函数merge（p1，p2），其功能是将以p1和p2为链首的两条链合并为1条，并返回合并后的链首值。第40页，课件共55页，创作于2023年2月控制语句是指程序设计语言中的if-then，if-then-else，while-do等含条件转移的语句。如将if语句文法改写为G[S]：（1）S→CS1

（2）S→TpS2

（3）C→ifEthen

（4）Tp→CS1elsewhile-do语句文法可改写为G[S]:

（1）S→WdS15.4.5简单说明语句的翻译第41页，课件共55页，创作于2023年2月（2）Wd→WEdo

（3）W→while那么语句while（A>B）doif（C>D）thenY:=X＋1将被翻译成如下一组四元式:ifA>Bgoto（3）(1)

goto（8）(2)

ifC>Dgoto（5）(3)

goto（1）(4)

T:=X＋1(5)

Y:=T(6)

goto（1）第42页，课件共55页，创作于2023年2月比较常见的两种循环语句：while-do语句和for循环语句。while-do语句已经在上一节中介绍，for循环语句，一般形式为:fori:=E1stepE2untilE3doSlt为循环控制变量，E1是i的初值，E2为步长，E3是i的终值，S1是循环体。语句代码结构见下图：

5.4.4循环语句的翻译第43页，课件共55页，创作于2023年2月对于循环语句:fori:=1step2untilendox:=y＋z图5.16for循环语句的代码结构i:=E1i≤E3?FTi:=i+E2

S1的代码第44页，课件共55页，创作于2023年2月可以翻译成如下四元式序列：1

i:=12

goto43

i:=i＋24

ifi≤ngoto65

goto1086

t:=y＋z7

x:=t8

goto3第45页，课件共55页，创作于2023年2月说明语句有常量说明语句、变量说明语句、类型说明语句、过程说明语句等等。说明语句的功能就是用来定义各种形式的有名实体，如常量、变量、过程、函数、数组、记录等等，在编译过程中，这些被定义的实体的名字和性质被登记在符号表中，以便编译程序及时检查实体的引用和说明是否一致。简单说明语句可用语法定义如下：D→integer〈namelist〉5.4.5简单说明语句的翻译第46页，课件共55页，创作于2023年2月

D→real〈namelist〉namelist→〈namelist〉，idnamelist→id其中关键字integer和real分别表示整型、实型，用来定义后继列表中一组名字的性质（类型）。这里，对简单说明语句的翻译，就是要将被定义的实体的名字及其性质登录到符号表中去。按照自底向上的方法对上述形式的文法进行制导翻译时，显然存在着这样一个问题，即我们必须第47页，课件共55页，创作于2023年2月首先用一个队列或者栈把所有的名字都保存下来形成一个串namelist，然后再把它们的性质成批登记到符号表。这样做，无疑给系统带来了额外的开销，增加了系统的负担。于是，我们把上述的文法进行如下改写:D→D1，idD→integeridD→realid这样，每当读进一个id时，就可以及时地把它的性质登记到符号表中，从而避免了将id集中起来再成批登记所带来的麻烦。为改写后的文法中每个产生式定义相应的语义规则：定义一个过第48页，课件共55页，创作于2023年2月程put（id，A），把名字id及性质A登录到符号表；给非终结符D定义语义变量D.ATT，来记录和传递说明语句引入的id性质，如real或integer。（1）D→integerid{put（id，integer）；

D.ATT:=integer}（2）D→realid{put（id，real）；

D.ATT:=real}（3）D→D1，id{put（id，D1.ATT）；

D.ATT:=D1.ATT}

第49页，课件共55页，创作于2023年2月数组是用来存储逻辑上相关的同类型数据的数据结构