第八章 语法制导翻译与中间代码生成

1、第第8章章 语法制导翻译和中间代码语法制导翻译和中间代码生成生成提纲：提纲： 属性文法属性文法 翻译模式翻译模式 中间代码中间代码 语句翻译语句翻译n语法制导翻译：语法制导翻译：n在语法分析的同时，完成相应的语义处理在语法分析的同时，完成相应的语义处理n语义分析的任务：语义分析的任务：n检查静态语义：类型、越界、维数、运算检查静态语义：类型、越界、维数、运算n翻译翻译(生成生成)中间中间(目标目标)代码：变量的存储分配、表代码：变量的存储分配、表达式的求值、语句的翻译达式的求值、语句的翻译8.1 属性文法属性文法n语义：语法成份的语义可以用文法符号的属性来表示，语义：语法成份的语义可以用文法符

2、号的属性来表示，通过属性的计算来完成翻译通过属性的计算来完成翻译n属性文法：在上下文无关文法的基础上，为每个文法属性文法：在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的符号（终结符或非终结符）配备若干相关的属性属性及一及一些附在产生式上的语义规则。些附在产生式上的语义规则。n属性代表与文法符号相关信息，如类型、值、代码属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等序列、符号表内容等n属性可以进行计算和传递属性可以进行计算和传递n语义规则语义规则：对于文法的每个产生式都配备了一组属：对于文法的每个产生式都配备了一组属性的计算规则性的计算规则l属性文法的

3、形式化定义：属性文法的形式化定义：l属性文法属性文法A是一个三元组是一个三元组:A=(G,V,F) lG:是一个上下文无关文法是一个上下文无关文法lV:有穷的属性集有穷的属性集lF:关于属性的语义规则关于属性的语义规则n属性的设定：属性的设定：n根据文法符号的语义，为文法符号设置属性根据文法符号的语义，为文法符号设置属性n例如：根据实际需要设置属性n表达式表达式E：E.type E.valn属性文法的例子：属性文法的例子：n文法文法 语义规则语义规则nEE1+E2 E.val := E1.val +E2.val E(E1) E.val := E1.val En E.val := n.lexl属

4、性文法的主要思想：属性文法的主要思想：l首先对每个文法符号引进相关的属性符号；首先对每个文法符号引进相关的属性符号；l其次对每个产生式写出属性值计算的规则。其次对每个产生式写出属性值计算的规则。l说明：说明：l属性有不同的类型，可以象变量一样地被赋值属性有不同的类型，可以象变量一样地被赋值.l例：例：E.val := E1.val +E2.vall赋值过程就是语义处理过程赋值过程就是语义处理过程.l例：例：在推导语法树的时候，诸属性的值被计算并通过在推导语法树的时候，诸属性的值被计算并通过赋值规则层层传递赋值规则层层传递.l语法推导树最后完成时，就得到开始符号的属性值语法推导树最后完成时，就得

5、到开始符号的属性值.也就是整个程序的语义也就是整个程序的语义.n属性的分类：属性的分类：n综合属性综合属性：“自下而上自下而上”传递信息传递信息n继承属性继承属性：“自上而下自上而下”传递信息传递信息l在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A 都有都有一套一套与之相关联的与之相关联的语义规则语义规则，每条规则的形式为：，每条规则的形式为：lb:=f(c1,c2,ck)l这里，这里，f是一个函数，是一个函数， c1,c2,ck是产生式文法符号或是产生式文法符号或A的属性的属性lb为为A的综合属性：的综合属性：l如果如果b是是A的一个的一个属性属性，并且，并且c1,c

6、2,ck是产生式右边是产生式右边文法符号的属性或者文法符号的属性或者A的其他属性。的其他属性。lb是文法符号是文法符号X的继承属性：的继承属性：l如果如果b是产生式右边某个文法符号是产生式右边某个文法符号X的一个的一个属性，属性，c1,c2,ck 是是A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。l两种情况下，属性两种情况下，属性b都依赖于属性都依赖于属性c1,c2,ck。l说明：说明：n终结符属性为综合属性，由词法分析器给出终结符属性为综合属性，由词法分析器给出n非终结符既可以有综合属性，也可以有继承属性非终结符既可以有综合属性，也可以有继承属性 产产 生生 式式 LEE

7、E1+T ETTT1*FTFF (E)Fdigit语语 义义 规规 则则print(E.val) 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.lexvalE、T、F的的Val属性是？属性是？综合属性综合属性例：简单算术表达式求值的语义描述（属性文法）例：简单算术表达式求值的语义描述（属性文法）产产 生生 式式 语语 义义 规规 则则 DTLL.in := T.type TintT.type := integer TrealT.type :=

8、 real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) T.type是综合属性是综合属性L.in是继承属性是继承属性例：说明语句中各种变量的类型信息的语义规则（属性文法）例：说明语句中各种变量的类型信息的语义规则（属性文法）n综合属性综合属性n在语法树中，一个结点的在语法树中，一个结点的综合属性综合属性的值由其的值由其子结点子结点的属性值确定。的属性值确定。n使用自底向上的方法在每一个结点处使用语义规则使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值计算综合属性的值3*5+4的的带语

9、义信息带语义信息的语法树的语法树 digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19L 产产 生生 式式 语语 义义 规规 则则 LE print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexvaln继承属

10、性继承属性n在语法树中，一个结点的在语法树中，一个结点的继承属性继承属性由此结点的由此结点的父结父结点和点和/或兄弟结点或兄弟结点的某些属性确定的某些属性确定句子句子real id1，id2，id3的的带语义信息带语义信息的语法树的语法树 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real产产 生生 式式 语语 义义 规规 则则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry,

11、 L.in) Lid addtype(id.entry, L.in) 8.2 语法制导翻译概论语法制导翻译概论n基于属性文法的处理方法基于属性文法的处理方法 n过程（一般情况）：过程（一般情况）：n对单词符号串进行语法分析，构造语法分析树对单词符号串进行语法分析，构造语法分析树n构造属性依赖图构造属性依赖图n获得语义规则的计算顺序获得语义规则的计算顺序n翻译结果（语义规则的计算）翻译结果（语义规则的计算）n产生代码n在符号表中存放信息n给出错误信息n执行任何其它动作n对输入符号串的对输入符号串的翻译翻译也就是根据语义规则进行也就是根据语义规则进行计算计算的结果。的结果。8.2.1 计算语义规则

12、计算语义规则n在一棵语法树中，结点的继承属性和综合属性之间的在一棵语法树中，结点的继承属性和综合属性之间的相互依赖关系可以由称作相互依赖关系可以由称作依赖图依赖图的一个有向图来描述的一个有向图来描述n为每一个包含过程调用的语义规则引入一个为每一个包含过程调用的语义规则引入一个虚综合属虚综合属性性b，这样把每一个语义规则都写成，这样把每一个语义规则都写成b:=f(c1,c2,ck)的形式的形式n依赖图中为每一个属性设置一个结点，如果属性依赖图中为每一个属性设置一个结点，如果属性b依赖依赖于属性于属性c，则从属性，则从属性c的结点有一条有向边连到属性的结点有一条有向边连到属性b的结点。的结点。 E

13、E1E2 E.val:=E1.val+E2.val E1+E2Evalvalval语义规则的计算次序语义规则的计算次序 n一个一个依赖图依赖图的任何的任何拓扑排序拓扑排序都给出一个语法树中结点都给出一个语法树中结点的语义规则计算的有效顺序的语义规则计算的有效顺序n基于属性文法的翻译是很精确的基于属性文法的翻译是很精确的n基础文法用于建立输入符号串的语法分析树基础文法用于建立输入符号串的语法分析树n根据语义规则建立依赖图根据语义规则建立依赖图n从依赖图的拓扑排序中，我们可以得到计算语义规从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序则的顺序 输入串输入串语法树语法树依赖图依赖图语义规则计算

14、次序语义规则计算次序属性计算属性计算n1）树遍历）树遍历n通过树遍历的方法计算属性的值通过树遍历的方法计算属性的值 n假设语法树已建立，且树中已带有开始符号的继承假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性属性和终结符的综合属性 n以某种次序遍历语法树，直至计算出所有属性以某种次序遍历语法树，直至计算出所有属性n深度优先，从左到右的遍历深度优先，从左到右的遍历 属性计算属性计算n2）一遍扫描的处理方法）一遍扫描的处理方法是在语法分析的同时计算属性是在语法分析的同时计算属性值值 n所采用的语法分析方法所采用的语法分析方法n属性的计算次序属性的计算次序8.2.2 S-属性文法

15、和自下而上翻译属性文法和自下而上翻译nS-属性文法属性文法：只含有综合属性：只含有综合属性nS属性文法适合于一遍扫描的属性文法适合于一遍扫描的自下而上自下而上分析分析n综合属性可以在分析输入符号串的同时由自下综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。而上的分析器来计算。n分析器可以保存与栈中文法符号有关的综合属分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。正在归约的产生式右边符号的属性值来计算。n在分析栈中使用一个附加的域来存放综合属性在分析栈中使用一个附加的域来

16、存放综合属性值值 n假设语义规则假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产是对应于产生式生式AXYZ的的 Sm Z.z Z Sm-1 Y.y Y Sm-2 X.x X S0 # TOP Sm-2 A.a A S0 # TOP 表达式文法的表达式文法的SLR（1）分析表）分析表ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5

17、:F (E) 6:Fi 产产 生生 式式 LEEE1+T ETTT1*FTFF (E)Fdigit语语 义义 规规 则则print(E.val) 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.lexvaln3*5+4的分析和值计算过程的分析和值计算过程n 输入输入 state sym val用到的产生式用到的产生式n 3*5+4# 0 # -n *5+4# 05#3 -n *5+4# 03 #F -3 Fdigitn *5+4# 02 #T

18、-3 TFn 5+4# 027#T* -3 -n +4# 0275 #T*5 -3 - -ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S11文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5:F (E) 6:Fin3*5+4的分析和值计算过程的分析和值计算过程输入输入 statesym val 用到的产生式用到的产生式+4# 0275 #T*5 -3 - -+4# 02710#T*F -3 - 5 FdigitACTIONGOTOi+*()#ETF

19、0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S11文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5:F (E) 6:Fin3*5+4的分析和值计算过程的分析和值计算过程输入输入 statesym val 用到的产生式用到的产生式+4# 0275 #T*5 -3 - -+4# 02710#T*F -3 - 5 Fdigit+4# 02 #T -15 TT*F+4# 01 #E -15 ET4# 016 #E+ -15- # 0165 #E+4 -15- 4ACTIONGOTOi+*()

20、#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S11文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5:F (E) 6:Fin3*5+4的分析和值计算过程的分析和值计算过程 输入输入 statesym val 用到的产生式用到的产生式 # 0165 #E+4 -15- - # 0163 #E+F -15- 4Fdigit # 0169 #E+T -15- 4TF # 01 #E -19 EE+T #L -19 LEACTIONGOTOi+*()#ETF0S5S41231S6acc

21、2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S11文法文法 0:LE 1: EE+T 2:ET 3:TT*F 4:TF 5:F (E) 6:Fi8.2.3 L-属性文法和自顶向下翻译属性文法和自顶向下翻译n一个属性文法称为一个属性文法称为L-L-属性文法属性文法，如果对于每个产，如果对于每个产生式生式AXAX1 1X X2 2X Xn n，其每个语义规则中的每个属性，其每个语义规则中的每个属性或者是综合属性，或者是或者是综合属性，或者是X Xj j(1(1 j j n)n)的一个继承属的一个继承属性且这个继承属性仅依赖于：性且这个继承

22、属性仅依赖于：(1)(1)产生式产生式X Xj j的左边符号的左边符号X X1 1，X X2 2，X Xj-1j-1的属性；的属性；(2)A(2)A的继承属性。的继承属性。nS-S-属性文法一定是属性文法一定是L-L-属性文法属性文法不是不是L-属性文法属性文法产产 生生 式式 语语 义义 规规 则则 ALM M.i :=m(L.s) AQR Q.i :=q(R.s) A.s :=f(Q.s) 例：将中缀表达式翻译成后缀表达式的属性文法例：将中缀表达式翻译成后缀表达式的属性文法nE-E addop T print(addop.lexeme)|TnT-num print(num.val)n其中，

23、其中，addop为为+或或-n是是L-属性文法属性文法n如果用如果用LR分析，很容易实现在语法分析时进行翻译分析，很容易实现在语法分析时进行翻译n例：将例：将2+3-5转换成中缀表达式转换成中缀表达式2Tprint 2E3Tprint +ETprint -E5print 5说明语义动作的语法树说明语义动作的语法树print 3例：将例：将2+3-5转换成中缀表达式转换成中缀表达式LR分析分析8.2.3 L-属性文法和自顶向下翻译属性文法和自顶向下翻译n对对L-属性文法进行自顶向下翻译属性文法进行自顶向下翻译nLL(1)文法适合自顶向下分析文法适合自顶向下分析nLL(1)文法不包含左递归文法不包

24、含左递归n文法：文法：nE-E addop T print(addop.lexeme)|TnT-num print(num.val)n此文法含有左递归此文法含有左递归n为了利用为了利用LL(1)方法分析，必须去除左递归方法分析，必须去除左递归 ETR Raddop T print(addop.lexeme) R1 | Tnum print(num.val) 例：例：9-5+2语义动作的语法树语义动作的语法树-ETR9print(9)TR5print(5)print(-)+T2print(2)Rprint(+) 改写后：改写后：E-E addop T print(addop.lexeme)|TT

25、-num print(num.val)这种语义处理的描述形这种语义处理的描述形式称为翻译模式式称为翻译模式8.2.3 L-属性文法和自顶向下翻译属性文法和自顶向下翻译n翻译模式翻译模式：是适合语法制导翻译的另一种描：是适合语法制导翻译的另一种描述形式，给出了使用语义规则进行计算的次述形式，给出了使用语义规则进行计算的次序序 n在翻译模式中，和文法符号相关的属性和语在翻译模式中，和文法符号相关的属性和语义规则用花括号义规则用花括号 括起来，插入到产生式右括起来，插入到产生式右部的合适位置上部的合适位置上设计翻译模式的原则设计翻译模式的原则n设计翻译模式时，必须保证当某个动作引用一设计翻译模式时，

26、必须保证当某个动作引用一个属性时它必须是有定义的。个属性时它必须是有定义的。nL-属性文法本身就能确保每个动作不会引用尚属性文法本身就能确保每个动作不会引用尚未计算出来的属性。未计算出来的属性。 当消除一个翻译模式的基本文法的左递归时同时考虑当消除一个翻译模式的基本文法的左递归时同时考虑属属性性 8.2.4 L-属性文法的自下而上的翻译属性文法的自下而上的翻译n方法：方法：n1）从翻译模式中去掉嵌入在产生式中间的动作，把所有的语）从翻译模式中去掉嵌入在产生式中间的动作，把所有的语义动作都放在产生式的末尾义动作都放在产生式的末尾n2）用综合属性代替继承属性）用综合属性代替继承属性n1）转换方法：

27、）转换方法：n加入新的产生式加入新的产生式M n把嵌入在产生式中的每个语义动作用不同的标记非终结符把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式代替，并把这个动作放在产生式M 的末尾的末尾 n翻译模式翻译模式 E TRR T print () R | T print () R | T num print (num.val)n转换为转换为 E TRR TMR | TNR | T num print (num.val)M print ()N print ()8.3 中间代码的形式中间代码的形式n中间代码：中间代码：是源程序的一种内部表示，复杂性介于源是源程序的一种

28、内部表示，复杂性介于源语言和目标机语言之间语言和目标机语言之间n中间代码的作用：中间代码的作用：n使编译程序的逻辑结构更加简单明确使编译程序的逻辑结构更加简单明确n利于进行与目标机无关的优化利于进行与目标机无关的优化n利于在不同目标机上实现同一种语言利于在不同目标机上实现同一种语言n中间代码的形式：中间代码的形式：n逆波兰式、四元式、三元式、树逆波兰式、四元式、三元式、树8.3.1 逆波兰式逆波兰式n逆波兰逆波兰表示法：一种表示表达式的方法，又称表示法：一种表示表达式的方法，又称后缀式后缀式表示法。表示法。n4+5*2-3n后缀式：后缀式：452*+3-n后缀式的计算后缀式的计算n要知道每个算

29、符的目数要知道每个算符的目数n用一个栈实现。用一个栈实现。n一般的计算过程是：自左至右扫描后缀式，每碰到一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到运算量就把它推进栈。每碰到k目运算符就把它作目运算符就把它作用于栈顶的用于栈顶的k个项，并用运算结果代替这个项，并用运算结果代替这k个项个项。8.3.1 逆波兰式逆波兰式n可将可将逆波兰表示扩充逆波兰表示扩充到表达式以外的范围到表达式以外的范围n例如：例如：n赋值语句赋值语句 a:=b*c+b*dn表示：表示：abc*bd*+:=n条件语句条件语句 if E then S1 else S2n表示：表示：ES1S2 n为三目

30、运算符为三目运算符8.3.2 三元式和树形表示三元式和树形表示n三元式三元式 n通过计算临时变量值的语句的位置来引用这个临时变通过计算临时变量值的语句的位置来引用这个临时变量量n三个域：三个域：op（运算符）、（运算符）、arg1(运算对象运算对象)和和arg2（运算对象）（运算对象）oparg1arg2(0)- c(1)*b(0)(2)- c(3)*b(2)(4)+(1)(3)(5)：= a(4)例如：例如：a:=b*(-c)+b*(-c)n例如，语句例如，语句X:=(A+B)*C;Y:=D(A+B)的三元式表示如下表所示。的三元式表示如下表所示。 三元式表示三元式表示 OP ARG1 AR

31、G2 (1) + A B (2) * (1) C (3) := X (2) (4) D (1) (5) := Y (4) 三元式也可以表示成树三元式也可以表示成树：=a+*b-c*b-c例如例如 a:=b*(-c)+b*(-c)的树表示法的树表示法8.3.3 四元式四元式n四元式四元式(普遍采用的中间代码形式普遍采用的中间代码形式)n一个带有四个域的记录结构，这四个域分别称为一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及及resultoparg1arg2result(0)- cT1(1)*bT1T2(2)- cT3(3)*bT3T4(4)+T2T4T5(5):=T5a

32、 例如：例如：a:=b*(-c)+b*(-c)8.3.3 四元式四元式n为了更直观，也把四元式的形式写成简单赋值形式为了更直观，也把四元式的形式写成简单赋值形式n(1)T1:=-cn(2)T2:=b*T1n(3) T3:=-cn(4)T4:=b*T3n(5)T5:=T2+T4n(6)a:=T5把（把（jump,-,-,L）写成）写成goto L把把(jrop,B,C,L)写成写成if B rop C goto L例如：例如：a:=b*(-c)+b*(-c)8.4 简单赋值语句的翻译简单赋值语句的翻译n在上面的四元式中，使用变量名字本身表示运算对象在上面的四元式中，使用变量名字本身表示运算对象n

33、在实际实现中，它们是在实际实现中，它们是n指针：指向符号表的某一登陆项指针：指向符号表的某一登陆项n或临时变量的整数码或临时变量的整数码n翻译的一般要求：翻译的一般要求：n充分了解各种语法成分的语义充分了解各种语法成分的语义n目标语言的语义目标语言的语义简单赋值语句的翻译：翻译成四元式简单赋值语句的翻译：翻译成四元式n下面为翻译中用到的信息：下面为翻译中用到的信息：n语义属性：语义属性： nE.place：存储位置或整数码：存储位置或整数码nlookup() ：子程序，在符号表中查找：子程序，在符号表中查找nemit(t:=arg1 op arg2)：子程序，生成

34、四元式：子程序，生成四元式nnewtemp：产生新的临时变量：产生新的临时变量产生赋值语句的四元式翻译模式产生赋值语句的四元式翻译模式 Sid:=E p:=lookup(); if p nil thenemit(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)产生赋值语句的四元式翻译模式（续）产生赋值语句的四元式翻译模式（续）E-E1

35、 E.place:=newtemp; emit(E.place:= -E 1.place)E(E1) E.place:=E1.placeEid p:=lookup(); if p nil then E.place:=p else error 例如：将例如：将x:=y+i*j翻译成四元式翻译成四元式Sid:=E p:=lookup(); if p nil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place)EE1*E2 E.pla

36、ce:=newtemp; emit(E.place := E 1.place * E 2.place)E-E1 E.place:=newtemp; emit(E.place:=-E 1.place)E(E1) E.place:=E1.placeEid p:=lookup(); if p nil then E.place:=p else error 在翻译中有时需要类型转换在翻译中有时需要类型转换用用E.type表示非终结符表示非终结符E的类型属性的类型属性 n假设只有整型和实型，对应产生式假设只有整型和实型，对应产生式EE1 op E2的语义动作的语义动作中关于中关于E.type

37、的语义规则可定义为：的语义规则可定义为： if E1.type=integer and E2.type=integer E.type:=integer else E.type:=real n算符区分为整型算符算符区分为整型算符int op和实型算符和实型算符real opnx:=yi*j 其中其中x、y为实型；为实型；i、j为整型。这个赋值句产生的四元为整型。这个赋值句产生的四元式代码（简写）为：式代码（简写）为： T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2关于产生式关于产生式EE1 E2 的语义动作的语义动作 E.place:=new

38、temp; if E1.type=integer and E2.type=integer then begin emit (E.place := E 1.place int+ E 2.place); E.type:=integer end else if E1.type=real and E2.type=real then begin emit (E.place := E 1.place real+ E 2.place); E.type:=real endelse if E1.type=integer and E2.type=real then beginu:=newtemp;emit (u

39、:= inttoreal E 1.place);emit (E.place := u real+ E 2.palce);E.type:=realendelse if E1.type=real and E1.type=integer then beginu:=newtemp;emit (u := inttoreal E 2.place);emit (E.place := E 1.place real+ u);E.type:=realend else E.type:=type_error8.5 布尔表达式的翻译布尔表达式的翻译布尔表达式的两个基本作用布尔表达式的两个基本作用:n计算逻辑值：计算逻辑

40、值：a&b|c (C语言语言)n控制语句的条件表达式：控制语句的条件表达式： (C语言语言)nif (a5) t-;n产生布尔表达式的文法产生布尔表达式的文法nEE or E | E and E | not E|(E) | i rop i | true|falsen约定布尔算符的优先顺序从高到低为约定布尔算符的优先顺序从高到低为not,and,or，并且，并且and和和or服从左结合服从左结合8.5.1 布尔表达式的翻译方法布尔表达式的翻译方法n通常计算布尔表达式的值有两种方法通常计算布尔表达式的值有两种方法:1. 如同计算算术表达式一样，一步步算（计算值）如同计算算术表达式一样，一步

41、步算（计算值） 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =12. 采用某种优化措施（控制语句中的条件表达式）采用某种优化措施（控制语句中的条件表达式） 计算计算A or B，若，若A为为1，可以不计算，可以不计算B 8.5.1 布尔表达式的翻译方法布尔表达式的翻译方法n若按第一种办法计算布尔表达式，则若按第一种办法计算布尔表达式，则a or b and not c 翻译成的四元式序列翻译成的四元式序列为：为：（1）t1:=not c（2）t2:=b and t1（3）t3:=a or t2n对于关系表达

42、式对于关系表达式ab可看成等价的条件语句可看成等价的条件语句nif ab then 1 else 0 n翻译成的四元式序列为：翻译成的四元式序列为：n（1）if ab goto （4） （2）t:=0（3）goto （5）（4）t:=1（5）关于布尔表达式的翻译模式关于布尔表达式的翻译模式n过程过程emit生成四元式生成四元式nnextstat给出输出序列中下一个四元式的地址给出输出序列中下一个四元式的地址na or b and not c 翻译成的四元式序列为：翻译成的四元式序列为：（1）t1:=not c 生成四元式（生成四元式（1）之后，）之后，nextstat的值为的值为2（2）t2:

43、=b and t1（3）t3:=a or t2n每产生一个四元式后，过程每产生一个四元式后，过程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

44、Eid1 rop id2 E.place:=newtemp; emit(if id1.place rop id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Etrue E.place:=newtemp;E.place=1; Efalse E.place:=newtemp;E.place=0; 对于关系表达式对于关系表达式ab可看成等价的条件语句可看成等价的条件语句if ab then 1 else 0 翻译成的四元式序列为：翻译成的四元式序列为： （1）if ab

45、goto （4） （2）t:=0（3）goto （5）（4） t:=1（5）产生布尔表达式的文法产生布尔表达式的文法EE or E | E and E | not E|(E) | i rop i | true|false 约定布尔算符的优先顺序从高到低为约定布尔算符的优先顺序从高到低为not,and,or，并且，并且and和和or服从左结合服从左结合给出布尔表达式给出布尔表达式ab or cd and ef的语法树（的语法树（根据算符优先根据算符优先关系，采用自下向上分析关系，采用自下向上分析）abEcdEefEandEorE布尔表达式布尔表达式ab or cd and ef的翻译结果的翻译结

46、果（假设（假设nextstat从从0开始）开始）0: if ab goto 31: T1:=02: goto 43: T1:=14: if cd goto 75: T2:=06: goto 87: T2:=18: if ef goto 119: T3:=010: goto 1211: T3:=112: T4:=T2 and T313: T5:=T1 or T4EE1 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

47、and E2.place)Enot E1 E.place:=newtemp; emit(E.place := not E 1.place)E(E1) E.place:=E1.placeEid1 rop id2 E.place:=newtemp;emit(if id1.place rop id2. place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place:= 1) Etrue E.place:=newtemp;E.place=1; Efalse E.place:=newtemp;E.place=

48、0; abEcdEeif E then S1| if E then S1 else S2|while E do S1 S-if E then S1| if E then S1 else S2|while E do S1 这些语句的代码结构示意图：这些语句的代码结构示意图：E的代码的代码S1的代码的代码真真假假E的代码的代码S1的代码的代码真真假假S2的代码的代码goto outout：begin：E的代码的代码S1的代码的代码真真假假goto begin8.5.2 控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译n布尔表达式布尔表达式E有两个出口：真出口和假出口有两个出口：真出口和假出口n

49、E.true是是E为为真真时控制流转向的标号时控制流转向的标号nE.false是是E为为假假时控制流转向的标号时控制流转向的标号n当当E为为a rop b（E-a rop b）作为条件转移时，仅把）作为条件转移时，仅把E翻译成两条代码：条件转和无条件转翻译成两条代码：条件转和无条件转n代码为代码为nif a rop b goto E.true ngoto E.false8.5.2 控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译n对于对于E为为E1 or E2的形式的形式n若若E1为真，则可知道为真，则可知道E为真为真nE1的真出口与的真出口与E的真出口一样的真出口一样n若若E1为假，则必

50、须计算为假，则必须计算E2nE1的假出口是的假出口是E2的第一个四元式标号的第一个四元式标号nE2的真出口和假出口与的真出口和假出口与E的真出口和假出口一样的真出口和假出口一样n对于对于E为为E1and E2的形式的形式n若若E1为假，则可知道为假，则可知道E为假为假nE1的假出口与的假出口与E的假出口一样的假出口一样n若若E1为真，则必须计算为真，则必须计算E2nE1的真出口是的真出口是E2的第一个四元式标号的第一个四元式标号nE2的真出口和假出口与的真出口和假出口与E的真出口和假出口一样的真出口和假出口一样8.5.2 控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译n例如：布尔表达式例如：布尔表达式ab or cf的翻译的翻译n(1) if ab goto E.truen(2) goto 3n(3) if cf goto E.truen(6) goto E.false注意：注意：E.true与与E.false的值有时不能在产生四元式的同时知道的值有时不能在产生四元式的同时知道语语句句 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.fals