语法制导翻译技术和中间代码生成.ppt
12/18/2022112/18/20221编编 译译 原原 理理Sunday,December 18,2022S.PO.P语义分析、生成中间代码语义分析、生成中间代码生成目标程序生成目标程序代码优化代码优化语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理12/18/2022212/18/20222编编 译译 原原 理理Sunday,December 18,2022第第5 5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成1.1.要求明确语义分析的要求明确语义分析的任务任务2.2.明确明确属性文法属性文法和和语法制导翻译语法制导翻译的含义的含义3.3.明确明确自底向上和自顶向下自底向上和自顶向下语法制导翻译的语法制导翻译的区别和特点区别和特点4.明确明确生成中间代码的目的，中间代码的几生成中间代码的目的，中间代码的几种形式种形式教学目标教学目标12/18/2022312/18/20223编编 译译 原原 理理Sunday,December 18,2022属性文法属性文法语法制导翻译法的基本思想语法制导翻译法的基本思想常见的中间代码常见的中间代码各种不同语法结构的语法制导翻译技术各种不同语法结构的语法制导翻译技术教学内容教学内容12/18/2022412/18/20224编编 译译 原原 理理Sunday,December 18,2022词法分析，语法分析词法分析，语法分析：解决单词和语言成分的识别：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器构造出来。容易地将其分析器构造出来。本章要介绍的是本章要介绍的是语义分析和中间代码生成技术语义分析和中间代码生成技术。程序语言中间代码目标代码程序语言中间代码目标代码翻译翻译翻译翻译12/18/2022512/18/20225编编 译译 原原 理理Sunday,December 18,2022根据语义规则对识别出的各种语法成分析其含义，根据语义规则对识别出的各种语法成分析其含义，进行初步翻译，生成相应的中间代码或直接生成目进行初步翻译，生成相应的中间代码或直接生成目标代码。标代码。第一，审查每个语法结构的静态语义，即检查语法结构合法第一，审查每个语法结构的静态语义，即检查语法结构合法的程序是否真正有意义。也称静态语义检查。的程序是否真正有意义。也称静态语义检查。（类型检查、（类型检查、控制流的检查、一致性检查、相关名字的检查）控制流的检查、一致性检查、相关名字的检查）第二，如果静态语义正确，语义处理则要执行真正的翻译，第二，如果静态语义正确，语义处理则要执行真正的翻译，要么生成中间代码，要么生成实际的目标代码。（要么生成中间代码，要么生成实际的目标代码。（说明性语说明性语句：填符号表；可执行性语句：生成中间代码）句：填符号表；可执行性语句：生成中间代码）语义分析的任务语义分析的任务12/18/2022612/18/20226编编 译译 原原 理理Sunday,December 18,2022类型检查类型检查。控制流检查控制流检查，确保控制语句有合法的转向点。例，确保控制语句有合法的转向点。例如，如，C语言中的语言中的break语句使控制跳离包括该语句的语句使控制跳离包括该语句的最小的最小的switch，while或或for语句。如果不存在包括它语句。如果不存在包括它的这样的语句，则应报错。的这样的语句，则应报错。静态语义检查静态语义检查12/18/2022712/18/20227编编 译译 原原 理理Sunday,December 18,2022静态语义检查静态语义检查一致性检查一致性检查。很多情况下要求对象只能被定义一。很多情况下要求对象只能被定义一次。例如，语言中规定一个标识符在同一作用域中次。例如，语言中规定一个标识符在同一作用域中只能被说明一次，同一只能被说明一次，同一case语句的标号不能相同，枚语句的标号不能相同，枚举类型的元素不能重复出现等。举类型的元素不能重复出现等。相关名字检查相关名字检查。有的语言中有时规定，同一名字。有的语言中有时规定，同一名字必须出现两次或多次。例如，必须出现两次或多次。例如，Ada语言中，循环或程语言中，循环或程序块可以有一个名字，它出现在这些结构的开头和结序块可以有一个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配尾，如同语句括号一般，编译程序必须检查它们的配对情况。对情况。12/18/2022812/18/20228编编 译译 原原 理理Sunday,December 18,2022附加了一组附加了一组属性属性和和运算（语义）规则运算（语义）规则的的文法文法 5.2 属性文法属性文法文法符号文法符号X的属性的属性t常用常用X.t来表示来表示 语义规则是根据产生式所语义规则是根据产生式所蕴涵的语义蕴涵的语义操作建立起来的，操作建立起来的，并与并与语义分析的目标语义分析的目标有关有关不同的不同的产生式产生式对应不同的语义规则对应不同的语义规则不同的不同的分析目标分析目标也对应不同的语义规则也对应不同的语义规则 1.属性的表示属性的表示2.语义规则语义规则的表示的表示语义信息语义信息语义之间的关系语义之间的关系静态语义检查、符号静态语义检查、符号表操作、代码生成及表操作、代码生成及打印各种错误信息打印各种错误信息 12/18/2022912/18/20229编编 译译 原原 理理Sunday,December 18,2022属性文法属性文法属性文法的形式定义：AG：AG=（G，V，E）G:上下文无关文法;V:属性的有穷集合;每一个属性与某一个文法符号相关联；用文法符号属性表示E:表示属性的断言或谓词的有穷集合(语义规则);每一个断言与文法的某个产生式相关联)属性:综合属性(自下而上传递信息)、继承属性（自上而下传递信息)12/18/20221012/18/202210编编 译译 原原 理理Sunday,December 18,2022 非终结符非终结符E E、T T及及F F都有一个综合属性都有一个综合属性valval,符号符号i i有一个综合属性。有一个综合属性。某些非终结符加下标是为了区分一个产生式中某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现同一非终结符多次出现语语 义义 规规 则则E E1+TE T T T1*FT FF (E)F i E.val=E1.val+T.valE.val=T.val T.val=T1.val F.valT.val=F.valF.val=E.val F.val=i.lexval产生式产生式例例5.15.112/18/20221112/18/202211编编 译译 原原 理理Sunday,December 18,2022语法制导翻译的过程语法制导翻译的过程语法制导翻译：语法制导翻译：将将语义规则语义规则与与语法规则语法规则相结合，在相结合，在语法分析语法分析的过程中通过执行的过程中通过执行语义动作语义动作，计算语义属，计算语义属性值，从而完成预定的翻译工作。性值，从而完成预定的翻译工作。12/18/20221212/18/202212编编 译译 原原 理理Sunday,December 18,2022语法制导翻译分为两种语法制导翻译分为两种处理方法处理方法：（1）自底向上语法制导翻译：）自底向上语法制导翻译：对每个产生式编制一个语义子程序，在进行语法分析的过对每个产生式编制一个语义子程序，在进行语法分析的过程中，程中，当一个产生式获得匹配时当一个产生式获得匹配时，就调用相应的语义子程，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。则的计算次序等实现细节，不必规定翻译顺序。（2）自顶向下语法制导翻译：）自顶向下语法制导翻译：在产生式右部的适当位置，插入相应的语义动作，按照分在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种析的进程，执行遇到的语义动作。这是一种动作与分析交动作与分析交错错的实现方案。的实现方案。12/18/20221312/18/202213编编 译译 原原 理理Sunday,December 18,2022语法制导定义语法制导定义对每个产生式编制一个对每个产生式编制一个语义子程序语义子程序在进行语法分析的过程中，在进行语法分析的过程中，当一个产生式获得匹配时当一个产生式获得匹配时，就调，就调用相应的语义子程序实现语义检查与翻译用相应的语义子程序实现语义检查与翻译综合属性综合属性继承属性继承属性自底向上自底向上传递信息传递信息自顶向下（自左向右）自顶向下（自左向右）传递信息传递信息12/18/20221412/18/202214编编 译译 原原 理理Sunday,December 18,2022 属性翻译文法的应用属性翻译文法的应用 综合属性与自下而上定值综合属性与自下而上定值 每个非终结符的属性值都是根据位于其下面那些符号每个非终结符的属性值都是根据位于其下面那些符号的属性值来确定的，即按一种自下而上的方式来确定的。的属性值来确定的，即按一种自下而上的方式来确定的。继承属性和自上而下定值继承属性和自上而下定值 非终结符的属性值或者根据其上层非终结符的属性来非终结符的属性值或者根据其上层非终结符的属性来确定或者根据产生式右部其它符号的属性来确定。这种属确定或者根据产生式右部其它符号的属性来确定。这种属性值是根据自上而下方式确定的。性值是根据自上而下方式确定的。12/18/20221512/18/202215编编 译译 原原 理理Sunday,December 18,2022 print(E.valprint(E.val)打印由打印由E E产生的算术表达式的值，产生的算术表达式的值，可认为这条规则定义了可认为这条规则定义了L L的一个的一个虚属性虚属性。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.val T.val=F.valF.val=E.valF.val=i.lexval例例5.5.综合属性综合属性语语 义义 规规 则则产生式产生式12/18/20221612/18/202216编编 译译 原原 理理Sunday,December 18,2022一个结点的综合属性值是其一个结点的综合属性值是其子子结点结点的某些属性来决定的的某些属性来决定的+3*4+3*4的注释分析树的注释分析树通常使用通常使用自底向上自底向上的分析方法的分析方法在在每个结点每个结点处使用语义规则处使用语义规则来计算综合属性值来计算综合属性值当一个当一个产生式获得匹配产生式获得匹配时，时，就调用相应的语义子程序就调用相应的语义子程序从从叶结点到根结点叶结点到根结点进行计算进行计算 只含有只含有综合属性综合属性的语法制导定义的语法制导定义称为称为S S属性定义属性定义12/18/20221712/18/202217编编 译译 原原 理理Sunday,December 18,2022S属性定义与自底向上翻译属性定义与自底向上翻译 LRLR分分析析器器可可以以改改造造为为一一个个翻翻译译器器，在在对对输输入入串串进进行行语法分析的同时对属性进行计算语法分析的同时对属性进行计算LRLR分析器增加分析器增加属性值（语义）栈属性值（语义）栈 1）为文法的每条规则设计相应的语义子程序；）为文法的每条规则设计相应的语义子程序；2）增加一个语义信息栈；）增加一个语义信息栈；3）在语法分析的同时做语义处理：即在用某一个）在语法分析的同时做语义处理：即在用某一个产生式进行规约的同时，调用相应的语义子程序完产生式进行规约的同时，调用相应的语义子程序完成所用规则的语义动作，并将每次动作后的值保存成所用规则的语义动作，并将每次动作后的值保存在语义栈中在语义栈中翻译步骤翻译步骤计算表达式计算表达式2+3*52+3*5 Sunday,October 2,2022 编编 译译 原原 理理状状态态ACTIONGOTOi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5GE：1 EE+T2 ET3 TT*F4 TF5 F(E)6 Fii+i*i Sunday,October 2,2022 编编 译译 原原 理理表达式表达式2+3*52+3*5的归约过程的归约过程步骤状态栈 语义栈符号栈输入串动作00_$2+3*5$S5105_ _$2 +3*5$r6203_ 2$F +3*5$r4302_ 2$T +3*5$r2401_ 2$E +3*5$S65016_ 2 _$E+3*5$S560165_ 2 _ _$E+3 *5$r6 Sunday,October 2,2022 编编 译译 原原 理理步骤状态栈 语义栈符号栈输入串动作70163_ 2 _ 3$E+F*5$r480169_ 2 _ 3$E+T*5$S7901697_ 2 _ 3 _$E+T*5$S510016975_ 2 _ 3 _ _$E+T*5$r61101697(10)_ 2 _ 3 _ 5$E+T*F$r3120169_ 2 _ 15$E+T$r11301_ 17$E$acc Sunday,October 2,2022 编编 译译 原原 理理注意句柄归约在先，语义动作调用在后句柄归约在先，语义动作调用在后归约时，栈内句柄各符号的语义信息与句柄及归约时，栈内句柄各符号的语义信息与句柄及同时出栈，整个句柄所表示的语义信息则赋给同时出栈，整个句柄所表示的语义信息则赋给相应产生式左部非终结符号的语义变量，并让相应产生式左部非终结符号的语义变量，并让该非终结符号及语义信息同时入栈该非终结符号及语义信息同时入栈 Sunday,October 2,2022 编编 译译 原原 理理12/18/20222312/18/202223编编 译译 原原 理理Sunday,December 18,2022生成中间代码的生成中间代码的目的目的(1)便于优化便于优化(2)便于移植便于移植(3)逻辑结构清晰逻辑结构清晰常见的中间代码常见的中间代码形式形式：后缀式后缀式三地址代码三地址代码（四元式、三元式和间接三元式（四元式、三元式和间接三元式）图形图形（抽象语法树、有向无环图）（抽象语法树、有向无环图）中间代码：一种介于中间代码：一种介于源语言和目标语言之间源语言和目标语言之间的中间语言形式的中间语言形式5.5.中间代码中间代码12/18/20222412/18/202224编编 译译 原原 理理Sunday,December 18,2022中缀表示中缀表示后缀表示后缀表示a+b ab+a+b*c abc*+(a+b)*c ab+c*a:=b*c+b*d abc*bd*+:=特点特点1、运算对象出现的顺序和原有顺序（从左到右）相同、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值优点：简明、便于计值 后缀式后缀式12/18/20222512/18/202225编编 译译 原原 理理Sunday,December 18,2022分别给出下列表达式的后缀表示分别给出下列表达式的后缀表示1.-a+b*(-c+d)2.X:=-(a+b)/(c-d)-(a+b*c)3.a=c b=d4.ab+c ada+bea-bc-d+*+Xab+-cd-/abc*+-:=ac=bd=abc+ad ab+e 12/18/20222612/18/202226编编 译译 原原 理理Sunday,December 18,2022逆波兰表示法（后缀式）逆波兰表示法（后缀式）特点：运算符直接写在其运算对象之后。不再有括号运算对象出现的次序未变求值过程简单，宜于用栈实现后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。12/18/20222712/18/202227编编 译译 原原 理理Sunday,December 18,2022三地址代码三地址代码种类种类（1）x=y op z形式的赋值语句，其中形式的赋值语句，其中op是二元运算符。是二元运算符。（2）x=op y形式的赋值语句，其中形式的赋值语句，其中op是一元运算符。是一元运算符。（3）x=y形式的赋值语句。形式的赋值语句。（4）无无条条件件转转移移语语句句goto L，表表示示下下一一个个要要执执行行的的语语句句是是标号为标号为L的语句。的语句。（5）条条件件转转移移语语句句if x rop y goto L中中，rop为为关关系系运运算算符符，如如果果x和和y满满足足关关系系rop，就就转转而而执执行行标标号号为为L的的语语句句，否否则则顺序执行下一个语句。顺序执行下一个语句。12/18/20222812/18/202228编编 译译 原原 理理Sunday,December 18,2022（6）过过程程调调用用语语句句param x 和和call p,n。源源程程序序中中的的过过程程调用语句调用语句p(x1，x2，xn)可以产生如下的三地址代码：可以产生如下的三地址代码：param x1param x2 param xncall p,n其中其中n为实参个数。过程返回语句形如为实参个数。过程返回语句形如return y，其中，其中y为过为过程返回的一个值。程返回的一个值。12/18/20222912/18/202229编编 译译 原原 理理Sunday,December 18,2022（7）变址赋值：）变址赋值：x=yi，把从，把从y开始的第开始的第i个存储单元的值赋给个存储单元的值赋给x。xi=y，把，把y的值赋给的值赋给x开始的第开始的第i个存储单元。个存储单元。其中，其中，x，y和和i都代表数据对象。都代表数据对象。（8）地址和指针赋值：）地址和指针赋值：x=&y，把，把y的地址赋给的地址赋给x。x=y，把，把y指示的地址单元中的内容赋给指示的地址单元中的内容赋给x。x=y，把，把x指向的存储单元的值置为指向的存储单元的值置为y。12/18/20223012/18/202230编编 译译 原原 理理Sunday,December 18,20222具体实现具体实现四元式四元式操作符操作符 操作数操作数1 操作数操作数2 结果结果结果：通常是由编译引进的临时变量结果：通常是由编译引进的临时变量例例:X=(A+B)*(C+D)-E+,A,B,T1+,C,D,T2*,T1,T2,T3-,T3,E,T4=,T4,一一,XT1,T2,T3,T4为临时变量，由四元式优为临时变量，由四元式优化比较方便化比较方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T412/18/20223112/18/202231编编 译译 原原 理理Sunday,December 18,2022操作符操作符 左操作符数左操作符数 右操作数右操作数 表达式的三元式：表达式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)第三个三元第三个三元式中的操作数式中的操作数(1)(2)表示第表示第(1)和第和第(2)条三元式的计条三元式的计算结果。算结果。三三元式元式12/18/20223212/18/202232编编 译译 原原 理理Sunday,December 18,2022例：例：A=B+C*D/E F=C*D三元式三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(1)不便于代码优化：删不便于代码优化：删除某些三元式后可能除某些三元式后可能需作一系列的修改需作一系列的修改 三元式三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)间接三元式间接三元式执行顺序执行顺序(1)(2)(3)(4)(1)(5)三元式的执行次序用另一张三元式的执行次序用另一张表表示表表示,优化时三元式可以优化时三元式可以不变，仅仅改变其执行顺序不变，仅仅改变其执行顺序表表12/18/20223312/18/202233编编 译译 原原 理理Sunday,December 18,2022图形表示法图形表示法无循环有向图无循环有向图(Directed Acyclic Graph(Directed Acyclic Graph，简称，简称DAG)DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAGDAG中都有一个中都有一个结点结点一个一个内部结点内部结点代表一个代表一个操作符操作符，它的孩子代表，它的孩子代表操作数操作数在一个在一个DAGDAG中代表公共子表达式的结点具有多中代表公共子表达式的结点具有多个父结点个父结点12/18/20223412/18/202234编编 译译 原原 理理Sunday,December 18,2022例：例：x=y+y z+y z 抽象语法树抽象语法树图形表示图形表示有向无环图有向无环图练习：练习：1.1.表达式表达式a+(-b)*ca+(-b)*c的三元式的三元式 (1)(,b,_);单目运算，运算对象2为空(2)(*,(1),c)(3)(+,a,(2)Sunday,October 2,2022 编编 译译 原原 理理三元式三元式X=a+b*c Y=d-b*c三元式表(1)(*,b,c)(2)(+,a,(1)(3)(=,x,(2)(4)(_,d,(1)(5)(=,y,(4)Sunday,October 2,2022 编编 译译 原原 理理2.2.四元式四元式(三地址代码）三地址代码）X=a*b+c*d的四元式序列 三地址代码(1)(*,a,b,T1)(1)T1=a*b(2)(*,c,d,T2)(2)T2=c*d(3)(+,T1,T2,T3)(3)T3=T1+T2(4)(=,T3,_,X)(4)X=T3 Sunday,October 2,2022 编编 译译 原原 理理 3.a:=b*(-c)+b*(-c)的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc Sunday,October 2,2022 编编 译译 原原 理理抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc抽象语法树抽象语法树*buminusc a:=b*(-c)+b*(-c)的图表示法的图表示法 Sunday,October 2,2022 编编 译译 原原 理理DAG对应的代码：对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 Sunday,October 2,2022 编编 译译 原原 理理自底向上的语法制导翻译自底向上的语法制导翻译自底向上的语法制导翻译方法是在自底向上的语法分析过程中自底向上的语法制导翻译方法是在自底向上的语法分析过程中逐步实现语义规则的翻译方法。在实现时注意以下几点：逐步实现语义规则的翻译方法。在实现时注意以下几点：（1 1）自底向上的翻译的特点，栈的操作，）自底向上的翻译的特点，栈的操作，对产生式的要求对产生式的要求等等（2 2）各种程序语句的）各种程序语句的目标结构目标结构（3 3）从源结构到目标结构的变换方法（包括对）从源结构到目标结构的变换方法（包括对产生式的改造产生式的改造等）等）Sunday,October 2,2022 编编 译译 原原 理理算术表达式和赋值语句的翻译算术表达式和赋值语句的翻译翻译步骤：翻译步骤：（1 1）分析文法的特点；）分析文法的特点；（2 2）设计一系列的语义变量、定义语义过程、）设计一系列的语义变量、定义语义过程、语义函数；语义函数；（3 3）设计每一条规则的语义子程序；）设计每一条规则的语义子程序；（4 4）增加一个语义信息栈，构造）增加一个语义信息栈，构造LRLR分析表分析表;(5)(5)语法分析同时语义处理语法分析同时语义处理.Sunday,October 2,2022 编编 译译 原原 理理例：例：有文法有文法GAGA：1.Ai:=E1.Ai:=E2.E E+TT2.E E+TT3.T T*FF3.T T*FF4.F 4.F P P5.P i(E)5.P i(E)简单算术表达式的计值顺序与四元式出现的顺序相同简单算术表达式的计值顺序与四元式出现的顺序相同,因此目因此目标代码的顺序标代码的顺序(结构结构)为为:(1)(1)先生成先生成E E的代码的代码(一系列顺序执行的四元式一系列顺序执行的四元式)(2)(2)把把E E的值赋给变量的值赋给变量i(i(表达式的结果赋给赋值语句的左变量表达式的结果赋给赋值语句的左变量)Sunday,October 2,2022 编编 译译 原原 理理引入语义变量,语义过程和语义函数(1)(1)语义变量语义变量E.place:E.place:表示存放表示存放E E值的变量名在符号表中的入值的变量名在符号表中的入口地址或临时变量的整数码口地址或临时变量的整数码.(2)(2)语义函数语义函数newtemp():newtemp():申请一个临时单元申请一个临时单元,存放中间结果存放中间结果;(3)(3)语义过程语义过程emit(T=argemit(T=arg1 1 op arg op arg2 2):):产生一条四元式产生一条四元式,并添入并添入四元式表中四元式表中;(4)(4)语义过程语义过程lookup(i.name):lookup(i.name):审查审查i.namei.name是否出现在符号表是否出现在符号表中中,在在:返回地址返回地址,不在不在:返回返回NULL;NULL;(5)(5)语义函数语义函数entry(i):entry(i):回送标识符回送标识符i i在符号表中的入口地址在符号表中的入口地址.Sunday,October 2,2022 编编 译译 原原 理理表达式的语义动作设计表达式的语义动作设计1.Ai:=E emit(entry(i)=E.place1.Ai:=E emit(entry(i)=E.place2.E E2.E E1 1+T E.place=newtemp(),+T E.place=newtemp(),emit(E.place)=E emit(E.place)=E1 1.place+T.place.place+T.place3.E T E.place=newtemp(),3.E T E.place=newtemp(),emit(E.place=T.place)emit(E.place=T.place)4.T T4.T T1 1*F T.place=newtemp(),*F T.place=newtemp(),emit(T.place)=T emit(T.place)=T1 1.place*F.place.place*F.place5.T F T.place=newtemp(),5.T F T.place=newtemp(),emit(T.place=F.place)emit(T.place=F.place)Sunday,October 2,2022 编编 译译 原原 理理6.F _P F.place=newtemp(),6.F _P F.place=newtemp(),emit(F.place)=P.place emit(F.place)=P.place7.P(E)P.place=newtemp(),7.P(E)P.place=newtemp(),emit(P.place=E.place)emit(P.place=E.place)8.P I P.place=newtemp(),8.P I P.place=newtemp(),emit(P.place=Entry(i)emit(P.place=Entry(i)Sunday,October 2,2022 编编 译译 原原 理理例如例如:表达式表达式X:=a+b*(c-d)X:=a+b*(c-d)的翻译的翻译K+1:T1:=c-dK+2:T2=b*T1K+3:T3:=a+T2K+4:X:=T3(-,c,d,T1)(*,b,T1,T2)(+,a,T2,T3)(:=,T3,_,X)Sunday,October 2,2022 编编 译译 原原 理理布尔表达式的翻译布尔表达式的翻译布尔表达式布尔表达式 是由布尔运算符是由布尔运算符(and,or,not)(and,or,not)作用于布尔变量作用于布尔变量(或常数或常数)或关系表达式而形成的。或关系表达式而形成的。布尔表达式的作用：布尔表达式的作用：用作控制语句中的条件：用作控制语句中的条件：if-thenif-then、while while、repeatrepeat等等逻辑赋值句中的逻辑运算逻辑赋值句中的逻辑运算 Sunday,October 2,2022 编编 译译 原原 理理布尔表达式到四元式的翻译 文法：文法：E EE E E E E E E EE E(E)(E)idid E rop EE rop E 其其中中，(and)(and)、(or)(or)、(not)(not)为为布布尔尔（逻逻辑辑）运运算算符符；roprop为为关关系系运运算算符符（，=，）；idid为为布布尔尔（逻逻辑辑）变变量量或或布布尔尔（逻逻辑辑）常常数数；E E rop rop E E为为关关系系表表达达式。式。布尔表达式的求值方法：布尔表达式的求值方法：通过逐步计算出各部分的值来计算整个表达式。通过逐步计算出各部分的值来计算整个表达式。利用布尔运算符的性质计算其值利用布尔运算符的性质计算其值 Sunday,October 2,2022 编编 译译 原原 理理布尔表达式作为控制语句中的条件式布尔表达式作为控制语句中的条件式作用是用于选择下一个执行点 while E do S1E的作用是选择S1执行,还是跳过S1语句,执行S1后面的语句E有两个出口:真:S1语句假:S1后面的语句 Sunday,October 2,2022 编编 译译 原原 理理WhileWhile语句的目标结构语句的目标结构 假E的代码 真 whilleS1的代码 doJMP W.headW.head Sunday,October 2,2022 编编 译译 原原 理理布尔初等量布尔初等量(布尔变量和关系表达布尔变量和关系表达式式)的目标结构的目标结构 由两个转移四元式构成由两个转移四元式构成,一个表示真出口一个表示真出口L Li i,另一个表示假另一个表示假出口出口L Lj j,设设E E是一布尔变量是一布尔变量,它的目标结构为它的目标结构为:(1)if E goto L(1)if E goto Li i (jump (jumpt t,_,_,L,_,_,Li i)(jnz,E,_,L(jnz,E,_,Li i)(2)if E(2)if E1 1 rop E rop E2 2 goto L goto Li i (jump(jump,E,E1 1 ,E ,E2 2 ,L ,Li i)(jrop,E(jrop,E1 1,E,E2 2,L,Li i)例例:(j,a,b,p):(j,a,b,p)(3)goto L(3)goto Lj j (jump L (jump Lj j)(j,_,_,L(j,_,_,Lj j)Sunday,October 2,2022 编编 译译 原原 理理举例举例:if:if abab then then A:=x+yA:=x+y的四元的四元式序列式序列 if ab goto Lif ab goto Li i(真真出口出口)goto L goto Lj j (假出口假出口)L Li i:S:S的第一个四元式的第一个四元式S S的最后一个四元式的最后一个四元式L Lj j:S :S 后面的语句后面的语句(1)if ab goto (3)(1)if ab goto (3)(2)goto (5)(2)goto (5)(3)T(3)T1 1:=x+y:=x+y(4)A:=T(4)A:=T1 1(5)(5)Sunday,October 2,2022 编编 译译 原原 理理 多因子组成的布尔表达式的翻译多因子组成的布尔表达式的翻译例:if ab c then S1 else S2分析结果如下分析结果如下:当当abab为真为真,执行执行S S1 1,不需要计算不需要计算c c的值的值当当abab为假为假,计算计算c c的值的值,c,c为真为真:执行执行S S1 1,为假为假:执行执行S S2 2当当abab与与c c分别为真时分别为真时,程序转向一致程序转向一致,真出口相同真出口相同(S(S1 1)当当abab与与c c分别为假时分别为假时,程序转向一致程序转向一致,假出口相同假出口相同(S(S2 2)Sunday,October 2,2022 编编 译译 原原 理理if ab c then Sif ab c then S1 1 elseS elseS2 2的四元式序列的四元式序列(1)if ab goto S(1)if ab goto S1 1的第一的第一条语句条语句 (5)(5)(2)goto(3)(2)goto(3)(3)if c goto S(3)if c goto S1 1的第一条的第一条语句语句 (5)(5)(4)goto S(4)goto S2 2的第一条语句的第一条语句 (p+1p+1(5)(5)关于关于S S1 1的四元式序列的四元式序列 (p)Goto q(p)Goto q(p+1)(p+1)关于关于S S2 2的四元式序列的四元式序列 (q)(q)后继四元式后继四元式 目标结构E的代码 TFS1的代码JUMP SS2的代码S（后继语句）Sunday,October 2,2022 编编 译译 原原 理理 if E then Sif E then S1 1 else S else S2 2的四元式序列的四元式序列(1)if E goto(3)(1)if E goto(3)(2)goto(S(2)goto(S2 2的第一个四元式的第一个四元式)(p+1)(p+1)(3)(3)关于关于S S1 1的四元式序列的四元式序列 (p)goto r(p)goto r(执行完执行完S S1 1后转出后转出)(p+1)(p+1)关于关于S S2 2的四元式序列的四元式序列(r)(r)后继四元式后继四元式 Sunday,October 2,2022 编编 译译 原原 理理 while E do Swhile E do S1 1的四元式序列的四元式序列(1)if E goto(3)(1)if E goto(3)(2)goto(S(2)goto(S1 1后面的语句后面的语句)(p+1)(p+1)(3)(3)关于关于S S1 1的四元式序列的四元式序列(p)goto(1)(p)goto(1)(p+1)(p+1)后继四元式后继四元式 Sunday,October 2,2022 编编 译译 原原 理理真出口链、假出口链、回填（真出口链、假出口链、回填（Backparch)Backpar
