语法制导翻译 (2)幻灯片.ppt

《语法制导翻译 (2)幻灯片.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译 (2)幻灯片.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语法制导翻译第1页，共47页，编辑于2022年，星期二5.1 引言引言在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的目标代码目标代码。现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码中间语言代码，然后再将其翻译为目标代码。优点优点优点优点：使编译程序各组成部分功能更单一;使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件 本章要讨论的中间代码生成中间代码生成，是指把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成表示。目前常见的中间语言

2、有逆波兰表示逆波兰表示、三元式三元式、四元式四元式等等。中间代码生成与语言的语义密切相关，目前采用语法制导翻译来描述语义。方法方法:对文法中的每个产生式都附加一个语义动作或语义子程序,语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。第2页，共47页，编辑于2022年，星期二5.1 引言引言(续续)这种模式既把语法分析与语义处理分开，又令其平行地进行，让其在同一遍扫描中同时完成语法分析和语义处理两项工作。由此可见，抽象文法符号的具体语义信息，是在与语法分析同步的语义处理与语法分析同步的语义处理过程中获取和加工的过程中获取和加工的。文法符号X的语义信息我们称之

3、为语义属性语义属性或简称为属性属性（Attributes）。我们用形如X.ATTR的记号来表示文法符号X的相关语义属性语义属性。如果一个文法符号X在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。第3页，共47页，编辑于2022年，星期二文法符号及其语义属性文法符号X的语义信息我们称之为语义属性语义属性或简称为属性属性（Attributes）。我们用形如X.ATTR的记号来表示文法符号X的相关语义属性语义属性。如果一个文法符号X在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。例如,文法GEGE:产生式产生式 语义子程序语义子程序EE(1)+TE.Val

4、=E(1).val+T.val;ET E.Val=T.Val;Tdigit T.Val=digit;为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个语语语语义义义义信信信信息息息息栈栈栈栈 语法分语法分析栈析栈语义分语义分析栈析栈TT.Val+E#第4页，共47页，编辑于2022年，星期二本章内容简介首先介绍一种适用于定义语义的一种特殊文法属性文法，进一步介绍适用于语义翻译的文法属性翻译文法的相关知识。在第三小节中我们将介绍几种常见的中间语言;在第四小节中引入程序设计语言中常见语法结构的语法制导翻译技术。第5页，共47页，编辑于2022年，星期二5.2 属性文法与属性

5、翻译文法 语法制导翻译方法语法制导翻译方法的实质，就是根据文法中每个产生式所蕴含的语义，为其配备一个（或多个）处理语句或子程序，对所要完成的功能进行描述。产生式的语义产生式的语义是由组成该产生式的文法符号的语义文法符号的语义所决定的。将这些语义以“属性属性”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的求求值规则值规则，从而形成一种附带有语义属性语义属性的前后文无关文法，即属性文法属性文法。第6页，共47页，编辑于2022年，星期二5.2.1 语义属性与属性文法语义属性与属性文法 定义 5.1 一一文法符号的语义性质称为该文法符号的语义属语义属性性（Attrib

6、utesAttributes），简称为属性属性。用A(X)表示X的所有属性的集合。每个属性表示X的一个特定性质，并可任意指定其取值范围。我们用X.a表示A(X)中的属性a。属性属性可表征诸如数、符号串、类型、存储空间和其它需表征的实体。终结符终结符至少有一种属性属性，即词文。它还可能具有其它属性，例如无符号数123123，单词“123”就是它的词文，而其数值以及它的类型（整型）是它的其它两个属性。终结符的属终结符的属性是其性是其内在性质内在性质.非终结符非终结符的属性属性是从其它符号的属性属性经计算而得的，即由其它符号的属性属性定义的。第7页，共47页，编辑于2022年，星期二属性依赖关系属性

7、依赖关系各个文法符号的属属性性之间，可能存在某种依依赖赖关关系系，这种依依赖赖关关系系可用属性规则（语义规则语义规则）定义。定定义义 5.25.2 设p:Xp:X0 0XX1 1X X2 2XXn n是文法G的一个产生式，则与p相关联的属性规则集 R(p)R(p)=X Xi i.a.a=f(=f(X Xk1k1.a.ak1k1,X,Xkmkm.a.akmkm)|)|X Xi i.a.aA(XA(Xi i)定义了该产生式所涉及的文法符号之属性的求求值值规规则则，它表示：X Xi i的a a属性是由X Xk1k1的a ak1k1属性，X Xkmkm的a akmkm属性计算而得的。定义定义定义定义

8、5.35.3 对每个产生式p:Xp:X0 0XX1 1X X2 2XXn n，设属性定义性出现的集合为AF(p)=X Xi i.a.a|X Xi i.a.a=f(=f(X Xk1k1.a.ak1k1,X,Xkmkm.a.akmkm)R(p),0k)R(p),0kj jnn 若X Xi i是产生式左部的非终结符(即i=0),则称属性X Xi i.a.a是综合属性;若X Xi i出现在产生式的右部(即1in),则称X Xi i.a.a是继承属性第8页，共47页，编辑于2022年，星期二加注语法树加注语法树在语法树中,将每个结点均视为由若干个域组成的结构结构,则可将其中的一些域用来存放相应文法符号诸

9、属性之值，并可用属性属性来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为加注语法树加注语法树由定义定义5.35.3可知：在加注语法树加注语法树中，一个文法符号X X在相应结点的综合属性之值，由其子结点的属性和（或）X的其它属性，通过相关属性规则经计算而得，故综合属性的求值在语法树中是按自下而上自下而上的方式进行的；X X的继承属性之值则由X X的父结点和(或)其它兄弟结点来定义,故继承属性的求值将按自上而下自上而下的方式进行。第9页，共47页，编辑于2022年，星期二属性文法的定义属性文法的定义定义定义定义定义5.45.45.45.4 属性文法属性文法AG是一个四元组：AG=(G

10、,A,R,B),其中,G是已简化的CFG;A=XVA(X)是属性的有限集合;R=pPR(p)是属性定义规则的有限集;B=pPB(p)是条件的有限集合，B(p)用于描述使规则R(p)有效的条件；且同时满足：（1）对G中任意两个不同的文法符号X和Y而言，属性集合A(X)和A(Y)不相交,A(X)A(Y)=（2）在G的任意一个语法树中，对文法符号X的每一次出现，可用于计算X的每个属性之值的规则至多有一条。第10页，共47页，编辑于2022年，星期二属性文法(续)由定义5.4可知，属属性性文文法法实际上就是对前后文无关文法的一种拓广。另外，每个产生式中的任一文法符号的属属性性计计算算规规则则只只能能是

11、是唯唯一一的，且任一文法符号的综综合合属属性性集集与继承属性集继承属性集不相交不相交，即AS(X)AI(X)=,其中：AS(X)=X.a|p:XP,X.aAF(p)(综合属性)AI(X)=X.a|q:YX P,X.aAF(q)(继承属性)第11页，共47页，编辑于2022年，星期二例5.1 简单赋值语句文法的属性文法第12页，共47页，编辑于2022年，星期二第13页，共47页，编辑于2022年，星期二属性依赖关系属性依赖关系定义定义定义定义5.65.65.65.6 对于每个产生式p:X0X1X2XnP,直接属性依赖关系由下式给出：DDP(p)=(Xi.a,Xj.b)|Xj.b=f(,Xi.a

12、,)R(p)若序偶(Xi.a,Xj.b)DDP(p)，则称属性Xj.b依赖于属性Xi.a，记作Xi.aXj.b。显然，若有Xi.aXj.b，则对Xj.b的计值，应在求出Xi.a的值之后进行。但若Xi.a又直接或间接地依赖于Xj.b,则称属性Xi.a和Xj.b是循环依赖循环依赖循环依赖循环依赖的。含有属性循环依赖的属性文法AG，其中的一些属性之值将不能得到有效的计算。第14页，共47页，编辑于2022年，星期二依赖关系图定义定义定义定义5.75.75.75.7 设T是L(G)中一个句子相应的加注语法树，并设在构造T时使用过产生式p:X0X1X2Xn，对于T中由X0,X1,X2,Xn所标记的每个结

13、点，若有(Xi.a,Xj.b)DDP(p),则在树中引一条从到的有向边，由此而得到的树称之为该句子的属性化语法树。所有这样的有向边构成的集合DT(T)，称为树T上的依赖关系。根据DT(T)所构造的关系图称为依赖关系图依赖关系图（或简称为依赖图依赖图）。例如，对于例5.1所给文法下的一个句子x:=y+zx:=y+z，相应属性化语法树的依赖关系如P191图5-3所示。第15页，共47页，编辑于2022年，星期二翻译文法的定义定义定义定义定义5.85.85.85.8 在文法产生式右部适当的位置上插入语义动作语义动作而得的新文法称为翻译文法翻译文法或增广文法增广文法(Augmented Augment

14、ed GrammarGrammar)。在一翻译文法翻译文法中，若每个产生式右部中的全部语义动作语义动作均出现在所有文法符号的右边，则称这样的翻译文法翻译文法为波兰翻译文法波兰翻译文法。为为了了区区分分文文法法符符号号与与语语义义动动作作，我我们们用用一一对对花花括括号号及及将将插插入入的的语语义义动动作作括括起起来来（语语义义动动作作采采用用C C语语言言格格式式书书写写）。而而且且，我我们们还还把把语语义义动动作作视视为为翻翻译译文文法法中中的的一一个个“符符符符号号号号”，称称为为动动动动作作作作符符符符号号号号。插插入入语语义义动动作作后后，翻翻译译文文法产生式的一般形式为：法产生式的一

15、般形式为：A(A(statementstatement;);)*V V*第16页，共47页，编辑于2022年，星期二翻译文法（续）翻译文法的作用是，在进行语法分析时，无论是用产生式进行推导还是进行归约，只要遇到其中带有语义动作的花括号，就要求编译系统自动执行花括自动执行花括号内指定的语义动作号内指定的语义动作，在执行完该动作之后才继续进行下一步的语法分析。例：ExprTerm ExprExpr+TermWriteCode(“+”);Expr|TermFactor TermTerm*Factor WriteCode(“*”);Term|Factoroperand WriteCode(yytext

16、);|(Expr)第17页，共47页，编辑于2022年，星期二递归下降分析中的翻译文法若用递归下降法进行语法分析，则与非终结符号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页，编辑于2022年，星期二属性翻译文法的定义定定义义5.95.9 属属性性翻翻译译文文法法（Attribute Translation G

17、rammar，简记为ATG）是具有以下性质的翻译文法翻译文法：1每个文法符号和语义动作符X都有一个相关的有限属性集合A(X)，且每个属性都有一个允许值的集合（属性的值域，可以是无限集）。2非终结符和动作符的属性可分为继承属性继承属性与综合属性综合属性两类。3继承属性继承属性的定义规则为：开始符号的继承属性继承属性具有指定的初始值；对于给定的产生式p:YX1X2XnP,Xi的继继承承属属性性值由p中其它符号的属性值进行计算：Xi.a=f(Y.b,Xk1.ak1,Xkm.akm)i k1,km 4综综合合属属性性的定义规则为：对于给定的产生式p:YX1X2XnP，Y的综综合合属性属性值由p中某些符

18、号的属性计算：Y.u=f(Y.v,Xk1.ak1,Xkm.akm)1 kj n；对于动作符号，其综合属性综合属性值由该动作符的其它属性计算；终结符的综合属性综合属性具有指定的初始值。第19页，共47页，编辑于2022年，星期二对属性文法的一些限制定定义义5.105.10 一属性翻译文法称为是L-L-属属性性的，当且仅当对其中的每个产生式p:AX1X2Xn，下面的三个条件成立：1 右 部 符 号Xi(1in)的 继 承 属 性 之 值，仅 依 赖 于X1,X2,Xi-1的任意属性或A的继承属性；2左部符号A的综合属性之值仅依赖于A的继承属性或(和)右部符号Xi(1in)的任意属性；3对一动作符号

19、而言，其综合属性之值是以该动作符号的继承属性或产生式右部符号的任意属性为变元的函数。第20页，共47页，编辑于2022年，星期二方法符号属性的求值顺序A的继承属性(AI(A)；X1的继承属性(AI(X1)；X1的综合属性(AS(X1),进入X1的子树后，返回时求出）；Xn的继承属性(AI(Xn)；Xn的综合属性(AS(Xn),进入Xn的子树后,返回时求出）；A的综合属性(AS(A),返回到A的上层）。第21页，共47页，编辑于2022年，星期二表达式属性翻译文法例5.2 表达式属性翻译文法：Program|$1=$2=NewName();Expr FreeName($0);Program Ex

20、prTerm Expr Expr+$1=$2=NewName();Termprintf(“+,%s,%s,%sn”,$0,$,$0);FreeName($0);Expr|TermFactor Term Term*$1=$2=NewName();Factor printf(“*,%s,%s,%sn”,$0,$,$0);FreeName($0);Term|FactorNumberprintf(“:=,%s,-,%sn”,yytext,$);|第22页，共47页，编辑于2022年，星期二S-属性文法的定义定义定义定义定义5.115.115.115.11 满足下面三个条件的属性文法称为S-S-属性文法

21、属性文法：所有非终结符只具有综合属性综合属性；在一个产生式中，每一个符号的各个综合属性综合属性的定义互不依赖；在一个产生式中，若某个文法符号X具有继继承承属属性性，则此继继承承属属性性之值仅依赖于该产生式右部且位于X左边的符号之属性。显然，S-S-属属性性文文法法也满足L-L-属属性性文文法法的条件，这就是说，S-S-属属性性文文法法一定是L-L-属属性文法性文法，而且还要求每个非终结符只具有综合属性综合属性。第23页，共47页，编辑于2022年，星期二S-属性文法的例子例例5.35.3 简单算术表达式的S-S-属性文法属性文法：ProgramExpr printf(“%dn”,$1);Exp

22、r Expr+Expr$=$1+$3;|Expr*Expr$=$1*$3;|(Expr)$=$2;|Number$=ToIntValue(yytext);上面的语义子程序采用了YACCYACC工具中的表示方法,其中$,$1,$2$,$1,$2分别表示产生式左部符号,右部的第一个,第二个符号(余类推)的语义属性语义属性语义属性语义属性.第24页，共47页，编辑于2022年，星期二5.3 常见中间语言简介常见中间语言简介第25页，共47页，编辑于2022年，星期二5.3.1 逆波兰表示逆波兰表示 波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都

23、置于其运算对象之后，故称为后缀表示。特点特点:表达式中各个运算运算是按运算符出现的顺序进行的运算符出现的顺序进行的，故无须使用括号来指示运算顺序，因而又称为无括号式无括号式。下面我们对照地给出一些表达式的两种表示：中缀表示中缀表示后缀表示后缀表示 A+BAB+A+B*CABC*+(A+B)*(C+D)AB+CD+*x/yz-d*exyz/de*-(a=0b3)(exy)a0=b3 exy第26页，共47页，编辑于2022年，星期二逆波兰式的特点在两种表示中，在两种表示中，运算对象运算对象运算对象运算对象出现的出现的顺序相同顺序相同顺序相同顺序相同；在后缀表示中，在后缀表示中，运算符运算符运算符

24、运算符按按实际计算顺序从左到右排列实际计算顺序从左到右排列实际计算顺序从左到右排列实际计算顺序从左到右排列，且每一运算符总，且每一运算符总是跟在其是跟在其运算对象之后运算对象之后运算对象之后运算对象之后。由由于于后后缀缀表表示示中中的的各各个个运运算算是是按按顺顺序序执执行行的的，因因此此，它它的的计计值值需需从从左到右依次扫视表达式中的各个符号，左到右依次扫视表达式中的各个符号，每遇一运算对象每遇一运算对象，就把它，就把它压入栈顶压入栈顶暂存起来；暂存起来；每每遇遇一一个个二二元元（或或一一元元）运运算算符符时时，就就取取出出栈栈顶顶的的两两个个（或或一一个个）运运算算对对象象进进行行相相应

25、应的的运运算算，并并用用运运算算结结果果去去替替换换栈栈顶顶的的这这两两（或或一）个运算对象；一）个运算对象；继续扫视余留的符号，直到扫视完整个表达式为止。继续扫视余留的符号，直到扫视完整个表达式为止。当上述过程结束时，当上述过程结束时，整个表达式的值将留于栈顶整个表达式的值将留于栈顶整个表达式的值将留于栈顶整个表达式的值将留于栈顶。第27页，共47页，编辑于2022年，星期二5.3.2 四元式和三元式四元式和三元式四四元元式式是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用。四四 元元 式式是 一 种“三三 地地 址址 语语

26、 句句”的 等 价 表 示。它 的 一 般 形 式 为：(op,arg1,arg2,resultresult)其中，op为一个二元(也可是一元或零元)运算符;arg1,arg2分别为它的两个运算对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入resultresult中。四元式还可写为类似于PASCAL语言的赋值语句的形式：result:=arg1 op arg2 第28页，共47页，编辑于2022年，星期二四元式的格式需要指出的是，每个四元式四元式只能有一个运算符，所以，一个复杂的表达式只能由多个四元式四元式构成的序列表示。例如，表达式A+B*C可写为序列 T1:=B*CT2

27、:=A+T1当op为一元、零元运算（如无条件转移）时，arg2甚至arg1应缺省，即result:=op arg1或 op result；对应的一般形式为：(op,arg1,-,result)或(op,-,-,result)。第29页，共47页，编辑于2022年，星期二三元式为了节省临时变量的开销，有时也可采用一种三元式结构来作为中间代码，其一般形式为(i)(op,arg1,arg2)其中，(i)为三三 元元 式式的编号，也代表了该式的运算结果；op,arg1,arg2的含义与四四元元式式类似，区别在于arg可以是某三三元元式式的序号，表示用该三三元元式式的结果作为运算对象。例如，对于赋值语句

28、a:=-b*(c+d)，若用三元式三元式表示，则可写成(U_minus,b,-)(+,c,d )(*,)(:=,a )式中的运算符U_minus表示一元减运算。第30页，共47页，编辑于2022年，星期二翻译程序中使用的辅助函数我们以算术表达式算术表达式算术表达式算术表达式到三元式三元式的翻译为例，说明如何为各产生式设计语义动作。为此，先介绍若干翻译过程中要使用的辅助函数：int LookUp(char*Name)以Name查符号表，若查到则返回相应登记项的序号(1),否则返回0。int Enter(char*Name)以Name为名字在符号表中登录新的一项,返回值为该项的序号。int Ent

29、ry(char*Name)以Name为名字查、填符号表:int Entry(char*Name)int i=LookUp(Name);if(i)return i;else return Enter(Name);第31页，共47页，编辑于2022年，星期二翻译程序中使用的辅助函数(续)注意，在实际的编译系统中，还应区分当前是否在处理说明部分：若是说明部分，则查表时i应为0（否则Name被重复定义）；若非，则i不能为0（否则Name尚未被定义）。int Trip(int op,int arg1,int arg2)根据给定的参数产生一个三元式三元式(op,arg1,arg2)并将它送入三三元元式式表

30、中，其返回值为表中序号。为区分参数arg表示的是三三元元式式还是变量，约定当arg0表示变量在符号表中登记项序号；arg=0表示参数为空。第32页，共47页，编辑于2022年，星期二三元式和四元式四元式之异同在产生式8中，终结符iden的属性是它的词文yytext，用$1表示。每个非终结符非终结符都有一个属性，代表以该符号为根的语法树的一个子树的运算结果，该属性的取值可以是整型数，或为一三元式三元式的序号，或为符号表项的序号。比较三元式三元式和四元式四元式这两种表示方法可以看出，无论在一个三元三元式式序列还是四元式四元式序列中，各个三元式三元式或四元式四元式都是按相应表达式的实际运算顺序出现的

31、。其次，对同一表达式而言，所需的三元三元式式或四元式四元式的个数一般是相同的。三元式三元式比四元式四元式更能节省存储空间,但不利于优化.可通过引入一些表格提高使用三元式三元式的效率(略,见P200-201)第33页，共47页，编辑于2022年，星期二5.4 简单算术表达式和赋值语句的翻译 约定约定1.E中仅含简单变量;2.全部变量同类型;3.翻译时不做语义检查.辅助定义辅助定义1.int NewTempNewTemp(void)产生临时变量的函数，每次调用都定义一个新的临时变量。返回值为该变量的编号。2.2.X.PLACEX.PLACE文法符号X的属性，其值为整型(00表示在符号表中序号,00

32、表示临时变量编号)3.int GENGEN(int Op,int Arg1Arg1,int Arg2Arg2,int ResultResult)根据所给实参产生一个四元式：(Op,Arg1Arg1,Arg2Arg2,ResultResult)，且送入四元式表中，返回值为该四元式的序号。Arg1Arg1或Arg2Arg2为零时表示该参数缺省 第34页，共47页，编辑于2022年，星期二赋值语句的S-属性翻译文法 1.StatementAssignSt 2.AssignStVariable:=Expr GENGEN(:=,$3.PLACE,0,$1.PLACE);(:=,$3.PLACE,0,$1

33、.PLACE);3.ExprExpr +Expr$.PLACE=$.PLACE=NewTempNewTemp();();GENGEN(+,$1.PLACE,$3.PLACE,$.PLACE);(+,$1.PLACE,$3.PLACE,$.PLACE);4.|Expr *Expr$.PLACE=$.PLACE=NewTempNewTemp();();GENGEN(*,$1.PLACE,$3.PLACE,$.PLACE);(*,$1.PLACE,$3.PLACE,$.PLACE);5.|(Expr )$.PLACE=$2.PLACE;$.PLACE=$2.PLACE;6.|identifier$.

34、PLACE=$.PLACE=EntryEntry($1);($1);7.Varable identifier$.PLACE=$.PLACE=EntryEntry($1);($1);第35页，共47页，编辑于2022年，星期二5.5 布尔表达式的翻译布尔表达式的翻译布尔表达式布尔表达式是布尔运算量和逻辑运算符按一定语法规则组成的式子。逻逻辑辑运运算算符符通常有、三种（在某些语言中，还有（等价）及（蕴含）等等）；逻逻辑辑运运算算对对象象可以是逻辑值（True 或 False）、布尔变量、关系表达式以及由括号括起来的布尔表达式。不论是布尔变量还是布尔表达式，都只能取逻辑值True或False。在计算

35、机内通常用1（或非零整数）表示真值（True），用0表示假值(False)。关关系系表表达达式式是形如E E1 1 RopRop E E2 2的式子，其中E E1 1和E E2 2为简单算术表达式，RopRop为关系运算符（,=,=,=,=,=,）。若E E1 1和E E2 2之值使该关系式成立，则此关系表达式之值为True，否则为False。第36页，共47页，编辑于2022年，星期二布尔表达式的等价解释为了方便起见，下面我们仅讨论由文法 EEE|EE|E|(E)|i|i Rop iEEE|EE|E|(E)|i|i Rop i(5.1)对于布布尔尔表表达达式式的计值和翻译，可采用类似算算术术

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

37、0:1(5.45.4)第37页，共47页，编辑于2022年，星期二布尔表达式的出口出口对于布尔表达式布尔表达式AA（BB（CDCD）)，其等价的表述是A A？1 1：（：（B B？（？（C C？0 0：1 1）？）？1 1：D D）：）：0 0 ）显然，采用此种结构可产生更为有效的中间代码。这里需假定原布尔表达式布尔表达式的计算过程中不含有任何的副作用副作用副作用副作用。在上式的计算中，根据A A、B B、C C、D D的取值不同，计算的结果以及运算的中止点亦不同。例如，当A=1A=1（真）时，结果为1 1且中止于左边第一个1111处。这样中止的点我们称为该布尔表达式布尔表达式的出口出口出口出

38、口，同时，把使布尔表达式布尔表达式取值为真真真真的出口出口出口出口称为真出真出真出真出口口口口，反之称为假出口假出口假出口假出口。对一个布尔表达式布尔表达式而言，它至少有一个真出口真出口真出口真出口和一个假出口假出口假出口假出口（当然可以有多个）。在用于控制流程的布尔表达式布尔表达式E E的计算中，这些出口出口出口出口分别指出当E E值为真真真真和假假假假时，控制所应控制所应控制所应控制所应转向的目标转向的目标转向的目标转向的目标（即某一四元式的序号）。第38页，共47页，编辑于2022年，星期二控制语句中的布尔表达式我们来研究包含在控制语句if E then S1 else S2或while

39、 E do S中的布尔表达式布尔表达式E的翻译。在这类语句中，布尔表达式布尔表达式仅用于对程序流程进行控制。根据这两种语句的语义，我们可右图(a)和(b)所示的结构进行翻译。在图(a)中可知，E的真、假出口真、假出口真、假出口真、假出口分别为语句S1和S2的入口入口入口入口四元式的序号。图(b)中，E的真出口真出口真出口真出口为S的入口入口入口入口，假出口假出口假出口假出口为整个while语句的出口 TE的代码S1的代码S2的代码E的代码S的代码TFF(a)(a)if if语句语句语句语句(b)(b)whilewhile语句语句语句语句第39页，共47页，编辑于2022年，星期二布尔表达式真假

40、值的确定一个布尔表达式E E的真假值的确定，是在语法翻译过程中，根据(5.2)-(5.4)等价解释式逐步进行的。例如，对于布尔表达式E=EE=E(1)(1)E E(2)(2)若E E(1)(1)为真，则E E必为真，故E E(1)(1)的真出口真出口必是E E的真出口真出口真出口真出口(之一);若E E(1)(1)为假，则E E的真假值取决于E E(2)(2)的真假值，此时，需对E E(2)(2)进行计算，由此可见，E E(1)(1)的假出口假出口假出口假出口应为E E(2)(2)对应的四元式的序号(E E(2)(2)的入口)，同时,E E(2)(2)的真、假出口也是E E的真、假出口。类似地

41、，可确定E E(1)(1)E E(2)(2)、E E E E及更复杂的表达式的真、假出口真、假出口真、假出口真、假出口。第40页，共47页，编辑于2022年，星期二条件语句的翻译结果在设计布尔表达式翻译算法（即编写语义动作）时，可定义和使用如下三类四元式：(jnz(jnz,A1A1,p),p)当A1A1为真(非零)时，转向第p p四元式；(jrop,A1,A2,p)(jrop,A1,A2,p)当关系A1 A1 rop rop A2A2 成立时，转向第p p四元式；(j,p)(j,p)无条件转向第p p四元式例如，对于条件语句if ABC then S1 else S2经翻译后，可得四元式序列：

42、(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（即表达式BC的第一四元式）；BC的真、假出口也分别是整个表达式的真、假出口。第41页，共47页，编辑于2022年，星期二拉链拉链与回填在自底向上的语语语语法法法法制制制制导导导导翻翻翻翻译译译译时（或者说，在S-S-属属性性翻翻译译文文法法中),在产生一个(无)条件转移四元式时,它所要转向的那个四元式有时尚未产

43、生，故无法立即产生一个完全的控制转移四元式。例如，在上例中，在产生第一个四元式时，由于语句S S1 1的中间代码尚未产生，即A A的真出口确切位置并不知道，故此时只能产生一个空空空空缺缺缺缺转转转转移移移移目目目目标标标标的四元式(jnz,A A,-,0 0),并将此四元式的序号(即1 1)作为语义信息存起来，待开始翻译S S1 1时，再将S S1 1的第一四元式的序号(即5 5)回回填填这个不完全的四元式。另外，在翻译过程中，常常会出现若干转移四元式转向同一目标若干转移四元式转向同一目标若干转移四元式转向同一目标若干转移四元式转向同一目标，但此目标的具体位置又尚未确定的情况，此时我们可将这些

44、四元式用拉链拉链拉链拉链的办法将它们链接起来，用一指针指向链头，在确定了目标四元式的位置之后，再回填回填这个链链链链。第42页，共47页，编辑于2022年，星期二布尔表达式的真假出口链对于一个布尔表达式E E来说，它应有两条链：真真真真出出出出口口口口链链链链(称为T T链链，记作TCTC)和假假假假出出出出口口口口链链链链(称为F F链链，记作FCFC)。它们就是非终结符ExprExpr的两个属性Expr.TCExpr.TC及Expr.FCExpr.FC。例如，对于上述if语句中的布尔式E E=A A BCB0时,它给出本链的后继四元式的序号，ResultResult=0时表示本四元式是链尾

45、结点。(1)(jnz,A,-,0)(2)(j,-,-,3)E.TCE.TC(3)(j,B,C,1)E.FCE.FC(4)(j,-,-,0)A AB BC C的四元式序列及其TCTC链和FCFC链第43页，共47页，编辑于2022年，星期二文法的“拆分”为便于实现布尔表达式的语法制导翻译，我们先改写文法，以便能在翻译过程中的适当时机获得所需的语义属性值。例如，可将文法(5.1)改写为：ExprExprExpr Expr|ExprExpr Expr|Expr Expr|Expr|Expr|Expr|iden|iden Rop iden|(Expr)iden|iden Rop iden|(Expr)

46、Expr Expr Expr Expr ExprExpr Expr Expr (5.7)将文法进行“拆分拆分”的目的目的目的目的:1.在翻译完运算符（）左侧的表达式后，能够及时获取其语义属性TCTC及FCFC2.完成用下一四元式序号（即运算符右侧表达式的第一四元式之序号）回填前一表达式的相应真（假）链TCTC（FCFC），3.将其另一链FCFC（TCTC）作为产生式左部符号的综合属性FCFC（TCTC）传播之。第44页，共47页，编辑于2022年，星期二语义变量及辅助语义函数1.NXQ全局变量，用于指示所要产生的下一四元式的序号；2.GEN（）其意义同前,每次调用,NXQ+；3.int Mer

47、ge(int p1,int p2)将链首“指针”分别为p1和p2的两条链合并为一条，并返回新链的链首“指针”（此处的“指针”实际上是四元式的序号，应为整型值）我们假定四元式是以一结构形式表示（存储）的：struct _Quadruple int Op,arg1,arg2,Result;QuadrupleList;4.void BackPatch(int p,int t)用四元式序号t回填以p为首的链，将链中每个四元式的Result域改写为t的值。函数MergeMerge()及BackPatchBackPatch()的程序见书中P207P207第45页，共47页，编辑于2022年，星期二翻译布尔

48、表达式的属性文法1.Expriden$.TC=NXQ;$.FC=NXQ+1;GEN(jnz,Entry($1),0,0);GEN(j,0,0,0);2.|iden rop iden$.TC=NXQ;$.FC=NXQ+1;GEN(jrop,Entry($1),Entry($3),0);GEN(j,0,0,0);3.|(Expr )$.TC=$2.TC;$.FC=$2.FC;4.|Expr$.TC=$2.FC;$.FC=$2.TC;5.|Expr Expr$.TC=$2.TC;$.FC=Merge($1.FC,$2.FC);6.|Expr Expr$.FC=$2.FC;$.TC=Merge($1.

49、TC,$2.TC);7.Expr Expr BackPatch($1.TC,NXQ);$.FC=$1.FC;8.Expr Expr BackPatch($1.FC,NXQ);$.TC=$1.TC;第46页，共47页，编辑于2022年，星期二布尔表达式的属性Expr具有两个语义属性：TC和FC。这两个链的回填，还需根据表达式E所处的程序环境做进一步的处理。（1）若E用于控制条件语句if-then-else,则遇到then时,应以当前NXQ值回填E的T链;对F链的回填，则在扫视到else时进行.对于while语句的情形,可类似地进行处理。（2）若布尔式E仅用于计算值,可引入临时变量T用于标识E的计算结果.将文法(5.7)拓广,增加产生式SEint N,T=NewTemp();BackPatch($1.TC,NXQ);BackPatch($1.FC,NXQ+2;)GEN(=,1,0,T);GEN(j,0,0,N);GEN(=,0,0,T);$.PLACE=T;$.Type=B;第47页，共47页，编辑于2022年，星期二