编译原理第八章

第八章语法制导翻译和中间代码生成源程序的结构分析词法分析ch4语法分析ch5、ch6、ch7语义分析由语法分析程序直接调用相应的语义子程序首先生成语法树（或该结构的某种表示），再进行语义处理生成中间代码编译中的逻辑阶段源语言程序代码优化目标代码（汇编或机器码）词法分析语义分析语法分析中间代码生成目标代码生成前端处理后端处理语义处理语义处理的任务：静态语义检查静态语义：语法结构

静态语义检查：审查静态语义动态语义处理动态语义：程序单元执行的操作

动态语义处理：生成(中间/目标)代码语义处理的实现：属性文法：描述语义规则。--工具语法制导翻译：在语法分析的同时，执行语义规则描述的动作：检查静态语义生成中间代码/目标代码语义处理的环境：符号表为语义分析提供类型、作用域等信息。为代码生成提供类型、作用域、存储类别、存储（相对）位置等信息。

本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式，最后讨论一些语法成分的翻译工作。

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

8．1属性文法8．2语法制导翻译概论

8．3中间代码的形式

8．4简单赋值语句的翻译

8．5布尔表达式的翻译

8．6控制结构的翻译8．7说明语句的翻译

8．8数组和结构的翻译

8．1属性文法

属性文法：语法制导翻译工具，说明程序设计语言的意义。属性文法构成：上下文无关文法+语义规则语义规则附在文法的产生式上，在语法分析过程中，完成附加在所使用产生式上的语义规则描述的动作，从而实现语义处理。

定义：

一个属性文法是一个三元组：

A=（G，V，F）其中:G：上下文无关文法V：属性的有穷集。每个属性与文法的某个非终结符或终结符相联F：关于属性的断言或谓词的有穷集。

--属性的计算规则每个断言与文法的某产生式相联。

例如G：E→T1+T2|T1orT2

T→num|true|false

属性文法记号中常使用N．t的形式表示与非终结符N相联的属性。E→T1+T2{T1．t=intANDT2．t=int}E→T1orT2{T1．t=boolANDT2．t=bool}T→num{T．t=int}T→true{T．t=bool}T→false{T．t=bool}可进行类型检查的属性文法（表达式）

对输入串3+4的语法树：

E{T1．t=T2．t}

{T1．=int}TT{T2．=int}3

4+

如果对G中的某一输入串而言，A中的所有断言对该输入串的语法树的结点的属性全为真，则该串也是A语言中的句子。编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。

A为属性文法例8.2

描述说明语句中各种变量的类型信息的语义规则产生式语义规则(1)DTLL.in:=T.type(2)TintT.type:=integer(3)TrealT.type:=real(4)LL1,idL1.in:=L.in;addtype(id.entry,L.in)(5)Lidaddtype(id.entry,L.in)要解决的问题：纪录标识符的类型类型信息传递方法：用T.type记录类型信息，并传给L.inentryid的属性：可以是它在符号表中的地址addtype在符号表中为变量填加类型信息8．2语法制导翻译概论

语法制导翻译：首先，使用属性文法为工具，描述程序设计语言的语义规则。在语法分析时，每应用一个产生式（推导或归约），同时完成该产生式上所附的语义规则描述的动作，从而完成语义处理。在进行语法分析的同时，完成相应的语义处理

语法制导翻译的具体实现途径不难。如有一个LR分析器，扩充它的分析栈，使得每个文法符号都跟有语义值。同时扩充LR分析器功能，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应语义子程序。

例算术表达式求值的语义描述

（0）L→Eprint（E.val)（1）E→E1+T

E.val:=E1.val+T.val（2）E→TE.val:=T.val（3）T→T1*FT.val:=T1.val*F.val（4）T→FT.val:=F.val（5）F→（E）F.val:=E.val（6）F→digitF.val:=digit.lexval

输入串2+3*5,语义处理是计算表达式的值，采用LR分析法，LR分析表如下：

LR分析表如下状态ACITON（动作）GOTO（转换）d+*（）#ETF0S5

S4

1231

S6

acc

2

r2S7

r2r2

3

r4r4

r4r4

4S5

S4

8235

r6r6

r6r6

6S5

S4

937S5

S4

108

S6

S11

9

r1S7

r1r1

10

r3r3

r3r3

11

r5r5

r5r5

LR分析输入串2+3*5步骤状态栈语义栈（值栈）符号栈剩余输入串归约动作10-#2+3*5#205--#2+3*5#303-2#F+3*5#

r6402-2#T+3*5#r4501-2#E+3*5#r26016-2-#E+3*5#70165-2--#E+3*5#

步骤状态栈语义栈（值栈）符号栈剩余输入串归约动作80163-2-3#E+F*5#r690169-2-3#E+T*5#r41001697-2-3-#E+T*5#11016975-2-3--#E+T*5#1201697（10）-2-3-5#E+T*F#r6130169-2-（15）#E+T#r31401-（17）

#E#

r115接受

按照上述实现办法，若把语义子程序改为产生中间代码的动作，则可在语法制导下生成中间代码。（选作实验）

8．3中间代码的形式

中间代码有多种形式，常见的有逆波兰式三元式四元式

树形表示

一、逆波兰记号

最简单的一种中间代码形式。将运算对象写在前面，运算符号写在后面如a+b写成ab+，也称后缀式。后缀表示法表示表达式的最大优点是计算机处理表达式方便。如B@CD*+（@表示一元减，中缀表示为-B+C*D）

逆波兰表示很容易扩充到表达式以外的范围，只要遵守运算对象后直接跟它们的运算符这条规则即可。

如GOTOL写为LjumpifEthenS1else

S2

表示为ES1S2¥，把if-then-else看成三目运算符，用¥表示。但要注意，要对新添加的运算符的含义正确处理。

二、三元式和树形表示

组成：（OP，ARG1，ARG2）OP为算符，ARG1和ARG2分别为第一、第二运算对象。

如：a：=b*c+c/d表示为：

（1）

（*，b，c）（2）

（/，c，d）（3）

（+，（1），（2））（4）（：=，（3），a）

三元式中的（1）、（2）表示第一和第二个三元式的结果。

对一元运算符，规定只用ARG1。

树形表示是三元式的翻版。表达式的树形表示很容易实现：简单变量或常数的树是自身，如果表达式e1和e2的树分别为T1和T2，那么e1+e2、e1*e2，-e1的树为：

e1+e2+T1T2*T1T2-T1e1*e2

-e1二目运算对应二叉子树，多目运算对应多叉子树。

三、四元式

普遍采用的一种中间代码形式。组成：（OP，ARG1，ARG2，RESULT）其中:OP，ARG1，ARG2的含义同三元式

RESULT是运算结果。

有时为了直观，也把四元式的形式写成简单赋值形式，例如把上述四元式写成：

（1）t1：=b*c（2）t2：=c/d（3）t3：=t1+t2（4）a：=t3

如，a：=b*c+c/d的四元式表示如下：

（1）（*，b，c，t1）（2）（/，c，d，t2）（3）（+，t1，t2，t3）（4）（：=，t3，-，a）

四元式和三元式的主要不同在于：四元式对中间结果的引用必须通过给定的名字，三元式是通过产生中间结果的三元式编号。

四元式表示类似于三地址指令，有时也把这种表示称为三地址代码，它对代码优化和目标代码生成都较有利。

8．4简单赋值语句的翻译

说明：

在实际实现中，四元式的ARG1和ARG2、RESULT，或者是一个指针，指向符号表的某一登录项；或者是一个临时变量的整数码。

语义变量id．name：id表示的单词的一属性语义变量E．place：表示存放E值的变量名在符号表的登录项或一整数码语义过程emit：表示输出四元式到输出文件上语义过程newtemp：表示生成一临时变量。函数Lookup（id．name）：查id．name是否在符号表中，如在，则返回指向该登录项指针，否则返回nil。

下面列出了翻译赋值语句到四元式的语义描述，这里的语义工作包括对变量进行“先定义后使用”的检查。

（1）S→id：=E{p：=Lookup（id．name）；

ifｐ≠nil

then

emit（p‘：＝’E．place）

elseerror}四元式采用赋值形式，即result：=arg1oparg2（2）E→E1+E2

{E.place:=newtemp；

emit（E.place‘:=’E1.place‘+’E2.place）

}（3）E→E1*E2

{E.place:=newtemp；

emit（E.place‘:=’E1.place‘*’E2.place）

}（4）E→-E1{E.place:=newtemp；

emit（E.place‘:=’‘uminus’E1.place）

}（5）E→（E1）

{E.place:=E1.place}（6）E→id{p:=Lookup（）；

ifp≠nil

then

E.place:=pelseerror}

编译程序还可对表达式中的运算对象进行类型检查、类型转换。约定：当两个不同类型的量进行运算时，先将整型量转换为实型量，并增加E.type表示E的类型信息，值为int或real，用+i（*i）、+r（*r）区别整型加和实型加。

带类型转换的语义处理如下：（E→E1*E2）

E→E1*E2

{E.place:=newtemp；

ifE1.type=intANDE2.type=intthenbeginemit(E.place,‘:=’,E1.place,‘*i’,E2.place);

E.type:=intendelseifE1.type=realANDE2.type=realthen

beginemit(E.place,‘:=’,E1.place,‘*r’,E2.place);E.type:=realend

elseifE1．type=int/*E2．type=real*/thenbegint:=newtemp；

emit（t,‘:=’，itr，E1.place）；

emit（E.place,‘:=’，t,‘*r’,E2.place）；

E．type:=realendelse/*E1.type=realANDE2.type=int*/begint:=newtemp；

emit（t,‘:=’，itr，E2.place）

emit（E.place,‘:=’，E1.place,‘*r’，t）；

E.type:=realend；}

语义值的设计是与语义处理的描述相关的，如非终结符E，有语义值E．place、E．type或E．kind（见PL/0编译程序）

8．5布尔表达式的翻译

在程序设计语言中，布尔表达式的作用有两个：一是用作逻辑赋值语句的逻辑运算，二是用作控制语句中的条件表达式。

布尔表达式的形式为：E1ropE2，E1和E2是算术表达式，rop是关系符=、〈=、>=、〈、〉、≠。为简单起见，只考虑如下文法生成的布尔表达式：

E→EandE|EorE|notE|idropid|true|false布尔运算符的优先顺序为：not、and、or，并且and和or服从左结合。一、布尔表达式的翻译方法

计算布尔表达式的值有两种办法：

第一种：同算术表达式的计算一样，按步计算各部分的真假值，最后计算整个表达式的值。例如：1or（not0and0）or0=1or（1and0）or0=1or0or0=1or0=1采取哪种方法取决于程序设计语言的语义。

第二种：采取某种优化措施，只计算部分表达式，如AorB，若A的值为1，则无需计算B，整个布尔表达式的值为1。同理，对于AandB，若A为0，则整个布尔表达式值为0，无需计算B。

若按第一种方法计算布尔表达式，

aorbandnotc翻译成四元式为：

（1）

t1：=notc（2）

t2：=bandt1（3）t3：=aort2

对于a〈b这样的关系表达式，可看成等价的条件语句:ifa〈bthen1else0，翻译成的四元式序列为：

（1）

ifa〈bgoto（4）（2）

t：=0（3）

goto（5）（4）

t：=1（5）…

用t存放a〈b的值，（5）为后继的四元式序号。

p182图8.14给出了按第一种办法计算布尔表达式的值。其中：

nextstat：给出输出序列中下一四元式序号；

emit：输出四元式，每调用一次，nextstat

增加1。

E→E1orE2

{E.place:=newtemp；

emit（E.place‘:=’E1.place‘or’E2.place）}E→E1andE2

{E.place:=newtemp；

emit（E.place‘:=’E1.place‘and’E2.place）}E→notE1

{E.place:=newtemp；

emit（E.place‘:=’‘not’E1.place）}E→（E1

）

{E.place:=E1.place}

E→id1relopid2

{E.place:=newtemp；

emit（‘if’id1.placerelopid2.place‘goto’nextstat+3）；

emit（E.place‘:=’‘0’）；

emit（‘goto’nextstat+2）；

emit（E.place‘:=’‘1’）；}E→true{E.place:=newtemp；

emit（E.place‘:=’‘1’）}E→false{E.place:=newtemp；

emit（E.place‘:=’‘0’）}二、控制语句中布尔表达式的翻译讨论出现在if-then；if–then-else和while-do等语句中的布尔表达式E的翻译语法：

S→ifEthenS1|ifEthenS1elseS2

|whileEdoS1

begin：out：假假假真真真E的代码E的代码E的代码S1的代码S1的代码S1的代码S2的代码jumpoutjumpbeginifEthenS1ifEthenS1elseS2whileEdoS1控制语句的代码结构

作为条件转移的E，仅把E翻译成条件转移和无条件转移的四元式。翻译的基本思路是：

对于E为aropb的形式，生成代码为：

ifaropbgotoE.true和

gotoE.false对于E为E1orE2

的形式，若E1为真，则E为真，即E1的真出口和E的真出口一样。若E1为假则需计算E2，E1的假出口应是E2代码的第一个四元式标号，E2的真出口和假出口分别与E的真出口和假出口一样。

E为E1andE2

的形式，与2)类似，只需调换E1的真假出口即可

对于notE1的翻译，E的真假出口是E1的假真出口。

例8.3

布尔表达式a〈b

or

c〈dande〉f

翻译成如下四元式序列：

（1）

ifa〈bgotoE.ture（2）

goto3（3）

ifc〈dgoto5（4）

gotoE.false（5）

ife〉fgotoE.true（6）gotoE.false

上述四元式（2）是不需要的，这种问题可在代码优化阶段解决。

不是最优语句ifa<borc<dande<fthenS1elseS2的四元式(1)ifa<bgoto(7)

//转移至(E.true)(2)goto(3)

(3)ifc<dgoto(5)(4)goto(p+1)//转移至(E.false)(5)ife<fgoto(7)(6)goto(p+1)(7)(S1的四元式

……(p-1)……）(p)goto

(q)(p+1)(S2的四元式……(q-1)……）(q)//转移至(E.true)//转移至(E.false)//(E.false)入口//(E.true)入口E.true和E.false的值不能在产生四元式的同时就知道，要在整个布尔表达式（或语句）的四元式产生完毕之后才得知，因此要回填这个地址。

为了记录需回填地址的四元式，常采用一种拉链的办法：把需回填E.true的四元式拉成一链，称为“真”链，把需回填E.false的四元式拉成一链，称为“假”链。若有四元式序列：

（10）…gotoE.true（20）…gotoE.true（30）…gotoE.true（10）…goto（0）（20）…goto（10）（30）…goto（20）其中链首为（30），链尾为（10），0为链尾标志。则链成:使用：E.true和E.false：分别表示“真”链和“假”链nextstat：下一四元式地址emit：输出四元式merge（p1,p2）：合并p1、p2两条链，即将p2的链尾链接到p1链首，合并后p2为链首。例：merge(p1,p2)(p10)goto(0)

……

p1链(p100)goto(p10)……`(p1)goto(p100)(p20)goto(0)(p1)……

p2链(p200)goto(p20)……(p2)goto(p200)backpatch（p，t）：把p所链接的每个四元式的第四区段都填为tE.codebegin：E的第一个四元式序号（语义值）

自下而上的分析中布尔表达式的一种翻译方案，如p167图8.13所示

（1）E→E1orE2

{backpatch(E1.false,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=merge（E1.true,E2.true）;E.false:=E2.false；

}（2）E→E1andE2

{backpatch(E1.true,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge（E1.false,E2.false）；

}

（3）E→notE1

{

E.true:=E1.false;E.codebegin:=E1.codebegin;E.false:=E1.true;}（4）E→(E1){

E.true:=E1.true;

E.codebegin:=E1.codebegin;E.false:=E1.false;}（5）E→id1relopid2

{E.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(‘if’id1.place‘rop’id2.place‘goto’_);emit(‘goto’_)；

}

（6）E→true{E.true:=nextstat;E.codebegin:=nextstat;emit(‘goto’_)；

}（7）E→false{E.false:=nextstat;E.codebegin:=nextstat;emit(‘goto’_)；

}以a〈borc〈dande〈f

为例，将分析产生语法树时的语义动作结果“真”“假”链情况注释在相应结点处

anda〈borEE.true={104，100}E.false={105，103}E1

E.true={100}E.false={101}E4

E.true={104}E.false={105，103}E2

E.true={102}E.false={103}E3

E.true={104}E.false={105}c〈d

e〈f过程：

1）归约a〈b到E1时，产生两个四元式：

100：ifa〈bgoto—101：goto—（假定nextstat初值为100）

E1.true和E1.false分别为{100}、{101}，

E1.codebegin=100；

2）归约c〈d到E2时，产生两个四元式：

102：ifc〈dgoto—103：goto—

E2.true和E2.fa