语法制导翻译技术和中间代码生成推选资料

语法制导翻译技术和中间代码生成第5章语法制导翻译技术和中间代码生成要求明确语义分析的任务明确属性文法和语法制导翻译的含义明确自底向上和自顶向下语法制导翻译的区别和特点明确生成中间代码的目的，中间代码的几种形式

教学目标属性文法语法制导翻译法的基本思想常见的中间代码各种不同语法结构的语法制导翻译技术教学内容词法分析，语法分析：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器构造出来。本章要介绍的是语义分析和中间代码生成技术。程序语言中间代码目标代码翻译翻译根据语义规则对识别出的各种语法成分析其含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。第一，审查每个语法结构的静态语义，即检查语法结构合法的程序是否真正有意义。也称静态语义检查。（类型检查、控制流的检查、一致性检查、相关名字的检查）第二，如果静态语义正确，语义处理则要执行真正的翻译，要么生成中间代码，要么生成实际的目标代码。（说明性语句：填符号表；可执行性语句：生成中间代码）

语义分析的任务中间代码：一种介于源语言和目标语言之间的中间语言形式例：x=y+yz+yz可执行性语句：生成中间代码）（1）语法制导定义（自底向上）：whileEdoS1的四元式序列语义规则是根据产生式所蕴涵的语义操作建立起来的，并与语义分析的目标有关100（j>,a,0,102)这是一种动作与分析交错的实现方案。翻译结果②控制流检查，确保控制语句有合法的转向点。(1)*,C,D２+3*4的注释分析树①类型检查。②控制流检查，确保控制语句有合法的转向点。例如，C语言中的break语句使控制跳离包括该语句的最小的switch，while或for语句。如果不存在包括它的这样的语句，则应报错。静态语义检查静态语义检查③一致性检查。很多情况下要求对象只能被定义一次。例如，Ｃ语言中规定一个标识符在同一作用域中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等。④相关名字检查。有的语言中有时规定，同一名字必须出现两次或多次。例如，Ada语言中，循环或程序块可以有一个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配对情况。附加了一组属性和运算（语义）规则的文法

5.2属性文法文法符号X的属性t常用来表示语义规则是根据产生式所蕴涵的语义操作建立起来的，并与语义分析的目标有关不同的产生式对应不同的语义规则不同的分析目标也对应不同的语义规则

1.属性的表示2.语义规则的表示语义信息语义之间的关系静态语义检查、符号表操作、代码生成及打印各种错误信息

属性文法属性文法的形式定义：AG：AG=（G，V，E）G:上下文无关文法;V:属性的有穷集合;每一个属性与某一个文法符号相关联；用文法符号·属性表示E:表示属性的断言或谓词的有穷集合(语义规则);每一个断言与文法的某个产生式相关联)属性:综合属性(自下而上传递信息)、继承属性（自上而下传递信息)

非终结符E、T及F都有一个综合属性val,符号i有一个综合属性。某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现语义规则EE1+TET

TT1*FTFF(E)Fi

E.val=E1

T.val=T1.val

产生式例语法制导翻译的过程语法制导翻译：将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。自底向上语法制导翻译自顶向下语法制导翻译语法制导翻译的实现语法制导翻译分为两种处理方法：（1）语法制导定义（自底向上）：对每个产生式编制一个语义子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。（2）翻译方案（自顶向下）：在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种动作与分析交错的实现方案。输入符号串

分析树

执行语义规则

翻译结果翻译步骤（２）从分析树得到描述结点属性间依赖关系的依赖图，由依赖图得到语义规则的计算次序

（1）分析输入符号串，建立分析语法树（３）进行语义规则的计算，得到翻译结果

语法制导定义对每个产生式编制一个语义子程序在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译综合属性继承属性自底向上传递信息自顶向下（自左向右）传递信息

print(E.val)打印由E产生的算术表达式的值，可认为这条规则定义了L的一个虚属性。

LEEE1+TET

TT1*FTFF(E)Fiprint(E.val)

E.val=E1

T.val=T1.val

例5.２综合属性语义规则产生式一个结点的综合属性值是其子结点的某些属性来决定的２+3*4的注释分析树通常使用自底向上的分析方法在每个结点处使用语义规则来计算综合属性值当一个产生式获得匹配时，就调用相应的语义子程序从叶结点到根结点进行计算只含有综合属性的语法制导定义称为S属性定义S属性定义与自底向上翻译LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算LR分析器增加属性值（语义）栈

首先，为文法的每条规则设计相应的语义子程序；增加一个语义信息栈；在语法分析的同时做语义处理：即在用某一个产生式进行规约的同时，调用相应的语义子程序完成所用规则的语义动作，并将每次动作后的值保存在语义栈中翻译步骤计算表达式2+3*5状态ACTIONGOTOi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5G[E]：1E→E+T2E→T3T→T*F4T→F5F→(E)6F→ii+i*i表达式2+3*5的归约过程步骤状态栈语义栈符号栈输入串动作00_$2+3*5$S5105__$2

+3*5$r6203_2$F

+3*5$r4302_2$T

+3*5$r2401_2$E

+3*5$S65016_2_$E+

3*5$S560165_2__$E+3*5$r6步骤状态栈语义栈符号栈输入串动作70163_2_3$E+F*5$r480169_2_3$E+T*5$S7901697_2_3_$E+T*

5$S510016975_2_3__$E+T*5$r61101697(10)_2_3_5$E+T*F$r3120169_2_15$E+T$r11301_17$E$acc注意句柄归约在先，语义动作调用在后归约时，栈内句柄各符号的语义信息与句柄及同时出栈，整个句柄所表示的语义信息则赋给相应产生式左部非终结符号的语义变量，并让该非终结符号及语义信息同时入栈生成中间代码的目的(1)便于优化(2)便于移植(3)逻辑结构清晰常见的中间代码形式：后缀式三地址代码（四元式、三元式和间接三元式）图形（抽象语法树、有向无环图）

中间代码：一种介于源语言和目标语言之间的中间语言形式5.３中间代码中缀表示后缀表示

a+bab+

a+b*cabc*+

(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特点1、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值后缀式分别给出下列表达式的后缀表示1.-a+b*(-c+d)2.X:=-(a+b)/(c-d)-(a+b*c)3.a=c∧b=d4.a≤b+c∧a>d∨a+b≠ea-bc-d+*+Xab+-cd-/abc*+-:=ac=bd=∧abc+≤ad>∧ab+e≠∨逆波兰表示法（后缀式）特点：运算符直接写在其运算对象之后。不再有括号运算对象出现的次序未变求值过程简单，宜于用栈实现后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。三地址代码１．种类（1）x=yopz形式的赋值语句，其中op是二元运算符。（2）x=opy形式的赋值语句，其中op是一元运算符。（3）x=y形式的赋值语句。（4）无条件转移语句gotoL，表示下一个要执行的语句是标号为L的语句。（5）条件转移语句ifxropygotoL中，rop为关系运算符，如果x和y满足关系rop，就转而执行标号为L的语句，否则顺序执行下一个语句。（6）过程调用语句paramx和callp,n。源程序中的过程调用语句p(x1，x2，…，xn)可以产生如下的三地址代码：paramx1paramx2…paramxncallp,n其中n为实参个数。过程返回语句形如returny，其中y为过程返回的一个值。

（7）变址赋值：x=y[i]，把从y开始的第i个存储单元的值赋给x。x[i]=y，把y的值赋给x开始的第i个存储单元。其中，x，y和i都代表数据对象。（8）地址和指针赋值：x=&y，把y的地址赋给x。x=

y，把y指示的地址单元中的内容赋给x。

x=y，把x指向的存储单元的值置为y。2．具体实现四元式操作符操作数1操作数2结果结果：通常是由编译引进的临时变量例:X=(A+B)*(C+D)-E+,A,B,T1+,C,D,T2*,T1,T2,T3-,T3,E,T4=,T4,一,XT1,T2,T3,T4为临时变量，由四元式优化比较方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T4操作符左操作符数右操作数表达式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)第三个三元式中的操作数(1)(2)表示第(1)和第(2)条三元式的计算结果。三元式例：A=B+C*D/EF=C*D三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(1)

不便于代码优化：删除某些三元式后可能需作一系列的修改三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)间接三元式执行顺序(1)(2)(3)(4)(1)(5)三元式的执行次序用另一张表表示,优化时三元式可以不变，仅仅改变其执行顺序表图形表示法无循环有向图(DirectedAcyclicGraph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点例：x=

y+y

z+y

z

抽象语法树图形表示有向无环图表达式a+(-b)*c的三元式

(1)(@,b,_);单目运算，运算对象2为空

(2)(*,(1),c)(3)(+,a,(2))三元式X=a+b*cY=d-b*c四元式

(三地址代码）

X=a*b+c*d的四元式序列三地址代码(1)(*,a,b,T1)(1)T1=a*b(2)(*,c,d,T2)(2)T2=c*d(3)(+,T1,T2,T3)(3)T3=T1+T2(4)(=,T3,_,X)(4)X=T3

a:=b*(-c)+b*(-c)的图表示法

assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc抽象语法树对应的代码：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5assigna+*buminusc抽象语法树*buminuscDAG对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树对应的代码：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5

属性翻译文法的应用

综合属性与自下而上定值

每个非终结符的属性值都是根据位于其下面那些符号的属性值来确定的，即按一种自下而上的方式来确定的。继承属性和自上而下定值

非终结符的属性值或者根据其上层非终结符的属性来确定或者根据产生式右部其它符号的属性来确定。这种属性值是根据自上而下方式确定的。自底向上的语法制导翻译自底向上的语法制导翻译方法是在自底向上的语法分析过程中逐步实现语义规则的翻译方法。在实现时注意以下几点：（1）自底向上的翻译的特点，栈的操作，对产生式的要求等（2）各种程序语句的目标结构（3）从源结构到目标结构的变换方法（包括对产生式的改造等）算术表达式和赋值语句的翻译翻译步骤：（1）分析文法的特点；（2）设计一系列的语义变量、定义语义过程、语义函数；（3）设计每一条规则的语义子程序；（4）增加一个语义信息栈，构造LR分析表;(5)语法分析同时语义处理.例：有文法G[A]：1.A→i:=E2.E→E+T∣T3.T→T*F∣F4.F→－P5.P→i∣(E)

简单算术表达式的计值顺序与四元式出现的顺序相同,因此目标代码的顺序(结构)为:(1)先生成E的代码(一系列顺序执行的四元式)(2)把E的值赋给变量i(表达式的结果赋给赋值语句的左变量)引入语义变量,语义过程和语义函数(1)语义变量E.place:表示存放E值的变量名在符号表中的入口地址或临时变量的整数码.(2)语义函数newtemp():申请一个临时单元,存放中间结果;(3)语义过程emit(T=arg1oparg2):产生一条四元式,并添入四元式表中;(4)语义过程lookup():审查是否出现在符号表中,在:返回地址,不在:返回NULL;(5)语义函数entry(i):回送标识符i在符号表中的入口地址.表达式的语义动作设计1.A→i:=E{emit(entry(i)=E.place}2.E→E1+T{E.place=newtemp(),emit(E.place)=E1.place+T.place}3.E→T{E.place=newtemp(),emit(E.place=T.place)}4.T→T1*F{T.place=newtemp(),emit(T.place)=T1.place*F.place}5.T→F{T.place=newtemp(),emit(T.place=F.place)}6.F→_P{F.place=newtemp(),emit(F.place)=@P.place}7.P→(E){P.place=newtemp(),emit(P.place=E.place)}8.P→i{P.place=newtemp(),emit(P.place=Entry(i))}例如:表达式X:=a+b*(c-d)的翻译K+1:T1:=c-dK+2:T2=b*T1K+3:T3:=a+T2K+4:X:=T3(-,c,d,T1)(*,b,T1,T2)(+,a,T2,T3)(:=,T3,_,X)布尔表达式的翻译布尔表达式是由布尔运算符(and,or,not)作用于布尔变量(或常数)或关系表达式而形成的。布尔表达式的作用：用作控制语句中的条件：if-then、while、repeat等逻辑赋值句中的逻辑运算布尔表达式到四元式的翻译

文法：E

E

E

E

E

E

(E)

id

EropE

其中，

(and)、

(or)、

(not)为布尔（逻辑）运算符；rop为关系运算符（>，≥，

，≤，=，≠）；id为布尔（逻辑）变量或布尔（逻辑）常数；EropE为关系表达式。布尔表达式的求值方法：①通过逐步计算出各部分的值来计算整个表达式。②利用布尔运算符的性质计算其值布尔表达式作为控制语句中的条件式作用是用于选择下一个执行点

whileEdoS1E的作用是选择S1执行,还是跳过S1语句,执行S1后面的语句E有两个出口:真:S1语句假:S1后面的语句While语句的目标结构

假E的代码真

whilleS1的代码

doJMPW.headW.head布尔初等量(布尔变量和关系表达式)的目标结构

由两个转移四元式构成,一个表示真出口Li,另一个表示假出口Lj,设E是一布尔变量,它的目标结构为:(1)ifEgotoLi(jumpt,E,_,Li)

(jnz,A,_,Li)(2)ifE1ropE2gotoLi(jumpθ,E1,E2,Li)

(jrop,E1,E2,Li)例:(j<,a,b,p)(3)gotoLj(jumpLj)(j,_,_,Lj)举例:ifa<bthenA:=x+y的四元式序列

ifa<bgotoLi(真出口)gotoLj(假出口)Li:S的第一个四元式…S的最后一个四元式Lj:S后面的语句(1)ifa<bgoto(3)(2)goto(5)(3)T1:=x+y(4)A:=T1(5)

多因子组成的布尔表达式的翻译例:ifa<b∨cthenS1elseS2分析结果如下:当a<b为真,执行S1,不需要计算c的值当a<b为假,计算c的值,c为真:执行S1,为假:执行S2当a<b与c分别为真时,程序转向一致,真出口相同(S1)当a<b与c分别为假时,程序转向一致,假出口相同(S2)ifa<b∨cthenS1elseS2的四元式序列(1)ifa<bgotoS1的第一条语句(5)(2)goto(3)(3)ifcgotoS1的第一条语句(5)(4)gotoS2的第一条语句(p+1(5)关于S1的四元式序列

…

(p)Gotoq(p+1)关于S2的四元式序列

…

(q)后继四元式目标结构E的代码TFS1的代码JUMPSS2的代码S（后继语句）

ifEthenS1elseS2

的四元式序列(1)ifEgoto(3)(2)goto(S2的第一个四元式)(p+1)(3)关于S1的四元式序列……(p)gotor(执行完S1后转出)(p+1)关于S2的四元式序列……(r)后继四元式

whileEdoS1的四元式序列(1)ifEgoto(3)(2)goto(S1后面的语句)(p+1)(3)关于S1的四元式序列……(p)goto(1)(p+1)后继四元式真出口链、假出口链、回填（Backparch)在多个因子组成的布尔表达式中，可能有多个因子的真出口或假出口的转移去向相同，但又不能立刻知道具体转向位置。把转移方向相同的四元式链在一起，一旦发现具体转移目标，就回填。真出口用Etrue来表示。假出口用Efalse来表示。回填Backparch（g,t)将t填入由g所指向的四元式的结果部分ifa<b∨cthenS1elseS2

的真假出口回填描述语法制导翻译中使用的公共变量、过程和函数

guad:四元式指针(表示四元式的编号或地址)GEN(X):生成一条四元式,把它放到四元式表的尾部,(和前面介绍的emit功能相同)Nextguad:指向下一个即将形成的四元式的编号,其初值为1,执行一次GEN(X),Nextguad自动加1;merg（p1,p2)函数将以p1,p2为链首的两个四元式合并为一,返回合并后的链首条件语句的翻译

基本思路：①先对定义它的文法进行改造，以便能在相应处添加上语义子程序；②根据它的语义，设计出相应语义子程序的动作。

if语句的文法S→ifEthenS1S→ifEthenS1elseS2(E是转移条件)对ifEthenS1elseS2,其Etrue直到扫描到then,产生S1的第一个四元式序号时,才能将该标号作为E的真链填入到Etrue,而Efalse

直到扫描到else,产生S2的第一个四元式序号时,才得到Efalse的值。if语句文法的改造(1)C→ifEthen(2)T→CS1else(3)S→TS2(4)S→CS1目标结构如右图T.chainS1.chainE.true

E.falseelseIf

thenS1的代码

JUMP0E的代码C.chainS2.chainS2的代码S.chainif语句的语义动作(1)C→ifEthen{backpatch(Etrue,

Nextguad),C.chain=Efalse}

当用产生式ifEthen进行归约时,生成了条件E的代码,E的假出口不能回填,通过非终结符C向后传递,所以引入链.if语句的语义动作(2)T→CS1else{q:=

Nextguad,emit(goto0)Backpatch(C.chain,Nextguad),T.chain=merg(S1.chain,q)}当用产生式T→CS1else归约时,S1的代码已经形成,回填E的假出口即。此时S2

的代码尚未形成,S1的转出链和JMP转向相同,合并为一,通过T向后传递.if语句的语义动作(3)S→TS2{S.chain:=merg(T.chain,S2.chain)}(4)S→CS1{S.chain:=merg(C.chain,S1.chain)IfA∧B∧C＞DthenifA＜BthenF:=1elseF:=0elseG:=G+1(9)F:=1(10)goto0(15)(11)F:=0(12)goto(10)(15)(13)T:=G+1(14)G:=T(15)IfA∧B∧C＞DthenifA＜BthenF:=1elseF:=0elseG:=G+1四元式形式代码(1)(jnz,A,_,(3))(2)(j,_,_,0)(13)(3)(jnz,B,_,(5)(4)(j,_,_,(2))(13)(5)(j>,C,D,(7))(6)(j,_,_,(4))(13)(7)(j<,A,B,(9))(8)(j,_,_,0)(11)While语句的翻译文法:G[S]S→whileEdoS

文法改造为:S→CS1C→WEdoW→while

Etrue

S1chainEfalse

do

假E的代码

真whilleS1的代码JMPW.headW.headC.chainWhile语句的语义动作（1）W→while{W.head:=

Nextguad;}当用W→while归约时,Nextguad记下E的第一个四元式的位置,保留在Wguad中。（2）C→WEdo{backpatch(Etrue,Nextguad,C.chain=Efalse,C.head=W.head}当使用C→WEdo进行归约时,E的代码已经生成有两个出口Etrue和Efalse,扫描完do后,可以回填Etrue,而Efalse要到S1语句全部生成后才能回填,因此为待填信息,由C向后传递。While语句的语义动作（3）S

CS1

{Backpatch(S1chain,C.head);S.chain:=C.chain;GEN(goto,W.head);当用上式进行归约时，S1语句全部产生，while语句结束应返回，因此产生四元式（gotow.head),同时回填Efalse

whilea>0∧b>0do

ifx>ythenb:=b-1elsea:=a-1

假设四元式序列从100开始编号100（j>,a,0,102)101(j,_,_,0)(112)102(j>,b,0,104)103(j,_,_,101)(112)104(j>,x,y,106)105(j,_,_,0)(109)106(-,b,1,T1)107(:=,T1,_,b)108(j,_,_,100)109(j,a,1,T2)110(:=,T2,_.a)111(j,_,_,100)112文法G[S]:S→SaA︱AA→AbB︱BB→cSd︱e(1)证明AacAbcBaAdbed是文法的一个句型.(2)请写出该句型的所有短语、素短语及句柄。（3）为文法G[S]的产生式构造相应的翻译子程序，使句型AacAbcBaAdbed经该翻译方案翻译后，输出为。文法及相应的翻译方案如下:S→bTc{print”1”}S→a{print”2”}T→R{print”3”}R→R/S{print”4”}R→S{print”5”}对于输入符号串bR/bTc/bSc/ac,该符号串的输出是什么?输出为1453142431归约的次序为:(1)S→bTc(1)(2)R→R/S(4)(3)R→S(5)(4)T→R(3)(5)S→bTc(1)(6)R→R/S(4)(7)S→a(2)(8)R→R/S(4)(9)T→R(3)(10)S→bTc(1)采用then与else的最近匹配原则(三地址指令)a+b*cabc*+例