程序设计语言与编译原理-第九章语义分析和中间代码生成课件.ppt

1、程序设计语言与编译本章主要讨论对语法正确的句子进行语义分析；本章主要讨论对语法正确的句子进行语义分析；语义分析的目的是生成代码并实现句子的语义；语义分析的目的是生成代码并实现句子的语义；语义分析生成的不是最终的目标代码，而是便于语义分析生成的不是最终的目标代码，而是便于实现优化的某种中间代实现优化的某种中间代码；码；程序设计语言与编译第一节第一节 语义分析概论语义分析概论一一.语义分析的主要工作语义分析的主要工作语义检查语义检查:主要进行一致性检查和越界检查。语义处理语义处理:对说明语句：登记信息;对可执行语句：生成中间代码。一致性检查一致性检查：（1）表达式中操作数是否保持类型一致；（2）赋

2、值语句的左右两边是否类型一致；（3）形、实参数类型是否一致；（4）数组元素与数组说明是否一致。越界检查越界检查：数组下标是否越界；子界类型是否越界等等。程序设计语言与编译u 语义分析时语义检查的分类：语义分析时语义检查的分类：u动态语义检查动态语义检查u 需要生成相应的目标代码，它是在运行时进行的；需要生成相应的目标代码，它是在运行时进行的；u 例如：除零溢出错误。例如：除零溢出错误。u静态语义检查静态语义检查u 在编译时完成的，它涉及以下几个方面：在编译时完成的，它涉及以下几个方面：u (1)(1)类型检查类型检查u (2)(2)控制流检查控制流检查u (3)(3)一致性检查一致性检查程序设

3、计语言与编译各种条件表达式的类型不是布尔类型各种条件表达式的类型不是布尔类型;运算符的分量类型不相容运算符的分量类型不相容;赋值语句左右类型不相容赋值语句左右类型不相容;形、实参类型不相容形、实参类型不相容;函数说明和函数返回类型不相容函数说明和函数返回类型不相容;int x;int x;float f();float f();x=f();x=f();符合变量声明的语法、语义符合函数声明的语法、语义符合赋值语句的语法、不符合语义(1)类型检查程序设计语言与编译u (2)(2)控制流检查控制流检查u 用以保证控制语句有合法的转向点。如用以保证控制语句有合法的转向点。如C C语语言中不允许言中不允

4、许gotogoto语句转入语句转入casecase语句流；语句流；breakbreak语句需语句需寻找包含它的最小寻找包含它的最小switchswitch、whilewhile或或forfor语句方可找语句方可找到转向点，否则出错。到转向点，否则出错。u (3)(3)一致性检查一致性检查u 如在相同作用域中标识符只能说明一次、如在相同作用域中标识符只能说明一次、casecase语句的标号不能相同、语句的标号不能相同、函数调用参数个数要相函数调用参数个数要相同同等。等。程序设计语言与编译常见的语义错误u声明和使用相关的语义错误声明和使用相关的语义错误标识符没有声明标识符没有声明;重复声明重复声明

5、;u如何检查如何检查?每当遇到新声明的标识符每当遇到新声明的标识符,查符号表查符号表如果当前有效的所有标识符中有相同名字的如果当前有效的所有标识符中有相同名字的,则则是重复声明错误是重复声明错误;否则生成它的属性信息否则生成它的属性信息,保存到符号表中保存到符号表中;每当遇到标识符的使用每当遇到标识符的使用,查符号表查符号表如果没有找到如果没有找到,说明该标识符没有声明说明该标识符没有声明;否则否则,得到该标识符的属性得到该标识符的属性,进行进一步分析进行进一步分析;程序设计语言与编译u 语义分析阶段只产生中间代码而不语义分析阶段只产生中间代码而不生成目标代码的方法使编译程序的开发变生成目标代

6、码的方法使编译程序的开发变得较为容易，但语义分析不像词法分析和得较为容易，但语义分析不像词法分析和语法分析那样可以分别用正规文法和上下语法分析那样可以分别用正规文法和上下文无关文法描述。文无关文法描述。u 由于语义是上下文有关的，因此语由于语义是上下文有关的，因此语义的形式化描述是非常困难的义的形式化描述是非常困难的，目前较为目前较为常见的是用常见的是用属性文法属性文法作为描述程序语言语作为描述程序语言语义的工具，并采用义的工具，并采用语法制导翻译的方法语法制导翻译的方法完完成对语法成分的翻译工作。成对语法成分的翻译工作。程序设计语言与编译二二.语法制导翻译语法制导翻译语法制导翻译语法制导翻译

7、：在语法分析过程中，根据每个产生式对应的语义子程序（语义动作）进行翻译（生成中间代码）的方法称为语法制导翻译。为每个产生式配上一个语义子程序,完成语义检查和语义处理：在语法分析过程中,当用一个产生式进行匹配匹配或归约归约时,就调用相应的语义程序进行翻译翻译。语义检查和语义处理核心是生成相应的中间代码 程序设计语言与编译 在描述语义动作时，需要赋予每个文法符号以各种不同的“值”，这些值统称为“语义值”.如，“类型类型”，“种 属种 属”，“地 址地 址”或“代 码代 码”等。通 常 用X.TYPE,X.CAT,X.VAL来表示这些值。例：EE+EE0E1EE1+E2E.VAL:=E1.VAL+E

8、2.VALE0E.VAL:=1E1E.VAL:=0EE+EE+E+EE+E+E+E1+0+1+1+0每使用一次产生式则调用相应的语义子程序，则推导完成时，语义值E.VAL也计算出来。三、语义值三、语义值程序设计语言与编译10 中间语言中间语言(复杂性界于源语言和目标语言复杂性界于源语言和目标语言之间之间)的好处：的好处：便于进行与机器无关的代码优化工作便于进行与机器无关的代码优化工作 易于移植易于移植 使编译程序的结构在逻辑上更为简单明确使编译程序的结构在逻辑上更为简单明确 源语言源语言程序程序目标语目标语言程序言程序中间语中间语言程序言程序CompilerFront EndCompilerB

9、ack End四、中间代码四、中间代码程序设计语言与编译11 常用的中间语言：常用的中间语言：后缀式，逆波兰表示后缀式，逆波兰表示 图表示：图表示：DAG、抽象语法树、抽象语法树 三地址代码三地址代码 三元式三元式 四元式四元式 间接三元式间接三元式程序设计语言与编译四元式形式:(op,ARG1,ARG2,RESULT)op运算符 ARG1第一运算量 ARG2第二运算量 RESULT结果 程序设计语言与编译如如:A:=-B:A:=-B*(C+D)(C+D)(,B,_,t1)(+,C,D,t2)(*,t1,t2,t3)(:=,t3,_,A)翻译成：翻译成：四元式出现顺序和表达式计值顺序一致四元式

10、出现顺序和表达式计值顺序一致;四元式之间的联系通过临时变量来实现。四元式之间的联系通过临时变量来实现。程序设计语言与编译14五、三地址代码五、三地址代码三地址代码是由下面一般形式的语句构三地址代码是由下面一般形式的语句构成的序列：成的序列：x:=y op z，其中，其中,x,y,z为名字、为名字、常数或编译时产生的临时变量，常数或编译时产生的临时变量，op代表运算代表运算符号，如定点运算符、浮点运算符、逻辑运符号，如定点运算符、浮点运算符、逻辑运算符等，每个语句的右边只能有一个运算符，算符等，每个语句的右边只能有一个运算符，如源语言表达式如源语言表达式 x+y z可翻译为：可翻译为：T1:=y

11、 zT2:=x+T1程序设计语言与编译15三地址代码所表示的语句通常包含三个三地址代码所表示的语句通常包含三个地址，两个操作数，一个结果。实际实现时，地址，两个操作数，一个结果。实际实现时，三地址代码中的名字将由指向符号表中相应三地址代码中的名字将由指向符号表中相应名字入口的指针所代替。名字入口的指针所代替。程序设计语言与编译16三地址语句类似汇编代码，可带有符号标号，三地址语句类似汇编代码，可带有符号标号，而且存在各种控制流语句，其种类大致有：而且存在各种控制流语句，其种类大致有：形如形如x:=y op z的赋值语句，的赋值语句，op为二目算术为二目算术算符或逻辑算符；算符或逻辑算符；赋值语

12、句赋值语句x:=op y，op为一元算符，如一元为一元算符，如一元减减uminus,not,移位及转换算符移位及转换算符(如将定点如将定点数转换为浮点数数转换为浮点数)；赋值语句赋值语句x:=y；无条件转移语句无条件转移语句 goto L；程序设计语言与编译17 地址和指针赋值，地址和指针赋值，x:=&y,x:=y和和 x:=y。条件转移语句条件转移语句 if x relop y goto L 或或 if a goto L,relop为关系算符为关系算符(,=,等等)，a为布尔变量或常量；为布尔变量或常量；过程调用语句过程调用语句 param x和和call p,n，以及返以及返回语句回语句r

13、eturn y；索引赋值索引赋值 x:=yi及及xi:=y；程序设计语言与编译第二节第二节 简单赋值语句的翻译简单赋值语句的翻译一、语义变量及过程一、语义变量及过程X.aX.anewtempnewtempentry(i)entry(i)文法符X相应属性a,如i.name,E.place语义函数，每调用一次产生一个新的临时变量。语义函数，查符号表，返回变量i的入口。emit(OP,ARG1,ARG2,RESULT)emit(OP,ARG1,ARG2,RESULT)语义过程，生成一个四元式(OP,ARG1,ARG2,RESULT),并填入四元式表中。同时ip:=ip+1E.place:表示E所代表

14、的变量在符号表的入口地址。IPIP指令指针，初始化为0，也可以是指定的初值。程序设计语言与编译二简单算术表达式及赋值语句的翻译二简单算术表达式及赋值语句的翻译u简单算术表达式是一种仅含简单变量的算简单算术表达式是一种仅含简单变量的算术表达式；简单变量是指普通变量和常数术表达式；简单变量是指普通变量和常数，但不含数组元素及结构引用等复合型数，但不含数组元素及结构引用等复合型数据结构。据结构。u 简单算术表达式的计值顺序与四元式出简单算术表达式的计值顺序与四元式出现的顺序相同，因此很容易将其翻译成四现的顺序相同，因此很容易将其翻译成四元式形式。元式形式。程序设计语言与编译 实现简单算术表达式和赋值

15、语句到四元式实现简单算术表达式和赋值语句到四元式的翻译一般采取下列步骤：的翻译一般采取下列步骤：（1）分析文法的特点。）分析文法的特点。（2）设置一系列语义变量，定义语义过程、）设置一系列语义变量，定义语义过程、语义函数。语义函数。（3）修改文法，写出每一条规则的语义子）修改文法，写出每一条规则的语义子程序。程序。（4）扩充）扩充LR分析栈，构造分析栈，构造LR分析表。分析表。程序设计语言与编译u 考虑以下文法考虑以下文法GA：Ai=Eu EE+E E*E E (E)iu 为了实现由表达式到四元式的翻译为了实现由表达式到四元式的翻译，需要给文法加上语义子程序，以便在进，需要给文法加上语义子程序

16、，以便在进行归约的同时执行对应的语义子程序。行归约的同时执行对应的语义子程序。程序设计语言与编译u 语义子程序所涉及的语义变量、语义过语义子程序所涉及的语义变量、语义过程及函数说明如下：程及函数说明如下：u (1)对非终结符对非终结符E定义语义变量定义语义变量E.place，即，即用用E.place表示存放表示存放E值的变量名在符号表中的值的变量名在符号表中的入口地址或临时变量名的整数码。入口地址或临时变量名的整数码。u (2)定义语义函数定义语义函数newtemp()，即每次调用，即每次调用newtemp()时都将回送一个代表新临时变量的时都将回送一个代表新临时变量的整数码；临时变量名按产生

17、的顺序可设为整数码；临时变量名按产生的顺序可设为T1、T2、。u (3)定义语义过程定义语义过程emit(op,arg1,arg2,result),emit的功能是产生一个四元式并填入四元式表的功能是产生一个四元式并填入四元式表中。中。程序设计语言与编译u(4)定义语义函数定义语义函数lookup(i.name)，（，（entry(i.name)）其功能是检查其功能是检查i.name是否出现在符号表中，是则返回是否出现在符号表中，是则返回i.name在符号表的入口指针，否则返回在符号表的入口指针，否则返回NULL。u 使用上述语义变量、过程和函数，可写出文使用上述语义变量、过程和函数，可写出文

18、法法GA中的每一个规则的语义子程序。中的每一个规则的语义子程序。u (1)Ai=E p=lookup(i.name);u if(p=NULL)error();u else emit(=,E.place,_,p);u (2)EE(1)+E(2)E.place=newtemp();u emit(+,E(1).place,E(2).place,E.place);程序设计语言与编译u(3)EE(1)*E(2)E.place=newtemp();u emit(*,E(1).place,E(2).place,E.place);u(4)EE(1)E.place=newtemp();u e m i t(u m

19、 i n u s,E(1).place,_,E.place);u(5)E(E(1)E.place=E(1).place;u(6)Ei p=lookup(i.name);u if(p!=NULL)E.place=p;u /*另一种表示为另一种表示为E.place=entry(i)*/u else error();程序设计语言与编译举例举例:a:=-b*(c+d)的移进-归约过程a:=-b b*(c+d)a:=-E1*(c+d)a:=E2*(c c+d)a:=E2*(E3+d)a:=E2*(E3+E4)a:=E2*(E5)a:=E2*E6a:=E7AE iE iE-EE-E1 1 (,b,_,t1

20、)(,b,_,t1)E iE iE iE iEEEE1 1 op E op E2 2(+,c,d,t2)(+,c,d,t2)E(EE(E1 1)EEEE1 1 op E op E2 2(*,t1,t2,t3),t1,t2,t3)Ai:=E i:=E (:=,t3,_,a)(:=,t3,_,a)程序设计语言与编译p运算合法性检查运算合法性检查利用符号表保存的名字类型利用符号表保存的名字类型p类型自动转换类型自动转换填加专用指令填加专用指令p临时变量空间的统计临时变量空间的统计了解需求、及时释放了解需求、及时释放程序设计语言与编译三、类型转换三、类型转换对表达式E增加类型属性E.type;引进类型

21、转换指令(itr,x,_,t)EEEE1 1 op E op E2 2的语义子程序如后的语义子程序如后 程序设计语言与编译t:=newtemp;t:=newtemp;if Eif E1 1.type=integer.type=integer and E and E2 2.type=integer.type=integer then begin then begin gen(op gen(opi i,E,E1 1.place,E.place,E2 2,place,t);,place,t);E.type:=integer E.type:=integer endendelse if Eelse if

22、 E1 1.type=real.type=real and E and E2 2.type=real.type=real then begin then begin gen(op gen(opr r,E,E1 1.place,E.place,E2 2.place,t);.place,t);E.type:=real E.type:=real endend else if Eelse if E1 1.type=integer then.type=integer then begin t1:=newtemp;begin t1:=newtemp;gen(itr,E gen(itr,E1 1.place

23、,_,t1);.place,_,t1);gen(op gen(opr r,t1,E,t1,E2 2.place,t);.place,t);E.type:=realE.type:=real endendelse begin t1:=newtemp;else begin t1:=newtemp;gen(itr,E gen(itr,E2 2.place,_,t1);.place,_,t1);gen(op gen(opr r,E,E1 1.place,t1,t);.place,t1,t);E.type:=real E.type:=real end;end;E.place:=t;E.place:=t;程

24、序设计语言与编译9.4 9.4 说明语句的翻译说明语句的翻译一、文法一、文法DD1;D2i:TTrealintegerarraynum of T1T1 程序设计语言与编译二、主要工作二、主要工作不产生可执行指令仅负责填表将被说明对象的类型类型及相对存储位置相对存储位置记入各自的符号表中 程序设计语言与编译DD1;D2i:TTrealintegerarraynum of T1T11.1.类型类型2.2.相对存储位置相对存储位置T.TypeT.Type全部变量全部变量OffsetOffset：相对位移量1.赋初值2.增值Offset=Offset+T.WidthOffset=Offset+T.Wi

25、dthS MDM Offset=0 Offset=0 T.WidthT.Width程序设计语言与编译三、语义变量及过程三、语义变量及过程(1)offset:相对位移量,初值为0,是一个全局变量(2)T.type:数据类型(3)T.width:数据宽度(4)enter:语义过程,将变量名及其类型和相对存储位置记入符号表中。程序设计语言与编译四、翻译方案四、翻译方案S MDM D D1;D2D i:T offset:=0 enter(i.name,T.type,offset);offset:=offset+T.width 程序设计语言与编译 T.type:=pointer(T1.type);T.w

26、idth:=4 Tinteger Tinteger T.type:=integer;T.width:=4 Treal T.type:=real;T.width:=4 Tarraynum of T1 T.type:=array(num.val,T1.type);T.width:=num.val*T1.width TT1 程序设计语言与编译五、其它说明语句五、其它说明语句(1)说明语句可能为如下形式先改写为先改写为DD,iinteger ireal iDD,iinteger ireal iD integer namelistreal namelistnamelist namelist,ii 程序设

27、计语言与编译(2)说明语句可能为如下形式Dnamelist integer|namelist realnamelistnamelist,i|i翻译时需引进队列翻译时需引进队列namelist.QUEUEnamelist.QUEUE用以存放变量名用以存放变量名 程序设计语言与编译内容回顾内容回顾1.1.语义分析语义分析(1)语义检查(2)语义处理一致性检查越界检查说明语句可执行语句信息登记四元式2.2.语法制导翻译语法制导翻译3.3.简单赋值语句的翻译简单赋值语句的翻译4.4.说明语句的翻译说明语句的翻译 程序设计语言与编译DD1;D2i:TTrealintegerarraynum of T1T

28、1S MDM D D1;D2D i:T Treal T.type:=real;T.width:=4 内容回顾内容回顾 offset:=0 enter(i.name,T.type,offset);offset:=offset+T.width 程序设计语言与编译第四节第四节 控制语句的翻译控制语句的翻译一、布尔表达式的翻译一、布尔表达式的翻译BiBi1 rop i21.文法及其分析作为控制条件的布尔表达式，它为真或假时，要转移到不同的地方。true,flase或布尔变量关系运算符:大于，小于，等于 程序设计语言与编译布尔表达式文法：E EE|EE|E|(E)|i rop i|i计算布尔表达式值的两

29、种表示方法：数值表示法 真：E.place=1；假：E.place=0；真假出口表示法（作为其它语句的条件改变控制流程）真出口：E.true 假出口：E.false程序设计语言与编译411 数值表示法数值表示法u用1 表示真，0 表示假来实现布尔表达式的翻译。用这种方法，布尔表达式将从左到右按类似算术表达式的求值方法来计算。a or b and not c 被翻译成如下三地址序列：T1:=not c T2:=b and T1 T3:=a or T2 ua b 的关系表达式可等价地写if ab then 1 else 0，并可将它翻译成如下三地址语句序列（我们假定语句序号从100 开始）:100

30、:if ab goto 103 101:T:=0 102:goto 104 103:T:=1 104程序设计语言与编译42 关于布尔表达式的数值表示法的翻译模式 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程序设计语言与编译43关于布尔表

31、达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.place goto nextstat+3);emit(E.place:=0);emit(goto nextstat+2);emit(E.place:=1)Eid E.place:=id.place ab 翻译成翻译成100:if ac or b c goto L2 “真真”出口出口 goto L1L1:if bd goto L2 “真真”出口出口 goto L3 “假假”出口出口 L2:(关于关于S1的三地

32、址代码序列的三地址代码序列)goto LnextL3:(关于关于S2的三地址代码序列的三地址代码序列)Lnext:程序设计语言与编译u 对于对于ab ab 的四元式翻译：的四元式翻译：u if ab goto p (jif ab goto p (j，a a，b b，p)p)u goto q (j goto q (j，_ _，_ _，q)q)u 一般情况，每一个关系表达式对应一真一假两个四一般情况，每一个关系表达式对应一真一假两个四元式，其格式也是固定的，即元式，其格式也是固定的，即u (jrop(jrop，X X，Y Y，0)0)u (j (j，_ _，_ _，0)0)u /*X X、Y Y为

33、关系运算符两侧的变量或值为关系运算符两侧的变量或值*/u 每一个布尔变量每一个布尔变量a a也对应一真一假两个四元式，并也对应一真一假两个四元式，并且格式是固定的，即且格式是固定的，即u (jnz(jnz，a a，_ _，0)0)/*a a为布尔变量为布尔变量*/u (j (j，_ _，_ _，0)0)布尔表达式到四元式的翻译布尔表达式到四元式的翻译程序设计语言与编译2.语义变量B.T:B.T:真出口记录B为真的转移语句的地址；B.F:B.F:假出口记录B为假的转移语句的地址。程序设计语言与编译3.转移语句的四元式条件转移条件转移 (jrop,P1,P2,0)(jnz,P1,-,0)无条件转移

34、无条件转移(j,-,-,0)程序设计语言与编译4.翻译方案BiBi B.T:=ip;gen(jnz,entry(i),-,0);B.F:=ip;gen(j,-,-,0)BiBi1 1 rop i rop i2 2 B.T:=ip;gen(jrop,entry(i1),entry(i2),0);B.F:=ip;gen(j,-,-,0)程序设计语言与编译二、无条件转移语句翻译二、无条件转移语句翻译1.goto L的两种情形L:./*此时，将L登记入符号表*/goto L;/*查表，发现L已定义，生成四元式*/（1 1）L L已经定义已经定义 程序设计语言与编译goto L;/*将L记入符号表，定义

35、否标记为“否”*/goto L;/*拉链*/L:/*定义否标记改为“是”，回填*/（2 2）L L未定义未定义 程序设计语言与编译名字 类型定义否 地址L标号未r(p)(j,_,_,0)(q)(j,_,_,p)(r)(j,_,_,q)程序设计语言与编译2.带标号语句的处理方法设文法：设文法：label i:label i:当用label i:进行归约时（1 1）i i（假定为（假定为L L）不在符号表中）不在符号表中 则把它填入，置“类型”栏为“标号”，“定义否”栏 为“已”，“地址”栏为ip的当前值；（2 2）若）若L L已在符号表中已在符号表中 但“类型”不为“标号”,或“定义否”为“已”

36、则报“名字重定义”错 程序设计语言与编译(3)(3)若若L L已在符号表中已在符号表中“类型”为“标号”:把“定义否”改为“已”然后把“地址栏”中的链首q取出，同时把ip当前值填入其中 最后执行backpatch（q，ip）语义过程进行回填backpatch（q，ip）为语义过程：把q为链首的链上所有四元式的第四区段都填为ip 程序设计语言与编译三、条件语句的翻译三、条件语句的翻译1.1.文法及其分析文法及其分析Sif B then S1 if B then S1 else S2 程序设计语言与编译B BS S1 1?if B then Sif B then S1 1B B为假为假B B为真为

37、真S S1 1的第一条四元式的第一条四元式用以用以“回填回填 程序设计语言与编译B BS S1 1S S2 2?if B then Sif B then S1 1 else S else S2 2B B为假为假B B为真为真S S1 1、S S2 2的第一条的第一条四元式用以四元式用以“回填回填”此处产生一无条件此处产生一无条件转移语句转移语句 程序设计语言与编译由上面几个图可见：由上面几个图可见：(1)B(1)B具有真假出口具有真假出口 B为真假时的转向不同 在翻译B时其真假出口有待“回填”(2)(2)因因ifif语句的嵌套语句的嵌套,必须记录不确定转移目标必须记录不确定转移目标 的四元式的

38、地址的四元式的地址拉链技术拉链技术 程序设计语言与编译2.2.语义变量及过程语义变量及过程(1)N.CHAIN:记录不确定转移目标的四元式形成的链 如：S.CHAIN记录了S中不确定转移目标的且转向地址均相同的四元式（这些四元式形成一个链,S.CHAIN为链头）程序设计语言与编译如:(p)(j,-,-,0)(q)(j,-,-,0)(r)(j,-,-,0)S.CHAIN=rS.CHAIN=r程序设计语言与编译(2)merge(t1,t2):语义函数 将t1、t2合并，返回合并后的链头t2 (3)backpatch(t1,code):语义过程 用code回填t1;程序设计语言与编译如如:(p)(j

39、,-,-,0)(u)(j,-,-,0)(p)(j,-,-,0)(u)(j,-,-,0)(q)(j,-,-,p)(v)(j,-,-,u)(q)(j,-,-,p)(v)(j,-,-,u)(r)(j,-,-,q)(w)(j,-,-,v)(r)(j,-,-,q)(w)(j,-,-,v)t t1 1=r t=r t2 2=w=w执行执行merge(tmerge(t1 1,t,t2 2)后后 程序设计语言与编译得得 (p)(j,-,-,0)(u)(j,-,-,r)(p)(j,-,-,0)(u)(j,-,-,r)(q)(j,-,-,p)(v)(j,-,-,u)(q)(j,-,-,p)(v)(j,-,-,u)

40、(r)(j,-,-,q)(w)(j,-,-,v)(r)(j,-,-,q)(w)(j,-,-,v)链头链头t t2 2=w=w 程序设计语言与编译执行执行backpatch(tbackpatch(t2 2,120),120)后后 (p)(j,-,-,120)(u)(j,-,-,120)(q)(j,-,-,120)(v)(j,-,-,120)(r)(j,-,-,120)(w)(j,-,-,120)程序设计语言与编译B BS S1 1?if B then Sif B then S1 1B B为假为假B B为真为真S S1 1的第一条四元式的第一条四元式用以用以“回填回填 3.3.翻译方案翻译方案程序

41、设计语言与编译Sif B then Sif B then S1SM S1Mif B thenMif B thenMif B then backpatch(B.T,ip);M.CHAIN:=B.F SM SSM S1 1 S.CHAIN:=merge(M.CHAIN,S1.CHAIN)程序设计语言与编译if abif B if B thenM M a:=a+b M A M S1 S 102102例1:if ab then a:=a+b 的翻译 100:(j,a,b,0)100:(j,a,b,0)101:(j,-,-,0)101:(j,-,-,0)B.T=100B.F=101backpatch(1

42、00,102)M.CHAIN=101102:(+,a,b,t1)102:(+,a,b,t1)103:(:=,t1,-,a)103:(:=,t1,-,a)S1.CHAIN=0S.CHAIN=merge(M.CHAIN,S1.CHAIN)=101 S.CHAIN=merge(M.CHAIN,S1.CHAIN)=101 程序设计语言与编译B BS S1 1S S2 2?if B then Sif B then S1 1 else S else S2 2B B为假为假B B为真为真S S1 1、S S2 2的第一条的第一条四元式用以四元式用以“回填回填”此处产生一无条件此处产生一无条件转移语句转移语句

43、 程序设计语言与编译Sif B then Sif B then S1 else else S2 Mif B thenif B thenNM S1 elseSN S2 程序设计语言与编译NM SNM S1 1 else else q:=ip;gen(j,-,-,0);backpatch(M.CHAIN,ip);N.CHAIN:=merge(S1.CHAIN,q)Mif B thenMif B then backpatch(B.T,ip);M.CHAIN:=B.F Sif B then Sif B then S1 else else S2 SN SSN S2 2S.CHAIN:=merge(N.C

44、HAIN,S1.CHAIN)程序设计语言与编译if abif B if B thenM M a:=a+b M S1 M S1 elseN N a:=a-bN S2 S 102102105105例例2:if ab then a:=a+b else a:=a-b 2:if ab then a:=a+b else a:=a-b 的翻译的翻译 100:(j,a,b,0)100:(jb do if cb W B1 W B1 doDD if c,a,b,0)101(j,-,-,0)B1.T=100B1.F=101backpatch(100,102)D.CHAIN=B1.F=101D.code=W.code

45、=100102(j,c,d,0)103(j,-,-,0)B2.T=102 B2.F=103 程序设计语言与编译D if B2 thenD M backpatch(102,104)M.CHAIN=B2.F=103 D M e:=f+gD M S1 S1.CHAIN=0 104(+,f,g,t1)105(:=,t1,-,E)D S2 S2.CHAIN=merge(103,0)=103S backpatch(103,100)S.CHAIN=101 106(j,-,-,100)L L.CHAIN=S.CHAIN=101L;backpatch(101,107)程序设计语言与编译 100(j100(j10

46、2(j，B B，0 0，104)104)103(j103(j，-，-，109)109)104(j104(j，C C，0 0，106)106)105(j105(j，-，-，109)109)106(+106(+，C C，D D，T1)T1)107(:=107(:=，T1T1，-，C)C)108(j108(j，-，-，104)104)109109练习练习if (AX)if (A0)then while C0 do C:=C+D(B0)then while C0 do C:=C+D程序设计语言与编译BS1?B B为假为假B B为真为真while B do S1B B的第一条四元式需记录、的第一条四元式

47、需记录、S S1 1的第一条四元式用以的第一条四元式用以“回填回填”此处产生一无条件转移语句此处产生一无条件转移语句 内容回顾内容回顾程序设计语言与编译 backpatch(B.T,ip);D.CHAIN:=B.F;D.code:=W.code;while B do S1WwhileWwhile W.code:=ip DW B doDW B doSD SSD S1 1 backpatch(S1.CHAIN,D.code);gen(j,-,-,D.code);S.CHAIN:=D.CHAIN;内容回顾内容回顾程序设计语言与编译 100(j100(j102(j，B B，0 0，104)104)10

48、3(j103(j，-，-，109)109)104(j104(j，C C，0 0，106)106)105(j105(j，-，-，109)109)106(+106(+，C C，D D，T1)T1)107(:=107(:=，T1T1，-，C)C)108(j108(j，-，-，104)104)109109练习练习if (AX)if (A0)then while C0 do C:=C+D;(B0)then while C0 do C:=C+D;程序设计语言与编译四、循环语句的翻译四、循环语句的翻译Sfor i:=1 to N do S1其语义为 i:=1;if iN then begin S1;i:=i

49、+1;goto again end1.1.文法及分析文法及分析 again:程序设计语言与编译代码结构可为：F+0:（:，1，i）F+1:(j100 then C=C+1；的中间代码序列。程序设计语言与编译 for i=1 to 10 do if A100 then C=C+1；100:(=,I,1,i)101:(J,A,100,0)104:(J,-,-,0)105:(+,C,1,t1)106:(=,t1,C)107:(+,i,1,i)108:(J,-,-,101)109:105107109程序设计语言与编译 for i=1 to 10 do if A100 then C=C+1for i=1

50、 to 10 do F100:(=,I,1,i)101:(J100F if Bif B103:(J,A,100,0)104:(J,-,-,0 )B.T=103B.F=104F if B then if B then F M Mbackpatch(B.T,ip)M.Chain=B.F=104F M S1S2.Chain=merge(M.Chain,S1.Chain)=104F S2F M M C=C+1C=C+1105:(+,C,1,t1)106:(=,t1,C)S Sbackpatch(S2.CHAIN,ip)107:(+,i,1,i)108:(j,-,-,101)S.Chain=F.Chin