语法制导翻译推选资料

语法制导翻译编译中的语义处理是指两个功能：

一、审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。二、如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。教学内容属性文法与属性翻译文法语法制导翻译概论常见中间语言概述简单算术表达式和赋值语句的翻译布尔表达式的翻译程序流程控制语句的翻译含数组元素及其在赋值语句中的翻译§5.1属性文法与属性翻译文法

一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上，在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。属性文法

属性，常用以描述事物或人的特征、性质、品质等等。比如，谈到一个物体，可以用“颜色”描述它，谈起某人，可以使用“有幽默感”来形容他。对编译程序使用的语法树的结点，可以用“类型”、“值”或“存储位置”来描述它。

G：是一个上下文无关文法。

V：有穷的属性集,每个属性与文法的一个终结符或非终结符相连。

F：关于属性的属性断言或谓词集。每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性。属性文法是一个三元组：A=（G，V，F），其中

如，有文法G为：

E→T1+T2|T1orT2

T→num|true|false

因为T在同一个产生式里出现了两次，使用上角标将它们区分开。属性文法记号中常使用的形式表示与非终结符N相联的属性t。比如可把完成对上面表达式的类型检查的属性文法写成形式：

类型检查的属性文法

E→T1+T2｛T1.t=intANDT2.t=int｝

E→T1orT2｛T1.t=boolANDT2.t=bool｝

T→false｛：=bool｝

T→num｛：=int｝

T→true｛：=bool｝

与每个非终结符T相联的有属性t，t要么是int，要么是bool。与非终结符E的产生式相联的断言指明：两个T的属性必须相同。

1）E→E1+E2｛：=E1.val+E2.val｝可以用如下的方式定义E的“值”的语义：

2）E→1 ｛：=1｝

3）E→0 ｛：=0｝属性分成两类：继承属性和综合属性，我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。在编译的许多实际应用中，属性和断言以多种形式出现，也就是说，与每个文法符号相联的可以是各种属性、断言、以及语义规则，或者某种程序设计语言的程序段等等。

产生式语义规则（0）L→E

print（）（1）E→E1+T

E.val:=E1（2）E→T

（3）T→T1*F

T.val:=T1（4）T→F

（5）F→（E）（6）F→digit

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

在该描述中，每个非终结符都有一个属性：一个整数值的称作val的属性。按照语义规则对每个产生式来说，它的左部E，T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性。单词digit仅有综合属性，它的值是由词法分析程序提供的。和产生式L→E相联的语义规则是一个过程，打印由E产生的表达式的值。我们可以理解为L的属性是空的或是虚的。5.2语法制导翻译的概述基本思想： 在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行推导（对于自上而下分析）或归约（对于自下而上分析），就执行该产生式所对应的语义动作，完成相应的翻译工作。语法制导翻译就是把语言的一些属性附加到代表语言结构的文法符号上，这些属性值是由附加到文法产生式的“语义规则”中计算的，也就是为每个产生式配备翻译子程序，即语义子程序。语法制导翻译法不论对自上而下分析或自下而上分析都适用。翻译的任务：语法结构的静态语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。使用的方法:称作语法制导翻译。基本思想（简言之）:根据翻译的需要设置文法符号的属性(这些属性代表与文法符号相关的信息)，以描述语法结构的语义。属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。一个属性文法它包含一个上下文无关文法和一系列语义规则，这些语法规则附在文法的每个产生式上。在一个语法制导定义中，

A→

P都有与之相关联的一套语义规则，规则形式为

b：=f（c1，c2，…，ck），f是一个函数，而且

1．b是A的一个综合属性并且c1，c2，…，ck是

中的符号的属性，或者

2．b是

中的符号的一个继承属性并且c1，c2，…，ck是A或

中的任何文法符号的属性。在两种情况下，都说

属性b依赖于属性c1，c2，…，ck。语法制导定义的形式

一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内“封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算,由属性计算器的参数提供。特例：开始符号没有继承属性，在开始时要确定；终结符则只能有综合属性，而不能有继承属性。非终结符既可有综合属性也可有继承属性语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成过程调用，或过程段。综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S—属性文法。继承属性：在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。例6.1台式计算器程序的语法制导定义（表6.1)产生式语义规则S’Eprint(Eval)EE1+TEval:=E1val+TvalETEval:=TvalTT1*FTval:=T1val*FvalTFTval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexval每个文法符号和一个属性值val联系，属性值的设置和语法结构的语义以及翻译程序的需要有关。例如：把左例中的类型扩充到int和real。综合属性

S-属性定义唯独只使用综合属性的语法制导定义。结点属性值的计算正好和自底向上分析建立分析树结点同步进行。例6.2输入：3*5+4n

digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19例输入3*5+4nLEnEE1+TETTT1*FTFF(E)Fdigit

◆综合属性值的计算方法

对于s-属性定义通常使用自底向上的分析方法在建立每一个结点处综合属性值使用语义规则来计算即：哪个产生式进行归约后，就执行那个产生式的s-属性定义计算属性的值，从叶结点到根结点进行计算。继承属性继承属性值是由此结点的父结点和／或兄弟结点的某些属性值来决定的。例描述说明语句中各种变量的类型信息的语义规则。

文法定义了一种说明语句，该说明语句的形式由关键字int或real开头，后跟一个标识符表，每个标识符间有逗号隔开。非终结符号T有一个综合属性type，它的值由关键字int或real决定。与产生式D->TL相联的语义将的属性值置为该说明语句指定的类型。属性将沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了它。过程addtype的功能是把每个标识符的类型信息登录在符号表中相关项中。(-,A,21,T2)（3）（*，t1，t2，t3）goto′nextstat+3）；2．b是中的符号的一个继承属性并且c1，c2，…，ck是A或中的任何文法符号的属性。属性b依赖于属性c1，c2，…，ck。(2)扫描do后，回填；place:=newtemp；类型检查的属性文法应无条件转移到REPEAT语句的第一个四元式。对于s-属性定义通常使用自底向上的分析方法place′:=′E1.解决方法是暂时保存该四元式的地址作为E的语义值，等表达式的四元式产生完了之后在来回填这个转移目标。

带有继承属性的语法制导定义

产生式语义规则

DTLL

in:=T

typeTintT

type:=integerTrealT

type:=realLL1,idL1

in:=L

inaddtype(id

entry,L

in)Lidaddtype(id

entry,L

in)分析reali1,i2,i3DTLrealLi3Li2i1reali3.entryi2.entryi1.entry语法制导翻译的实现途径以自下而上（LR分析）的语法制导翻译来说明将LR分析器能力扩大，增加在归约后调用语义规则的功能增加语义栈，语义值放到与符号栈同步操作的语义栈中，多项语义值可设多个语义栈，栈结构为：状态栈符号栈语义栈SmXmXm.val………S1X1X1.valS0#-例简单算术表达式求值的属性文法L→E{print(E.val)}E→E1+T {E.val:＝E1.val+T.val}E→T {E.val:＝T.val}T→T1*digit {T.val:＝T1.val*digit.lexval}T→digit {T.val:＝digit.lexval}

状态ACTIONGOTOd+*#ET0S3

12

1S4

acc2r3

S5r3

33r5r5

r54S3

75S6

6

r4r4

r47r2S5r2步骤状态栈语义栈符号栈剩余输入串ActionGOTO00-#2＋3*5＃S3103--#2＋3*5＃r52202-2#T＋3*5＃r31301-2#E＋3*5＃S44014-2-#E+3*5＃S350143-2--#E+3*5＃r5760147-2-3#E+T*5＃S5701475-2-3-#E+T*5＃S68014756-2-3-5#E+T*5＃r4790147-2-15#E+T#r211001-17#E#acc分析并计算2＋3*5的过程如下:语义子程序一个语义子程序描述了一个产生式对应的翻译工作。这些工作有：改变编译程序某些变量的值、查填各种符号表、发现并报告源程序错误、产生中间代码。在描述语义动作时需要为每个文法符号赋以各种不同的语义值：类型、地址、代码值等。如果一个产生式中一个符号多次出现，就用上角标来区分，如：E=E(1)+E(2)

假定我们现在要分析的语法成分是简单算术表达式，所完成的语义的处理不是将它翻译成中间代码或目标代码，而是计算表达式的值。采用的描述系统是上节的例1。假如语法分析方法是自下而上的。在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的“值”也就同时产生了，例如输入串是3*5+4。LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树

法制导翻译的具体实现途径不困难。假定有一个LR语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在属性文法中描述的语义动作。每步工作后的语义值保存在扩充的分析栈里“语义值”栏中。采用LR分析，其中使用d代替digit。分析和计值2+3*5的过程。

接受15）##E-1701r114）##E+T—2—(15)169r313）##E+T*F—2—3—501697(10)r612）##E+T*5—2—3——01697511）5##E+T*—2—3—0169710）*5##E+T—2—30169r49）*5##E+F—2—30163r68）*5##E+3—2——01657）3*5##E+—2—0166）+3*5##E—201r25）+3*5##T—202r44）+3*5##F—203r63）+3*5##2——052）2+3*5##—01）留余输入串符号栈语义栈状态栈归约动作步骤2+3*5的分析和计值过程所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。中间代码形式常见中间语言概述

逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。

逆波兰记号

程序设计语言中的逆波兰表示：

a+b

ab+

a+b*c

abc*+（a+b）*c

ab+c*

a:=b*c+b*d

abc*bd*+:=

后缀表示法表示表达式，其最大的优点是最易于计算机处理表达式。利用一个栈，自左至右扫描算术表达式（后缀表示）。每碰到运算对象，就把它推进栈；碰到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施运算，并将运算结果代替这两个运算对象而进栈。若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈。最后的结果留在栈顶。

B@CD*+（它的中缀表示为-B+C*D，使用@表示一目减）的计值过程为：

1、B进栈；

2、对栈顶元素施行一目减运算，并将结果代替栈顶，即-B置于栈顶；

3、C进栈；

4、D进栈；

5、栈顶两元素相乘，两元素退栈，相乘结果置栈顶；

由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。

6、栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。

把表达式及各种语句表示成一组三元式。每个三元式三个组成部分是：算符op，第一运算对象ARG1，和第二运算对象ARG2。

三元式表示a:=b*c+b*d的三元式表示为：

（1）（*，b，c）（2）（*，b，c）（3）（+，（1），（2））（4）（:=，（3），a）：=a

+**

b

c

b

d

树形表示是三元式表示翻版。上述三元式可表示成下面的树表示：*

T1

T2e1*e2+

T1T2e1+e2——T1-e1

表达式的树形表示很容易实现：简单变量或常数的树就是该变量或常数自身，如果表达式e1和e2的树分别为T1和T2，那么e1+e2，e1*e2，-e1的树分别为：例：A+B*（C–D）+E/（C-D）^N

三元式（1）（-

C

D）（2）（*B（1））（3）（+

A（2））（4）（-

C

D）（5）（^（4）N）（6）（/

E（5））（7）（+（3）（6））

间接三元式：间接三元式序列间接码表（1）（-

C

D）（1）（2）（*B（1））（2）（3）（+

A（2））（3）（4）（^（1）N）（1）（5）（/

E（4））（4）（6）（+（3）（5）)（5）（6）

A+B*（C-D）+E/（C-D）^N

四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。四元式

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

（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（*，t1，t2，t3）（4）（:=，t3，＿，a）

A+B*（C-D）+E/（C-D）^N

四元式：（1）（-

C

D

T1）（2）（*B

T1

T2）（3）（+

A

T2

T3）（4）（-

C

D

T4）（5）（^

T4

N

T5）（6）（/

E

T5

T6）（7）（+

T3

T6

T7）

逆波兰：ABCD-*+ECD–N/+

四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。

四元式表示很类似于三地址指令，有时把这类中间表示称为“三地址代码”因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条“指令”包含操作符和三个地址，两个是为运算对象的，一个是为结果的。这种表示对于代码优化和目标代码生成都较有利。

为了更直观，把四元式的形式写成简单赋值形式。比如把上述四元式序列写成：

（1）t1:=b*c（2）t2:=b*d（3）t3:=t1+t2（4）a:=t3把（jump，—，—，L）写成gotoL把（jrop，B，C，L）写成ifBropCgotoL。为了叙述的方便，两种形式我们将同时使用。语法制导生成后缀式利用算符优先进行语法分析设置一个一维数组POST来寄存后缀式，初值为1，然后再为产生式配置语义子程序：(1)EE(1)OPE(2) {POST[k]:=OP；k:=k+1}(2)E(E(1)) {}(3)Ei {POST[k]:=ENTRY(i)；k:=k+1}假设已经有了算符优先表，则利用算符优先分析法分析，在对素短语进行归约时，执行上述的语义子程序，可得到后缀式。语法制导生成后缀式利用优先函数进行语法指导翻译设置一个一维数组POST存放后缀式，并t初：=1;POST[t]:=0;下推栈初始指针K:=1;S[k]=#翻译算法如下：(1)从左至右扫描源程序串，每次读一字符给a；(2)若g(a)>f(s[k])则k:=k+1,s[k]:=a，转(1);(3)若g(a)<f(s[k])则s[k]上弹并送至POST[t],t:=t+1;k:=k-1，转(2)；(4)若g(a)=f(s[k])且不等于1，则上弹s[k];k:=k-1，转(1)(5)若g(a)=f(s[k])=1，结束。后缀式的计算后缀式的计算过程：自左至右扫描后缀式，每碰到运算量就把它推进栈，每碰到k目算符就把它作用于栈顶的k项，并将运算结果来代替这k项。后缀式产生中间代码：自左至右扫描后缀式，每碰到运算量就把它推进栈，每碰到k目算符就把它作用于栈顶的k项，并生成相应的中间代码，并以结果的临时变量序号代替该栈顶的k项。后缀式的推广(1)赋值语句A:=E，后缀式为：AE:=(2)转向语句GOTOL的后缀式为：L’jmp(3)条件语句ifx>ythenm:=xelsem:=y1234567891011121314xy>11jezmx:=14jmy:=…(3)Ei {POST[k]:=ENTRY(i)；place:=newtemp；ifp≠nilthen：与给终结符E相联系的语义变量，可能式某变量的入口地址，或者为临时变量序号。beginS1；(3)翻译S(1)语句称代码段，无条件转移到E代码段的第一条四元式，若S(1)有语句链，也应转到E代码段的第一条四元式。(4)(j,_,_,p+1)（4）（^（1）N）（1）t=bool｝属性分成两类：继承属性和综合属性，我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。goto′nextstat+3）；应无条件转移到REPEAT语句的第一个四元式。例：A∨B<C∧D=E翻译后的四元式为：（6）（/E（5））对编译程序使用的语法树的结点，可以用“类型”、“值”或“存储位置”来描述它。MODE=intELSEE.解决方法是暂时保存该四元式的地址作为E的语义值，等表达式的四元式产生完了之后在来回填这个转移目标。三元式表达式以及各种语句都可以表示成三元式序列，由算符OP，第一运算量ARG1，第二运算量ARG2组成，形势如下：(op,ARG1,ARG2)例：A+B*C可表示成：(1)(*,B,C)(2)(+,A,(1))树+AB*+CAB+-*CBAA+B(A+B)*C-A+B*C主要用于表达式和赋值语句简单算术表达式和赋值语句的翻译赋值语句文法：Ai:=E EE+E|E*E|-E|(E)|i为了实现翻译，需要一些语义变量和过程：NEWTEMP：函数，返回一个临时变量序号；ENTRY(i)：函数，查找变量i的入口地址；GEN(OP,ARG1,ARG2,RESULT)：语义过程，产生一个四元式，并填入四元式表；：与给终结符E相联系的语义变量，可能式某变量的入口地址，或者为临时变量序号。类型转换在一个表达式中，可能出现各种不同类型的变量或常量，编译程序必须做到拒绝接受某种混合运算或者产生有关类型转换的指令。在混合运算情况下，每个非终结符的语义值必须添加类型信息。我们用表示非终结符E的类型信息，的值为r(实型)或int(整型)类型转换如：产生式EE(1)opE(2)的语义动作中关于的规则可定义为：{IFE(1).MODE=intandE(2).MODE=intTHENE.MODE=intELSEE.MODE=r}需添加一各类型转换的四元式：(itr,A1,--,T)意味着把整型量A1转换成实型，结果存放在T中。此外，对于运算符应指出相应的类型。类型转换如：X:=Y+I*J，X,Y为实型，I,J为整型，则相应的四元式序列应为：(*i,I,J,T1)(itr,T1,--,T2)(+r,Y,T2,T3)(:=,T3,--,X)简单赋值语句的四元式翻译

首先对id表示的单词定义一属性，用做语义变量，用Lookup（）表示审查是否出现在符号表中，如在，则返回一指向该登录项的指针，否则返回nil。语义过程emit表示输出四元式到输出文件上。语义过程newtemp表示生成一临时变量，每调用一次，生成一新的临时变量。语义变量E.place，表示存放E值的变量名在符号表的登录项或一整数码产生式和语义描述：

（1）S→id:=E｛p:=lookup（）；

ifp≠nilthen emit（）

elseerror｝

（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

nilthen

E.place:=Pelseerror｝布尔表达式的翻译在程序设计语言中，布尔表达式的两个作用：做控制语句中的条件表达式；用于逻辑符值语句中布尔表达式演算。布尔表达式由布尔运算符作用于布尔变量(或常量)或关系表达式形成。布尔运算符有:∧(与)、∨(或)、┐(非)关系表达式为：E(1)ropE(2)，其中rop为关系运算符，E(1)

和E(2)为算术表达式。布尔表达式的翻译布尔表达式文法简化如下：EE∧E|E∨E|┐E|(E)|i|EaropEb

布尔表达式在逻辑演算中的翻译布尔表达式演算预算数表达式演算非常相似。在翻译为中间代码时，为每个产生式配上相应语义子程序。如：A∨B∧C=D控制语句中布尔式的翻译根据布尔表达式的特点，可以用if-then-else来解释布尔表达式，如：

A∨B==>ifAthentrueelseB;A∧B==>ifAthenBelsefalse;┐A==>ifAthenfalseelsetrue;出现在条件语句IfEthenS1elseS2中的布尔表达式E作用仅在于控制对S1和S2选择。控制语句中布尔式的翻译IfEthenS1elseS2转移条件E可以翻译成三种形式的四元式序列：(jnz,A1,_,p)(jθ,A1,A2,p)(j,_,_,p)E的代码序列S1的代码序列S2的代码序列条件语句的代码结构例：ifA∨B<DthenS1elseS2可翻译为如下的四元式序列：(1)(jnz,A,_,5)(2)(j,_,_,3)(3)(j<,B,D,5)(4)(j,_,_,p+1)(5)(关于S1的四元式序列)(p)(j,_,_,q)(p+1)(关于S2的四元式序列)(q)(j≥,B,D,p+1)一个布尔式的真假出口往往不能在产生四元式的同时就确定。解决方法是暂时保存该四元式的地址作为E的语义值，等表达式的四元式产生完了之后在来回填这个转移目标。为了实现上述过程，需要改写文法如下：

EEAE|E0E|┐E|(E)|i|EaropEaEAE∧E0E∨控制语句中布尔式的翻译为了实现，对于每个非终结符，需要赋予和两项语义值，分别记录表达式E所对应的四元式需回填“真”“假”出口的四元式的地址所构成的链。例：假定E的四元式中需回填“真”出口的有p,q,r三个四元式，可构成一条“真”链(TC)，的值是链首(r)：(p)(x,x,x,0)……(q)(x,x,x,p)……(r)(x,x,x,q)为了处理和两项语义值，需要下面的语义变量和过程：NXQ指示器：指向下一个将要形成但尚未形成的四元式的地址(编号)。初值为1，值型一次GEN后自动累加1；MERG(p1,p2)函数过程：把以p1和p2为链首的两条链合并为一，返回合并后的链首；BACKPATCH(p,t)过程：回填过程，把p所链接的每个四元式的第四区段都填为t。控制语句中布尔式的翻译例：A∨B<C∧D=E翻译后的四元式为：(1)(jnz,A,_,0)(2)(j,_,_,(3))(3)(j<,B,C,(5))(4)(j,_,_,0)(5)(j=,D,E,1)(6)(j,_,_,4)TC头FC头

程序设计语言中的布尔表达式有两个作用。一是计算逻辑值，二是用做改变控制流语句中的条件表达式，如if-then，if-then-else，或是while-do语句中那样。布尔表达式是由布尔算符（and，or和not）施于布尔变量或关系表达式而成。即布尔表达式的形式为E1ropE2，其中E1和E2都是算术表达式，rop是关系符，如〈=<，=，〉=，≠等等。布尔表达式的翻译

计算布尔表达式的值有两种办法，第一种办法，如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。例如，用数1表示true，用0表示false。那么布尔表达式1or（not0and0）or0的计算过程是：布达表达式的翻译方法

1or（not0and0）or0

=1or（1and0）or0

=1or0or0

=1or0

=1

另一种计算方法是采取某种优化措施，只计算部分表达式，例如要计算AorB，若计算出A的值为1，那么B的值就无需再计算了，因为不管B的值为何结果，AorB的值都为1。

上述两种方法对于不包含布尔函数调用的表达式是没有什么差别的。但是，假若一个布尔式中会有布尔函数调用，并且这种函数调用引起副作用（如有对全局量的赋值）时，这两种方法未必等价。采用哪种方法取决于程序设计语言的语义。

若按第一种办法计算布尔表达式。布尔表达式aorbandnotc翻译成四元式序列为：（1）t1:=notc（2）t1:=bandt1（3）t1:=aort2

对于像a<b这样的关系表达式，可看成等价的条件语句ifa<bthen1else0，它翻译成的四元式序列为：（1）ifa<bgoto（4）（2）t:=0（3）goto（5）（4）t:=1（5）…

下面给出了按第一种办法计算布尔表达式的值，将布尔表达式翻译成四元式的描述，其中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.place

relop.opid2.place′goto′nextstat+3）；

emit（E.place′:=′′0′）

emit（′goto′nextstat+2）

emit(E.place′:=′′1′）｝

E→ture｛：=newtemp；

emit(E.place′:=′′1′）｝

E→false（｛：=newtemp；

emit（E.place′:=′′0′）｝

E→id1relopid2｛E.place:=newtemp；

emit（relop.opid2.place′

goto′nextstat+3）；

emit（E.place′:=′′0′）

emit（′goto′nextstat+2）

emit（E.place′:=′′1′）｝

E→ture｛：=newtemp；

emit（E.place′:=′′1′）｝

E→false（｛：=newtemp；

emit（E.place′:=′′0′）｝

E.false控制语句S®ifEthenS1

elseS2E的代码E.trueE.true:S1的代码gotooutE.false:S2的代码out:

作为条件转移的E，仅把E翻译成代码是一串条件转和无条件转四元式。翻译的基本思路是，对于E为aropb的形式生成代码为：ifaropbgotoE.true和。

对于E为E1orE2的形式，若E1是真，则可知道E为真即E1的真出口和E的真出口一样。如果E1是假，那么必须计算E2，E1的假出口就是E2代码的第一个四元式标号，这时E2的真出口和假出口分别与E的真出口和假出口一样。

类似的考虑适于E1andE2的情形。E1的翻译理解容易，只需调换E1的真假出口即可得到E的真假出口。

1、把条件转移布尔表达式

E翻译成仅含条件真转和无条件转的四元式：

E:

a

rop

b

?

If

a

rop

b

goto

E.true

goto

E.false

如：a<borc<dande<f

可翻译成如下四元式：（1）ifa<b

goto

E.true（2）goto（3）（3）ifc<dgoto（5）（4）gotoE.false（5）ife<fgotoE.true（6）gotoE.false（翻译不是最优）（1）if

a<b

goto（7）（2）goto（3）（3）if

c<d

goto（5）（4）goto（p+1）（5）if

e<f

goto（7）（6）goto（p+1）（7）（S1的四元式……）（p）goto（q）（p+1）（s2四元式……）（q）（E.true）（1）和（5）拉链（真）（E.false）（4）和（6）拉链（假）

语句ifa<borc<dande<fthes1else

s2的四元式

上述四元式（1）和（5），（4）和（6）的转移地址并不能产生这些四元式的同时得知。例如（1）和（5）的转移地址是在整个布尔表达式的四元式产生完毕之后才得知。因此要回填这个地址。为了记录需回填地址的四元式，常采用一种“拉链”的办法。把需回填的四元式拉成一链，把需回填的四元式拉成一链，分别称做“真”链和“假”链。2．拉链返填……（10）

gotoL（10）goto0…………链尾

（10）（20）gotoL（20）goto10

……

……（30）

gotoL（30）goto20

……

……链头（30）（40）L:……

（40）L:?控制语句的翻译标号和转移语句(1)先定义后使用(2)先使用后定义NAMEINFORMATIONCAT….定义否地址……L标号已S.QUAD……L’标号未r(p)(x,x,x,0)

……(q)(x,x,x,p)

……(r)(x,x,x,q)IF语句的翻译描述IF语句的文法如下：SifEthenS(1)

或SifEThenS(1)elseS(2)翻译过程大致如下：(1)翻译E，获得一组四元式；(2)扫描E的真出口，回填；假出口尚不知；(3)翻译S(1)

，可以使IF语句也可以使其他；(4)遇到else，S(1)

结束，生成一条无条件转移四元式；但出口不明，需解决嵌套的情况；(5)翻译S(2)

，结束。IF语句的翻译为了完成翻译，需改写产生式如下：产生式SifEthenS(1)elseS(2)

改写为：CifEthenTCS(1)elseSTS(2)产生式SifEthenS(1)

改写为：CifEthenSCS(1)IF语句的翻译例：试翻译IfathenifbthenA:=2elseA:=3elseifcthenA:=4elseA:=5WHILE语句的翻译文法：SWhileEdoS(1)翻译过程大致如下：(1)翻译E，待填，链；(2)扫描do后，回填；(3)翻译S(1)语句称代码段，无条件转移到E代码段的第一条四元式，若S(1)有语句链，也应转到E代码段的第一条四元式。REPEAT语句的翻译文法：SrepeatS(1)untilE翻译过程大致如下：(1)翻译S(1)

，留下待回填语句链S(1).CHIAN(2)扫描until后，回填S(1).CHIAN(3)翻译E代码段，留待填的和；应无条