ch6语义分析和中间代码生成.ppt

第六章 属性文法,第六章 语义分析与中间代码生成,6.1 语义分析的任务 6.2 语法制导翻译 6.2.1 属性文法的定义 6.2.2 基于属性文法的处理方法 6.2.3 S属性文法的自下而上计算 6.2.4 L属性文法和自顶向下翻译。 6.3 中间代码生成,6.1 语义分析的任务,源程序经过词法分析、语法分析后，表明该源程序书写正确、符合程序语言所规定的语法，但语法分析并未对程序内部的逻辑含义加以分析，因此编译程序接着进行语义分析，即审查每个语法成分的静态语义。如果静态语义正确，则生成与该语言成分等效的中间代码，或直接生成目标代码。,6.1 语义分析的任务,语义分析进行的语义检查有两类：动态语义检查和静态语义检查。动态语义检查需生成相应的目标代码，在运行时进行；静态语义检查在编译时进行。,6.1 语义分析的任务,静态语义检查涉及以下几个方面： (1)类型检查，如运算操作数的类型应相容。 (2)控制流检查，用以保证控制语句有合法的 转向点。如C语言中不允许goto语句转入 case语句流；break语句需寻找包含它的最 小switch、while或for语句方可找到转向点。 (3)一致性检查，如在相同作用域中标识符只 能说明一次。,6.2 语法制导翻译,程序语言的词法和语法结构可分别用正规式和上下文无关文法来描述，已建立成熟的形式化描述方法。 由于语义是上下文有关的，因此语义的形式化描述非常困难，目前较常见的是用属性文法作为描述语义的工具，并采用语法制导翻译法完成对语法成分的翻译。该方法在语法分析的同时进行语义分析。,6.2.1 属性文法的定义,要利用语法制导的翻译方法，就需要在一个上下文无关文法的基础之上赋予每个文法符号以一定的属性，并规定文法的每个产生式对相关属性的运算规则，这种附加了一组属性和运算规则的文法称为属性文法。 例如：对一个算数表达式进行翻译，不仅要知道各个运算符的先后次序，而且还要知道表达式中各个变量和常量的数据类型、内存地址或值，还要知道中间结果存放的内存地址和值，这些信息被称为语义信息，也称为属性。,6.2.1 属性文法的定义,属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等等。属性和变量一样，可以进行计算和传递，依据则是语义规则。 属性的运算规则又称为语义规则或语义子程序，与相应的产生式密切相关，属性的值是由语义规则计算出来的，而语义规则的计算可以产生中间代码或目代码。,属性的表示,在属性文法中，文法符号X的属性t常用X.t来表示。例如：X.val、X.type、X.addr分别表示X的值、类型和地址。 例如：对于算数表达式文法GE: 如果只想计算表达式的值，则只需关心各文法符号的值属性，因此对每个非终结符都有一个整数值的属性，分别为E.val、T.val、F.val，i的属性为i.lexval。其他终结符+、*、（、）都代表语义动作，将在语义规则中反映。,E-E+T|T T-T*F|F F-(E)|i,语义规则的表示,一个产生式对应的语义规则是根据产生式所蕴涵的语义操作所建立的，并与语义分析的目标有关。 例如文法GE，已表达式求值为目标构造各产生式的语义规则如下：,E-E+T|T T-T*F|F F-(E)|i,语 义 规 则,E E1+T,E T,T T1 * F,T F,F (E),F digit,E.val:=E1.val+T.val,E.val:=T.val,T.val:=T1.val F.val,T.val:=F.val,F.val:=E.val,F.val:=digit.lexval,产 生 式,6.2.2 基于属性文法的处理方法,用属性描述语义信息，用语义规则描述属性间的关系，将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性的值，从而完成预定的翻译工作。这就是语法制导翻译的思想。,具体实现时，语法制导翻译有两种处理方法： 语法制导定义，即对每个产生式编制一个语义分析子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义分析子程序检查与翻译。这种实现方案隐藏了语义规则的计算次序等细节问题，不必规定翻译顺序。 翻译模式，即在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。,语法制导的定义,属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。,语法制导的定义,综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。 继承属性：在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便,语法制导的定义,在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条语义规则的形式为： b:=f(c1,c2,ck) 这里f是一个函数，或者： （1）b是A的一个综合属性并且c1,c2,ck是产生式右边文法符号的属性； （2）b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck是A或产生式右边任何文法符号的属性 在这两种情况下，我们都说属性b依赖于属性c1,c2,ck.,语法制导的定义,要特别强调的是： （1）终结符只有综合属性，它由词法分析器提供； （2）非终结符既可以有综合属性也可以有继承属性，但文法开始符号没有继承属性。,例6.1 台式计算器程序的语法制导定义,产生式 语义规则,LEn print(Eval) E E1+T E val := E1 val+T val E T E val := T val T T1*F T val := T1 val*F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,每个文法符号和一个属性值val 联系，属性值的设置和语法结构的语义以及翻译程序的需要有关。,例如：把左例中的类型扩充到 int和real。,综合属性 S-属性定义 唯独只使用综合属性的语法制导定义。 结点属性值的计算正好和自底向上分析建立分析树结点同步进行。,上例中输入串为3*5+4n的带注释的语法树,每个节点的属性值都标注出来的分析树叫做注释分析树,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=15,+,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,输入：3*5+4n,LEn E E1+T E T T T1*F T F F (E) F digit,例6.2：已知文法如下，构造个产生式的语义规则，将每个变量名及其类型信息填入符号表。,产生式 语义规则 DTL Lin:=T type T int T type :=integer T real T type :=real L L1,id L1 in :=L in addtype(id entry,L in) L id addtype(id entry,L in),表6.2 带有继承属性L.in的语法制导定义,上例文法定义了一种说明语句，该说明语句的形式由关键字int或real开头，后跟一个标识符表，每个标识符间有逗号隔开。非终结符号T有一个综合属性type，它的值由关键字int或real决定。与产生式D-TL相联的语义L.in:=T.type将L.in的属性值置为该说明语句指定的类型。属性L.in将沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了它。过程addtype的功能是把每个标识符的类型信息登录在符号表中相关项中。,下面给出句子real id1,id2,id3带注释的语法树。,T.type,L.in,real,L.in,i3.entry,L.in,i2.entry,i1.entry,基于属性文法的处理方法,从概念上讲，基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。 输入串语法树依赖图语义规则计算次序,基于属性文法的处理方法,这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。对输入串的翻译也就是根据语义规则进行计算得出结果。,依赖图,描述语法树中结点属性之间的相互依赖关系的有向图。 为包含过程调用的语义规则引入一个虚综合属性b，这样把每个语义规则都写成 b:=f(c1,c2,.,ck)的形式。 依赖图中为每一个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。,例如，假设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.,例6.3当下面的产生式应用于语法树时，我们就把有向边加到依赖图中。 产生式 语义规则 EE1+E2 E.val:=E1.val+E2.val,例6.4下页的图是例6.2带注释语法树的依赖图。,如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。,属性的计算次序 一个有向非循环图（DAG）的拓扑序是图中结点的任何顺序m1,m2, mk,使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。从依赖图的拓扑排序中可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。,例：上例中的一个拓扑排序可以从低序号到高序号顺序给出。从该拓扑排序可得到下列程序： a4:=real; a5:=a4; addtype(id3.entry,a5); a7:=a5; addtype(id2.entry,a7); a9:=a7; addtype(id1.entry,a9);,树遍历的属性计算方法 设语法树已经建立起了，并且树中已带有开始符号的综合属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。 一遍扫描的处理方法 与树遍历的属性计算文法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且并无需构造实际的语法树。,如果按这种一遍扫描的编译程序模型来理解语法制导翻译方法的话，所谓语法制导翻译法，直观上说是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则.在自上而下的语义分析中,若一个产生式匹配输入串成功,或者在自下而上分析中,当一个产生式被用于进行归约时,此产生式相应的语义规则就被计算,完成有关语义分析和代码生成的工作.,6.3 S属性文法的自下而上计算,S属性文法：只含有综合属性的属性文法。 S属性文法的翻译器可借助于LR分析器实现。在分析栈中使用一个附加的域来存放综合属性值。,当第i个state对应的符号为A时，vali中就存放语法树中与结点A对应的属性值。,设当栈顶由指针top指示。我们假设综合属性是刚好在每次归约前计算的。假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式AXYZ的。在把XYZ归约成A以前，属性Z.z的值放在valtop中，Y.y的值放在valtop-1中，X.x的值放在valtop-2中。如果一个符号没有综合属性，那么数组val中相应的元素就不定义。归约后，top值减2，A的状态存放在statetop中（也就是X的位置）综合属性A.a的值存放在valtop中。,例：下表台式计算器的属性文法。在自底向上分析输入串2+3*5n时，分析器在每次规约前执行表中的代码段。,文法GE (1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F:=(E) (6)F:=i,假定输入串为2+3*4n， LR分析器的工作过程: 步骤 状态 符号 语义栈 输入串 (1) 0 # - 2+3*4# 05 #2 -2 +3*4# 03 #F -2 +3*4# 02 #T -2 +3*4# (5) 01 #E -2 +3*4#,文法GE (1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F:=(E) (6)F:=i,假定输入串为i*i+i， LR分析器的工作过程: 步骤 状态 符号 语义栈 输入串 016 #E+ -2- 3*4# 0165 # E+ 3 -2-3 *4# 0163 # E+ F -2-3 *4# 0169 # E+ T -2-3 *4# (10) 01697 # E+ T* -2-3- 4#,文法GE (1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F:=(E) (6)F:=i,假定输入串为i*i+i， LR分析器的工作过程: 步骤 状态 符号 语义栈 输入串 016975 # E+ T* 4 -2-3- 4 # 01697(10) # E+ T* F -2-3- 4 # (13)0169 # E+ T -2-(12) # (14)01 #E -(14) # (15) 接受,L属性文法：如果每个产生式AX1X2.Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且这个继承属性仅依赖于： 1.产生式Xj的左边符号X1,X2,.,Xj-1的属性； 2.A的继承属性。 S属性文法一定是L属性文法。,6.4 L属性文法和自顶向下翻译,例: 请判断下表所示属性文法是不是L属性文法,6.4.1 翻译模式 用属性文法计算时必须先确定计算的顺序,为了使用户从确定翻译顺序的工作中解脱出来,可以使用翻译模式. 在翻译模式中，和文法符号相关的属性和语义规则用花括号 括起来，插入到产生式右部的合适位置上。这样翻译模式给出了使用语义规则进行计算的顺序。,例:下例是一个翻译模式,它将带加号和减号的中缀表达式翻译成相应的后缀表达式.,每个语义动作都作为相应产生式左部符号节点的儿子,我们把它看作是终结符,表示在 什么时候应该执行那些动作.这样我们深度优先执行后得到后缀表达式95-2+,左图是关 于输入串 9-5+2的 语法树,如何建立翻译模式 1. 只有综合属性 为每一个语义规则建立一个包含赋值的动作,并把这个动作放在相应的产生式右边的末尾. 例如, 假设有下面的产生式和语义规则: 产生式 语义规则 T T*F T.val:=T1.val+F.val 建立其对应的翻译模式如下: T T*F T.val:=T1.val+F.val,2.既有综合属性又有继承属性 (1)产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。 (2)一个动作不能引用这个动作右边符号的综合属性。 (3)产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,例:,6.4.2 自顶向下翻译 为使更多的文法可以使用自顶向下分析，采用消除基本文法左递归时，同时考虑属性计算的变换。 例：带左递归的算术表达式的文法翻译模式 EE1+T E.val:=E1.val+T.val EE1-T E.val:=E1.val-T.val ET E.val:=T.val T(E) T.val:=E.val Tnum T.val:=num.val,消除左递归后的翻译模式 ET R.i:=T.val R E.val:=R.s R + T R1.i:=R.i+T.val R1 R.s :=R1.s R - T R1.i:=R.i-T.val R1 R.s :=R1.s R R.s :=R.i T( E ) T.val:=E.val Tnum T.val:=num.val,对于自顶向下分析,我们假设动作是在处于相同位置上的符 号被完全展开(匹配成功)时执行的.,转换左递归翻译模式方法的一般化： 设有下列翻译模式： AA1Y A.a :=g(A1.a,Y.y) AX A.a :=f(X.x) 消除左递归后的翻译模式： AX R .i :=f(X.x) R A.a :=R.s RY R1.i :=g(R.i,Y.y R1 R.s :=R1.s R R.s:=R.i,消除左递归前、后的翻译模式等价：,R.s=R.i,中间语言：源程序的一种内部表示，不依赖目标机的结构，便于优化，便于移植。 中间语言形式：后缀式、三地址代码（包括三元式、四元式、间接三元式）、 AST、 DAG图表示。,6.5 中间语言,6.5.1 后缀式（逆波兰式） 将运算对象写在前面，运算符写在后面。 例： a+b ab+ (a+b)*c ab+c* a+b*c abc*+ a:=b*c+b*d abc*bd*+:=,一个表达式E的后缀形式可以如下定义： （1）若E是变量或常量，则E1的后缀式是E （2）若E是E1opE2形式的表达式，则E的后缀式为E1E2op，其中E1、E2分别为E1和E2的后缀式。 （3）若E是（E1）形式的表达式，则E1的后缀式就是E 的后缀式。后缀表示法不需要括号，如：(a+b)*c表示为ab+c*,把表达式翻译成后缀式的语义规则描述,注：E.code表示E的后缀表达式，op表示任意二元操作符，“|”表示后缀形式的连接。,例：把下述产生式定义的算术表达式映射到后缀波兰表示：,确定输入a+aa的输出： (E,E)(E+T,ET+) (T+T,TT+) (F+T,FT+) (a+T,aT+) (a+TF,aTF+) (a+FF,aFF+) (a+aF,aaF+) (a+aa,aaa+),后缀式的最大优点是易于计算机处理 处理过程： 利用一个栈，自左向右扫描逆波兰式，碰到运算对象，把它推进栈，碰到运算符： 若是双目运算符，则对栈顶的两个运算对象实施该运算并将运算结果代替这两个运算对象进栈； 若是单目运算符，对栈顶元素，执行该运算，将运算结果代替该元素进栈，最后结果即栈顶元素。,例：表达式bc*d的后缀式b uminus cd*+的计值过程,t1= - b,t2= c*d,t3= t1+t2,逆波兰表示法的扩充 逆波兰表示法很容易扩充到表达式以外的范围 例如：,把表达式翻译成后缀式的语义规则描述,产生式 EE(1)op E(2) E (E(1) Eid,语义动作 E.code:= E(1).code | E(2).code |op E.code:= E(1).code E.code:=id,E.code表示E后缀形式 op表示任意二元操作符 “|”表示后缀形式的连接。,数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式 程序段 EE(1)op E(2) POSTk:=op;k:=k+1 E (E(1) Ei POSTk:=i;k:=k+1 例：输入串a+b+c的分析和翻译 POST： 1 2 3 4 5,EE(1)op E(2) E.code:= E(1).code | E(2).code |op E (E(1) E.code:= E(1).code Eid E.code:=id,a,b,+,c,+,6.5.2 图表示法 图表示法包括：包括DAG和AST。 DFG：无循环有向图。 与AST相同，DAG为每个子表达式设一个结点，内部结点代表操作符，孩子结点为操作数。DAG中公共子表达式结点具有多个父结点，而AST中公共子表达式表示为重复的子树。,抽象语法树,语法树作为一种合适的中间语言形式,我们可以通过对它的遍历完成属性的计算.为了获得更有小的源程序中间表示,需要在语法树中去掉那些对翻译不必要的信息,这种经变换后的语法树称为抽象语法树(AST) .,表达式的语法树被定义为具有下述性质的一棵树: （1） 根与内部节点由表达式中的操作符或关键字标记； （2） 叶子由表达式中的操作数标记； （3） 用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。 例如,句子-(id+id)和句型if C then s1 else s2 ：,-,+,id,id,S if C then S1 else S2,例：画出a+a*(b-c)+(b-c)*d的抽象语法树。 画出a:= b*-c+b*-c,如何建立抽象语法树 建立表达式的抽象语法树,我们通过为每个运算分量或运算符号都建立一个结点来为子表达式建立子树. 抽象语法树中的每一个结点可以由包含几个域的记录来实现的. 在一个运算符号对应的结点中,一个域标识运算符号，其它域包含指向运算分量的结点的指针。运算符号通常叫做这个结点的标号。当我们进行翻译时，抽象语法树中的结点可能会用附加域来存放结点的属性值(或指向属性的指针）。,用下列函数建立表示带有二目算符的表达式的抽象语法树中的结点。每个函数都返回一个指向新建立结点的指针。 mknode(op,left,right) 建立一个运算符号结点 mkleaf(id,entry) 建立一个标识符结点 mkleaf(num,val) 建立一个数结点,建立抽象语法树的语义规则,例：下列函数调用建立表达式a-4+c的抽象语法树。 p1:=mkleaf(id,entrya); p2:=mkleaf(num,4); p3:=mknode( - ,p1,p2); p4:=mkleaf(id,entryc); p5:=mknode( + ,p3,p4);,DFG DFG：无循环有向图。 与AST相同，DAG为每个子表达式设一个结点，内部结点代表操作符，孩子结点为操作数。DAG中公共子表达式结点具有多个父结点，而AST中公共子表达式表示为重复的子树。,抽象语法树有两种表达形式：,6.5.3 三地址代码 一般形式为 x:=y op z 特点：每个语句的右边只有一个操作符。 例：源程序语言表达式x+y*z可以被翻译为如下语句序列： T1:=y*z T2:=x+T1 三地址码可以看成是DAG或AST的一种线性表示。,例如：,a:=b*-c+b*-c的抽象语法树,T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,AST的三地址码,a:=b*-c+b*-c的DAG,T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,DAG的三地址码,三个地址：两个存放操作数，一个存放结果。 三地址语句的种类： （1）形如x:=y op z的赋值语句，其中op为二元算符或逻辑算符。 （2）形如x:=op y的赋值语句，其中op为一元算符 （3）形如x:=y的赋值语句。 （4）形如goto L的无条件转移语句 （5）形如if x relop y goto L或if a goto L的条件转移语句。,（6）用于过程调用的语句 param x 和call p,n,以及返回语句return y。上述语句为p(x1,x2,xn)三地址代码。 （7）形如x:=yi及xi:=y的索引值。 （8）形如x:=&y, x:=*y, *x:=y的地址赋值。,例：下表是赋值语句生成三地址码的S-属性文法。,三地址语句有三种表示方法：四元式、三元式、间接三元式。 1.四元式 是带有四个域的记录结构：op、arg1、arg2、result。 例：复制语句的a:=b*c+b*d的四元式,(1)t1:=b*c (2)t2:=b*d (3)t3:=t1+t2 (4)a:=t3 三地址码,(1)(*,b,c,t1) (2)(*,b,d,t2) (3)(+,t1,t2,t3) (4)(:=,t3, ,a) 三地址码用四元式表示,例：a:=b*-c+b*-c的四元式表示,T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 三地址码,例: 三地址码 四元式 x:=y op z (op, y, z,x) x:=op y (op, y, ,x) x:= y (:=, y, ,x) goto L (j, , ,L) if x goto L (jnz, x, ,L) if x relop y goto L (jrelop, x, y,L) x:=yi (=, yi, ,x) xi:=y (=, y, ,xi),2.三元式： 为避免将临时变量写入符合表，通过指针来引用临时变量。因此三元式只包括：op arg1 arg2。 两个操作数arg1和 arg2或者是指向符号表的指针，或者是指向三元式表的指针。,例：a:=b*-c+b*-c的三元式表示：,3.间接三元式： 为便于优化处理，不直接使用三元式表，而是另设一张间接码表。该表将按运算先后顺序列出三元式的位置。 例：X:=(A+B)*C; Y:=D(A+B)的间接三元式为,间接三元式和三元式： （1）当在代码优化过程中需要调整运算顺序时，只需重新安排简介码表，无需改动三元式表； （2）相同的三元式无需重复添加在三元式中。 三元式和四元式：三元式表很难调整改动，而要调整四元式之间的相对位置则较为简单。因此，当对中间代码优化时,四元式比三元式更方便。,练习:将下述语句分别翻译成后缀式、三元式和四元式。 (1) a*-(b+c) (2) -(a+b)*(c+d)+(a+b-c),赋值语句的翻译,为赋值语句生成三地址代码的S-属性文法定义,产生式 语义规则 Sid:=E S.code:=E.code | gen(id.place := E.place) EE1+E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place) E (E1) E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,产生赋值语句三地址代码的翻译模式,Sid:=E p:=lookup(); if pnil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; emit(E.place := E 1.place * E 2.place),Sid:=E S.code:=E.code | gen(id.place := E.place) EE1+E2 E.place:=newtemp; E.code:=E1.code | E2.code |gen(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place * E2.place),产生赋值语句三地址代码的翻译模式,E-E1 E.place:=newtemp; emit(E.place:= uminusE 1.place) E(E1) E.place:=E1.place Eid p:=lookup(); if pnil then E.place:=p else error ,E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place) E (E1) E.place:=E1.place; E.code:=E1.code Eid E.place:=id.place; E.code= ,布尔表达式的翻译,布尔表达式的两个基本作用: 用于逻辑演算,计算逻辑值; 用于控制语句的条件式. 产生布尔表达式的文法: EE or E | E andE | E | (E) | i rop i | true | false,计算布尔表达式通常采用两种方法: 1. 如同计算算术表达式一样,一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =1 2. 采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else false 把 A解释成 if A then false else true,两种不同的翻译方法: 第一种翻译法： A or B and C=D翻译成 (1) (=, C, D, T1) (2) (and, B, T1, T2) (3) (or, A, T2, T3) 第二种翻译法适合于作为条件表达式的布尔表达式使用.,7.4.1 数值表示法,a or b and not c 翻译成 T1:=not c T2:=b and T1 T3:=a or T2 ab的关系表达式可等价地写成 if ab then 1 else 0 ，翻译成 100: if ab goto 103 101: T:=0 102: goto 104 103: T:=1 104:,关于布尔表达式的数值表示法的翻译模式,过程emit将三地址代码送到输出文件中 nextstat给出输出序列中下一条三地址语句的地址索引 每产生一条三地址语句后，过程emit便把nextstat加1,关于布尔表达式的数值表示法的翻译模式,EE1 or E2 E.place:=newtemp; emit(E.place := E 1.place or E2.place) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) Enot E1 E.place:=newtemp; emit(E.place := not E 1.place) E(E1) E.place:=E1.place,关于布尔表达式的数值表示法的翻译模式,Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop. op id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Eid E.place:=id.place ,ab 翻译成 100: if ab goto 103 101: T:=0 102: goto 104 103: T:=1 104:,布尔表达式ab or cd and ef的翻译结果,100: if ab goto 103 101: T1:=0 102: goto 104 103: T1:=1 104: if cd goto 107 105: T2:=0 106: goto 108 107: T2:=1 108: if ef goto 111 109: T3:=0 110: goto 112 111: T3:=1 112: T4:=T2 and T3 113: T5:=T1 or T4,Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop. op id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Eid E.place:=id.place EE1 or E2 E.place:=newtemp; emit(E.place := E 1.place or E2.place) EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place) ,7.4.2 作为条件控制的布尔式翻译,条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假,E.code,S1.code,S2.code,To E.true,To E.false,goto S.next,S.next,E.true:,E.false:,例：把语句: if ac or b c goto L2 “真”出口 goto L1 L1: if bd goto L2 “真”出口 goto L3 “假”出口 L2: (关于S1的三地址代码序列) goto Lnext L3: (关于S2的三地址代码序列) Lnext:,每次调用函数newlabel后都返回一个新的符号标号 对于一个布尔表达式E，引用两个标号 E.true是E为真时控制流转向的标号 E.false是E为假时控制流转向的标号,产生布尔表达式三地址代码的语义规则,产生式 语义规则 EE1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code | gen(E1.false :) | E2.code,产生布尔表达式三地址代码的语义规则,产生式 语义规则 EE1 and E2 E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code | gen(E1.true :) | E2.code,产生布尔表达式三地址代码的语义规则,产生式 语义规则 Enot E1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.code E (E1) E1.true:=E.true; E1.false:=E.false; E.code:=E1.code,产生布尔表达式三地址代码的语义规则,产生式 语义规则 Eid1 relop id2 E.code:=gen(if id1.place relop.op id2.place goto E.true) | gen(goto E.false) Etrue E.code:=gen(goto E.true) Efalse E.code:=gen(goto E.false),考虑如下表达式： ab or cd and ef 假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：,if ab goto Ltrue goto L1 L1: if cd goto L2 goto Lfalse L2: if ef goto Ltrue goto Lfalse,布尔表达式的翻译,两遍扫描 为给定的输入串构造一棵语法树； 对语法树进行深度优先遍历，进行语义规则中规定的翻译。 一遍扫描,一遍扫描实现布尔表达式的翻译,采用四元式形式 把四元式存入一个数组中，数组下标就代表四元式的标号 约定 四元式(jnz, a, -, p) 表示 if a goto p 四元式(jrop, x, y, p)表示 if x rop y goto p 四元式(j, -, -, p) 表示 goto p,有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地址作为E的语义值保存,待机“回填“。,为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表 例如:假定E的四元式中需要回填“真“出口的p，q，r三个四元式，则E.truelist为下列链: (p) (x， x，x，0) (q) (x，x，x，p) (r) (x，x，x，q),链尾,E. truelist =r,为了处理E.truelist和E.falselist ，引入下列语义变量和过程: 变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)。nextquad的初值为1，每当执行一次emit之后，nextquad将自动增1。 函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针。 函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。 过程backpatch(p, t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。,布尔表达式的文法,(1) E E1 or M E2 (2) | E1 and M E2 (3) | not E1 (4) | (E1) (5) | id1 relop id2 (6) | id (7) M,布尔表达式的翻译模式,(7) M M.quad:=nextquad ,布尔表达式的翻译模式,(1) EE1 or M E2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist); E.falselist:=E2.falselist (2) EE1 and M E2 backpatch(E1.truelist, M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) ,布尔表达式的翻译模式,(3) Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist (4) E(E1) E.truelist:=E1.truelist; E.falselist:=E1. falselist,布尔表达式的翻译模式,(5) Eid1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place, 0); emit(j, , , 0) (6) Eid E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , , 0)； emit( j, -, -, 0) ,布尔表达式的翻译模式,作为整个布尔表达式的“真“假“出口(转移目标)仍待回填.,ab or cd and ef,100 (j, a, b, 0) 101 (j, -, -, 102) 102 (j, c, d, 104) 103 (j, -, -, 0) 104 (j, e, f, 100) truelist 105 (j, -, -, 103) falselist,控制语句的翻译,7.5 控制语句的翻译,考虑下列产生式所定义的语句 S if E then S1 | if E then S1 else S2 | while E do S1 其中E为布尔表达式。,if-then语句 S if E then S1,E.code,S1.code,To E.true,To E.