语法制导翻译技术和中间代码生成.pptx

第第5 5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成要求明确语义分析的要求明确语义分析的任务任务明确明确属性文法属性文法和和语法制导翻译语法制导翻译的含义的含义明确明确自底向上和自顶向下自底向上和自顶向下语法制导翻译的语法制导翻译的区别和特点区别和特点明确明确生成中间代码的目的，中间代码的几生成中间代码的目的，中间代码的几种形式种形式教学目标教学目标第1页/共80页属性文法属性文法语法制导翻译法的基本思想语法制导翻译法的基本思想常见的中间代码常见的中间代码各种不同语法结构的语法制导翻译技术各种不同语法结构的语法制导翻译技术教学内容教学内容第2页/共80页词法分析，语法分析词法分析，语法分析：解决单词和语言成分的识别：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器构造出来。容易地将其分析器构造出来。本章要介绍的是本章要介绍的是语义分析和中间代码生成技术语义分析和中间代码生成技术。程序语言中间代码目标代码程序语言中间代码目标代码翻译翻译翻译翻译第3页/共80页根据语义规则对识别出的各种语法成分析其含义，根据语义规则对识别出的各种语法成分析其含义，进行初步翻译，生成相应的中间代码或直接生成目进行初步翻译，生成相应的中间代码或直接生成目标代码。标代码。第一，审查每个语法结构的静态语义，即检查语法结构合法第一，审查每个语法结构的静态语义，即检查语法结构合法的程序是否真正有意义。也称静态语义检查。的程序是否真正有意义。也称静态语义检查。（类型检查、（类型检查、控制流的检查、一致性检查、相关名字的检查）控制流的检查、一致性检查、相关名字的检查）第二，如果静态语义正确，语义处理则要执行真正的翻译，第二，如果静态语义正确，语义处理则要执行真正的翻译，要么生成中间代码，要么生成实际的目标代码。（要么生成中间代码，要么生成实际的目标代码。（说明性语说明性语句：填符号表；可执行性语句：生成中间代码）句：填符号表；可执行性语句：生成中间代码）语义分析的任务语义分析的任务第4页/共80页类型检查类型检查。控制流检查控制流检查，确保控制语句有合法的转向点。例，确保控制语句有合法的转向点。例如，如，C语言中的语言中的break语句使控制跳离包括该语句的语句使控制跳离包括该语句的最小的最小的switch，while或或for语句。如果不存在包括它语句。如果不存在包括它的这样的语句，则应报错。的这样的语句，则应报错。静态语义检查静态语义检查第5页/共80页静态语义检查静态语义检查一致性检查一致性检查。很多情况下要求对象只能被定义一。很多情况下要求对象只能被定义一次。例如，语言中规定一个标识符在同一作用域中次。例如，语言中规定一个标识符在同一作用域中只能被说明一次，同一只能被说明一次，同一case语句的标号不能相同，枚语句的标号不能相同，枚举类型的元素不能重复出现等。举类型的元素不能重复出现等。相关名字检查相关名字检查。有的语言中有时规定，同一名字。有的语言中有时规定，同一名字必须出现两次或多次。例如，必须出现两次或多次。例如，Ada语言中，循环或程语言中，循环或程序块可以有一个名字，它出现在这些结构的开头和结序块可以有一个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配尾，如同语句括号一般，编译程序必须检查它们的配对情况。对情况。第6页/共80页附加了一组附加了一组属性属性和和运算（语义）规则运算（语义）规则的的文法文法 5.2 属性文法属性文法文法符号文法符号X的属性的属性t常用来表示常用来表示 语义规则是根据产生式所语义规则是根据产生式所蕴涵的语义蕴涵的语义操作建立起来的，操作建立起来的，并与并与语义分析的目标语义分析的目标有关有关不同的不同的产生式产生式对应不同的语义规则对应不同的语义规则不同的不同的分析目标分析目标也对应不同的语义规则也对应不同的语义规则 1.属性的表示属性的表示2.语义规则语义规则的表示的表示语义信息语义信息语义之间的关系语义之间的关系静态语义检查、符号静态语义检查、符号表操作、代码生成及表操作、代码生成及打印各种错误信息打印各种错误信息 第7页/共80页属性文法属性文法属性文法的形式定义：AG：AG=（G，V，E）G:上下文无关文法;V:属性的有穷集合;每一个属性与某一个文法符号相关联；用文法符号属性表示E:表示属性的断言或谓词的有穷集合(语义规则);每一个断言与文法的某个产生式相关联)属性:综合属性(自下而上传递信息)、继承属性（自上而下传递信息)第8页/共80页 非终结符非终结符E E、T T及及F F都有一个综合属性都有一个综合属性val,val,符号符号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产生式产生式第9页/共80页语法制导翻译的过程语法制导翻译的过程语法制导翻译：语法制导翻译：将将语义规则语义规则与与语法规则语法规则相结合，在相结合，在语法分析语法分析的过程中通过执行的过程中通过执行语义动作语义动作，计算语义属，计算语义属性值，从而完成预定的翻译工作。性值，从而完成预定的翻译工作。第10页/共80页语法制导翻译分为两种语法制导翻译分为两种处理方法处理方法：（1）自底向上语法制导翻译：）自底向上语法制导翻译：对每个产生式编制一个语义子程序，在进行语法分析的过对每个产生式编制一个语义子程序，在进行语法分析的过程中，程中，当一个产生式获得匹配时当一个产生式获得匹配时，就调用相应的语义子程，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。则的计算次序等实现细节，不必规定翻译顺序。（2）自顶向下语法制导翻译：）自顶向下语法制导翻译：在产生式右部的适当位置，插入相应的语义动作，按照分在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种析的进程，执行遇到的语义动作。这是一种动作与分析交动作与分析交错错的实现方案。的实现方案。第11页/共80页语法制导定义语法制导定义对每个产生式编制一个对每个产生式编制一个语义子程序语义子程序在进行语法分析的过程中，在进行语法分析的过程中，当一个产生式获得匹配时当一个产生式获得匹配时，就调，就调用相应的语义子程序实现语义检查与翻译用相应的语义子程序实现语义检查与翻译综合属性综合属性继承属性继承属性自底向上自底向上传递信息传递信息自顶向下（自左向右）自顶向下（自左向右）传递信息传递信息第12页/共80页 属性翻译文法的应用属性翻译文法的应用 综合属性与自下而上定值综合属性与自下而上定值 每个非终结符的属性值都是根据位于其下面那些符每个非终结符的属性值都是根据位于其下面那些符号的属性值来确定的，即按一种自下而上的方式来确定号的属性值来确定的，即按一种自下而上的方式来确定的。的。继承属性和自上而下定值继承属性和自上而下定值 非终结符的属性值或者根据其上层非终结符的属性来非终结符的属性值或者根据其上层非终结符的属性来确定或者根据产生式右部其它符号的属性来确定。这种确定或者根据产生式右部其它符号的属性来确定。这种属性值是根据自上而下方式确定的。属性值是根据自上而下方式确定的。第13页/共80页 )打印由打印由E E产生的算术表达式的值，可认为这条产生的算术表达式的值，可认为这条规则定义了规则定义了L L的一个的一个虚属性虚属性。L EE E1+TE T T T1*FT FF (E)F i)E.val=E1=T.val=T1.val =例例5.5.综合属性综合属性语语 义义 规规 则则产生式产生式第14页/共80页一个结点的综合属性值是其一个结点的综合属性值是其子子结点结点的某些属性来决定的的某些属性来决定的+3*4+3*4的注释分析树的注释分析树通常使用通常使用自底向上自底向上的分析方法的分析方法在在每个结点每个结点处使用语义规则处使用语义规则来计算综合属性值来计算综合属性值当一个当一个产生式获得匹配产生式获得匹配时，时，就调用相应的语义子程序就调用相应的语义子程序从从叶结点到根结点叶结点到根结点进行计算进行计算 只含有只含有综合属性综合属性的语法制导定义的语法制导定义称为称为S S属性定义属性定义第15页/共80页S属性定义与自底向上翻译属性定义与自底向上翻译 LRLR分分析析器器可可以以改改造造为为一一个个翻翻译译器器，在在对对输输入入串串进进行行语法分析的同时对属性进行计算语法分析的同时对属性进行计算LRLR分析器增加分析器增加属性值（语义）栈属性值（语义）栈 1）为文法的每条规则设计相应的语义子程序；）为文法的每条规则设计相应的语义子程序；2）增加一个语义信息栈；）增加一个语义信息栈；3）在语法分析的同时做语义处理：即在用某一个）在语法分析的同时做语义处理：即在用某一个产生式进行规约的同时，调用相应的语义子程序完产生式进行规约的同时，调用相应的语义子程序完成所用规则的语义动作，并将每次动作后的值保存成所用规则的语义动作，并将每次动作后的值保存在语义栈中在语义栈中翻译步骤翻译步骤第16页/共80页 2023年2月23日 计算表达式计算表达式2+3*52+3*5第17页/共80页 2023年2月23日 状态状态ACTIONGOTOi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5GE：1 EE+T2 ET3 TT*F4 TF5 F(E)6 Fii+i*i第18页/共80页 2023年2月23日 表达式表达式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第19页/共80页 2023年2月23日 步骤状态栈 语义栈符号栈输入串动作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第20页/共80页 2023年2月23日 注意句柄归约在先，语义动作调用在后句柄归约在先，语义动作调用在后归约时，栈内句柄各符号的语义信息与句柄及归约时，栈内句柄各符号的语义信息与句柄及同时出栈，整个句柄所表示的语义信息则赋给同时出栈，整个句柄所表示的语义信息则赋给相应产生式左部非终结符号的语义变量，并让相应产生式左部非终结符号的语义变量，并让该非终结符号及语义信息同时入栈该非终结符号及语义信息同时入栈第21页/共80页生成中间代码的生成中间代码的目的目的(1)便于优化便于优化(2)便于移植便于移植(3)逻辑结构清晰逻辑结构清晰常见的中间代码常见的中间代码形式形式：后缀式后缀式三地址代码三地址代码（四元式、三元式和间接三元式（四元式、三元式和间接三元式）图形图形（抽象语法树、有向无环图）（抽象语法树、有向无环图）中间代码：一种介于中间代码：一种介于源语言和目标语言之间源语言和目标语言之间的中间语言形式的中间语言形式5.5.中间代码中间代码第22页/共80页中缀表示中缀表示后缀表示后缀表示a+b ab+a+b*c abc*+(a+b)*c ab+c*a:=b*c+b*d abc*bd*+:=特点特点1、运算对象出现的顺序和原有顺序（从左到右）相同、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值优点：简明、便于计值 后缀式后缀式第23页/共80页分别给出下列表达式的后缀表示分别给出下列表达式的后缀表示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 第24页/共80页逆波兰表示法（后缀式）逆波兰表示法（后缀式）特点：运算符直接写在其运算对象之后。不再有括号运算对象出现的次序未变求值过程简单，宜于用栈实现后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。第25页/共80页三地址代码三地址代码种类种类（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的的语语句句，否否则则顺序执行下一个语句。顺序执行下一个语句。第26页/共80页（6）过过程程调调用用语语句句param x 和和call p,n。源源程程序序中中的的过过程程调用语句调用语句p(x1，x2，xn)可以产生如下的三地址代码：可以产生如下的三地址代码：param x1param x2 param xncall p,n其中其中n为实参个数。过程返回语句形如为实参个数。过程返回语句形如return y，其中，其中y为过为过程返回的一个值。程返回的一个值。第27页/共80页（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。第28页/共80页2具体实现具体实现四元式四元式操作符操作符 操作数操作数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=T4第29页/共80页操作符操作符 左操作符数左操作符数 右操作数右操作数 表达式的三元式：表达式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)第三个三元第三个三元式中的操作数式中的操作数(1)(2)表示第表示第(1)和第和第(2)条三元式的计条三元式的计算结果。算结果。三三元式元式第30页/共80页例：例：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)三元式的执行次序用另一张三元式的执行次序用另一张表表示表表示,优化时三元式可以不优化时三元式可以不变，仅仅改变其执行顺序表变，仅仅改变其执行顺序表第31页/共80页图形表示法图形表示法无循环有向图无循环有向图(Directed Acyclic Graph(Directed Acyclic Graph，简，简称称DAG)DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAGDAG中都有一个结点中都有一个结点一个一个内部结点内部结点代表一个代表一个操作符操作符，它的孩子代表操作数，它的孩子代表操作数在一个在一个DAGDAG中代表公共子表达式的结点具有多个父结点中代表公共子表达式的结点具有多个父结点第32页/共80页例：例：x=y+y z+y z 抽象语法树抽象语法树图形表示图形表示有向无环图有向无环图第33页/共80页 2023年2月23日 练习：练习：1.1.表达式表达式a+(-b)*ca+(-b)*c的三元式的三元式 (1)(,b,_);单目运算，运算对象2为空(2)(*,(1),c)(3)(+,a,(2)第34页/共80页 2023年2月23日 三元式三元式X=a+b*c Y=d-b*c三元式表(1)(*,b,c)(2)(+,a,(1)(3)(=,x,(2)(4)(_,d,(1)(5)(=,y,(4)第35页/共80页 2023年2月23日 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第36页/共80页 2023年2月23日 3.a:=b*(-c)+b*(-c)的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc第37页/共80页 2023年2月23日 抽象语法树对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc抽象语法树*buminusc a:=b*(-c)+b*(-c)的图表示法 第38页/共80页 2023年2月23日 DAG对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5第39页/共80页 2023年2月23日 自底向上的语法制导翻自底向上的语法制导翻译译自底向上的语法制导翻译方法是在自底向上的语法分析过程自底向上的语法制导翻译方法是在自底向上的语法分析过程中逐步实现语义规则的翻译方法。在实现时注意以下几点：中逐步实现语义规则的翻译方法。在实现时注意以下几点：（1 1）自底向上的翻译的特点，栈的操作，）自底向上的翻译的特点，栈的操作，对产生式的要求对产生式的要求等等（2 2）各种程序语句的）各种程序语句的目标结构目标结构（3 3）从源结构到目标结构的变换方法（包括对）从源结构到目标结构的变换方法（包括对产生式的改造产生式的改造等）等）第40页/共80页 2023年2月23日 算术表达式和赋值语句的翻译算术表达式和赋值语句的翻译翻译步骤：翻译步骤：（1 1）分析文法的特点；）分析文法的特点；（2 2）设计一系列的语义变量、定义语义过程、）设计一系列的语义变量、定义语义过程、语义函数；语义函数；（3 3）设计每一条规则的语义子程序；）设计每一条规则的语义子程序；（4 4）增加一个语义信息栈，构造）增加一个语义信息栈，构造LRLR分析表分析表;(5)(5)语法分析同时语义处理语法分析同时语义处理.第41页/共80页 2023年2月23日 例：例：有文法有文法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(表达式的结果赋给赋值语句的左变表达式的结果赋给赋值语句的左变量量)第42页/共80页 2023年2月23日 引入语义变量,语义过程和语义函数(1)(1)语义变量语义变量:表示存放表示存放E E值的变量名在符号表中的入口值的变量名在符号表中的入口地址或临时变量的整数码地址或临时变量的整数码.(2)(2)语义函数语义函数newtemp():newtemp():申请一个临时单元申请一个临时单元,存放中间结存放中间结果果;(3)(3)语义过程语义过程emit(T=argemit(T=arg1 1 op arg op arg2 2):):产生一条四元式产生一条四元式,并添入四元式表中并添入四元式表中;(4)(4)语义过程语义过程):):审查是否出现在符号表中审查是否出现在符号表中,在在:返回地址返回地址,不在不在:返回返回NULL;NULL;(5)(5)语义函数语义函数entry(i):entry(i):回送标识符回送标识符i i在符号表中的入口在符号表中的入口地址地址.第43页/共80页 2023年2月23日 表达式的语义动作设计表达式的语义动作设计1.Ai:=E emit(entry(i)=1.Ai:=E emit(entry(i)=2.E E2.E E1 1+T =newtemp(),+T =newtemp(),)=E )=E1 1.place+T.place.place+T.place3.E T =newtemp(),3.E T =newtemp(),=)=)4.T T4.T T1 1*F =newtemp(),*F =newtemp(),)=T )=T1 1.place*F.place.place*F.place5.T F =newtemp(),5.T F =newtemp(),=)=)第44页/共80页 2023年2月23日 6.F _P =newtemp(),6.F _P =newtemp(),)=)=7.P(E)=newtemp(),7.P(E)=newtemp(),=)=)8.P I =newtemp(),8.P I =newtemp(),=Entry(i)=Entry(i)第45页/共80页 2023年2月23日 例如例如:表达式表达式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)第46页/共80页 2023年2月23日 布尔表达式的翻译布尔表达式的翻译布尔表达式布尔表达式 是由布尔运算符是由布尔运算符(and,or,not)(and,or,not)作用于布尔变量作用于布尔变量(或或常数常数)或关系表达式而形成的。或关系表达式而形成的。布尔表达式的作用：布尔表达式的作用：用作控制语句中的条件：用作控制语句中的条件：if-thenif-then、whilewhile、repeatrepeat等等逻辑赋值句中的逻辑运算逻辑赋值句中的逻辑运算第47页/共80页 2023年2月23日 布尔表达式到四元式的翻译 文法：文法：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为为关关系系表达式。表达式。布尔表达式的求值方法：布尔表达式的求值方法：通过逐步计算出各部分的值来计算整个表达式。通过逐步计算出各部分的值来计算整个表达式。利用布尔运算符的性质计算其值利用布尔运算符的性质计算其值 第48页/共80页 2023年2月23日 布尔表达式作为控制语句中的条件布尔表达式作为控制语句中的条件式式作用是用于选择下一个执行点 while E do S1E的作用是选择S1执行,还是跳过S1语句,执行S1后面的语句E有两个出口:真:S1语句假:S1后面的语句第49页/共80页 2023年2月23日 WhileWhile语句的目标结构语句的目标结构 假E的代码 真 whilleS1的代码 doJMP W.headW.head第50页/共80页 2023年2月23日 布尔初等量布尔初等量(布尔变量和关系表达式布尔变量和关系表达式)的目标结构的目标结构 由两个转移四元式构成由两个转移四元式构成,一个表示真出口一个表示真出口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)第51页/共80页 2023年2月23日 举例举例: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 (1)if ab goto (3)(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)第52页/共80页 2023年2月23日 多因子组成的布尔表达式的翻译多因子组成的布尔表达式的翻译例: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)第53页/共80页 2023年2月23日 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+1(p+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（后继语句）第54页/共80页 2023年2月23日 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)后继四元式后继四元式第55页/共80页 2023年2月23日 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)后继四元式后继四元式第56页/共80页 2023年2月23日 真出口链、假出口链、回填（真出口链、假出口链、回填（Backparch)Backparch)在多个因子组成的布尔表达式中，可能有多个因子的真出口或在多个因子组成的布尔表达式中，可能有多个因子的真出口或假出口的转移去向相同，但又不能立刻知道具体转向位置。假出口的转移去向相同，但又不能立刻知道具体转向位置。把转移方向相同的四元式链在一起，一旦发现具体转移目标，把转移方向相同的四元式链在一起，一旦发现具体转移目标，就回填。就回填。真出口用真出口用E Etruetrue来表示。来表示。假出口用假出口用E Efalsefalse来表示。来表示。回填回填BackparchBackparch（g,t)g,t)将将t t填入由填入由g g所指向的四元式的结果部分所指向的四元式的结果部分第57页/共80页 2023年2月23日 if ab c then Sif ab c then S1 1 elseS elseS2 2的真假出口回填描述的真假出口回填描述(1)if ab goto 0/*E(1)if a,C,D,(7)(5)(j,C,D,(7)(6)(j,_,_,(4)(6)(j,_,_,(4)(13)(13)(7)(j,A,B,(9)(7)(j0b0 do if xy then b:=b-1 else a:=a-1 假设四元式序列从假设四元式序列从100100开始编号开始编号100100（j,a,0,102)j,a,0,102)101 (j,_,_,0)101 (j,_,_,0)(112)(112)102 (j,b,0,104)102 (j,b,0,104)103 (j,_,_,101)103 (j,_,_,101)(112)(112)104 (j,x,y,106)104 (j,x,y,106)105 (j,_,_,0)105 (j,_,_,0)(109)(109)106(-,b,1,T106(-,b,1,T1 1)107(:=,T107(:=,T1 1,_,b),_,b)108(j,_,_,100)108(j,_,_,100)109(j,a,1,T109(j,a,1,T2 2)110(:=,T110(:=,T2 2,_.a),_.a)111(j,_,_,100)111(j,_,_,100)112112第71页/共80页 2023年2月23日 文法文法GS:SSaAGS:SSaAA A AAbB AAbBB B BcSd BcSde e(1)(1)证明证明AacAbcBaAdbedAacAbcBaAdbed是文法的一个句型是文法的一个句型.(2)(2)请写出该句型的所有短语、素短语及句柄。请写出该句型的所有短语、素短语及句柄。（3 3）为文法）为文法GS GS 的产生式构造相应的翻译子程序，使的产生式构造相应的翻译子程序，使句型句型AacAbcBaAdbedAacAbcBaAdbed经该翻译方案翻译后，输出为。经该翻译方案翻译后，输出为。第72页/共80页 2023年2月23日 文法及相应的翻译方案如下:SbTc print”1”Sa print”2”TR print”3”RR/S print”4”RS print”5”对于输入符号串对于输入符号串bR/bTc/bSc/ac,该符号该符号串的输出是什么串的输出是什么?输出为输出为1453142431归约的次序为归约的次序为:(1)SbTc (1)(2)RR/S (4)(3)RS (5)(4)TR (3)(5)SbTc (1)(6)RR/S (4)(7)Sa (2)(8)RR/S (4)(9)TR (3)(10)SbTc (1)第73页/共80页 2023年2月23日 数组赋值语句的翻译数组数组:相同类型数据的相同类型数据的N N维复合结构维复合结构.数组中每一个元素在计算机中占有相同的存储空数组中每一个元素在计算机中占有相同的存储空间间数组分为静态数组和动态数组数组分为静态数组和动态数组数组的一般定义数组的一般定义:AlAl1 1:u:u1 1,l,l2 2:u:u2 2,l,lk k:u:uk k,l,ln n:u:un n 其中其中:A:A 是数组名是数组名l lk k是数组下标的下限是数组下标的下限,u,uk k是上限是上限 k k是数组的维是数组的维数数数组在内存中是用一片连续的存储单元来表示数组在内存中是用一片连续的存储单元来表示.数组的定义和存储第74页/共80页 2023年2月23日 一维数组一维数组:al:al1 1:u:u1 1(l(l1 1iuiu1 1)每个元素的宽度为每个元素的宽度为w,w,地址为地址为:b b1 1+(i-l+(i-l1 1)*w)*w是数组是数组a a的第一个元素的相对地址的第一个元素的相对地址,称为起始地称为起始地址址可以表示为可以表示为:i*w+(bi*w+(b1 1-l-l1 1*w)*w)令令C=bC=b1 1-l-l1 1*w*w(可以计算出来可以计算出来)故故:ai=i*w+cai=i*w+c数组元素的地址表示数组元素的地址表示第75页/共80页 2023年2月23日 数组元素的地址表示二维数组二维数组AlAl1 1:u:u1 1,l,l2 2:u:u2 2:事先约定存储顺序事先约定存储顺序按行存储、按列存储按行存储、按列存储数组元素数组元素aiai1 1,i,i2 2 地址可表示为：地址可表示为：D=bap+vapD=bap+vapbap:bap:固定部分，在编译时可以计算出来固定部分，在编译时可以计算出来,a,a是数组元素是数组元素首地址，首地址，d d2 2是第二维的维长，是第二维的维长，c=lc=l1 1d d2 2+l+l2 2 Bap=a-cBap=a-cvap:vap:可变部分可变部分Vap=iVap=i1 1d d2 2+i+i2 2第76页/共80页 2023年2月23日 数