语法制导翻译和中间代码生成 (2)精.ppt

《语法制导翻译和中间代码生成 (2)精.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码生成 (2)精.ppt（97页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、语法制导翻译和中间语法制导翻译和中间代码生成代码生成第1页，本讲稿共97页在编译程序中使用了这样的一种技术，在编译程序中使用了这样的一种技术，就是在语法分析的同时进行语义分析的就是在语法分析的同时进行语义分析的工作，并同步地完成相应语句的翻译。工作，并同步地完成相应语句的翻译。这种技术就称为语法制导翻译。这种技术就称为语法制导翻译。第2页，本讲稿共97页第第5章教学内容章教学内容属性文法的概念属性文法的概念；语法制导翻译的概念；语法制导翻译的概念；常用的中间代码形式常用的中间代码形式；程程序序设设计计语语言言的的语语法法结结构构的的自自底底向向上上的的语法制导翻译方法。语法制导翻译方法。第3页

2、，本讲稿共97页一、属性文法一、属性文法属性文法是在上下文无关文法的基础上为每个文法属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的符号（终结符或非终结符）配备若干个相关的“值值”（称为属性）。这些属性代表与文法符号相关（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列的信息，例如它的类型、值、代码序列、符号表、符号表内容等等。属性和变量一样，可以进行计算和传递。内容等等。属性和变量一样，可以进行计算和传递。属性一般分为两类：综合属性和继承属性。简单属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于的说，综合属性用于“自下而

3、上自下而上”传递信息，而继传递信息，而继承属性用于承属性用于“自上而下自上而下”传递信息。传递信息。第4页，本讲稿共97页属性加工的过程即是语义处理的过程，对于文法属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，的每一个产生式都配备了一组属性的计算规则，则称为语义规则。则称为语义规则。在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A A都有一套都有一套与之相关联的语义规则，每条语义规则的形式为：与之相关联的语义规则，每条语义规则的形式为：b:=f(c1,c2,b:=f(c1,c2,ck),ck)这里这里f f是一个函数，而且或者是一个函

4、数，而且或者（1 1）b b是是A A的一个综合属性并且的一个综合属性并且c1,c2,c1,c2,ckck是产生式是产生式右边文法符号的属性；或者右边文法符号的属性；或者（2 2）b b是产生式右边某个文法符号的一个继承属性并且是产生式右边某个文法符号的一个继承属性并且c1,c2,c1,c2,ckck是是A A或产生式右边任何文法符号的属或产生式右边任何文法符号的属性。性。在这两种情况下，属性在这两种情况下，属性b b依赖于属性依赖于属性c1,c2c1,c2,ck,ck。第5页，本讲稿共97页要特别强掉的是：要特别强掉的是：终结符只有综合属性，它由词法分析器提供；终结符只有综合属性，它由词法分

5、析器提供；非终结符既可以有综合属性也可以有继承属非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性性，文法开始符号的所有继承属性作为属性计算前的初始值。计算前的初始值。第6页，本讲稿共97页一般来讲，对出现在产生式右边的继承一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属中只能使用相应产生式的文法符号的属性，这有利于产生式范围内性，这有利于产生式范围内“封装封装”属属性的依赖性。然而，出现在产生式左边性的依赖性。然

6、而，出现在产生式左边的继承属性和出现在产生式右边的综合的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规进行计算，它们由其它产生式的属性规则计算则计算,由属性计算器的参数提供。由属性计算器的参数提供。第7页，本讲稿共97页语义规则所描述的工作可以包括属性计语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函产生代码），也可能不是变元的严格函数（如某个规则给出可

7、用的下一个数据数（如某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写单元的地址）。这样的语义规则通常写成过程调用，或过程段。成过程调用，或过程段。第8页，本讲稿共97页综合属性综合属性在语法树中，一个结点的综合属性的值在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称用综合属性的属性文法称S S属性文法。属性文法。第9页，本讲稿共97页继承属性继承属性在语法树中，一个结点的

8、继承属性由此在语法树中，一个结点的继承属性由此结点的父结点和结点的父结点和/或兄弟结点的某些属性或兄弟结点的某些属性确定。用继承属性来表示程序语言结构确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。中的上下文依赖关系很方便。第10页，本讲稿共97页属性文法的定义属性文法的定义【定定义义】一一个个属属性性文文法法AG是是一一个个四四元元组组，即即AG=(G,A,R,B)，其中，其中G=(N,T,S,P)是一个前后文无关文法；是一个前后文无关文法；A=X NT A(X)是一个属性的有限集合；是一个属性的有限集合；R=p P R(p)是是一一个个语语义义规规则则式式的的有有限限集合；集合

9、；B=p P B(p)是一个条件的有限集合；是一个条件的有限集合；第11页，本讲稿共97页属性文法的定义属性文法的定义并且并且满满足以下两个条件：足以下两个条件：1对对任任意意两两个个符符号号的的X和和Y，若若XY，则则A(X)A(Y)=；2对对于于任任何何在在L(G)的的句句子子所所对对应应的的语语法法树树上上出出现现的的符符号号X，X的的任任意意一一个个属属性性X.a的的计计算算，至至多多只只有有一一条条语语义义规规则则式可以式可以应应用。用。第12页，本讲稿共97页属性文法示例属性文法示例【例例51】简单简单台式台式计计算器的算算器的算术术表达式的属性文法：表达式的属性文法：产产生式集生

10、式集G:语义规则语义规则式集式集R:L E print(E.val)E E1+T E.val=E1.val+T.valE T E.val=T.valT T1*F T.val=T1.val F.valT F T.val=F.valF (E)F.val=E.valF digit F.val=digit.lexval 第13页，本讲稿共97页示例示例 在在该该描描述述中中，每每个个非非终终结结符符都都有有一一个个属属性性：一一个个整整数数值值的的称称作作valval的的属属性性。按按照照语语义义规规则则对对每每个个产产生生式式来来说说，它它的的左左部部E E，T T，F F的的属属性性值值的的计计算

11、算来来自自它它右右部部的的非非终终结结符符，这这种种属属性性称称作作综综合合属属性性。单单词词digitdigit仅仅有有综综合合属属性性，它它的的值值是是由由词词法法分分析析程程序序提提供供的的。和和产产生生式式L L E E相相联联的的语语义义规规则则是是一一个个过过程程，打打印印由由E E产产生生的的表表达达式式的的值值。我我们们可可以以理理解解为为L L的的属属性是空的或是虚的。性是空的或是虚的。第14页，本讲稿共97页设表达式为设表达式为3*5+4，则语义动作打印数值，则语义动作打印数值19LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F

12、.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树第15页，本讲稿共97页 LR分分析析器器可可以以改改造造为为一一个个翻翻译译器器，在在对对输输入入串串进进行行语语法法分分析析的的同同时时对对属属性性进行计算。进行计算。LR分析器增加语义栈。分析器增加语义栈。#X1 1Xm mI0 0I1 1Im m 语义栈语义栈-X1 1.VALXm m .VAL第16页，本讲稿共97页SLR(1)SLR(1)分析表分析表digit+*()ETF0s5s41231s6acc2r2s7r2r23r4r4

13、r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5状态ACTIONGOTO第17页，本讲稿共97页步骤步骤分析栈分析栈 栈顶状态栈顶状态,输入符输入符剩余输入串剩余输入串 10#-Action0,2=S5移进移进22+3*5*5#20 5#2-Action5,+=r6用用F digit归约，执行语义动归约，执行语义动作作F.val=2+3*5*5#30 3#F-2Action3,+=r4用用T F 归约，执行语义动作归约，执行语义动作T.val=F.val+3*5*5#LRLR分分析析：增增加加语语义义栈

14、栈 归归约约时时进进行行语语义义动动作作。给给出出*的分析和计值过程。的分析和计值过程。第18页，本讲稿共97页步骤步骤分析栈分析栈 栈顶状态栈顶状态,输入符输入符剩余输入串剩余输入串 40 2#T-2Action2,+=r2用用E T归约，执行语义动作归约，执行语义动作E.val=T.val +3*5*5#50 1#E-2Action1,+=S6移进移进+3*5*5#60 1 6#E+-2 -Action6,3=S5移进移进33*5*5#第19页，本讲稿共97页70 1 6 5#E+3-2 -Action5,*=r6用用F digit归约，执行语义动归约，执行语义动作作F.val=3 *5

15、5#80 1 6 3#E+F-2-3Action3,*=r4用用T F 归约，执行语义动作归约，执行语义动作T.val=F.val *5 5#90 1 6 9#E+T-2-3Action9,*=S7移进移进*5 5#100 1 6 9 7#E+T*-2-3-Action7,5=S5移进移进5 5 5#第20页，本讲稿共97页110 1 6 9 7 5#E+T*5*5-2-3-Action5,#=r6用用F digit归约归约,执行语义动作执行语义动作F.val=5#120 1 6 9 7 10#E+T*F*F-2-3 -5Action10,#=r3用用T T*F归约归约,执行语义动作执行语义动

16、作T.val=T.val F.val3515#130 1 6 9#E+T-2-15Action9,#=r1用用E E+T 归约归约,执行语义动作执行语义动作E.val=E.val T.val21517#140 1#E-17Action1,#=acc成功接收成功接收输入串输入串#第21页，本讲稿共97页二二.语义分析的任务语义分析的任务 编编译译程程序序的的任任务务是是把把源源程程序序翻翻译译成成目目标标程程序序，这这个个目目标标程程序序必必须须和和源源程程序序的的语语义义等等同同，也也就就是是说说，尽尽管管它它们们的的语语法法结结构构完完全全不不同同，但但它它们们所所表表达达的的结结果果应应完

17、完全全相相同同。通通常常，在在词词法法分分析析程程序序和和语语法法分分析析程程序序对对源源程程序序的的语语法法结结构构进进行行分分析析之之后后，要要么么由由语语法法分分析析程程序序直直接接调调用用相相应应的的语语义义子子程程序序进进行行语语义义处处理理，要要么么首首先先生生成成语语法法树树或或该该结构的某种表示，再进行语义处理。结构的某种表示，再进行语义处理。第22页，本讲稿共97页编译中的语义处理是指两个功能：编译中的语义处理是指两个功能：审查每个语法结构的静态语义，即验证审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。语法结构合法的程序是否真正有意义。有时把这个工作称为

18、静态语义分析或静有时把这个工作称为静态语义分析或静态审查。态审查。如果静态语义正确，语义处理则要执行如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种真正的翻译，即，要么生成程序的一种中间表示形式（中间代码），要么生成中间表示形式（中间代码），要么生成实际的目标代码。实际的目标代码。第23页，本讲稿共97页通常包括：通常包括：类型检查。类型检查。控控制制流流检检查查。控控制制流流语语句句必必须须使使控控制制转转移移到到合合法法的的地地方方。例例如如，在在C C语语言言中中breakbreak语语句句使使控控制制跳跳离离包包括括该该语语句句的的最最小小whilewhile、fo

19、rfor或或switchswitch语语句句。如如果果不不存存在在包包括括它它的的语语句句，则则报错。报错。一致性检查。在很多场合要求对象只能被定义一次。例一致性检查。在很多场合要求对象只能被定义一次。例如如PascalPascal语言规定同一标识符在一个分程序中只能被说明语言规定同一标识符在一个分程序中只能被说明一次，同一一次，同一casecase语句的标号不能相同，枚举类型的元素不语句的标号不能相同，枚举类型的元素不能重复出现等等。能重复出现等等。相关名字检查。有时，同一名字必须出现两次或多次。相关名字检查。有时，同一名字必须出现两次或多次。例如，例如，AdaAda语言程序中，循环或程序块

20、可以有一个名字，出现语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。名字是相同的。名字的作用域分析。名字的作用域分析。第24页，本讲稿共97页三、中间代码三、中间代码翻译为中间语言的好处：翻译为中间语言的好处：（1 1）便于进行与机器无关的代码优化；）便于进行与机器无关的代码优化；（2 2）使编译程序改变目标机更容易；）使编译程序改变目标机更容易；（3 3）使编译程序的结构在逻辑上更为简单明确，）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清以

21、中间语言为界面，编译前端和后端的接口更清晰。晰。编译程序所使用的中间代码有多种形式。常见的编译程序所使用的中间代码有多种形式。常见的有逆波兰式、三元式和树形、四元式表示。有逆波兰式、三元式和树形、四元式表示。第25页，本讲稿共97页1.逆波兰式逆波兰式逆波兰式是最简单的一种中间代码表示逆波兰式是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。卡西维奇发明的。这种表示法将运算对象写在前面，把运这种表示法将运算对象写在前面，把运算符号写在后面，比如把算符号写在后面，比如把

22、a+b写成写成ab+，把把a*b写成写成ab*，用这种表示法表示的表，用这种表示法表示的表达式也称做后缀式。达式也称做后缀式。第26页，本讲稿共97页示例示例中缀算术表达式中缀算术表达式逆波兰式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+d*e abc*de*+=a=b*(c+b)*d/eabcb+*d*e/=第27页，本讲稿共97页后缀表示法表示表达式，其最大的优点是易于计算机后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。常用的算法是使用一个栈，自左至右扫处理表达式。常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就描

23、算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。栈，最后的结果留在栈顶。由于后缀式表示上的简洁和计值的方便，特别适用由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具于解释执

24、行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。有堆栈体系的计算机的目标代码生成。第28页，本讲稿共97页2.三元式和树形表示三元式和树形表示另一类中间代码形式是三元式。把表达式及各种语句另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式。表示成一组三元式。每个三元式由三个部分组成，分别是：每个三元式由三个部分组成，分别是：(算符算符op，第一运算对象，第一运算对象ARG1，第二运算对象，第二运算对象ARG2)运算对象可能是源程序中的变量，也可能是某个三运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。元式的结果，用三元式的编号表示。

25、对于一目算符对于一目算符op，只需选用一个运算对象，不妨规定只，只需选用一个运算对象，不妨规定只用用ARG1。至于多目算符，可用若干个相继的三元式表示。至于多目算符，可用若干个相继的三元式表示。第29页，本讲稿共97页示例示例【例如例如】a=b*c+d*e的三元式表示为：的三元式表示为：（1）（）（*，b ，c ）（2）（）（*，d ，e ）（3）（）（+，（，（1），（2）（4）（）（，（，（3），），a ）第30页，本讲稿共97页树形表示树形表示树形表示是树形表示是三元式表示三元式表示的翻版。的翻版。b c*+a d e=第31页，本讲稿共97页3.3.四元式四元式四元式是一种比较普遍采用

26、的中间代码四元式是一种比较普遍采用的中间代码形式。形式。四元式的四个组成成分是：四元式的四个组成成分是：算符算符opop第一运算对象第一运算对象ARG1ARG1第二运算对象第二运算对象ARG2ARG2运算结果运算结果RESULTRESULT运算对象和运算结果有时指用户自己定运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时义的变量，有时指编译程序引进的临时变量。变量。第32页，本讲稿共97页示例示例四元式形式四元式形式：(op,arg1,arg2,result)【例如例如】a=b*c+d*e的四元式为的四元式为：（1）（）（*，b，c，T1）（2）（）（*，d，e，T2）（3

27、）（）（+，T1，T2，T3）（4）（）（=，T3，a）第33页，本讲稿共97页四四元元式式表表示示很很类类似似于于三三地地址址指指令令，确确实实，有有时时把把这这类类中中间间表表示示称称为为“三三地地址址代代码码”，因因为为这这种种表表示示可可看看作作一一种种虚虚拟拟三三地地址址机机的的通通用用汇汇编编码码，即即这这种种虚虚拟拟机机的的每每条条“指指令令”包包含含操操作作符符和和三三个个地地址址，两两个个是是为为运运算算对对象象的的，一一个个是是为为结结果果的的。这这种种表表示示对对于于代代码码优优化化和和目目标标代代码生成都较有利码生成都较有利。第34页，本讲稿共97页示例示例为为了了更更

28、直直观观，也也把把四四元元式式的的形形式式写写成成简简单单赋赋值值形形式或更易理解的形式：式或更易理解的形式：resultarg1 op arg2【例如例如】把上述四元式序列写成：把上述四元式序列写成：（1 1）t t1 1=b*c=b*c （2 2）t t2 2=b*d=b*d（3 3）t t3 3=t=t1 1+t+t2 2（4 4）a=ta=t3 3（jumpjump，L L）写成）写成goto Lgoto L（jropjrop，B B，C C，L L）写成）写成if B rop C goto Lif B rop C goto L第35页，本讲稿共97页例如例如:A+B*(C-D)+E/

29、(C-D)N第36页，本讲稿共97页四、简单赋值语句的翻译四、简单赋值语句的翻译语义过程语义过程GEN表示产生一个四元式，并表示产生一个四元式，并且填入四元式表中。且填入四元式表中。语义过程语义过程Newtemp表示生成一个临时变表示生成一个临时变量，每调用一次，生成一新的临时变量。量，每调用一次，生成一新的临时变量。语义变量语义变量Eplace，表示存放，表示存放E值的变量值的变量名在符号表的登录项或一整数码（若此名在符号表的登录项或一整数码（若此变量是一个临时变量）。变量是一个临时变量）。语义变量语义变量Entry(id)回送标识符回送标识符id在符号表在符号表中的入口地址。中的入口地址。

30、第37页，本讲稿共97页简单简单赋值语句的赋值语句的属性文法属性文法 产生式产生式 语义规则语义规则 Sid=E GEN（=，E.Place，_，Entry(id)）EE1+E2 E.place=Newtemp；GEN(+,E1.place,E2.place,E.place)EE1*E2 Eplace=Newtemp；GEN(*,E1.place,E2.place,E.Place)EE1 E.place=Newtemp；GEN(,E1.place,_,E.place)E（E1）E.place=E1.place Eid E.place=Entry(id)第38页，本讲稿共97页a=b*c+d*e

31、的翻译过程的翻译过程a =b *c +d *e E(c)EE(b)E(d)E(e)T11.(*,b,c,T1)ET22.(*,d,e,T2)ET33.(+,T1,T2,T3)S4.(=,T3,_,a)第39页，本讲稿共97页（1）（）（*，b，c，T1）（2）（）（*，d，e，T2）（3）（）（+，T1，T2，T3）（4）（）（=，T3，_，a ）a=b*c+d*e的翻译结果的翻译结果第40页，本讲稿共97页a=-b*(c+d)的翻译过程的翻译过程略。略。第41页，本讲稿共97页类型转换的语义处理类型转换的语义处理实际上，在一个表达式中可能会出现各种不同类实际上，在一个表达式中可能会出现各种不

32、同类型的变量或常数。即编译程序还应执行这样的语型的变量或常数。即编译程序还应执行这样的语义动作：对表达式中的运算对象应进行类型检查，义动作：对表达式中的运算对象应进行类型检查，如不能接受不同类型的运算对象的混合运算，则如不能接受不同类型的运算对象的混合运算，则应指出错误；如能接受混合运算，则应进行类型应指出错误；如能接受混合运算，则应进行类型转换的语义处理。转换的语义处理。例如，算术表达式可以进行实型量与整型量的混例如，算术表达式可以进行实型量与整型量的混合运算，并且约定，当两个不同类型的量进行运合运算，并且约定，当两个不同类型的量进行运算时，必须首先将整型量转换为实型量。算时，必须首先将整型

33、量转换为实型量。第42页，本讲稿共97页语义变量语义变量语义变量语义变量Etype表示表示E的类型信息；的类型信息；为区别整型加（乘）和实型加（乘），为区别整型加（乘）和实型加（乘），把把+（*）分别写作）分别写作+i（*i）和）和+r（*r）。）。用一目算符用一目算符itr表示将整型运算对象转换表示将整型运算对象转换成实型。成实型。第43页，本讲稿共97页示例示例产生式：产生式：EE1*E2语义动作：语义动作：Eplace=Newtemp；if E1.type=int AND E2.typeint GEN（*i，E1.place，E2.place，E.place,）；）；Etype=int

34、else if E1.type=real AND E2.type=real GEN(*r,E1place,E2place,E.place);E.type=real 第44页，本讲稿共97页示例示例else if E1.typeint/*and E2.type=real*/t=Newtemp；GEN（itr，E1.place，_，t）；）；GEN（*r，t，E2.place，E.place,）E.type=real else/*E1typereal and E2typeint*/t=Newtemp；GEN（itr，E2.place，_，t）；）；GEN（*r，E1.place，t，E.place

35、,）Etype=real 第45页，本讲稿共97页五、布尔表达式的翻译五、布尔表达式的翻译程序设计语言中的布尔表达式有两个作程序设计语言中的布尔表达式有两个作用。用。一是计算逻辑值，一是计算逻辑值，二是用做改变控制流语句中的条件表达二是用做改变控制流语句中的条件表达式，如在式，如在if-then，if-then-else，或是，或是while-do语句中那样。语句中那样。第46页，本讲稿共97页布尔表达式是由布尔算符布尔表达式是由布尔算符and，or和和not施于布尔施于布尔变量或关系表达式而成。即布尔表达式的形式为变量或关系表达式而成。即布尔表达式的形式为E1 rop E2，其中，其中E1和

36、和E2都是算术表达式，都是算术表达式，rop是关是关系符，如系符，如，等等。等等。只考虑简单的布尔表达式文法：只考虑简单的布尔表达式文法：EE and E|E or E|not E|id rop id|id并且按通常习惯，约定布尔算符的优先顺序（从高到并且按通常习惯，约定布尔算符的优先顺序（从高到低）为低）为not、and、or，并且，并且and和和or服从左结合。服从左结合。第47页，本讲稿共97页布尔表达式的翻译方法布尔表达式的翻译方法通常，计算布尔表达式的值有两种办法，第一种办通常，计算布尔表达式的值有两种办法，第一种办法，如同计算算术表达式一样，计算出各部分的真法，如同计算算术表达式一

37、样，计算出各部分的真假值，最后计算出整个表达式的值。假值，最后计算出整个表达式的值。例如，用数值例如，用数值1表示表示true，用，用0表示表示false。那么布尔。那么布尔表达式表达式1 or（not 0 and 0）or 0的计算过程是：的计算过程是：1 or（not 0 and 0）or 01 or（1 and 0）or 01 or 0 or 01 or 01第48页，本讲稿共97页布尔值的翻译方案布尔值的翻译方案EE1 or E2E.place=Newtemp；GEN（or，E1.place，E2.place，E.place）EE1 and E2 E.place=Newtemp；GEN

38、（and，E1.place，E2.place，E.place）Enot E1 E.place=Newtemp；GEN（not，E1.place，_，E.place）E（E1）E.place=E1.placeEid1 rop id2 E.place=Newtemp；GEN(jrop,Entry(id1),Entry(id2),E.place)Eid E.place=Entry(id)第49页，本讲稿共97页另一种计算方法是采取某种优化措施，另一种计算方法是采取某种优化措施，只计算部分表达式只计算部分表达式:A or B，若，若A的值为的值为1，则无需计算，则无需计算B的值，的值，因为不管因为不管

39、B的值为何结果，的值为何结果，A or B的值都的值都为为1。A and B，若，若A的值为的值为0，则无需计算，则无需计算B的的值，因为不管值，因为不管B的值为何结果，的值为何结果，A and B的值都为的值都为0。第50页，本讲稿共97页控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译条件控制语句条件控制语句if E then Sif E then S1 1 else S else S2 2的目标的目标代码结构如下：代码结构如下：E E的代码的代码S S1 1的代码的代码S S2 2的代码的代码真假第51页，本讲稿共97页“真真”出口与出口与“假假”出口出口布尔表达式布尔表达式E的作用

40、仅在于控制对的作用仅在于控制对S S1 1和和S S2 2的选择，而无须最终保留的选择，而无须最终保留E值，故作为转值，故作为转移条件的布尔表达式移条件的布尔表达式E，可赋予它两种出，可赋予它两种出口：口：“真真”出口出口 E.TC S S1 1“假假”出口出口 E.FC S S2 2第52页，本讲稿共97页作为转移条件的布尔表达式作为转移条件的布尔表达式E，可翻译为，可翻译为如下的四元式序列：如下的四元式序列：（jnz,A ,_ ,p)表示 if A goto p (jrop,A1,A2,p )表示 if A1 rop A2 goto p (j ,_,_,p )表示 goto p第53页，本

41、讲稿共97页示例示例【例如例如】条件语句条件语句 if A or Bif A or BC then SC then S1 1 else S else S2 2 可翻译为：可翻译为：(1)(jnz,A ,_ ,(5)(2)(j ,_,_,(3)(3)(j,B,C,(5)(4)(j ,_,_,(p+1)(5)(5)关于关于S S1 1的四元式序列的四元式序列(p)(j ,_,_,(q)(p+1)(p+1)关于关于S S2 2的四元式序列的四元式序列(q)(q)第54页，本讲稿共97页如何确定一个表达式的真假出口如何确定一个表达式的真假出口考虑考虑E为为E1 or E2的形式：的形式：若若E1为真，

42、则为真，则E为真，所以为真，所以E1的真出口就的真出口就是整个是整个E的真出口。的真出口。若若E1为假，则必须计算为假，则必须计算E2，E2代码的第代码的第一个四元式标号就是一个四元式标号就是E1的假出口，而的假出口，而E2的真出口和假出口就是整个的真出口和假出口就是整个E的真出口和的真出口和假出口。假出口。第55页，本讲稿共97页如何确定一个表达式的真假出口如何确定一个表达式的真假出口考虑考虑E为为E1 and E2的形式：的形式：若若E1为假，则为假，则E为假，所以为假，所以E1的假出口就的假出口就是整个是整个E的假出口。的假出口。若若E1为真，则必须计算为真，则必须计算E2，E2代码的第

43、代码的第一个四元式标号就是一个四元式标号就是E1的真出口，而的真出口，而E2的真出口和假出口就是整个的真出口和假出口就是整个E的真出口和的真出口和假出口。假出口。考虑考虑E为为not E1 的形式：的形式：只需调换只需调换E1 的真假出口即可得到的真假出口即可得到E的真的真假出口。假出口。第56页，本讲稿共97页拉链拉链为了记录需回填地址的四元式，常采用为了记录需回填地址的四元式，常采用一种一种“拉链拉链”的办法。的办法。把需回填把需回填ETC的四元式拉成一条链子，的四元式拉成一条链子，把需回填把需回填EFC的四元式拉成一条链子，的四元式拉成一条链子，分别称做分别称做真真链和链和假假链。链。第

44、57页，本讲稿共97页示例示例若有四元式序列：若有四元式序列：（10）gotoETC（20）gotoETC（30）gotoETC则把需回填则把需回填E.TC的四元式的四元式(10)，(20)和和(30)链成链成:（10）goto（0）（20）goto（10）（30）goto（20）把地址（把地址（30）称作链首，）称作链首，0为链尾标志，即地址（为链尾标志，即地址（10）为链尾。）为链尾。第58页，本讲稿共97页自底向上分析中的一种翻译方案自底向上分析中的一种翻译方案E E1 or E2(1)EAE1 or Backpatch(E1.FC,NXQ);EA.TC=E1.TC(1)E EAE2 E

45、.FC=E2.FC;E.TC=Merg(EA.TC,E1.TC)【说明说明】Backpatch(p,t):将将p p链接的四元式的第四元都回填链接的四元式的第四元都回填t t；Merg(p1,p2):将以将以p1p1和和p2p2为链首的两条链合并为一为链首的两条链合并为一条链，返回时的函数值作为合并后的链首。条链，返回时的函数值作为合并后的链首。第59页，本讲稿共97页E E1 and E2(2)EBE1 and Backpatch(E1.TC,NXQ);EB.FC=E1.FC(2)E EBE2 E.TC=E2.TC;E.FC=Merg(EB.FC,E1.FC)(3)Enot E1 E.TC=

46、E1.FC;E.FC=E1.TC 第60页，本讲稿共97页(4)E(E1)E.TC=E1.TC;E.FC=E1.FC(5)Eid1 rop id2 E.TC=NXQ;E.FC=NXQ+1;GEN(jrop，Entry(id1)，Entry(id2)，0);GEN(j，_，_，0)(6)Eid E.TC=NXQ；E.FC=NXQ1;GEN(jnz，Entry(id)，_，0);GEN(j，_，_，0)第61页，本讲稿共97页六、控制语句的翻译六、控制语句的翻译考虑考虑if then，if then else和和while do语句的翻译。语句的翻译。GS：S if E then S|if E t

47、hen S else S|while E do S|begin L end|A L L；S|S其中各非终结符号的意义是：其中各非终结符号的意义是：S-语句语句L-语句串语句串A-赋值句赋值句E-布尔表达式布尔表达式第62页，本讲稿共97页1.条件语句条件语句if的翻译的翻译考虑考虑if 语句的翻译。语句的翻译。产生式产生式 S if E then S|if E then S else S 第63页，本讲稿共97页两个问题两个问题布尔式布尔式E的的真、真、假假出口尚待回填出口尚待回填E.TC,E.FC。if E then S1 else S2 else S3 在翻译完在翻译完S2之后，之后，S1

48、后的无后的无条件转移目标仍无法确定，因为它不仅要跨越条件转移目标仍无法确定，因为它不仅要跨越S2还应跨还应跨越越S3。即转移目标的确定和语句所处的环境密切。即转移目标的确定和语句所处的环境密切相关。故也可象处理布尔表达式一样，让非终结相关。故也可象处理布尔表达式一样，让非终结符符S（和（和L）含有一项语义值）含有一项语义值SCHAIN（和（和LCHAIN）。也是一条链，它把所有那些四元式串在）。也是一条链，它把所有那些四元式串在一起，这些四元式期待在翻译完一起，这些四元式期待在翻译完S（L）之后回填转）之后回填转移目标。真正的回填工作将在处理移目标。真正的回填工作将在处理S的外层环境的某的外层

49、环境的某一适当时候完成。一适当时候完成。第64页，本讲稿共97页单分支条件语句的目标结构单分支条件语句的目标结构if E then Sif E then S1 1 的目标代码结构如下：的目标代码结构如下：E E的代码的代码S S1 1的代码的代码E.TCE.FCS S1 1.CHAINS S.CHAIN第65页，本讲稿共97页多分支条件语句的目标结构多分支条件语句的目标结构if E then Sif E then S1 1 else S else S2 2的目标代码结构如下：的目标代码结构如下：E E的代码的代码S S1 1的代码的代码S S2 2的代码的代码E.TCE.FCjmp 0S S1

50、 1.CHAINS S2 2.CHAINS S.CHAIN第66页，本讲稿共97页翻译方案翻译方案if E then Sif E then S1 1 C if E then Backpatch(E.TC,NXQ);C.CHAIN=E.FC S C S1 S.CHAIN=Merg(C.CHAIN,S1.CHAIN)第67页，本讲稿共97页if E then Sif E then S1 1 else S else S2 2C if E then Backpatch(E.TC,NXQ);C.CHAIN=E.FC TP C S1 else q=NXQ;GEN(j,_,_,0);Backpatch(C.