语法制导翻译和中间代码

语法制导翻译和中间代码第1页，课件共72页，创作于2023年2月本章内容8.1属性文法8.2语法制导翻译概论8.3中间代码的形式8.4简单赋值语句的翻译8.5布尔表达式的翻译8.6控制结构的翻译8.7说明语句的翻译8.8数组和结构的翻译符号表第2页，课件共72页，创作于2023年2月编译程序的任务是将汇编语言或高级语言书写成的源程序转换成等价的目标代码程序。其中要求目标代码程序和源程序的语义(Semantics）必须相同。

什么是语义？程序的语义就是它的“意思”。语义分析的任务包括两方面:一个是静态语义检查;一个是动态语义的解释执行（通俗地说就是计算并生成中间代码。8.1属性文法第3页，课件共72页，创作于2023年2月一、静态语义分析或静态语义审查语义分析的工作:包括：（1）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。

（2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则报错。（3）一致性检查。

（4）上下文相关性检查。比如，变量名字必须先声明后引用；

(5)名字的作用域分析例例第4页，课件共72页，创作于2023年2月1、各种条件表达式的类型是不是boolean型？2、运算符的分量的类型是否相容？3、赋值语句的左右部的类型是否相容？4、形参和实参的类型是否相容？5、下标表达式的类型是否为所允许的类型？6、函数说明中的函数类型和返回值的类型是否一致？第5页，课件共72页，创作于2023年2月1、每个使用的标识符是否都有声明？在同层内有无标识符被声明多次？

【例如】Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。2、标号是否有声明？有无重复声明和重复定位错误？有无非法转入错误？

3、子界类型中的下界和上界类型是否相容？下界是否小于等于上界？第6页，课件共72页，创作于2023年2月二、动态语义处理

如果静态语义正确，语义处理则执行真正的翻译（动态语义）即：生成程序的一种中间表示形式或生成实际的目标代码。中间代码(中间语言)是介于源语言和机器语言的一种表示形式。通常语义分析生成中间代码的原因：便于移植：中间代码相对独立于目标机，在编译程序移植时编译前端保持不变。利于优化：将优化分为与目标机无关的中间代码优化，以及与目标机相关的目标代码的优化，使优化更加细致有效。第7页，课件共72页，创作于2023年2月

语义分析的整个过程和词法及语法分析相类似。例如,在语法分析中，使用BackusNaus范式(BNF)中的上下文无关文法描述语法结构，并用各种自顶向下和自底向上的分析算法实现语法结构。由于没有标准的方法(如BNF)来说明语言的静态语义，因此语义分析就没有这么简单。常采用属性文法(attributegrammar)来描述语义。语义的形式化描述第8页，课件共72页，创作于2023年2月8.1属性文法一、属性（Attribute

）属性翻译文法是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。

第9页，课件共72页，创作于2023年2月二、属性文法（AttributeGrammar）的定义一个属性文法是一个三元组A＝(G,V,F)，其中：G为一上下文无关文法。V为属性的有穷集。F是关于属性的断言或一组属性的计算规则(称为语义规则)。第10页，课件共72页，创作于2023年2月属性文法的表示分两部分：首先在上下文无关文法中，对于每个文法符号引进相关的属性符号；其次对于每个产生式写出计算属性值的计算规则（即语义规则）,来描述各属性间的关系。形式为：

文法规则语义规则

规则1相关的属性等式

..

..

规则n相关的属性等式第11页，课件共72页，创作于2023年2月【例】用属性文法表示简单的无符号整数文法：

number→numberdigit|digit

digit→0|1|2|3|4|5|6|7|8|9【分析】一个数最重要的属性是它的值，将其命名为val。每个数字都有一个值，可以用它表示的实际数直接计算。1、文法规则：digit→0

语义规则：digit.val=0

2、文法规则：number→digit

语义规则：number.val=digit.val。3、文法规则number→numberdigit,必须表示出这个文法规则左边符号的值和右边符号的值之间的关系。通过使用下标进行区分，将文法写成如下形式：

number1→number2digit语义规则：number1.val:=number2.val*10+digit.val第12页，课件共72页，创作于2023年2月三、属性的分类（1）综合属性：用于“自下而上”传递信息分析树中，如果一个结点的属性值是通过子结点的属性值计算得到则称综合属性。（2）继承属性：用于“自上而下”传递信息分析树中，如果一个结点的属性值由该结点的父结点和/或兄弟结点定义的则称继承属性。第13页，课件共72页，创作于2023年2月四、语义规则在一个属性文法中，对应于每个产生式A→都有一套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,…,ck)

这里，f是一个函数，而且或者1）b是A的一个综合属性并且c1,c2,…,ck是产生式右边文法符号的属性，或者2）b是产生式右边某个文法符号的一个继承属性并且c1,c2,…,ck

是A或产生式右边任何文法符号的属性。 属性b依赖于属性c1,c2,…,ck。第14页，课件共72页，创作于2023年2月说明：终结符只有综合属性，由词法分析器提供非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供第15页，课件共72页，创作于2023年2月【例8.1】算术表达式求值的语义描述:

产生式语义规则L→Eprint(E.val)E→E1+T

E.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val×F.val

T→FT.val:=F.val

F→(E)F.val:=E.val

F→digit

F.val=digit.lexval语义过程L的属性为空E、T、F的val为综合属性digit仅有综合属性由词法分析程序提供第16页，课件共72页，创作于2023年2月【例8.2】

带有继承属性L.in的语义规则

产生式语义规则

DTLLin:=TtypeTintTtype:=intTrealTtype:=realLL1,idL1in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)第17页，课件共72页，创作于2023年2月8.2语法制导翻译概论语法制导翻译法在语法分析的基础上进行边分析边翻译。注：1）语法制导翻译时会根据文法产生式右部符号串的含义，进行翻译，翻译的结果是生成相应中间代码。

2）语法制导翻译的依据是语义子程序。

3）具体做法：为每个产生式配置一个语义子程序，当语法分析进行归约或推导时，调用语义子程序，完成一部分翻译任务。

4）语法分析完成，翻译工作也结束。第18页，课件共72页，创作于2023年2月语法制导翻译过程通常是这样的：1)对单词符号串进行语法分析，构造语法分析树;2)从语法分析树得到描述节点属性间依赖关系的依赖图;3)由此依赖图得到语义规则的计算次序;进行语义规则计算，得到翻译结果可表示为：输入串语法树依赖图语义规则计算次序

第19页，课件共72页，创作于2023年2月

在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。在为一棵语法树构造依赖图以前，为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成如下形式：

b:=f(c1,c2,…ck)依赖图中为每一个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。依赖图第20页，课件共72页，创作于2023年2月

for分析树中每一个结点ndo

for

结点的文法符号的每一个属性ado

为a在依赖图中建立一个结点；

for

分析树中每一个结点ndo

for结点n所用产生式对应的每一个语义规则

b:=f(c1,c2,…ck)do

fori:=1tokdo

从ci结点到b结点构造一条有向边

对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的：第21页，课件共72页，创作于2023年2月【例如】属性A.a:=f(X.x,Y.y)

对应于产生式AXY的语义规则,这条语义规则确定了依赖于属性X.x和Y.y的综合属性A.a。如果在语法树中应用这个产生式，那么在依赖图中会有三个结点A.a,X.x,和Y.y。由于A.a依赖X.x，所以有一条有向边从X.x到A.a.由于A.a也依赖于Y.y，所以还有一条有向边从Y.y连到A.a.

如果与产生式AXY对应的语义规则还有：

X.i:=g(A.a,Y.y)

那么，图中还应有两条有向边，一条从A.a连到X.i，另一条从Y.y连到X.i,因为X.i依赖于A.a和Y.y.A.aX.xY.yX.i第22页，课件共72页，创作于2023年2月如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。第23页，课件共72页，创作于2023年2月8.2.2S-属性文法的自下而上计算1、S-属性文法仅仅使用综合属性的属性文法称S－属性文法综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。第24页，课件共72页，创作于2023年2月2、S-属性文法的翻译器

S-属性文法的翻译器通常可借助LR分析器来实现在分析栈中使用一个附加的域来存放综合属性值假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式A→XYZ的第25页，课件共72页，创作于2023年2月 产生式 代码段

L→En print(val[top]) E→E1+T val[ntop]:=val[top-2]+val[top] E→T T→T1*F val[ntop]:=val[top-2]*val[top] T→F F→(E) val[ntop]:=val[top-1] F→digit

产生式语义规则

L→Enprint(E.val)E→E1+TE.val:=E1.val+T.valE→TE.val:=T.valT→T1*FT.val:=T1.val*F.valT→F T.val:=F.valF→(E)F.val:=E.valF→digitF.val:=digit.lexval第26页，课件共72页，创作于2023年2月输入 state sym val 用到的产生式

3*5+4n0 # - *5+4n05 #3 -3 *5+4n03 #F -3 F→digit*5+4n02 #T -3 T→F5+4n027 #T* -3- +4n0275 #T*5 -3-5 产生式 代码段

L→En print(val[top]) E→E1+T val[ntop]:=val[top-2]+val[top] E→T T→T1*F val[ntop]:=val[top-2]*val[top] T→F F→(E) val[ntop]:=val[top-1] F→digit 第27页，课件共72页，创作于2023年2月输入 state sym val 用到的产生式

+4n0275 #T*5 -3-5 +4n02710 #T*F -3-5 F→digit+4n02 #T -15 T→T*F+4n01 #E -15 E→T4n016 #E+ -15- n0165 #E+4 -15-4 产生式 代码段

L→En print(val[top]) E→E1+T val[ntop]:=val[top-2]+val[top] E→T T→T1*F val[ntop]:=val[top-2]*val[top] T→F F→(E) val[ntop]:=val[top-1] F→digit 第28页，课件共72页，创作于2023年2月输入 state symval 用到的产生式

n0165 #E+4 -15-4 n0163#E+F -15-4 F→digitn0169#E+T -15-4 T→Fn01 #E-19 E→E+T #En -19- #L -19 L→En 产生式 代码段

L→En print(val[top]) E→E1+T val[ntop]:=val[top-2]+val[top] E→T T→T1*F val[ntop]:=val[top-2]*val[top] T→F F→(E) val[ntop]:=val[top-1] F→digit 第29页，课件共72页，创作于2023年2月8.2.3L-属性文法和自顶向下翻译

通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值LL(1)：自上而下分析方法，深度优先建立语法树第30页，课件共72页，创作于2023年2月一个属性文法称为L-属性文法，如果对于每个产生式A→X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且这个继承属性仅依赖于：(1)产生式Xj的左边符号X1，X2，…，Xj-1的属性；(2)A的继承属性。S-属性文法一定是L-属性文法第31页，课件共72页，创作于2023年2月【思考】非L-属性的语法制导定义【分析】该语法制导定义不是L-属性定义，文法符号Q的继承属性依赖于它右边文法符号R的属性。产生式语义规则ALMAQRL.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)第32页，课件共72页，创作于2023年2月8.3中间代码的形式中间代码是源程序的一种内部表示复杂性介于源语言和目标机语言之间中间代码的作用使编译程序的逻辑结构更加简单明确利于进行与目标机无关的优化利于在不同目标机上实现同一种语言中间代码的形式逆波兰式、四元式、三元式、树第33页，课件共72页，创作于2023年2月1、后缀表示式Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。一个表达式E的后缀形式可以如下定义：1）如果E是一个变量或常量，则E的后缀式是E自身。2）如果E是E1opE2形式的表达式，其中op是任何二元运算符，则E的后缀式为E1E2op，其中E1和E2分别为E1

和E2的后缀式。3）如果E是(E1)形式的表达式，则E1

的后缀式就是E的后缀式。第34页，课件共72页，创作于2023年2月1、后缀表示式逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。

例如：（a+b）*c表示成ab+c*后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。第35页，课件共72页，创作于2023年2月1、后缀表示式把表达式翻译成后缀式的语义规则描述产生式E→E(1)opE(2)E→(E(1))E→id 语义动作E.code:=E(1).code||E(2).code||opE.code:=E(1).codeE.code:=idE.code表示E后缀形式op表示任意二元运算符“||”表示后缀形式的连接。第36页，课件共72页，创作于2023年2月数组POST存放后缀式：k为下标，初值为1上述语义动作可实现为： 产生式 程序段 E→E(1)opE(2) {POST[k]:=op;k:=k+1} E→(E(1)) {} E→i {POST[k]:=i;k:=k+1}例：输入串a+b+c的分析和翻译 POST：12345E→E(1)opE(2) E.code:=E(1).code||E(2).code||opE→(E(1)) E.code:=E(1).codeE→id E.code:=idab+c+…第37页，课件共72页，创作于2023年2月2、图表示法DAG（无循环有向图）抽象语法树（1）无循环有向图(DirectedAcyclicGraph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点第38页，课件共72页，创作于2023年2月

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

assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc后缀式是抽象语法树的线性表示形式：abc-*bc-*+:=

第39页，课件共72页，创作于2023年2月抽象语法树对应的代码：

T1:=-c T2:=b*T1

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

a:=T5assigna+*buminusc抽象语法树*buminusc第40页，课件共72页，创作于2023年2月DAG对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树对应的代码：

T1:=-c T2:=b*T1

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

a:=T5第41页，课件共72页，创作于2023年2月三地址代码三地址代码x:=yopz三地址代码可以看成是抽象语法树或DAG的一种线性表示第42页，课件共72页，创作于2023年2月三地址语句的种类x:=yopzx:=opyx:=ygotoLifxrelopygotoL或ifagotoLparamx和callp,n，以及返回语句returnyx:=y[i]及x[i]:=y的索引赋值x:=&y,x:=*y和*x:=y的地址和指针赋值第43页，课件共72页，创作于2023年2月3、四元式形式：一个带有四个域的记录结构：（Op，ARG1，ARG2，Result）注：1）ARG1，ARG2，Result可能是用户自己定义的变量，也可能是编译时引进的变量。这里Op是双目运算符，若只有一个运算量，则是单目运算符。

2）四元式中变量采用符号表的入口地址，而不用变量的地址，因为语义分析不仅需要变量的地址，还需要从符号表查到变量的属性、类型和地址等。第44页，课件共72页，创作于2023年2月3、四元式形式：例如：a：=b*c+b*d的四元式表示如下：（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（+，t1，t2，t3）（4）（:=，t3，-，a）第45页，课件共72页，创作于2023年2月4、三元式形式（Op，ARG1，ARG2）注：1）这里三元式本身作为存放结果的单元。

2）为了在其它三元式中利用当前三元式的结果，需要对三元式进行编号。三元式的编号就作为相应三元式的结果值。例如：a：=b*c+b*d的四元式表示如下：（1）（*，b，c）（2）（*，b，d）（3）（+，（1），（2））（4）（:=，（3），a）第46页，课件共72页，创作于2023年2月8.5布尔表达式的翻译布尔表达式的两个基本作用:用于逻辑演算,计算逻辑值;用于控制语句的条件式。产生布尔表达式的文法:E→EorE|EandE|notE|(E)|iropi|i第47页，课件共72页，创作于2023年2月计算布尔表达式通常采用两种方法:1.如同计算算术表达式一样,一步步算 1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采用某种优化措施把AorB解释成 ifAthentrueelseB把AandB解释成 ifAthenBelsefalse把notA解释成 ifAthenfalseelsetrue第48页，课件共72页，创作于2023年2月两种不同的翻译方法:第一种翻译法：AorBandC=D翻译成 (1)(=,C,D,T1) (2)(and,B,T1,T2) (3)(or,A,T2,T3)第二种翻译法适合于作为条件表达式的布尔表达式使用。第49页，课件共72页，创作于2023年2月8.5.1数值表示法aorbandnotc翻译成

T1:=notc T2:=bandT1 T3:=aorT1a<b的关系表达式可等价地写成

ifa<bthen1else0，翻译成

100: ifa<bgoto103 101: T:=0 102: goto104 103: T:=1 104:第50页，课件共72页，创作于2023年2月关于布尔表达式的数值表示法的翻译模式过程emit将三地址代码送到输出文件中nextstat给出输出序列中下一条三地址语句的地址索引每产生一条三地址语句后，过程emit便把nextstat加1第51页，课件共72页，创作于2023年2月关于布尔表达式的数值表示法的翻译模式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}第52页，课件共72页，创作于2023年2月关于布尔表达式的数值表示法的翻译模式Eid1relopid2{E.place:=newtemp;

emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3);

emit(E.place‘:=’‘0’);

emit(‘goto’nextstat+2);

emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}a<b翻译成100: ifa<bgoto103101: T:=0102: goto104103: T:=1104:第53页，课件共72页，创作于2023年2月布尔表达式a<borc<dande<f的翻译结果100: ifa<bgoto103101: T1:=0 102: goto104103: T1:=1104: ifc<dgoto107105: T2:=0 106: goto108107: T2:=1108:ife<fgoto111109:T3:=0110:goto112111:T3:=1112:T4:=T2andT3113:T5:=T1orT4Eid1relopid2

{E.place:=newtemp; emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2); emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}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)}第54页，课件共72页，创作于2023年2月8.5.2作为条件控制的布尔式翻译条件语句ifEthenS1elseS2赋予E两种出口:一真一假E.codeS1.codeS2.codeToE.trueToE.falsegotoS.nextS.next……E.true:E.false:第55页，课件共72页，创作于2023年2月例：把语句:ifa>corb<dthenS1elseS2翻译成如下的一串三地址代码

ifa>cgotoL2“真”出口

gotoL1L1: ifb<dgotoL2“真”出口

gotoL3“假”出口L2: (关于S1的三地址代码序列) gotoLnextL3: (关于S2的三地址代码序列)Lnext:第56页，课件共72页，创作于2023年2月产生布尔表达式三地址代码的语义规则每次调用函数newlabel后都返回一个新的符号标号对于一个布尔表达式E，引用两个标号E.true是E为‘真’时控制流转向的标号E.false是E为‘假’时控制流转向的标号第57页，课件共72页，创作于2023年2月产生布尔表达式三地址代码的语义规则 产生式 语义规则

E→E1orE2

E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code|| gen(E1.false‘:’)||E2.code

E1.codeToE.trueToE1.falseE2.codeToE.trueToE.false第58页，课件共72页，创作于2023年2月产生布尔表达式三地址代码的语义规则

产生式 语义规则

E→E1andE2

E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code|| gen(E1.true‘:’)||E2.codeE1.codeToE.

falseToE1.trueE2.codeToE.trueToE.false第59页，课件共72页，创作于2023年2月产生布尔表达式三地址代码的语义规则

产生式 语义规则

E→notE1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.codeE→(E1) E1.true:=E.true; E1.false:=E.false; E.code:=E1.code第60页，课件共72页，创作于2023年2月产生布尔表达式三地址代码的语义规则 产生式 语义规则

E→id1relopid2E.code:=gen(‘if’id1.place relop.opid2.place‘goto’E.true)|| gen(‘goto’E.false)E→true E.code:=gen(‘goto’E.true)E→false E.code:=gen(‘goto’E.false)第61页，课件共72页，创作于2023年2月考虑如下表达式：

a<borc<dande<f

假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：

ifa<bgotoLtrue gotoL1 L1: ifc<dgotoL2 gotoLfalse L2: ife<fgotoLtrue gotoLfalse第62页，课件共72页，创作于2023年2月布尔表达式的翻译两遍扫描为给定的输入串构造一棵语法树；对语法树进行深度优先遍历，进行语义规则中规定的翻译。一遍扫描第63页，课件共72页，创作于2023年2月一遍扫描实现布尔表达式的翻译采用四元式形式把四元式存入一个数组中，数组下标就代表四元式的标号约定 四元式(jnz,a,-,p) 表示ifagotop

四元式(jrop,x,y,p)表示ifxropygotop

四元式(j,-,-,p)表示gotop第64页，课件共72页，创作于2023年2月有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地址作为E的语义值保存,待机"回填"。第65页，课件共72页，创作于2023年2月为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表例如:假定E的四元式中需要回填"真"出口的p，q，r三个四元式，则E.truelist为下列链:(p)(x，x，x，0)…(q)(x，x，x，