第8章 语法制导翻译及中间代码生成

1、第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成8.18.1概述概述语法分析语法分析后的源程序后的源程序语义处理语义处理中间代码中间代码或目标代或目标代码码一、语义处理的任务：一、语义处理的任务：根据语义规则对识别出的各种语法成分析其根据语义规则对识别出的各种语法成分析其含义，进行初步翻译，生成相应的中间代码含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。或直接生成目标代码。第一第一 静态语义分析或静态审查。静态语义分析或静态审查。第二第二 动态语义处理：动态语义处理：编译中的语义处理是指两个功能编译中的语义处理是指两个功能 类型检查。类型检查。 控制流检查：确保

2、控制语句有合法的转向点。控制流检查：确保控制语句有合法的转向点。 一致性检查。一致性检查。 相关名字检查。相关名字检查。 名字的作用域分析名字的作用域分析第一第一: : 静态语义分析通常包括：静态语义分析通常包括：如果静态语义正确，语义处理则要执行真正如果静态语义正确，语义处理则要执行真正的翻译，即，的翻译，即，或者将源程序翻译成程序的一或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程种中间表示形式（中间代码），或者将源程序翻译成目标代码。序翻译成目标代码。第二第二 动态语义处理：动态语义处理：实际应用中比较流行的语义分析方法：实际应用中比较流行的语义分析方法：基于基于属性文法

3、属性文法的的语法制导翻译方法语法制导翻译方法 8.28.2属性文法属性文法属性文法：属性文法： 属性：属性： 所谓属性，用以描述事物或人的特征、性所谓属性，用以描述事物或人的特征、性质，品质等等。比如，谈到一个物体，可质，品质等等。比如，谈到一个物体，可以用以用“颜色颜色”描述它，谈起某人，可以使描述它，谈起某人，可以使用用“有幽默感有幽默感“来形容他。来形容他。对一个文法对一个文法, ,文法中的每个符号都有属性，文法中的每个符号都有属性，可以用可以用 类型类型 、 值值 或或 存储位置存储位置 来描述来描述它。它。附加了一组附加了一组属性属性和和运算（语义）规则运算（语义）规则的的文法文法

4、属性文法属性文法文法符号文法符号X的属性的属性t常用常用X.t来表示来表示 语义规则用花括号语义规则用花括号 括起来，可被插入到产括起来，可被插入到产生式右部的任何合适的位置上生式右部的任何合适的位置上。不同的不同的产生式产生式对应不同的语义规则对应不同的语义规则不同的不同的分析目标分析目标也对应不同的语义规则也对应不同的语义规则 1. 属性的表示属性的表示2.语义规则语义规则的表示的表示语义信息语义信息语义之间的关系语义之间的关系一个属性文法是一个三元组：一个属性文法是一个三元组： A A（G G，V V，F F），）， G: G: 是一个上下文无关文法是一个上下文无关文法 V: V: 有穷

5、的属性集有穷的属性集, ,每个属性与文法的一终结符每个属性与文法的一终结符 或非终结符相连。或非终结符相连。 F: F: 关于属性的属性断言或谓词集关于属性的属性断言或谓词集. .每个断言与每个断言与 一个产生式相联。一个断言就是一个语义一个产生式相联。一个断言就是一个语义 规则，规则， 描述各属性的关系。描述各属性的关系。用法：用法：针对语义：为每个符号设置一个属性，终结符号用单针对语义：为每个符号设置一个属性，终结符号用单词属性。词属性。为每个产生式设置语义规则为每个产生式设置语义规则描述各属性的关系。描述各属性的关系。属性文法的定义：属性文法的定义：属性分为两种属性分为两种 继承属性和综

6、合属性继承属性和综合属性综合属性：综合属性：在语法树中，一个结点的综合属性由在语法树中，一个结点的综合属性由该结点的子结点的属性值确定。它的计算规则由该结点的子结点的属性值确定。它的计算规则由底向上底向上. .继承属性继承属性: :在语法树中，一个结点的继承属性由在语法树中，一个结点的继承属性由该结点的该结点的 父结点父结点/ /兄弟结点的属性确定。兄弟结点的属性确定。 例综合属性例综合属性 L EE E1+TE T T T1 * FT FF (E)F iprint(E.val) E.val=E1.val+T.valE.val=T.val T.val=T1.val F.valT.val=F.v

7、alF.val=E.valF.val=i.lexval语语 义义 规规 则则产生式产生式计算计算3*5+4的值的值3*5+4的分析树的分析树只使用综合属性.LEETTFTFFi 5 i 4i 3+*3*5+4的分析树的分析树 一个结点的综合属性一个结点的综合属性值是其值是其子结点子结点的某些的某些属性来决定的属性来决定的通常使用通常使用自底向上自底向上的分析方法的分析方法在在每个结点每个结点处使用语义规则来计算综合属性处使用语义规则来计算综合属性值值当一个当一个产生式获得匹配产生式获得匹配时，就调用相应的语时，就调用相应的语义子程序从义子程序从叶结点到根结点叶结点到根结点进行计算进行计算 L

8、EE E1+TE T T T1 * FT FF (E)F iprint(E.val) E.val=E1.val+T.valE.val=T.val T.val=T1.val F.valT.val=F.valF.val=E.valF.val=i.lexval语语 义义 规规 则则产生式产生式继承属性继承属性一个结点的继承属性值是由此结点的父结点和一个结点的继承属性值是由此结点的父结点和/ /或兄弟结点的某些属性来决定的。例，添加标或兄弟结点的某些属性来决定的。例，添加标识符类型的语义描述：识符类型的语义描述： 继承属性继承属性 L1.in:=L.in产生式语 义 规 则D TL T int T r

9、eal L L1,idL idL.in:=T.typeT.type=integerT.type:=real addtype(id.entry,L.in) addtype(id.entry,L.in )与与L L产生式相联的语义规则中有一个过程调用产生式相联的语义规则中有一个过程调用addtypeaddtype，过程，过程addtypeaddtype的功能是把每个标识的功能是把每个标识符的类型信息登录在符号表的相关项中。符的类型信息登录在符号表的相关项中。句子句子 int id1,id2 int id1,id2 的语法树，使用的语法树，使用 表示属性的传递表示属性的传递情况。情况。 L1.in:

10、=L.in产生式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real addtype(id.entry,L.in) addtype(id.entry,L.in )DTLLid1id2，int1、文法非终结符既、文法非终结符既可可有综合属性，也可有继承属性；有综合属性，也可有继承属性；2、开始符号没有继承属性；、开始符号没有继承属性；3、终结符只有综合属性，由词法分析器提供。、终结符只有综合属性，由词法分析器提供。几点说明：几点说明：语法制导翻译：将语法制导翻译：将语义规则语义规则与与语法规则语法规则

11、相结合，在相结合，在语法分析语法分析的过程中通过执行的过程中通过执行语义动作语义动作，计算语义属，计算语义属性值，从而完成预定的翻译工作。性值，从而完成预定的翻译工作。 8.38.3语法制导翻译语法制导翻译自底向上语自底向上语法制导翻译法制导翻译自顶向下语自顶向下语法制导翻译法制导翻译语法制导翻译的实现语法制导翻译的实现语法制导翻译分为两种语法制导翻译分为两种处理方法处理方法：（1）自底向上的翻译：（只有综合属性）自底向上的翻译：（只有综合属性）对每个产生式编制一个语义子程序，在进行语法分析的过对每个产生式编制一个语义子程序，在进行语法分析的过程中，程中，当一个产生式获得匹配时，当一个产生式获

12、得匹配时，就调用相应的语义子程就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。则的计算次序等实现细节，不必规定翻译顺序。（2）自顶向下翻译（含有继承属性）：）自顶向下翻译（含有继承属性）：在产生式右部的适当位置，插入相应的语义动作，即语义在产生式右部的适当位置，插入相应的语义动作，即语义规则或语义动作用花括号规则或语义动作用花括号 括起来，可被插入到产生式括起来，可被插入到产生式右部的任何合适的位置上。右部的任何合适的位置上。按照分析的进程，执行遇到的语义动作。这是一种按照分析的进

13、程，执行遇到的语义动作。这是一种动作与动作与分析交错分析交错的实现方案。的实现方案。语法制导定义语法制导定义对每个产生式编制一个对每个产生式编制一个语义子程序语义子程序在进行语法分析的过程中在进行语法分析的过程中，当一个产生式获得匹配时，当一个产生式获得匹配时，就调就调用相应的语义子程序实现语义检查与翻译用相应的语义子程序实现语义检查与翻译综合属性综合属性继承属性继承属性自底向上自底向上传递信息传递信息自顶向下（自左自顶向下（自左向右）向右）传递信息传递信息n仅包含综合属性的语法制导定义仅包含综合属性的语法制导定义 如：算术表达式求值的属性文法如：算术表达式求值的属性文法n既包括综合属性，又包

14、括继承属性，即既包括综合属性，又包括继承属性，即对对于所有于所有1 1 2 2 n n，每一个属性，每一个属性或者都是综合属性，或者或者都是综合属性，或者i i 属性计算仅属性计算仅使用使用 1 1 2 2 i-1i-1 的属性的属性n其属性可用其属性可用深度优先深度优先的顺序从左至右计算的顺序从左至右计算非非L-属性的语法制导定义属性的语法制导定义产生式语义规则ALMA QRL.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)表中的语法制导定义不是表中的语法制导定义不是L-L-属性定义属性定义文法符号文法符号Q

15、Q的继承属性依赖于它右边文法符的继承属性依赖于它右边文法符号号R R的属性的属性例如：定义表达式的文法如下：例如：定义表达式的文法如下： E EE+E E+E E E(E)(E) E En n 给出定义表达式值的属性文法。给出定义表达式值的属性文法。E EE E1 1+E+E2 2 E.val := E E.val := E1 1.val +E.val +E2 2.val.valE E(E(E1 1) E.val := E) E.val := E1 1.val .val E En E.val := n.lexn E.val := n.lex属性文法的属性文法的主要思想有两点：主要思想有两点：首

16、先对于每个文法符号引进相关的属性符号；首先对于每个文法符号引进相关的属性符号；其次对于每个产生式写出属性值计算的规则。其次对于每个产生式写出属性值计算的规则。例 一个简单的翻译模式 ETR Raddop Tprint(addop.lexeme)R1| Tnumprint(num.val) 输入9-5+2,其分析树如下页图，当按深度优先遍历它，执行遍历中访问的语义动作，将输出： 9 5 - 2 +9 5 - 2 +它是输出表达式9-5+2的后缀式。ET9TPt(9)RPt(-)Pt(+)R-5Pt(5)+T2Pt(2)R9-5+2的带语义动作的分析树ETRETRRaddop Tprint(add

17、op.lexeme)RRaddop Tprint(addop.lexeme)R1 1|Tnumprint(num.val)Tnumprint(num.val)输出：输出： 9 5 - 2 +设计翻译模式设计翻译模式分两种情况分两种情况: :1、只需要综合属性的情况只需要综合属性的情况2. 2. 既有综合属性又有继承属性既有综合属性又有继承属性为每一个语义规则建立一个包含赋值的动作，并为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。把这个动作放在相应的产生式右边的末尾。例如：例如：T TT T1 1* *F TF T val:=Tval:=T1 1 valval*

18、 *F F valval T TT T1 1* *F TF T val:=Tval:=T1 1 valval* *F F valval1. 1. 只需要综合属性的情况：只需要综合属性的情况： 产生式右边的符号的继承属性必须在这个产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。符号以前的动作中计算出来。 一个动作不能引用这个动作右边符号的属一个动作不能引用这个动作右边符号的属性。性。 产生式左边非终结符号的综合属性只有在产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产计算。计算这种属性的

19、动作通常可放在产生式右端的未尾。生式右端的未尾。2. 2. 既有综合属性又有继承属性既有综合属性又有继承属性下面的翻译模式不满足要求下面的翻译模式不满足要求,不满足第不满足第1)个个条件：条件： SA1A2 A1 in:=1; A2 in:=2 A a print(A in) 可以看出可以看出,按深度优先遍历输入串按深度优先遍历输入串aa的语法树，当要打印的语法树，当要打印属性属性A.in时，该属性还没有定义。也就是说，从时，该属性还没有定义。也就是说，从S开始按开始按深度优先遍历深度优先遍历A1和和A2子树之前，子树之前，A1.in和和A2.in的值还的值还未赋值。未赋值。SA1A2aaA1

20、.in:=1;A2.in:=2Print(A.in)Print(A.in)如果计算如果计算A1.in和和A2.in的值的动作分别被嵌入在的值的动作分别被嵌入在产生式产生式SA1A2 的右部的右部A1和和A2之前，而不是后之前，而不是后面，那么面，那么A.in在执行在执行Print（A.in）时已有定义。）时已有定义。S A1in:=1 A1A2 in:=2 A2A a print(A in) SA1A2aaA1.in:=1;Print(A.in)Print(A.in)A2.in:=2;常见的中间代码常见的中间代码形式形式：后缀式后缀式三地址代码三地址代码（四元式、三元式和间接三元式（四元式、三

21、元式和间接三元式 ）图形图形（抽象语法树等）（抽象语法树等） 中间代码：一种介于中间代码：一种介于源语言和目标语言之间源语言和目标语言之间的中间语言形式的中间语言形式中间代码中间代码逆波兰记号逆波兰记号 逆波兰记号是最简单的一种中间代码表示逆波兰记号是最简单的一种中间代码表示形式。形式。这种表示法将运算对象写在前面，把运这种表示法将运算对象写在前面，把运算符号写在后面，比如把算符号写在后面，比如把a+ba+b写成写成ab+ab+，把把a a* *b b写成写成abab* *，用这种表示法表示的表，用这种表示法表示的表达式也称做后缀式。达式也称做后缀式。中缀表示中缀表示后缀表示后缀表示a+b a

22、b+a+b*c abc*+(a+b)*c ab+c*a:=b*c+b*d abc*bd*+:=特点特点1、运算对象出现的顺序和原有顺序（从左到右）相同、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值优点：简明、便于计值后缀表示法表示表达式，其最大的优点是易于计算机处理后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。表达式。常用的算法是使用一个栈，自左至右扫描算术表达式（后常用的算法是使用一个栈，自左至

23、右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。果代替该元素进栈，最后的结果留在栈顶。例如例如 BCD*+（它的中缀表示为它的中缀表示为B+CB+C* *D D，使用，使用表示一目减）的计值

24、过程为：表示一目减）的计值过程为： B B进栈；进栈； 对栈顶元素施行一目减运算，并将结果代替对栈顶元素施行一目减运算，并将结果代替栈顶，即栈顶，即B B置于栈顶；置于栈顶； C C进栈；进栈； D D进栈；进栈； 栈顶两元素相乘，两元素退栈，相乘结果置栈栈顶两元素相乘，两元素退栈，相乘结果置栈顶；顶；1.1. 栈顶两元素相加，两元素退栈，相加结果进栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。栈，现在栈顶存放的是整个表达式的值。逆波兰表示很容易扩充到表达式以外的范围。逆波兰表示很容易扩充到表达式以外的范围。只要遵守运算对象后直接紧跟它们的运算符的规只要遵守运算对象

25、后直接紧跟它们的运算符的规 则即可。则即可。比如把转语句比如把转语句GOTO LGOTO L写为写为“L jump L jump ， 运算对象运算对象L L为语句标号，运算符为语句标号，运算符jumpjump表示转到某个标表示转到某个标号号L L 。再比如再比如条件语句条件语句if E then S1 else S2if E then S1 else S2 可表示为：可表示为：ES1S2ES1S2￥，把，把if then elseif then else看成三目运看成三目运 算符，用￥来表示。算符，用￥来表示。生成后缀式的属性文法生成后缀式的属性文法产产生生式式 语语义义规规则则 Sid:=E

26、 EE1+E2 EE1*E2 E -E1 E (E1) E id E num Print( | E.code | “:=”) E.code := E1.code | E2.code | ”+” E.code := E1.code | E2.code | ”*” E.code := E1.code | “-“ E.code := E1.code E.code := E.code := num.val； 属属性性 code 表表示示生生成成的的代代码码 注释：注释： | | 表示代码序列的连接表示代码序列的连接例例:给出下列表达式的逆波兰式给出下列表达式的逆波兰式:

27、(1) a*(-b+c) (2) a+b*(c+d/e)解解 (1) abc+* (2) abcde/+*+ 练习练习:P202 1另一类中间代码形式是三元式。把表达式及各另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式种语句表示成一组三元式(op,ARG1,ARG2)(op,ARG1,ARG2)。分。分别是算符别是算符opop，第一运算对象，第一运算对象ARG1ARG1和第二运算对和第二运算对象象ARG2ARG2。运算对象可能是源程序中的变量，也。运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表可能是某个三元式的结果，用三元式的编号表示。示。例如例如 a

28、:=ba:=b* *c+bc+b* *d d的表示为：的表示为：（1 1）（）（* *， b b，c c）（2 2）（）（* *， b b，d d）（3 3）（）（+ + （1 1），）， （2 2）（4 4）（）（ （3 3），）， a a）三元式和树形表示三元式和树形表示例 : A + B * ( C - D ) + E / ( C - D ) N三元式：三元式：（1）（）（CD）（2）（）（*B（1）（3）（）（+A（2）（4）（）（CD）（5）（）（4）N）（6）（）（/E（5）（7）（）（+（3）（）（6）间接三元式：间接三元式： （1）(CD )（2）(*B(1) )（3）(+A

29、(2) )（4）( (1)N）（5）( /E (4) )（6）( +(3)(5) )间接码表间接码表（1）（2）（3）（1）（4）（5）（6）每生成一条指令，先检查已生成的间接三元式序列，若已有每生成一条指令，先检查已生成的间接三元式序列，若已有, ,不再不再生成生成, ,只把序号列入间接码表。间接码表明了间接三元式执行的顺序只把序号列入间接码表。间接码表明了间接三元式执行的顺序树形表示是三元式表示的翻版。树形表示是三元式表示的翻版。 例例:a =b:a =b* *c+bc+b* *d d可表可表示成下面的树表示：示成下面的树表示：A A1 12 2- -B B* *6 6+ +将赋值语句变换

30、为语法结构树将赋值语句变换为语法结构树n基本函数基本函数结点构造结点构造uMknode(op,left,right) Mknode(op,left,right) 建标记为建标记为opop的算符的算符结点结点, ,结点有两个域，分别为结点有两个域，分别为leftleft和和right.right.uMkleaf(id,entry) Mkleaf(id,entry) 建建标记为标记为idid的的叶结点，叶结点，有一个有一个entryentry域，它是指向符号表的入口。域，它是指向符号表的入口。uMkleaf(num,val)Mkleaf(num,val)建建标记为标记为idid的的叶结点叶结点,

31、,有一有一个个valval域，是表示该数的值。域，是表示该数的值。构造构造 a-4+c的语法树：的语法树： id指向c的入口id指向a 的入口num 4(1) p1:=mkleaf(id,entry a);(2) p2:=mkleaf(num, 4);(3) p3:=mknode(-，p1,p2)(4) p4:=mkleaf(id, entry c)(5) p5:=mknode(+,p3,p4)语法制导定义语法制导定义( (属性文法属性文法) )产产生生式式 语语义义规规则则 Sid:=E EE1+E2 EE1*E2 E -E1 E (E1) E id E num S.p:= mknode(:

32、=, mkleaf(id, id.entry), E.p) E.p:= mknode(+, E1.p, E2.p) E.p:= mknode(*, E1.p, E2.p) E.p:= mknode(-, 0, E1.p) E.p:= E1.p E.p:= mkleaf(id, id.entry) E.p:=mkleaf(num,num.val) E.p E.p 是语法结构树指针是语法结构树指针四元式和三元式的主要不同在于，四元式对中间结果的引四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的用必须通过给定的名字，而三元式是通过产生中间结果的三元

33、式编号。也就是说，三元式编号。也就是说，四元式之间的联系是通过临时变四元式之间的联系是通过临时变量实现的。量实现的。有时，为了更直观，也把四元式的形式写成简单赋值形式或有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把更易理解的形式。比如把a =b*c+b*d四元式序列写成：四元式序列写成： （1 1）t1=bt1=b* *c c（2 2）t2=bt2=b* *d d（3 3）t3=t1+t2t3=t1+t2（4 4）a=t3a=t3把（把（jumpjump，L L）写成）写成goto Lgoto L 把（把（jropjrop，B B，C C，L L）写成）写成if B

34、 rop C goto Lif B rop C goto L请将表达式请将表达式-(a+b)-(a+b)* *(c+d)-(a+b)(c+d)-(a+b)分别表示成三元式、分别表示成三元式、间接三元式和四元式序列。间接三元式和四元式序列。三元式三元式 (1) (+ a, b) (2) (+ c, d) (3) (* (1), (2) (4) (- (3), /)(5) (+ a, b)(6) (- (4), (5) 间接三元式间接三元式间接三元式序列间接三元式序列 间接码表间接码表(1) (+ a, b) (1)(2) (+ c, d) (2) (3) (* (1), (2) (3) (4)

35、(- (3), /) (4)(5) (- (4), (1) (1) (5)四元式四元式(1) (+, a, b, t1)(2) (+, c, d, t2)(3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5)(6) (-, t4, t5, t6) 简单的赋值语句的（四元式）翻译简单的赋值语句的（四元式）翻译四元式形式：四元式形式：t:=arg1 op arg2语义属性：语义属性： , E.place 函数：函数：lookup() 过程：过程：emit(t:=arg1 op arg2)（ 生成一条指令）生成一条

36、指令） newtemp ; (; (分配一个临时工作单元）分配一个临时工作单元）(1) Sid =E p =lookup（ idname）；）； if pnilthen Emit（p = Eplace） elseerror(2) EE1+E2 Eplace =newtemp； Emit（E.place = E1. place +E2place）(3) EE1*E2 E.placeE =newtemp； Emit（E.place = E1.place * E2. place）(4) EE1 E . Place = newtemp； Emit（EPlace := uminusE1place ）(5

37、) E（E1） EPlace = E1place(6) Eid p:=lookup（idname）；ifp nil thenEplaceE = pelseerror赋值语句的四元式翻译赋值语句的四元式翻译 实际上，在一个表达式中可能出现各种不同类型的变量，而不象前面假定为同一类型。因此，上例应改为P181 图8.13 的形式。8.3 8.3 布尔表达式的翻译布尔表达式的翻译程序设计语言中的布尔表达式有两个作用。一是计算逻辑值更多的情况是二:用做改变控制流语句中的条件表达式，如在if-then，if-then-else，或是while-do语句中那样。布尔表达式是由布尔算符and，or和not或

38、表示为（，和）施于布尔变量或关系表达式而成。约定优先顺序为, ,遵循左结合。布尔表达式有两个作用： 是计算逻辑值 用来改变控制流语句中的条件表达式。布尔表达式的翻译方法布尔表达式的翻译方法通常，计算布尔表达式的值有两种办法通常，计算布尔表达式的值有两种办法: :第一种办法，如同计算算术表达式一样，步步第一种办法，如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表计算出各部分的真假值，最后计算出整个表达式的值。达式的值。那么布尔表达式那么布尔表达式1 or1 or（not 0 and 0not 0 and 0）or 0or 0的计算过程是：的计算过程是： 1 or1 or（not

39、 0 and 0not 0 and 0）or 0or 01 or1 or（1 and 01 and 0）or 0or 01 or 0 or 01 or 0 or 01 or 01 or 01 1用数值用数值1 1表示表示truetrue，用，用0 0表示表示falsefalse。另一种计算方法是采取某种优化措施，只计另一种计算方法是采取某种优化措施，只计算部分表达式算部分表达式. .例如要计算例如要计算A or BA or B，若计算出，若计算出A A的值为的值为1 1，那，那么么B B的值就无需再计算了，因为不管的值就无需再计算了，因为不管B B的值为的值为何结果，何结果，A or BA o

40、r B的值都为的值都为1 1。如计算如计算A and B A and B 若若A A为假值为假值0 0，则无需计算，则无需计算B B，结果为结果为0 0。这种计算方法，意味着可以用这种计算方法，意味着可以用if if then- else then- else来解来解释释，和和即：即：把把A BA B解释成：解释成：if A then true else Bif A then true else B把把A BA B解释成：解释成：if A then B else fals.if A then B else fals.把把A A解释成：解释成：if A then false else truei

41、f A then false else true控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译现在讨论出现在现在讨论出现在 if thenif then；if then elseif then else和和while dowhile do等语句中的布尔表达式等语句中的布尔表达式E E的翻译。的翻译。 这三种语句的语法为：这三种语句的语法为： Sif E then S1Sif E then S1| |if E then S1 else if E then S1 else S2S2| |while E do S1while E do S1控制语句的代码结构控制语句的代码结构 (a) if E

42、 then S1E的代码的代码 . 。S1的代码的代码Jump outS2的代码的代码out(b)|if E then S1 else S2E 的代码的代码 . 。 S1 的代码的代码 真真假假beginE的代码的代码 . 。S1的代码的代码Jump begin(c)while E do S1对于对于E E为为 E1 or E2 E1 or E2 的形式：的形式：1 1、E1E1为真，则为真，则E E为真，即为真，即E E的真出口为的真出口为E1E1的真的真 出口。出口。2 2、E1E1为假，计算为假，计算E2E2，即，即E1E1的假出口应的假出口应 为为E2E2的第一个四元式标号，的第一个四

43、元式标号，E2E2的真、假出的真、假出 口与口与E E的真、假出口一样。的真、假出口一样。翻译的基本思路：翻译的基本思路：对于对于E E为为a rop b,a rop b,形成代码为：形成代码为：If a rop b goto E.true If a rop b goto E.true goto E.false goto E.false把条件转移的布尔表达式把条件转移的布尔表达式E E翻译成翻译成仅含仅含条件转移条件转移和和无条件转移无条件转移的四元式的四元式E： a rop bif a rop b goto E.true goto E.false如：如：ab or cd and ef可以翻成

44、如下四元可以翻成如下四元式：式：（1) if ab goto (2) goto （3）if cd goto (4) goto (5) if ef goto (6) gotoE.tue(3)(5)E.falseE.trueE.false我们使用我们使用E Etruetrue和和E Efalsefalse分别表示分别表示整个表达式整个表达式a ab or cb or cd and efd and ef的真、的真、假出口，而假出口，而E Etruetrue和和E Efalsefalse的值并的值并不能在产生四元式的同时就知道。为了不能在产生四元式的同时就知道。为了看清这一点，我们把该表达式放在条件看

45、清这一点，我们把该表达式放在条件语句中考虑，如语句语句中考虑，如语句 If ( aIf ( ab or cb or cd and ef )then Sd and ef )then S1 1 else Selse S2 2 的四元式序列见下页：的四元式序列见下页：（1）ifabgoto （2）goto（3）ifcdgoto（4）goto（5）ifefgoto（6）goto（7） （关于（关于S1的四元式）的四元式） （p）goto （p+1）（关于）（关于S2的四元式）的四元式） （q）If ( ab or cd and ef )then S1 else S2 的四元式序列为的四元式序列为（7）

46、（3）（5）(p+1)（q）（7）（p+1）语语句句 if ab or cd and ef then S1 else S2的的四四元元式式(1) if ab goto (7) (E.true ) (1)和和(5）(2) goto (3) 拉拉链链（真真）(3) if cd goto (5)(4) goto (p+1)(E.false)(4) 和和(6)(5) if ef goto (7)拉拉链链（假假）(6) goto (p+1)(7)( S1的的四四元元式式 (p-1) ）(p) goto (q)(p+1) (S2的的四四元元式式(q-1) ）(q)(1) if ab goto (E.tru

47、e )(2) goto (3) (3) if cd goto (5)(4) goto (E.false)(5) if ef goto (E.true ) (6) goto (E.false) (E.true)( S1的的四四元元式式序序列列 ）(p) goto (q)(E.false) (S2的的四四元元式式序序列列(q-1) ）使用拉链回填翻译控制语句中的布尔表达式 拉链： . L1: goto L; . L2: goto L; . L3: goto L; . L: . L2L10语义描述使用的量：语义描述使用的量： E.true “真真”链，链， E.false “假假”链链 E.code

48、begin E的第一个四元式的第一个四元式 nextstat 下一四元式地址下一四元式地址 过程：过程： emit( ) 输出一条四元式输出一条四元式 merge(p1,p2) 例：例： merge(p1,p2)(p100) goto 0 p1链链 (p10) goto p100(p1) goto p10(p200) goto 0 p2链链 (p20) goto p200(p2) goto p20 backpatch(p,t) 把把 p所链接的每个四元式的第四区所链接的每个四元式的第四区段都填为段都填为t。如：如：E1 or E2 E1有一个真出口，有一个真出口，E2也有一个真也有一个真 出口

49、，将出口，将两个链合并为一条链。两个链合并为一条链。p1布布尔尔表表达达式式的的一一种种翻翻译译方方案案： (1) EE1 or E2 backpatch(E1.false, E2.Codebegin); E.Codebegin:= E1.codebegin; E.true:=merge(E1.true, E2.true) E.false:= E2.false (2) EE1 and E2 backpatch(E1.true, E2.codebegin); E.Codebegin:= E1.codebegin; E.true:= E2.true; E.false:= merge(E1.fals

50、e, E2false); (3) Enot E1 E.true:= E1.false; E.Codebegin:= E1.codebegin; E.false:= E1.true (4) E(E1) E.true:= E1.true; E.Codebegin:= E1.codebegin; E.false:= E1.false (5) Eid1 rop id2 E.true:=nextstat; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emit(goto-) (6) E

51、id E.true:=nextstat; E.codebegin:=nextstat; E.false:=nextstat+1; emit(if id.place goto); emit(goto-) （7 7）E true E.true:=nextstat;E true E.true:=nextstat; E.codebegin:= nextstat; E.codebegin:= nextstat; emit( emit(gotogoto _) _) (8) E false E.false:=nextstat;(8) E false E.false:=nextstat; E.codebegi

52、n:= nextstat; E.codebegin:= nextstat; emit( emit(gotogoto _) 以表达式以表达式 ab or cf 为例，它的为例，它的四元式序列：四元式序列：100 ： if ab goto 101: goto 102： if cf goto 105: goto 将分析产生语法树时的语义动作结果将分析产生语法树时的语义动作结果“真真”“”“假假”链情况注释在相应结点处，见链情况注释在相应结点处，见P185 图图8.17E.true102104E.falseE.trueE.false控制语句的翻译控制语句的翻译条件转移条件转移考虑考虑if then，i

53、f then else和和while do语句，在图语句，在图8.12中已给出了中已给出了它们的代码结构。这里我们使用下面文法它们的代码结构。这里我们使用下面文法GS定义这些语句：定义这些语句：GS（1）Sif E then S（2）|if E then S else S（3）|while E do S（4）|begin L end（5）|A（6）LL；S（7）|S其中各非终结符号的意义是：其中各非终结符号的意义是：S-语句语句L-语句串语句串A-赋值句赋值句E-布尔表达式布尔表达式为了能使语义在程序置于每个产生式的最后，需对原文为了能使语义在程序置于每个产生式的最后，需对原文法的产生式拆分，

54、对法的产生式拆分，对G(S)进行拆分修改为进行拆分修改为G(S):(1) SCS1 (8) Cif E then(2) STpS2 (9) TpCS else(3) SWdS3 (10) Wd W E do(4) S begin L end (11) Wwhile(5) S A(6) S Ls S1 (12) Ls L; (7) L S(1) SCS1 S.Chain:=merge( C.Chain, S1 .Chain)(8) Cif E then backpatch (E.true, nextstat) C.chain:=E.false(9) TpCS1 else q:=nextstat

55、emit( goto _ ) backpatch(C.Chain, nextstat) Tp .Chain:=merge(S1.chain, q) (2) STpS2 S.chain:= merge(Tp .Chain , S2 .Chain)(11) Wwhile W.codebegin :=nextstat (10) Wd W E do backpatch(E.true, nextstat) Wd .chain:=E.false Wd .codebegin:= W.codebegin SWdS3 backpatch(S3 .chain, Wd .codebegin) emit( goto

56、Wd .codebegin) S.chain:= Wd .chain(4) S begin L end S.chain:= L.chain(5) S A S.chain:= 0 /*空链*/L S L.chain:=S.chain(12) Ls L; backpatch( L.chain, nextstat)(6) L Ls S1 L.chain:= S1 .chain 按照上述文法产生式相应的语义动作，加上前述关于赋值句和布尔按照上述文法产生式相应的语义动作，加上前述关于赋值句和布尔表达式的翻译法，语句表达式的翻译法，语句while （AB） do if （CD） then X =Y+Z将被

57、翻译成如下的一串四元式：将被翻译成如下的一串四元式：100if AB goto 101goto102ifCD goto 103goto 100104T =Y+Z105X =T106goto 100107 while （AB） do if （CD） then X =Y+Z102107104for循环语句循环语句for i =E1 step E2 until E3 do S1为了简单起见，假定为了简单起见，假定E2总是正的。在这种假定总是正的。在这种假定下，上述循环句的意义等价于：下，上述循环句的意义等价于：i =E1；goto OVER；AGAIN： i =i+E2；OVER： if iE3 t

58、henbegin S1； goto AGAIN end； 翻译见翻译见P191-P192开关语句开关语句开关语句（开关语句（case语句或语句或switch语句）语句）switch E ofcase V1：S1case V2：S2case Vn-1：Sn-1default：Snend如果分叉不太多，如果分叉不太多，case语句翻译成如下的一连串条件转移语句。语句翻译成如下的一连串条件转移语句。t =E；L1：if tV1 goto L2； S1；goto next；L2：if tV2 goto L3；S2goto next；Ln-1：if tVn-1 goto Ln；Sn-1；goto nex

59、t；Ln：Sn；next： 另一种方法另一种方法:P190 图图8.18 计算计算E值，并把结果放到临时变量值，并把结果放到临时变量t中中 goto testL1: S1的中间代码的中间代码 goto nextL2: S2的中间代码的中间代码 goto next Ln: Sn的中间代码的中间代码 goto nexttest: if t=v1 goto L1; if t=v2 goto L2; . if t=vn-1 goto Ln-1; goto Lnnext:gotogoto语句语句多数程序语言中的转移是通过标号和多数程序语言中的转移是通过标号和gotogoto语句实现语句实现的。带标号语句

60、的形式是的。带标号语句的形式是LSLS；gotogoto语句的形式是语句的形式是goto Lgoto L。当当LSLS；语句被处理之后，标号；语句被处理之后，标号L L是是 定义了定义了 的。即在的。即在符号表中，将登记符号表中，将登记L L的项的的项的 地址地址 栏中登上语句栏中登上语句S S的第一的第一个四元式的地址。个四元式的地址。如果如果goto Lgoto L是一个向上转移的语句，那么，当编译程序碰是一个向上转移的语句，那么，当编译程序碰到这个语句时，到这个语句时，L L必是已定义了的。通过对必是已定义了的。通过对L L查找符号表获查找符号表获得它的定义地址得它的定义地址p p，编译