语法制导翻译技术和中间代码生成幻灯片.ppt

《语法制导翻译技术和中间代码生成幻灯片.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译技术和中间代码生成幻灯片.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语法制导翻译技术和中间代码生成第1页，共83页，编辑于2022年，星期二第第5 5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成1.1.要求明确语义分析的要求明确语义分析的任务任务2.2.明确明确属性文法属性文法和和语法制导翻译语法制导翻译的含义的含义3.3.明确明确自底向上和自顶向下自底向上和自顶向下语法制导翻译的区语法制导翻译的区别和特点别和特点4.明确明确生成中间代码的目的，中间代码的几种生成中间代码的目的，中间代码的几种形式形式教学目标教学目标第2页，共83页，编辑于2022年，星期二属性文法属性文法语法制导翻译法的基本思想语法制导翻译法的基本思想常见的中间代码常见的

2、中间代码各种不同语法结构的语法制导翻译技术各种不同语法结构的语法制导翻译技术教学内容教学内容第3页，共83页，编辑于2022年，星期二词法分析，语法分析词法分析，语法分析：解决单词和语言成分的识别及词：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器来描述。给定一组产生式，我们能够很容易地将其分析器构造出来。构造出来。本章要介绍的是本章要介绍的是语义分析和中间代码生成技术语义分析和中间代码生成技术。程序语言中间代码目标代码程序语言中间代码目标代码翻译翻译翻译翻译第4

3、页，共83页，编辑于2022年，星期二根据语义规则对识别出的各种语法成分析其含义，进行根据语义规则对识别出的各种语法成分析其含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。初步翻译，生成相应的中间代码或直接生成目标代码。第一，审查每个语法结构的静态语义，即检查语法结构合法的程序第一，审查每个语法结构的静态语义，即检查语法结构合法的程序是否真正有意义。也称静态语义检查。是否真正有意义。也称静态语义检查。（类型检查、控制流的检查、（类型检查、控制流的检查、一致性检查、相关名字的检查）一致性检查、相关名字的检查）第二，如果静态语义正确，语义处理则要执行真正的翻译，要第二，如果静态语义正确，

4、语义处理则要执行真正的翻译，要么生成中间代码，要么生成实际的目标代码。（么生成中间代码，要么生成实际的目标代码。（说明性语句：说明性语句：填符号表；可执行性语句：生成中间代码）填符号表；可执行性语句：生成中间代码）语义分析的任务语义分析的任务第5页，共83页，编辑于2022年，星期二类型检查类型检查。控制流检查控制流检查，确保控制语句有合法的转向点。例如，确保控制语句有合法的转向点。例如，C语言中的语言中的break语句使控制跳离包括该语句的最小的语句使控制跳离包括该语句的最小的switch，while或或for语句。如果不存在包括它的这样的语语句。如果不存在包括它的这样的语句，则应报错。句，

5、则应报错。静态语义检查静态语义检查第6页，共83页，编辑于2022年，星期二静态语义检查静态语义检查一致性检查一致性检查。很多情况下要求对象只能被定义一次。很多情况下要求对象只能被定义一次。例如，语言中规定一个标识符在同一作用域中只能被例如，语言中规定一个标识符在同一作用域中只能被说明一次，同一说明一次，同一case语句的标号不能相同，枚举类型的语句的标号不能相同，枚举类型的元素不能重复出现等。元素不能重复出现等。相关名字检查相关名字检查。有的语言中有时规定，同一名字必须。有的语言中有时规定，同一名字必须出现两次或多次。例如，出现两次或多次。例如，Ada语言中，循环或程序块可以语言中，循环或程

6、序块可以有一个名字，它出现在这些结构的开头和结尾，如同语句有一个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配对情况。括号一般，编译程序必须检查它们的配对情况。第7页，共83页，编辑于2022年，星期二附加了一组附加了一组属性属性和和运算（语义）规则运算（语义）规则的的文法文法 5.2 属性文法属性文法文法符号文法符号X的属性的属性t常用常用X.t来表示来表示 语义规则是根据产生式所语义规则是根据产生式所蕴涵的语义蕴涵的语义操作建立起来的，并与操作建立起来的，并与语义分析的目标语义分析的目标有关有关不同的不同的产生式产生式对应不同的语义规则对应不同的语义规则不同

7、的不同的分析目标分析目标也对应不同的语义规则也对应不同的语义规则 1.属性的表示属性的表示2.语义规则语义规则的表示的表示语义信息语义信息语义之间的关系语义之间的关系静态语义检查、符号表操作、静态语义检查、符号表操作、代码生成及打印各种错误信代码生成及打印各种错误信息息 第8页，共83页，编辑于2022年，星期二属性文法属性文法属性文法的形式定义：AG：AG=（G，V，E）G:上下文无关文法;V:属性的有穷集合;每一个属性与某一个文法符号相关联；用文法符号属性表示E:表示属性的断言或谓词的有穷集合(语义规则);每一个断言与文法的某个产生式相关联)属性:综合属性(自下而上传递信息)、继承属性（自

8、上而下传递信息)第9页，共83页，编辑于2022年，星期二 非终结符非终结符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产生式产生式例例5.15.1第10页，

9、共83页，编辑于2022年，星期二语法制导翻译的过程语法制导翻译的过程语法制导翻译：语法制导翻译：将将语义规则语义规则与与语法规则语法规则相结合，在相结合，在语法语法分析分析的过程中通过执行的过程中通过执行语义动作语义动作，计算语义属性值，从而，计算语义属性值，从而完成预定的翻译工作。完成预定的翻译工作。第11页，共83页，编辑于2022年，星期二自底向上语法自底向上语法制导翻译制导翻译自顶向下语法自顶向下语法制导翻译制导翻译语法制导翻译的实现语法制导翻译的实现第12页，共83页，编辑于2022年，星期二语法制导翻译分为两种语法制导翻译分为两种处理方法处理方法：（1）语法制导定义（自底向上）：

10、）语法制导定义（自底向上）：对每个产生式编制一个语义子程序，在进行语法分析的过程中，对每个产生式编制一个语义子程序，在进行语法分析的过程中，当一个产生式获得匹配时当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。不必规定翻译顺序。（2）翻译方案（自顶向下）：）翻译方案（自顶向下）：在产生式右部的适当位置，插入相应的语义动作，按照分析在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是

11、一种的进程，执行遇到的语义动作。这是一种动作与分析交错动作与分析交错的实的实现方案。现方案。第13页，共83页，编辑于2022年，星期二输入符号串输入符号串 分析树分析树执行执行语义规则语义规则 翻译结果翻译结果翻译步骤翻译步骤（）从分析树得到描述结点属性间依赖关系的（）从分析树得到描述结点属性间依赖关系的依赖图依赖图，由依赖图得，由依赖图得到语义规则的到语义规则的计算次序计算次序（1）分析输入符号串，建立）分析输入符号串，建立分析语法树分析语法树（）进行语义规则的计算，得到翻译结果（）进行语义规则的计算，得到翻译结果 第14页，共83页，编辑于2022年，星期二语法制导定义语法制导定义对每个

12、产生式编制一个对每个产生式编制一个语义子程序语义子程序在进行语法分析的过程中，在进行语法分析的过程中，当一个产生式获得匹配时当一个产生式获得匹配时，就调用相应，就调用相应的语义子程序实现语义检查与翻译的语义子程序实现语义检查与翻译综合属性综合属性继承属性继承属性自底向上自底向上传传递信息递信息自顶向下（自左向自顶向下（自左向右）右）传递信息传递信息第15页，共83页，编辑于2022年，星期二 print(E.val)print(E.val)打印由打印由E E产生的算术表达式的值，产生的算术表达式的值，可认为这条规则定义了可认为这条规则定义了L L的一个的一个虚属性虚属性。L EE E1+TE

13、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.综合属性综合属性语语 义义 规规 则则产生式产生式第16页，共83页，编辑于2022年，星期二一个结点的综合属性值是一个结点的综合属性值是其其子结点子结点的某些属性来的某些属性来决定的决定的+3*4+3*4的注释分析树的注释分析树通常使用通常使用自底向上自底向上的分析方法的分析方法在在每个结点每个结点处使用语义规则来计处使用语义规则来计算综合属性值算综合

14、属性值当一个当一个产生式获得匹配产生式获得匹配时，就时，就调用相应的语义子程序调用相应的语义子程序从从叶结点到根结点叶结点到根结点进行计算进行计算 只含有只含有综合属性综合属性的语法制导定的语法制导定义称为义称为S S属性定义属性定义第17页，共83页，编辑于2022年，星期二S属性定义与自底向上翻译属性定义与自底向上翻译 LRLR分分析析器器可可以以改改造造为为一一个个翻翻译译器器，在在对对输输入入串串进进行语法分析的同时对属性进行计算行语法分析的同时对属性进行计算LRLR分析器增加分析器增加属性值（语义）栈属性值（语义）栈 首先，为文法的每条规则设计相应的语义子程序；首先，为文法的每条规则

15、设计相应的语义子程序；增加一个语义信息栈；增加一个语义信息栈；在语法分析的同时做语义处理：即在用某一个产生式在语法分析的同时做语义处理：即在用某一个产生式进行规约的同时，调用相应的语义子程序完成所用规进行规约的同时，调用相应的语义子程序完成所用规则的语义动作，并将每次动作后的值保存在语义栈中则的语义动作，并将每次动作后的值保存在语义栈中翻译步骤翻译步骤第18页，共83页，编辑于2022年，星期二计算表达式2+3*5第19页，共83页，编辑于2022年，星期二状状态态ACTIONGOTOi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r

16、6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5GE：1 EE+T2 ET3 TT*F4 TF5 F(E)6 Fii+i*i第20页，共83页，编辑于2022年，星期二表达式2+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第21页，共83页，编辑于2022年，星期二步骤状态栈 语义栈符号栈输入串动作701

17、63_ 2 _ 3$E+F*5$r480169_ 2 _ 3$E+T*5$S7901697_ 2 _ 3 _$E+T*5$S510 016975 _ 2 _ 3 _ _$E+T*5$r61101697(10)_ 2 _ 3 _ 5$E+T*F$r312 0169_ 2 _ 15$E+T$r113 01_ 17$E$acc第22页，共83页，编辑于2022年，星期二注意注意句柄归约在先，语义动作调用在后归约时，栈内句柄各符号的语义信息与句柄及同时出栈，整个句柄所表示的语义信息则赋给相应产生式左部非终结符号的语义变量，并让该非终结符号及语义信息同时入栈第23页，共83页，编辑于2022年，星期二生

18、成中间代码的生成中间代码的目的目的(1)便于优化便于优化(2)便于移植便于移植(3)逻辑结构清晰逻辑结构清晰常见的中间代码常见的中间代码形式形式：后缀式后缀式三地址代码三地址代码（四元式、三元式和间接三元式（四元式、三元式和间接三元式）图形图形（抽象语法树、有向无环图）（抽象语法树、有向无环图）中间代码：一种介于中间代码：一种介于源语言和目标语言之间源语言和目标语言之间的中间语言形式的中间语言形式5.5.中间代码中间代码第24页，共83页，编辑于2022年，星期二中缀表示中缀表示后缀表示后缀表示a+b ab+a+b*c abc*+(a+b)*c ab+c*a:=b*c+b*d abc*bd*+

19、:=特点特点1、运算对象出现的顺序和原有顺序（从左到右）相同、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值优点：简明、便于计值 后缀式后缀式第25页，共83页，编辑于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*+-:=

20、ac=bd=abc+ad ab+e 第26页，共83页，编辑于2022年，星期二逆波兰表示法（后缀式）逆波兰表示法（后缀式）特点：运算符直接写在其运算对象之后。不再有括号运算对象出现的次序未变求值过程简单，宜于用栈实现后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。第27页，共83页，编辑于2022年，星期二三地址代码三地址代码种类种类（1）x=y op z形式的赋值语句，其中形式的赋值语句，其中op是二元运算符。是二元运算符。（2）x=op y形式的赋值语句，其中形式的赋值语句，其中

21、op是一元运算符。是一元运算符。（3）x=y形式的赋值语句。形式的赋值语句。（4）无无条条件件转转移移语语句句goto L，表表示示下下一一个个要要执执行行的的语语句句是是标标号为号为L的语句。的语句。（5）条条件件转转移移语语句句if x rop y goto L中中，rop为为关关系系运运算算符符，如如果果x和和y满满足足关关系系rop，就就转转而而执执行行标标号号为为L的的语语句句，否否则则顺顺序序执执行行下下一个语句。一个语句。第28页，共83页，编辑于2022年，星期二（6）过过程程调调用用语语句句param x 和和call p,n。源源程程序序中中的的过过程程调调用用语语句句p(

22、x1，x2，xn)可以产生如下的三地址代码：可以产生如下的三地址代码：param x1param x2 param xncall p,n其中其中n为实参个数。过程返回语句形如为实参个数。过程返回语句形如return y，其中，其中y为过程返为过程返回的一个值。回的一个值。第29页，共83页，编辑于2022年，星期二（7）变址赋值：）变址赋值：x=yi，把从，把从y开始的第开始的第i个存储单元的值赋给个存储单元的值赋给x。xi=y，把，把y的值赋给的值赋给x开始的第开始的第i个存储单元。个存储单元。其中，其中，x，y和和i都代表数据对象。都代表数据对象。（8）地址和指针赋值：）地址和指针赋值：x

23、=&y，把，把y的地址赋给的地址赋给x。x=y，把，把y指示的地址单元中的内容赋给指示的地址单元中的内容赋给x。x=y，把，把x指向的存储单元的值置为指向的存储单元的值置为y。第30页，共83页，编辑于2022年，星期二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+

24、DT3=T1+T2T4=T3-EX=T4第31页，共83页，编辑于2022年，星期二操作符操作符 左操作符数左操作符数 右操作数右操作数 表达式的三元式：表达式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)第三个三元第三个三元式中的操作数式中的操作数(1)(2)表示第表示第(1)和第和第(2)条三元式的计条三元式的计算结果。算结果。三三元式元式第32页，共83页，编辑于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)不便于代码

25、优化：删除某不便于代码优化：删除某些三元式后可能需作一系些三元式后可能需作一系列的修改列的修改 三元式三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)间接三元式间接三元式执行顺序执行顺序(1)(2)(3)(4)(1)(5)三元式的执行次序用另一张三元式的执行次序用另一张表表示表表示,优化时三元式可以不优化时三元式可以不变，仅仅改变其执行顺序表变，仅仅改变其执行顺序表第33页，共83页，编辑于2022年，星期二图形表示法图形表示法无循环有向图无循环有向图(Directed Acyclic Graph(Directed Acyclic Grap

26、h，简称，简称DAG)DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAGDAG中都有一个结点中都有一个结点一个一个内部结点内部结点代表一个代表一个操作符操作符，它的孩子代表操作，它的孩子代表操作数数在一个在一个DAGDAG中代表公共子表达式的结点具有多个中代表公共子表达式的结点具有多个父结点父结点第34页，共83页，编辑于2022年，星期二例：例：x=y+y z+y z 抽象语法树抽象语法树图形表示图形表示有向无环图有向无环图第35页，共83页，编辑于2022年，星期二表达式a+(-b)*c的三元式 (1)(,b,_);单目运算，运算对象2为空(2)(*,(1),c)(3)(+

27、,a,(2)第36页，共83页，编辑于2022年，星期二三元式X=a+b*c Y=d-b*c三元式表(1)(*,b,c)(2)(+,a,(1)(3)(=,x,(2)(4)(_,d,(1)(5)(=,y,(4)第37页，共83页，编辑于2022年，星期二四元式(三地址代码）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第38页，共83页，编辑于2022年，星期二 a:=b*(-c)+b*(-c)a:=b*(-c)+b*(-

28、c)的图表示法的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc第39页，共83页，编辑于2022年，星期二抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc抽象语法树抽象语法树*buminusc第40页，共83页，编辑于2022年，星期二DAG对应的代码：对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代

29、码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5第41页，共83页，编辑于2022年，星期二 属性翻译文法的应用 综合属性与自下而上定值综合属性与自下而上定值 每个非终结符的属性值都是根据位于其下面那些符号的属性值来确定的，即按一种自下而上的方式来确定的。继承属性和自上而下定值继承属性和自上而下定值 非终结符的属性值或者根据其上层非终结符的属性来确定或者根据产生式右部其它符号的属性来确定。这种属性值是根据自上而下方式确定的。第42页，共83页，编辑于2022年，星期二自底向上的语法制导翻译自底向上的语法制导翻译方法是在自底向上的语法分析过程中逐步

30、实现语义规则的翻译方法。在实现时注意以下几点：（1）自底向上的翻译的特点，栈的操作，对产生式的要求等（2）各种程序语句的目标结构（3）从源结构到目标结构的变换方法（包括对产生式的改造等）第43页，共83页，编辑于2022年，星期二算术表达式和赋值语句的翻译翻译步骤：（1）分析文法的特点；（2）设计一系列的语义变量、定义语义过程、语义函数；（3）设计每一条规则的语义子程序；（4）增加一个语义信息栈，构造LR分析表;(5)语法分析同时语义处理.第44页，共83页，编辑于2022年，星期二例：有文法GA：1.Ai:=E2.E E+TT3.T T*FF4.F P5.P i(E)简单算术表达式的计值顺序

31、与四元式出现的顺序相同,因此目标代码的顺序(结构)为:(1)先生成E的代码(一系列顺序执行的四元式)(2)把E的值赋给变量i(表达式的结果赋给赋值语句的左变量)第45页，共83页，编辑于2022年，星期二引入语义变量,语义过程和语义函数(1)语义变量E.place:表示存放E值的变量名在符号表中的入口地址或临时变量的整数码.(2)语义函数newtemp():申请一个临时单元,存放中间结果;(3)语义过程emit(T=arg1 op arg2):产生一条四元式,并添入四元式表中;(4)语义过程lookup(i.name):审查i.name是否出现在符号表中,在:返回地址,不在:返回NULL;(5

32、)语义函数entry(i):回送标识符i在符号表中的入口地址.第46页，共83页，编辑于2022年，星期二表达式的语义动作设计1.Ai:=Eemit(entry(i)=E.place2.E E1+TE.place=newtemp(),emit(E.place)=E1.place+T.place3.E T E.place=newtemp(),emit(E.place=T.place)4.T T1*FT.place=newtemp(),emit(T.place)=T1.place*F.place5.T F T.place=newtemp(),emit(T.place=F.place)第47页，共8

33、3页，编辑于2022年，星期二6.F _P F.place=newtemp(),emit(F.place)=P.place7.P(E)P.place=newtemp(),emit(P.place=E.place)8.P iP.place=newtemp(),emit(P.place=Entry(i)第48页，共83页，编辑于2022年，星期二例如:表达式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)第49页，共83页，编辑于2022年，星期

34、二布尔表达式的翻译布尔表达式 是由布尔运算符(and,or,not)作用于布尔变量(或常数)或关系表达式而形成的。布尔表达式的作用：用作控制语句中的条件：if-then、while、repeat等逻辑赋值句中的逻辑运算第50页，共83页，编辑于2022年，星期二布尔表达式到四元式的翻译布尔表达式到四元式的翻译 文法：EEEEEE(E)idE rop E 其中，(and)、(or)、(not)为布尔（逻辑）运算符；rop为关系运算符（，=，）；id为布尔（逻辑）变量或布尔（逻辑）常数；E rop E为关系表达式。布尔表达式的求值方法：通过逐步计算出各部分的值来计算整个表达式。利用布尔运算符的性质

35、计算其值 第51页，共83页，编辑于2022年，星期二布尔表达式作为控制语句中的条件式作用是用于选择下一个执行点 while E do S1E的作用是选择S1执行,还是跳过S1语句,执行S1后面的语句E有两个出口:真:S1语句假:S1后面的语句第52页，共83页，编辑于2022年，星期二While语句的目标结构 假E的代码 真 whilleS1的代码 doJMP W.headW.head第53页，共83页，编辑于2022年，星期二布尔初等量(布尔变量和关系表达式)的目标结构 由两个转移四元式构成,一个表示真出口Li,另一个表示假出口Lj,设E是一布尔变量,它的目标结构为:(1)if E got

36、o Li (jumpt,E,_,Li)(jnz,A,_,Li)(2)if E1 rop E2 goto Li (jump,E1 ,E2 ,Li)(jrop,E1,E2,Li)例:(j,a,b,p)(3)goto Lj (jump Lj)(j,_,_,Lj)第54页，共83页，编辑于2022年，星期二举例:if ab then A:=x+y的四元式序列 if ab goto Li(真出口)goto Lj (假出口)Li:S的第一个四元式S的最后一个四元式Lj:S 后面的语句(1)if ab goto (3)(2)goto (5)(3)T1:=x+y(4)A:=T1(5)第55页，共83页，编辑于

37、2022年，星期二 多因子组成的布尔表达式的翻译例:if ab c then S1 else S2分析结果如下:当ab为真,执行S1,不需要计算c的值当ab为假,计算c的值,c为真:执行S1,为假:执行S2当ab与c分别为真时,程序转向一致,真出口相同(S1)当ab与c分别为假时,程序转向一致,假出口相同(S2)第56页，共83页，编辑于2022年，星期二if ab c then S1 elseS2的四元式序列(1)if ab goto S1的第一条语句(5)(2)goto(3)(3)if c goto S1的第一条语句(5)(4)goto S2的第一条语句(p+1(5)关于S1的四元式序列

38、(p)Goto q(p+1)关于S2的四元式序列 (q)后继四元式 目标结构E的代码 TFS1的代码JUMP SS2的代码S（后继语句）第57页，共83页，编辑于2022年，星期二 if E then S1 else S2的四元式序列(1)if E goto(3)(2)goto(S2的第一个四元式)(p+1)(3)关于S1的四元式序列(p)goto r(执行完S1后转出)(p+1)关于S2的四元式序列(r)后继四元式第58页，共83页，编辑于2022年，星期二 while E do S1的四元式序列(1)if E goto(3)(2)goto(S1后面的语句)(p+1)(3)关于S1的四元式序

39、列(p)goto(1)(p+1)后继四元式第59页，共83页，编辑于2022年，星期二真出口链、假出口链、回填（Backparch)在多个因子组成的布尔表达式中，可能有多个因子的真出口或假出口的转移去向相同，但又不能立刻知道具体转向位置。把转移方向相同的四元式链在一起，一旦发现具体转移目标，就回填。真出口用E Etruetrue来表示。假出口用E Efalsefalse来表示。回填BackparchBackparch（g,t)g,t)将t填入由g所指向的四元式的结果部分第60页，共83页，编辑于2022年，星期二if ab c then S1 elseS2的真假出口回填描述(1)if a,C,

40、D,(7)(6)(j,_,_,(4)(13)(7)(j0b0 do if xy then b:=b-1 else a:=a-1 假设四元式序列从100开始编号100（j,a,0,102)101 (j,_,_,0)(112)102 (j,b,0,104)103 (j,_,_,101)(112)104 (j,x,y,106)105 (j,_,_,0)(109)106(-,b,1,T1)107(:=,T1,_,b)108(j,_,_,100)109(j,a,1,T2)110(:=,T2,_.a)111(j,_,_,100)112第74页，共83页，编辑于2022年，星期二文法GS:SSaAA AAb

41、BB BcSde(1)证明AacAbcBaAdbed是文法的一个句型.(2)请写出该句型的所有短语、素短语及句柄。（3）为文法GS 的产生式构造相应的翻译子程序，使句型AacAbcBaAdbed经该翻译方案翻译后，输出为131042521430。第75页，共83页，编辑于2022年，星期二文法及相应的翻译方案如下: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)

42、(4)TR (3)(5)SbTc (1)(6)RR/S (4)(7)Sa (2)(8)RR/S (4)(9)TR (3)(10)SbTc (1)第76页，共83页，编辑于2022年，星期二数组赋值语句的翻译第77页，共83页，编辑于2022年，星期二数组的定义和存储数组:相同类型数据的N维复合结构.数组中每一个元素在计算机中占有相同的存储空间数组分为静态数组和动态数组数组的一般定义:Al1:u1,l2:u2,lk:uk,ln:un其中:A 是数组名lk是数组下标的下限,uk是上限 k是数组的维数数组在内存中是用一片连续的存储单元来表示.第78页，共83页，编辑于2022年，星期二数组元素的地址

43、表示一维数组:al1:u1(l1iu1)每个元素的宽度为w,地址为:b1+(i-l1)*w是数组a的第一个元素的相对地址,称为起始地址可以表示为:i*w+(b1-l1*w)令C=b1-l1*w(可以计算出来)故:ai=i*w+c第79页，共83页，编辑于2022年，星期二数组元素的地址表示二维数组Al1:u1,l2:u2:事先约定存储顺序按行存储、按列存储数组元素ai1,i2地址可表示为：D=bap+vapbap:固定部分，在编译时可以计算出来,a是数组元素首地址，d2是第二维的维长，c=l1d2+l2 Bap=a-cvap:可变部分Vap=i1d2+i2第80页，共83页，编辑于2022年，

44、星期二数组元素的四元式:bapvap临时单元T=bap T1=vap（1）数组元素的引用 X:=TT1四元式为：（=，TT1，-，X）（2）数组元素的赋值 TT1:=X四元式为：（=，X，-，TT1）第81页，共83页，编辑于2022年，星期二数组元素翻译举例设一数组为A:array1.10,1.20 of reald1=10,d2=20 c=l1d2+l2=21赋值句AI,J+2:=10.0+AI+1,J+1的四元式序列为：K+0:(+,J,2,T1)K+1:(*,I,20,T2)/*计算vap=i1d2+i2K+2:(+,T2,T1,T1)K+3:(-,a,21,T3)/*计算bap=a-c c=21K+4:(+,I,1,T4)/*计算AI+1,J+1的地址K+5:(+,J,1,T5)第82页，共83页，编辑于2022年，星期二K+6:(*,T4,20,T6)K+7:(+,T6,T5,T5)/*T5为vapK+8:(,a,21,T7)/*T7为bapK+9:(=,T7T5,-,T8)/T8为AI+1,J+1的值K+10:(+,10.0,T8,T9)K+11:(=,T9,-,T3T2)第83页，共83页，编辑于2022年，星期二