编译课件2表达式翻译5 2 4 5

5.2.4四元式表示法四元式是一种普遍采用的中间代码形式，每个四元式包括四个组成部分:OP，ARG1，ARG2，RESULT，表示形式为四元组(OP,ARG1,ARG2,RESULT)。其中:OP——算符。ARG1，ARG2——运算量。RESULT——运算结果。例，赋值语句A:=-B*(C+D)可表示成四元式表:凡只需一个运算量的算符(单目运算符)，一律使用ARG1。

T1临时变量T1——B@（1）T2临时变量T2DC+（2）T3临时变量T3T2T1*（3）赋值运算A——T3:=（4）注解RESULTARG2ARG1OP序号运算量和运算结果有时指用户自定义的变量，有时指编译程序引进的临时变量。四元式间的联系是通过临时变量实现的，这样更改四元式表很容易。

相对来说，更改三元式比较困难，因为它意味着必须改变其中一系列指示器的值。

在对中间代码进行优化处理时，四元式比三元式方便。

学习要点:

熟悉语法制导翻译的过程。

掌握各种语法结构生成的中间代码。

了解语义子程序的设计。5.3表达式及赋值语句的翻译

5.3.1算术表达式与赋值语句的翻译

1.只含整型变量的简单赋值语句的翻译

A

i:=EE

E+E|E*E|

-E|

(E)|i例，X:=5+6*7为了实现翻译，需要定义一系列语义变量和语义过程。

生成四元式为:(*，6，7，T1)(+，5，T1，T2)(:=，T2，，X)语义变量和语义过程:

NEWTEMP:

函数过程，产生临时变量，每次调用时，回送一个代表新临时变量名的整数码作为函数值，临时变量名产生顺序可想象为T1，T2……。ENTRY(i):

函数过程，查找并取得与i相对应的标识符在符号表中的位置(入口)，简称i值。

E.PLACE:

与E有联系的语义变量，表示存放E值的变量名在符号表入口或整数码

(若此变量是一个临时变量)。

GEN(OP,ARG1,ARG2,RESULT):

语义过程，将四元式(OP,ARG1,ARG2,RESULT)填进四元式表中。

上述文法的语义动作描述:产生式

语义动作

(1)A

i:=E

{GEN(:=,E.PLACE,—,ENTRY(i))}(2)E

E(1)+E(2){E.PLACE=NEWTEMP；

GEN(+,E(1).PLACE,E(2).PLACE,E.PLACE)}(3)E

E(1)

*E(2)

{E.PLACE=NEWTEMP；

GEN(*,E(1).PLACE,E(2).PLACE,E.PLACE)}(4)E

-E(1) {E.PLACE=NEWTEMP；

GEN(@,E(1).PLACE,—,E.PLACE)}(5)E

(E(1))

{E.PLACE=E(1).PLACE}(6)E

i

{E.PLACE=ENTRY(i)}输入

栈

PLACE四元式

A:=-B*(C+D):=-B*

(C+D)i-B*

(C+D)i:=

A_B*(C+D)i:=

-

A_

_*(C+D)i:=-i A_

_B

*(C+D)i:=-E A_

_B

(@,B,—,T1)

*

(C+D)i:=E A_T1(C+D)i:=E*

A_T1_C+D)i:=E*( A_T1_

_+D)i:=E*(i A_T1_

_C

+D)i:=E*(E A_T1_

_C例，A:=-B*(C+D)的语法制导翻译过程i:=-i*(i+i)D)i:=E*(E+A_T1_

_C_)i:=E*

(E+iA_T1_

_C_D

)i:=E*

(E+E

A_T1_

_C_D

(+,C,D,T2)

)i:=E*

(EA_T1_

_T2i:=E*

(E)A_T1_

_T2_

i:=E*EA_T1_T2

(*,T1,T2,T3)

i:=E

A_T3

(:=,T3,—,A)

A输入

栈

PLACE四元式

最终生成:(@,B,—,T1)(+,C,D,T2)(*,T1,T2,T3)(:=,T3,—,A)2.类型转换

一个表达式中可能出现各种不同类型的变量和常数。

所以，编译程序必须做到:或者拒绝接受某种混合运算，或者产生有关类型转换的指令。

A

i:=EE

E+E|E*E|

-E|

(E)|i文法中的i

既可是整型量，又可是实型量。当两个不同类型的量进行运算时，规定首先必须把整型量转换成实型量。

(1)

为实现类型转换，每个非终结符的语义值必须增加类型信息。用E.MODE表示，取值为r(实型)或int(整型)。

例，对于整形运算，产生式

E

E(1)opE(2)，E.MODE的语义规则将定义为:{if((E(1).MODE==int)&&(E(2).MODE==int))E.MODE=int；}(2)

在四元式中增加一个整型变量转换为实型变量的四元式:(itr,A,—,T)，同时在运算符上应指出相应的类型，这里规定用上角标表示(opi，opr)。

例，赋值语句:X:=Y+I*J其中:X,Y为实型；I,J为整型

它产生的四元式为:

(

*i,I,J,T1)(itr,T1,—,T2)(+r,Y,T2,T3)(:=,T3,—,X)产生式:E

E(1)opE(2)的语义子程序的描述是:

if((E(1).MODE==int)&&(E(2).MODE==int)){GEN(opi,E(1).PLACE,E(2).PLACE,T)；

E.MODE=int；

}elseif((E(1).MODE==r)&&(E(2).MODE==r)){GEN(opr

,E(1).PLACE,E(2).PLACE,T)；

E.MODE=r；

}T=NEWTEMP；elseif(E(1).MODE==int)/*&&(E(2).MODE==r)*/U=NEWTEMP；

GEN(itr,E(1).PLACE,—,U)；

GEN(opr,U,E(2).PLACE,T)；

E.MODE=r；{}{}else/*(E(1).MODE==r)&&(E(2).MODE==int)*/U=NEWTEMP；

GEN(itr,E(2).PLACE,—,U)；

GEN(opr,E(1).PLACE,U,T)；

E.MODE=r；E.PLACE=T；输入

栈

PLACE四元式

X:=Y+I*J:=Y+I*JiY+I*Ji:=

X_+I*Ji:=iX_

Y

+I*Ji:=E X_

Y I*Ji:=E+X_Y_*Ji:=E+

iX_Y_I

*Ji:=E+

EX_Y_I例，X:=Y+I*J的语法制导翻译过程i:=i+i*iJi:=E+

E

*X_Y_I_i:=E+

E

*

i

X_Y_I_Ji:=E+

E*

EX_Y_I_J

(*i,I,J,T1)

i:=EX_T3(:=,T3,—,X)i:=E+

EX_Y_T1(itr,T1,—,T2)(+r,Y,T2,T3)输入

栈

PLACE四元式

A5.3.2布尔表达式的翻译

布尔表达式在程序语言中有两个基本功用:

一是作为控制语句(如

if或

while语句)的条件式；

二是作逻辑运算，获得逻辑值。

IfX=0thenY:=3；1∨

(

┐0∧0)

∨0布尔表达式由布尔算符作用于布尔变量或常量，或关系表达式而形成的。

布尔算符(按优先级)有:┐(非)，∧(与)，∨(或)。

关系符rop有:<，≤，=，≠，>，≥

布尔变量:Boolean:A，B，C。

布尔常量:true，false，1，0。

关系表达式是由关系符作用于算术表达式而形成，如E1ropE2。布尔表达式的文法:E

E∧E|E∨E|┐E|(E)|i|iropi计算布尔表达式的值:

1.直接计算

按算术表达式的计算方式根据布尔运算符的优先级和结合关系计算布尔表达式。

例，令true=1，false=0，计算布尔表达式:1∨(┐0∧0)∨0=

1∨(1∧0)∨0=

1∨0∨0=

1∨0=

12.

采用某种优化措施来计算

计算A∨B，只要计算出A=1，则不必再算B，可知结果为1；

计算A∧B，只要计算出A=0，则不必再算B，可知结果为0；

用条件句来解释布尔计算:A∨B解释为

ifAthentrueelseBA∧B解释为

ifAthenBelsefalse┐A解释为

ifAthenfalseelsetrue针对两种算法有两种不同的翻译方法。

优化计算条件语句的翻译:条件语句

ifEthenS1elseS2中的布尔式E，它的作用在于控制对S1

和

S2的选择。

E的代码S1的代码S2的代码真假为了表述真、假出口，引入三种形式的四元式:

(1)(jnz,A1,—,p)若A1为‘真’，则转向第p个四元式。

(2)(jθ,A1,A2,p)若A1θA2为‘真’,则转向第p个四元式。

(3)(j

,—,—,p)无条件转向第p个四元式。

例，将

ifA∨B<DthenS1elseS2

翻译成四元式序列为每一个子布尔式都定义两个四元式，分别指向真假出口。(jnz,A,—,0)真出口(j,—,—,0)假出口(j<,B,D,0)真出口(j,—,—,0)假出口(1)(jnz,A,—,0) A的“真”出口开始未知，填0；ifA∨B<DthenS1elseS2翻译成四元式序列为:

(2)(j,—,—,0) A的“假”出口开始未知0；(3)(j<,B,D,1) B<D的“真”出口与1真出口合并；(4)(j,—,—,0

) B<D的“假”出口未知，填0；(5)(关于S1的四元式序列)；(p)(j,—,—,0) 跳过S2的代码段，开始未知；(p+1)

(关于S2的四元式序列)；(q)……(1)(jnz,A,—,5) A的“真”出口为5；(3)(j<,B,D,5) B<D的“真”出口为5；(4)(j,—,—,p+1

) B<D的“假”出口为(p+1)；(p)(j,—,—,q) 跳过S2的代码段；E的代码S1的代码S2的代码(2)(j,—,—,3) A的“假”出口为3；注意一个布尔表达式的真假出口:

如

E

E(1)∨E(2)

若E(1)为真，则E为真，E(1)的真出口即E的真出口；

若E(1)为假，再看E(2)。

E(2)为真，则E为真，E(2)的真出口就是E的真出口E(2)为假，则E为假，E(2)的假出口就是E的假出口如

E

E(1)∧E(2)

若E(1)为假，则E为假，E(1)的假出口即E的假出口；

若E(1)为真，再看E(2)。

E(2)为真，则E为真，E(2)的真出口就是E的真出口E(2)为假，则E为假，E(2)的假出口就是E的假出口如

E

┐E(1)若E(1)为假，则E为真，E(1)的假出口即E的真出口；

若E(1)为真，则E为假，E(1)的真出口即E的假出口；

问题1.在自下而上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上，必须等到分析后面的语句时进行回填，所以需要回填的四元式的地址必须被保存起来。

存在两个问题:例，A∨B<DA归约为E(E

i)时产生四元式p

(jnz,A,—,0)E

E∧E|E∨E|┐E|(E)|i|iropi解决方法:对非终结符定义两个语义值

E.TC

和

E.FC，分别记录表达式E所对应的四元式需回填的真、假出口的四元式地址所构成的链。

例，E的四元式中需回填的‘真’出口的有p,q和r三个四元式，这三个四元式可以用一条‘真’链

(TC)连接，E.TC的的值为链首r。

(p)(……0) 0为链末标志

(q)(……p)(r)(……q) 地址(r)为TC链之首，

E.TC之值。

……(1)(jnz,A,—,0)A的“真”出口开始未知，填0；例，ifA∨B<DthenS1elseS2(2)(j,—,—,3)A的“假”出口为3；(3)(j<,B,D,1)B<D的“真”出口与1真出口合并；(4)(j,—,—,0

)B<D的“假”出口未知，填0；(5)(关于S1的四元式序列)；(1)(jnz,A,—,5)A的“真”出口为5；(3)(j<,B,D,5)B<D的“真”出口为5；E.TC=3为了处理E.TC和

E.FC，定义新的语义变量和语义过程:NXQ——指示器，指向下一个将要形成但尚未形成的四元式的地址(编号)。其初值为1。每执行GEN一次，自动增1。

MERG(p1,p2)——合并函数，把以p1和p2为链首的链合而为一，合并后的链首作为函数值送回。

BACKPATCH(p,t)——回填函数，把p所链接的每个四元式的第四区段都回填进t。

if(p2==NULL)returnp1；p=p2；while(四元式p的第四区段的内容不为NULL)p=四元式p的第四区段的内容；把p1填进四元式p的第四区段；returnp2；void*MERG(void*p1,void*p2)void*p；{}else{}函数MERG(p1,p2)把p1和p2为链首的链二而为一，p2作为合并后的链首以函数值的形式返回。

（……0） .（……

p1）（……） .（……）

…… ……p1（……）

p2（……）若p2≠NULL，则p2链的链尾NULL改成p1，p2为新的链首；否则，若p2=NULL，p1为新的链首。

q=p；q1=四元式q的第四区段的内容；把t填进四元式q的第四区段；q=q1；while(q!=NULL){}void*BACKPATCH(void*p,void*t){void*q,*q1；}函数BACKPATCH(p,t)，负责把p所链接的每个四元式的第四区段都回填进t。

(1)(jnz,A,—,0)A的“真”出口开始未知，填0；例，ifA∨B<DthenS1elseS2(2)(j,—,—,3)A的“假”出口为3；(3)(j<,B,D,0)B<D的“真”出口开始为0；(4)(j,—,—,0

)B<D的“假”出口未知，填0；(5)(关于S1的四元式序列)；(3)(j<,B,D,1)B<D的“真”出口与1真出口合并；E.TC=3(1)(jnz,A,—,5)A的“真”出口为5；(3)(j<,B,D,5)B<D的“真”出口为5；问题2:真假出口何时回填？E

E∧E|E∨E|┐E|(E)|i|iropi例，ifA∨B<DthenS1elseS2(1)(jnz,A,—,0) A的“真”出口开始未知，填0；(2)(j,—,—,0) A的“假”出口开始未知0；(3)(j<,B,D,1) B<D的“真”出口与1真出口合并；(2)(j,—,—,3) A的“假”出口为3；(4)(j,—,—,0

)B<D的“假”出口未知，填0；E

E∧E|E∨E|┐E|(E)|i|iropi例，ifA∧B<DthenS1elseS2(1)(jnz,A,—,0) A的“真”出口开始未知，填0；(2)(j,—,—,0) A的“假”出口开始未知0；(3)(j<,B,D,0) B<D的“真”出口开始未知0；(1)(jnz,A,—,3) A的“真”出口为3；(4)(j,—,—,2) B<D的“假”出口与2假出口合并；为了使用语法制导翻译，在扫描到∧或∨时能及时回填一些业已明确的待填的转移目标，需要对文法改写成:E

EAE|EOE|┐E|(E)|i|iropiEA

E∧

EO

E∨

E

E∧E|E∨E|┐E|(E)|i|iropi文法的每个产生式相应的语义子程序如下:(1)E

i{E.TC=NXQ；E.FC=NXQ+1；GEN(jnz,ENTRY(i),—,0)；GEN(j,—,—,0)}(2)E

i(1)ropi(2)

{E.TC=NXQ；E.FC=NXQ+1；GEN(jrop,ENTRY(i(1)),ENTRY(i(2)),0)；GEN(j,—,—,0)}(3)E

(E(1)){E.TC

=E(1).TC；E.FC=E(1).FC}(4)E

┐E(1)

{E.TC

=E(1).FC；E.FC=E(1).TC}(5)EA

E(1)∧

{

BACKPATCH(E(1).TC，NXQ)；EA.FC=E(1).FC}(6)E

EAE(2)

{E.TC=E(2).TC；E.FC=MERG

(EA.FC，E(2).FC)}(7)EO

E(1)∨

{BACKPATCH(E(