语法制导翻译

语法制导翻译第1页，共47页，2023年，2月20日，星期二5.1引言在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的目标代码。现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码，然后再将其翻译为目标代码。

优点：使编译程序各组成部分功能更单一;使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件

本章要讨论的中间代码生成，是指把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成表示。

目前常见的中间语言有逆波兰表示、三元式、四元式等等。

中间代码生成与语言的语义密切相关，目前采用语法制导翻译来描述语义。方法:对文法中的每个产生式都附加一个语义动作或语义子程序,语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。

第2页，共47页，2023年，2月20日，星期二5.1引言(续)这种模式既把语法分析与语义处理分开，又令其平行地进行，让其在同一遍扫描中同时完成语法分析和语义处理两项工作。由此可见，抽象文法符号的具体语义信息，是在与语法分析同步的语义处理过程中获取和加工的。文法符号X的语义信息我们称之为语义属性或简称为属性（Attributes）。我们用形如X.ATTR的记号来表示文法符号X的相关语义属性。如果一个文法符号X在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。

第3页，共47页，2023年，2月20日，星期二文法符号及其语义属性文法符号X的语义信息我们称之为语义属性或简称为属性（Attributes）。我们用形如X.ATTR的记号来表示文法符号X的相关语义属性。如果一个文法符号X在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。

例如,文法G[E]:产生式 语义子程序E→E(1)+T {E.Val=E(1).val+T.val;}E→T {E.Val=T.Val;}T→digit {T.Val=digit;}为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个语义信息栈

语法分析栈语义分析栈TT.Val+‘+’E……#

第4页，共47页，2023年，2月20日，星期二本章内容简介首先介绍一种适用于定义语义的一种特殊文法属性文法，进一步介绍适用于语义翻译的文法属性翻译文法的相关知识。在第三小节中我们将介绍几种常见的中间语言;在第四小节中引入程序设计语言中常见语法结构的语法制导翻译技术。

第5页，共47页，2023年，2月20日，星期二5.2属性文法与属性翻译文法

语法制导翻译方法的实质，就是根据文法中每个产生式所蕴含的语义，为其配备一个（或多个）处理语句或子程序，对所要完成的功能进行描述。产生式的语义是由组成该产生式的文法符号的语义所决定的。

将这些语义以“属性”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的求值规则，从而形成一种附带有语义属性的前后文无关文法，即属性文法。

第6页，共47页，2023年，2月20日，星期二5.2.1语义属性与属性文法

定义5.1

一文法符号的语义性质称为该文法符号的语义属性（Attributes），简称为属性。用A(X)表示X的所有属性的集合。每个属性表示X的一个特定性质，并可任意指定其取值范围。我们用X.a表示A(X)中的属性a

。

属性可表征诸如数、符号串、类型、存储空间和其它需表征的实体。终结符至少有一种属性，即词文。它还可能具有其它属性，例如无符号数123，单词“123”就是它的词文，而其数值以及它的类型（整型）是它的其它两个属性。终结符的属性是其内在性质.

非终结符的属性是从其它符号的属性经计算而得的，即由其它符号的属性定义的。

第7页，共47页，2023年，2月20日，星期二属性依赖关系各个文法符号的属性之间，可能存在某种依赖关系，这种依赖关系可用属性规则（语义规则）定义。定义5.2

设p:X0→X1X2…Xn是文法G的一个产生式，则与p相关联的属性规则集

R(p)={Xi.a=f(Xk1.ak1,…,Xkm.akm)|Xi.a∈A(Xi)}定义了该产生式所涉及的文法符号之属性的求值规则，它表示：Xi的a属性是由Xk1的ak1属性，…，Xkm的akm属性计算而得的。

定义

5.3

对每个产生式p:X0→X1X2…Xn

，设属性定义性出现的集合为AF(p)={Xi.a|Xi.a=f(Xk1.ak1,…,Xkm.akm)∈R(p),0≤kj≤n}若Xi是产生式左部的非终结符(即i=0),则称属性Xi.a是综合属性;若Xi出现在产生式的右部(即1≤i≤n),则称Xi.a是继承属性第8页，共47页，2023年，2月20日，星期二加注语法树在语法树中,将每个结点均视为由若干个域组成的结构,则可将其中的一些域用来存放相应文法符号诸属性之值，并可用属性来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为加注语法树由定义5.3可知：在加注语法树中，一个文法符号X在相应结点的综合属性之值，由其子结点的属性和（或）X的其它属性，通过相关属性规则经计算而得，故综合属性的求值在语法树中是按自下而上的方式进行的；X的继承属性之值则由X的父结点和(或)其它兄弟结点来定义,故继承属性的求值将按自上而下的方式进行。第9页，共47页，2023年，2月20日，星期二属性文法的定义定义5.4

属性文法AG是一个四元组：AG=(G,A,R,B),其中,G是已简化的CFG;A=∪X∈VA(X)是属性的有限集合;R=∪p∈PR(p)是属性定义规则的有限集;B=∪p∈PB(p)是条件的有限集合，B(p)用于描述使规则R(p)有效的条件；且同时满足：（1）对G中任意两个不同的文法符号X和Y而言，属性集合A(X)和A(Y)不相交,A(X)∩A(Y)=（2）在G的任意一个语法树中，对文法符号X的每一次出现，可用于计算X的每个属性之值的规则至多有一条。

第10页，共47页，2023年，2月20日，星期二属性文法(续)由定义5.4可知，属性文法实际上就是对前后文无关文法的一种拓广。另外，每个产生式中的任一文法符号的属性计算规则只能是唯一的，且任一文法符号的综合属性集与继承属性集不相交，即AS(X)∩AI(X)=,其中：AS(X)={X.a|p:XP,X.aAF(p)}(综合属性)AI(X)={X.a|q:YXP,X.aAF(q)}(继承属性)第11页，共47页，2023年，2月20日，星期二例5.1

简单赋值语句文法的属性文法第12页，共47页，2023年，2月20日，星期二第13页，共47页，2023年，2月20日，星期二属性依赖关系定义5.6

对于每个产生式p:X0→X1X2…Xn∈P,直接属性依赖关系由下式给出：

DDP(p)={(Xi.a,Xj.b)|Xj.b=f(…,Xi.a,…)∈R(p)}

若序偶(Xi.a,Xj.b)∈DDP(p)，则称属性Xj.b依赖于属性Xi.a

，记作Xi.a→Xj.b。

显然，若有Xi.a→Xj.b

，则对Xj.b的计值，应在求出Xi.a的值之后进行。但若Xi.a又直接或间接地依赖于Xj.b,则称属性Xi.a和Xj.b是循环依赖的。含有属性循环依赖的属性文法AG，其中的一些属性之值将不能得到有效的计算。

第14页，共47页，2023年，2月20日，星期二依赖关系图定义5.7

设T是L(G)中一个句子相应的加注语法树，并设在构造T时使用过产生式p:X0→X1X2…Xn

，对于T中由X0,X1,X2,…,Xn所标记的每个结点，若有

(Xi.a,Xj.b)∈DDP(p),则在树中引一条从到的有向边，由此而得到的树称之为该句子的属性化语法树。 所有这样的有向边构成的集合DT(T)，称为树T上的依赖关系。根据DT(T)所构造的关系图称为依赖关系图（或简称为依赖图）。例如，对于例5.1所给文法下的一个句子x:=y+z，相应属性化语法树的依赖关系如P191图5-3所示。

第15页，共47页，2023年，2月20日，星期二翻译文法的定义定义5.8

在文法产生式右部适当的位置上插入语义动作而得的新文法称为翻译文法或增广文法(AugmentedGrammar)。在一翻译文法中，若每个产生式右部中的全部语义动作均出现在所有文法符号的右边，则称这样的翻译文法为波兰翻译文法。

为了区分文法符号与语义动作，我们用一对花括号‘{’及‘}’将插入的语义动作括起来（语义动作采用C语言格式书写）。而且，我们还把语义动作视为翻译文法中的一个“符号”，称为动作符号。插入语义动作后，翻译文法产生式的一般形式为：A→({statement;})*

∈V*第16页，共47页，2023年，2月20日，星期二翻译文法（续）翻译文法的作用是，在进行语法分析时，无论是用产生式进行推导还是进行归约，只要遇到其中带有语义动作的花括号，就要求编译系统自动执行花括号内指定的语义动作，在执行完该动作之后才继续进行下一步的语法分析。例：Expr→TermExpr’Expr’→+Term{WriteCode(“+”);}Expr’ |Term→FactorTerm’Term’→*Factor

{WriteCode(“*”);}

Term’ |Factor→operand

{WriteCode(yytext);}

|(Expr)第17页，共47页，2023年，2月20日，星期二递归下降分析中的翻译文法若用递归下降法进行语法分析，则与非终结符号Expr’相对应的递归程序可扩充为：int

Eprim(){if(CurrentToken==‘+’)

if(Term()) {WriteCode(“+”);

if(Eprim())return

1;else

return

0; }

if(CurrentToken==‘)‘||CurrenToken==‘#’)return

1;

else

return

0;}第18页，共47页，2023年，2月20日，星期二属性翻译文法的定义定义5.9

属性翻译文法（AttributeTranslationGrammar，简记为ATG）是具有以下性质的翻译文法：1．每个文法符号和语义动作符X都有一个相关的有限属性集合A(X)，且每个属性都有一个允许值的集合（属性的值域，可以是无限集）。2．非终结符和动作符的属性可分为继承属性与综合属性两类。3．继承属性的定义规则为： ①开始符号的继承属性具有指定的初始值；

②对于给定的产生式p:Y→X1X2…Xn∈P,Xi的继承属性值由p中其它符号的属性值进行计算：Xi.a=f(Y.b,Xk1.ak1,…,Xkm.akm)i{k1,…,km}

4．综合属性的定义规则为：①对于给定的产生式p:Y→X1X2…Xn∈P，Y的综合属性值由p中某些符号的属性计算：

Y.u=f(Y.v,Xk1.ak1,…,Xkm.akm)1≦kj≦n；

②对于动作符号，其综合属性值由该动作符的其它属性计算；

③终结符的综合属性具有指定的初始值。

第19页，共47页，2023年，2月20日，星期二对属性文法的一些限制定义5.10

一属性翻译文法称为是L-属性的，当且仅当对其中的每个产生式p:A→X1X2…Xn，下面的三个条件成立：1．右部符号Xi(1≦i≦n)的继承属性之值，仅依赖于X1,X2,…,Xi-1的任意属性或A的继承属性；2．左部符号A的综合属性之值仅依赖于A的继承属性或(和)右部符号Xi(1≦i≦n)的任意属性；3．对一动作符号而言，其综合属性之值是以该动作符号的继承属性或产生式右部符号的任意属性为变元的函数。

第20页，共47页，2023年，2月20日，星期二方法符号属性的求值顺序A的继承属性(∈AI(A))；

X1的继承属性(∈AI(X1))；

X1的综合属性(∈AS(X1),进入X1的子树后，返回时求出）；

…

Xn的继承属性(∈AI(Xn))；

Xn的综合属性(∈AS(Xn),进入Xn的子树后,返回时求出）；A的综合属性(∈AS(A),返回到A的上层）。第21页，共47页，2023年，2月20日，星期二表达式属性翻译文法例5.2表达式属性翻译文法：⒈Program→⒉ |{$1=$2=NewName();}Expr {FreeName($0);} ‘;’

Program

⒊Expr→Term

Expr’⒋Expr’→’+’{$1=$2=NewName();}Term{printf(“+, %s,%s,%s\n”,$0,$$,$0);FreeName($0);} Expr’⒌ |⒍Term→FactorTerm’⒎Term’→’*’{$1=$2=NewName();}Factor{printf(“*, %s,%s,%s\n”,$0,$$,$0);FreeName($0);}Term’⒏ |⒐Factor→Number{printf(“:=,%s,-,%s\n”,yytext,$$);}⒑ |第22页，共47页，2023年，2月20日，星期二S-属性文法的定义定义5.11

满足下面三个条件的属性文法称为S-属性文法：⒈所有非终结符只具有综合属性；⒉在一个产生式中，每一个符号的各个综合属性的定义互不依赖；⒊在一个产生式中，若某个文法符号X具有继承属性，则此继承属性之值仅依赖于该产生式右部且位于X左边的符号之属性。显然，S-属性文法也满足L-属性文法的条件，这就是说，S-属性文法一定是L-属性文法，而且还要求每个非终结符只具有综合属性。第23页，共47页，2023年，2月20日，星期二S-属性文法的例子例5.3

简单算术表达式的S-属性文法：Program→Expr{printf(“%d\n”,$1);}Expr→Expr

’+’

Expr{$$=$1+$3;} |Expr

‘*’

Expr{$$=$1*$3;} |‘(’

Expr

‘)’{$$=$2;} |Number {$$=ToIntValue(yytext);}上面的语义子程序采用了YACC工具中的表示方法,其中$$,$1,$2分别表示产生式左部符号,右部的第一个,第二个符号(余类推)的语义属性.第24页，共47页，2023年，2月20日，星期二5.3常见中间语言简介第25页，共47页，2023年，2月20日，星期二5.3.1逆波兰表示

波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。特点:表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序，因而又称为无括号式。下面我们对照地给出一些表达式的两种表示：

中缀表示 后缀表示

A+B AB+ A+B*C ABC*+ (A+B)*(C+D) AB+CD+* x/y^z-d*e xyz^/de*- (a=0b>3)(ex<>y) a0=b3>exy<>第26页，共47页，2023年，2月20日，星期二逆波兰式的特点①在两种表示中，运算对象出现的顺序相同；②在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在其运算对象之后。由于后缀表示中的各个运算是按顺序执行的，因此，它的计值需从左到右依次扫视表达式中的各个符号，每遇一运算对象，就把它压入栈顶暂存起来；每遇一个二元（或一元）运算符时，就取出栈顶的两个（或一个）运算对象进行相应的运算，并用运算结果去替换栈顶的这两（或一）个运算对象；继续扫视余留的符号，直到扫视完整个表达式为止。当上述过程结束时，整个表达式的值将留于栈顶。第27页，共47页，2023年，2月20日，星期二5.3.2四元式和三元式四元式是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用。四元式是一种“三地址语句”的等价表示。它的一般形式为：(op,arg1,arg2,result)其中，op为一个二元(也可是一元或零元)运算符;arg1,arg2分别为它的两个运算对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言的赋值语句的形式：result:=arg1

op

arg2

第28页，共47页，2023年，2月20日，星期二四元式的格式需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式只能由多个四元式构成的序列表示。例如，表达式A+B*C可写为序列

T1:=B*C

T2:=A+T1当op为一元、零元运算（如无条件转移）时，arg2甚至arg1应缺省，即result:=op

arg1或op

result

；对应的一般形式为：

(op,arg1,-,result)或

(op,-,-,result)。第29页，共47页，2023年，2月20日，星期二三元式为了节省临时变量的开销，有时也可采用一种三元式结构来作为中间代码，其一般形式为(i)(op,arg1,arg2)

其中，(i)为三元式的编号，也代表了该式的运算结果；op,arg1,arg2的含义与四元式类似，区别在于arg可以是某三元式的序号，表示用该三元式的结果作为运算对象。例如，对于赋值语句a:=-b*(c+d)，若用三元式表示，则可写成 ① (U_minus,b,-) ② (+,c,d) ③ (*,①,②) ④ (:=, ③, a)式①中的运算符U_minus表示一元减运算。第30页，共47页，2023年，2月20日，星期二翻译程序中使用的辅助函数我们以算术表达式到三元式的翻译为例，说明如何为各产生式设计语义动作。为此，先介绍若干翻译过程中要使用的辅助函数：⒈int

LookUp(char*Name)—以Name查符号表，若查到则返回相应登记项的序号(≥1),否则返回0。⒉int

Enter(char*Name)—以Name为名字在符号表中登录新的一项,返回值为该项的序号。⒊int

Entry(char*Name)—以Name为名字查、填符号表:

int

Entry(char*Name){inti=LookUp(Name);

if(i)returni;else

return

Enter(Name);}第31页，共47页，2023年，2月20日，星期二翻译程序中使用的辅助函数(续)注意，在实际的编译系统中，还应区分当前是否在处理说明部分：若是说明部分，则查表时i应为0（否则Name被重复定义）；若非，则i不能为0（否则Name尚未被定义）。⒋int

Trip(int

op,int

arg1,int

arg2)—根据给定的参数产生一个三元式

(op,arg1,arg2)

并将它送入三元式表中，其返回值为表中序号。为区分参数arg表示的是三元式还是变量，约定当arg<0时表示三元式序号；arg>0表示变量在符号表中登记项序号；arg=0表示参数为空。第32页，共47页，2023年，2月20日，星期二三元式和四元式之异同在产生式8中，终结符iden的属性是它的词文yytext，用$1表示。每个非终结符都有一个属性，代表以该符号为根的语法树的一个子树的运算结果，该属性的取值可以是整型数，或为一三元式的序号，或为符号表项的序号。

比较三元式和四元式这两种表示方法可以看出，无论在一个三元式序列还是四元式序列中，各个三元式或四元式都是按相应表达式的实际运算顺序出现的。其次，对同一表达式而言，所需的三元式或四元式的个数一般是相同的。

三元式比四元式更能节省存储空间,但不利于优化.可通过引入一些表格提高使用三元式的效率(略,见P200-201)第33页，共47页，2023年，2月20日，星期二5.4简单算术表达式和赋值语句的翻译

约定E中仅含简单变量;全部变量同类型;翻译时不做语义检查.辅助定义int

NewTemp(void)产生临时变量的函数，每次调用都定义一个新的临时变量。返回值为该变量的编号。

X.PLACE文法符号X的属性，其值为整型(>0表示在符号表中序号,<0表示临时变量编号)int

GEN(int

Op,int

Arg1,int

Arg2,int

Result)根据所给实参产生一个四元式：(Op,Arg1,Arg2,Result)，且送入四元式表中，返回值为该四元式的序号。Arg1或Arg2为零时表示该参数缺省第34页，共47页，2023年，2月20日，星期二赋值语句的S-属性翻译文法

1.Statement→AssignSt

{}2.AssignSt→Variable

:=

Expr

{GEN(:=,$3.PLACE,0,$1.PLACE);}3.Expr→Expr

+

Expr

{$$.PLACE=NewTemp(); GEN(+,$1.PLACE,$3.PLACE,$$.PLACE);}4. |Expr

*

Expr

{$$.PLACE=NewTemp();

GEN(*,$1.PLACE,$3.PLACE,$$.PLACE);}5. |(

Expr

)

{$$.PLACE=$2.PLACE;}6. |identifier

{$$.PLACE=Entry($1);}7.Varable→identifier

{$$.PLACE=Entry($1);}第35页，共47页，2023年，2月20日，星期二5.5

布尔表达式的翻译布尔表达式是布尔运算量和逻辑运算符按一定语法规则组成的式子。逻辑运算符通常有∧、∨、﹃三种（在某些语言中，还有≡（等价）及→（蕴含）等等）；逻辑运算对象可以是逻辑值（True

或False）、布尔变量、关系表达式以及由括号括起来的布尔表达式。不论是布尔变量还是布尔表达式，都只能取逻辑值True或False。在计算机内通常用1（或非零整数）表示真值（True），用0表示假值(False)。关系表达式是形如E1

RopE2的式子，其中E1和E2为简单算术表达式，Rop为关系运算符（<,>,=,<=,>=,<>）。若E1和E2之值使该关系式成立，则此关系表达式之值为True，否则为False。第36页，共47页，2023年，2月20日，星期二布尔表达式的等价解释为了方便起见，下面我们仅讨论由文法E→E∧E|E∨E|┑E|(E)|i|iRopi (5.1)对于布尔表达式的计值和翻译，可采用类似算术表达式的方式来进行。例如，对于布尔表达式A∨B∧C，可翻译为：

(∧, B, C, T1) (∨, A, T1, T2)但是，对于一个布尔表达式而言，我们的目的仅仅是为了判定它的真假值。因此，有时只需计算它的一个子表达式，便能确定整个布尔表达式的真假值。例如，对于A∨B，只要知道A为真，则无论B取何值，表达式的结果一定为真。可见，对于三种常见逻辑运算，可作如下等价的解释：

A∧B (A)?B:0 (5.2) A∨B (A)?1:B (5.3) ﹃A (A)?0:1 (5.4)第37页，共47页，2023年，2月20日，星期二布尔表达式的出口对于布尔表达式A∨（B∧（┑C∨D）)，其等价的表述是

A？1：（B？（（C？0：1）？1：D）：0

）显然，采用此种结构可产生更为有效的中间代码。这里需假定原布尔表达式的计算过程中不含有任何的副作用。在上式的计算中，根据A、B、C、D的取值不同，计算的结果以及运算的中止点亦不同。例如，当A=1（真）时，结果为1且中止于左边第一个‘1’处。这样中止的点我们称为该布尔表达式的出口，同时，把使布尔表达式取值为真的出口称为真出口，反之称为假出口。对一个布尔表达式而言，它至少有一个真出口和一个假出口（当然可以有多个）。在用于控制流程的布尔表达式E的计算中，这些出口分别指出当E值为真和假时，控制所应转向的目标（即某一四元式的序号）。第38页，共47页，2023年，2月20日，星期二控制语句中的布尔表达式我们来研究包含在控制语句if

E

then

S1

else

S2或while

E

do

S中的布尔表达式E的翻译。在这类语句中，布尔表达式仅用于对程序流程进行控制。根据这两种语句的语义，我们可右图

(a)和(b)所示的结构进行翻译。在图(a)中可知，E的真、假出口分别为语句S1和S2的入口四元式的序号。图(b)中，E的真出口为S的入口，假出口为整个while语句的出口

TE的代码S1的代码S2的代码E的代码S的代码TFF(a)if语句(b)while语句第39页，共47页，2023年，2月20日，星期二布尔表达式真假值的确定一个布尔表达式E的真假值的确定，是在语法翻译过程中，根据(5.2)-(5.4)等价解释式逐步进行的。例如，对于布尔表达式 E=E(1)∨E(2)

若E(1)为真，则E必为真，故E(1)的真出口必是E的真出口(之一);

若E(1)为假，则E的真假值取决于E(2)的真假值，此时，需对E(2)进行计算，由此可见，E(1)的假出口应为E(2)对应的四元式的序号(E(2)的入口)，同时,E(2)的真、假出口也是E的真、假出口。 类似地，可确定E(1)∧

E(2)

、﹃E及更复杂的表达式的真、假出口。

第40页，共47页，2023年，2月20日，星期二条件语句的翻译结果在设计布尔表达式翻译算法（即编写语义动作）时，可定义和使用如下三类四元式：(jnz,A1,,p)当A1为真(非零)时，转向第p四元式；(jrop,A1,A2,p)当关系A1ropA2

成立时，转向第p四元式；(j,,,p)

无条件转向第p四元式例如，对于条件语句ifA∨B<C

then

S1

else

S2经翻译后，可得四元式序列：

(1) (jnz,A,-,5) (2) (j,-,-,3) (3) (j<,B,C,5) (4) (j,-,-,p+1) (5) S1相应的四元式序列

(p) (j,-,-,q) (p+1)S2相应的四元式序列

(q) …

其中，表达式A的真出口为5（也是整个表达式的真出口），假出口为3（即表达式B<C的第一四元式）；B<C的真、假出口也分别是整个表达式的真、假出口。第41页，共47页，2023年，2月20日，星期二拉链与回填在自底向上的语法制导翻译时（或者说，在S-属性翻译文法中),在产生一个(无)条件转移四元式时,它所要转向的那个四元式有时尚未产生，故无法立即产生一个完全的控制转移四元式。例如，在上例中，在产生第一个四元式时，由于语句S1的中间代码尚未产生，即A的真出口确切位置并不知道，故此时只能产生一个空缺转移目标的四元式 (jnz,A,-,0),并将此四元式的序号(即1)作为语义信息存起来，待开始翻译S1时，再将S1的第一四元式的序号(即5)回填这个不完全的四元式。 另外，在翻译过程中，常常会出现若干转移四元式转向同一目标，但此目标的具体位置又尚未确定的情况，此时我们可将这些四元式用拉链的办法将它们链接起来，用一指针指向链头，在确定了目标四元式的位置之后，再回填这个链。

第42页，共47页，2023年，2月20日，星期二布尔表达式的真假出口链对于一个布尔表达式E来说，它应有两条链：真出口链(称为T链，记作TC)和假出口链(称为F链，记作FC)。它们就是非终结符Expr的两个属性Expr.TC及Expr.FC。例如，对于上述if语句中的布尔式E=A∨B<C，在翻译过程中形成的T链和F链如右图所示。其中，每条链都是利用四元式中的Result域连接的，Result>0时,它给出本链的后继四元式的序号，Result=0时表示本四元式是链尾结点。

(1) (jnz,A,-,0)(2) (j,-,-,3)

E.TC→(3)(j<,B,C,1)E.FC→

(4)(j,-,-,0)

A∧B∨C的四元式序列及其TC链和FC链第43页，共47页，2023年，2月20日，星期二文法的“拆分”为便于实现布尔表达式的语法制导翻译，我们先改写文法，以便能在翻译过程中的适当时机获得所需的语义属性值。例如，可将文法(5.1)改写为：ExprExpr^Expr|Expr∨Expr|﹃Expr| iden|idenRopiden|(Expr) Expr^Expr∧ Expr∨Expr∨

(5.7)

将文法进行“拆分”的目的:1.在翻译完运算符∧（∨）左侧的表达式后，能够及时获取其语义属性TC及FC2.完成用下一四元式序号（即运算符右侧表