编译技术：第05章 语义分析

1、第五章 语义分析词法分析词法分析中间代码生成中间代码生成语法分析语法分析语义分析语义分析中间代码优化中间代码优化目标代码优化目标代码优化目标代码生成目标代码生成源程序机器代码编译的步骤2Zhou, ErqiangSchool of Information and Software Engineering概述程序在程序在“词法词法分析分析”中无错误中无错误 标识符：符合定义规则标识符：符合定义规则 字符串：正常结束字符串：正常结束程序在程序在“语法语法分析分析”中无错误中无错误 类：结构正确类：结构正确 表达式：句法正确表达式：句法正确程序程序一定合法一定合法？Zhou, Erqiang3Sch

2、ool of Information and Software Engineering概述Zhou, Erqiang4School of Information and Software EngineeringMyInterfaceMyInterface是否定义是否定义string string 类型错误类型错误string string 不支持乘法不支持乘法变量没有声明变量没有声明函数不能重复定义函数不能重复定义voidvoid类型类型 不能与不能与 整型相加整型相加class MyClass implements MyInterface string myInteger;void doSo

3、mething() int x = new string;x5 = myInteger * y;void doSomething() int fibonacci(int n) return doSomething() + fibonacci(n 1);概述静态语义检查静态语义检查 类型检查：如操作数类型应相容类型检查：如操作数类型应相容 控制流检查：控制流检查： 保证控制语句有合法的转向点保证控制语句有合法的转向点 goto goto 转入转入casecase语句？语句？ break break语句的循环语句？语句的循环语句？Zhou, Erqiang5School of Informatio

4、n and Software Engineering概述静态语义检查静态语义检查 一致性检查：一致性检查： 数组维数是否正确数组维数是否正确 变量是否已经定义变量是否已经定义 在同一作用域中标识符说明次数在同一作用域中标识符说明次数 case case常量不能相同等常量不能相同等Zhou, Erqiang6School of Information and Software Engineering概述语义分析保证程序有正确的意思语义分析保证程序有正确的意思验证前两阶段已获取的验证前两阶段已获取的各种属性各种属性属性信息保存在哪里属性信息保存在哪里？Zhou, Erqiang7School of

5、 Information and Software Engineering标识符定义标识符定义实体实体 实体属性保存在实体属性保存在符号表符号表符号表的形式符号表的形式 每个名字对应一个表项每个名字对应一个表项 一个表项包括一个表项包括名字域名字域和和信息域信息域名字名字属性信息属性信息符号表Zhou, Erqiang8School of Information and Software Engineering属性域属性域 多个多个子域子域及及标志位标志位 类型、值、存储大小、相对地址类型、值、存储大小、相对地址 形参标志、说明标志、赋值标志形参标志、说明标志、赋值标志符号表Zhou, Erq

6、iang9School of Information and Software Engineering名字域名字域 名字长度固定？名字长度固定？ 间接表技术间接表技术Zhou, Erqiang10School of Information and Software Engineering符号表x1bbstring; “abc”;第一项第一项Maxint;10第二项第二项名字域名字域属性域属性域Zhou, Erqiang11School of Information and Software Engineering符号表indexindexstring; “abc”;indexindexint;

7、10名字域名字域属性域属性域X 1 b b M a x 43 字符串表字符串表Zhou, Erqiang12School of Information and Software Engineering符号表indexindexstring; “abc”;indexindexint;10名字域名字域属性域属性域4 X 1 b b 3 M a x 字符串表字符串表名字域直接用名字域直接用“指针指针”嵌套语句如何处理？嵌套语句如何处理？0: int x = 137;1: int z = 10;2: int MyFunction(int x, int y) 3: printf(%d,%d,%dn, x

8、, y, z);4: 5: int x, z;6: z = y;7: x = z;8: 9: int y = x;10: printf(%d,%d,%dn, x, y, z);11: 12: 13: z = x + z; 14: 15: printf(%d,%d,%dn, x, y, z);16: 17: Zhou, Erqiang13School of Information and Software Engineering符号表x xint; 137z zint; 10名字域名字域属性域属性域 x xint; unknowny yint; unknownx xint; unknownz z

9、int; unknowny yint; unknown核心问题：对于抽象语法树中的核心问题：对于抽象语法树中的被引用被引用的标识符的标识符 如何如何在符号表中在符号表中找出找出其对应的属性？其对应的属性？声明：声明：录入录入符号表符号表引用：引用：访问访问符号表符号表Zhou, Erqiang14School of Information and Software Engineering符号表x xint; 137z zint; 10名字域名字域属性域属性域x xint; unknowny yint; unknownx xint; unknownz zint; unknowny yint; u

10、nknown2 22 201234560 01 12 22 21 13 3 个数个数指针指针嵌套数嵌套数0246两个并列的作用域？两个并列的作用域？x xint; unknowny yint; unknownotherFunc(int x, int y)仅仅嵌套层次嵌套层次与与变量名变量名 是否能确定变量对应的属性？是否能确定变量对应的属性？引入引入“嵌套关系表嵌套关系表”嵌套关系表嵌套关系表与应随当前访问的代码动态变化与应随当前访问的代码动态变化一般用一般用栈栈实现实现Zhou, Erqiang15School of Information and Software Engineering符

11、号表x xint; 137z zint; 10名字域名字域属性域属性域x xint; unknowny yint; unknownx xint; unknownz zint; unknowny yint; unknown2 22 201234560 01 12 22 21 13 3 个数个数指针指针嵌套数嵌套数0246x xint; unknowny yint; unknownotherFunc(int x, int y)2 21 1 2注意：注意： 符号表中的表项不用删除符号表中的表项不用删除 这里只是为了说明作用域的退出这里只是为了说明作用域的退出语法制导翻译Zhou, Erqiang16

12、School of Information and Software Engineering语义分析语义分析 语义检查语义检查 语义处理语义处理 说明语句：检查属性信息说明语句：检查属性信息 执行语句：生成中间代码执行语句：生成中间代码注意：注意： 根据所要生成的根据所要生成的“低级语言低级语言” （LLVM、汇编、机器）、汇编、机器） 说明语句需要翻译成说明语句需要翻译成该语言该语言对应的代码对应的代码语法制导翻译Zhou, Erqiang17School of Information and Software Engineering语义分析语义分析 语义检查语义检查 语义处理语义处理 说明

13、语句：检查属性信息说明语句：检查属性信息 执行语句：生成中间代码执行语句：生成中间代码分析方法分析方法 语法制导的翻译方法语法制导的翻译方法 即在语法分析时不建立即在语法分析时不建立AST，而是直接生成中间代码，而是直接生成中间代码适用于文法比较简单的语言适用于文法比较简单的语言建立建立AST是目前编译器的是目前编译器的标准标准步骤步骤语法制导翻译Zhou, Erqiang18School of Information and Software Engineering分析过程分析过程 每个每个产生式产生式配上一个配上一个语义子程序语义子程序 当对产生式进行当对产生式进行推导推导或或归约归约时时

14、 调用相应的语义程序调用相应的语义程序 进行语义分析进行语义分析将将 语法分析语法分析 与与 语义分析混在一起语义分析混在一起代码很难维护代码很难维护语法制导翻译Zhou, Erqiang19School of Information and Software Engineering语义子程序语义子程序 完成语义检查、语义处理完成语义检查、语义处理 检查：类型、控制流、一致性检查：类型、控制流、一致性 处理：记录信息、生成中间代码处理：记录信息、生成中间代码 核心是生成中间代码核心是生成中间代码语法制导翻译（示例1）Zhou, Erqiang20School of Information an

15、d Software Engineering计算器程序的语法制导翻译计算器程序的语法制导翻译L E print(E.val); E E1+T E.val = E1.val + T.val ; E T E.val = T.val ;T T1*F T.val = T1.val * F.val ;T F T.val = F.val ;F (E) F.val = E.val ;F digit F.val = digit.lexval ;语法制导翻译（示例1）Zhou, Erqiang21School of Information and Software Engineering3*F5TFE+TF4E

16、TL E E E1+TE TT T1*FT F F (E)F digit3*5+4 的的语法语法分析过程分析过程语法制导翻译（示例1）Zhou, Erqiang22School of Information and Software Engineeringdigit.lexval =3F.val = digit.lexval T.val =F.valdigit.lexval =5F.val:=5T.val =15*E.val =15+digit.lexval =4F.val =4T.val =4E.val =19print(19)3*5+4 的的语义语义分析过程分析过程L E print(E

17、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语法制导翻译Zhou, Erqiang23School of Information and Software Engineering在分析过程中必须保存语义值在分析过程中必须保存语义值 “ “类型类型”、“种属种属”、“地址地址”等等种属种属 常量、简单变量、数组、函数、标号、常量、简单变量、数组、函数、标号、

18、语义值语义值 X.type、X.category、X.address、语法制导翻译（示例2）Zhou, Erqiang24School of Information and Software Engineering如果采用自底向上的如果采用自底向上的LRLR分析法分析法X XABABY YCDCDZ ZXYXY状态栈状态栈符号栈符号栈语义栈语义栈B BA A B B的语义值的语义值A A的语义值的语义值 语法制导翻译（示例2）Zhou, Erqiang25School of Information and Software Engineering如果采用自底向上的如果采用自底向上的LRLR分析

19、法分析法X XABABY YCDCDZ ZXYXY状态栈状态栈符号栈符号栈语义栈语义栈X X X X的语义值的语义值 如果采用自底向上的如果采用自底向上的LRLR分析法分析法X XABABY YCDCDZ ZXYXYD D的语义值的语义值C C的语义值的语义值X X的语义值的语义值 D DC CX X 语法制导翻译（示例2）Zhou, Erqiang26School of Information and Software Engineering状态栈状态栈符号栈符号栈语义栈语义栈如果采用自底向上的如果采用自底向上的LRLR分析法分析法X XABABY YCDCDZ ZXYXY Y Y的语义值的

20、语义值X X的语义值的语义值 Y YX X 语法制导翻译（示例2）Zhou, Erqiang27School of Information and Software Engineering状态栈状态栈符号栈符号栈语义栈语义栈如果采用自底向上的如果采用自底向上的LRLR分析法分析法X XABABY YCDCDZ ZXYXY Y Y的语义值的语义值X X的语义值的语义值 Y YX X 语法制导翻译（示例2）Zhou, Erqiang28School of Information and Software Engineering状态栈状态栈符号栈符号栈语义栈语义栈如果采用自底向上的如果采用自底向上的

21、LRLR分析法分析法X XABABY YCDCDZ ZXYXY Z Z的语义值的语义值 Z Z 语法制导翻译（示例2）Zhou, Erqiang29School of Information and Software Engineering状态栈状态栈符号栈符号栈语义栈语义栈语法制导翻译（示例总结）Zhou, Erqiang30School of Information and Software Engineering产生式产生式 用下标区别产生式中相同非终结符用下标区别产生式中相同非终结符例如将产生式例如将产生式 EE+E 表示为表示为 EE1+E2 3 3个个E的语义值的语义值 如如E.V

22、AL，E1.VAL和和E2.VAL语法制导翻译（示例总结）Zhou, Erqiang31School of Information and Software Engineering产生式的语义动作产生式的语义动作 写在产生式后的花括号内写在产生式后的花括号内例如例如 EE1+E2 E.VAL = E1.VAL+E2.VAL ET E.VAL = T.VAL 语法制导翻译（示例总结）Zhou, Erqiang32School of Information and Software Engineering编译时仅编译时仅常量常量的值可以确定的值可以确定 对大多数归约对大多数归约 语义程序需要生成相

23、应的中间代码语义程序需要生成相应的中间代码中间代码如何表示？中间代码如何表示？ 三地址代码、抽象语法树、三地址代码、抽象语法树、LLVM指令等指令等 语义变量和语义函数Zhou, Erqiang33School of Information and Software Engineering语义值的表示语义值的表示 X.type、X.category、X.address、常用语义变量常用语义变量1) 1) : : 语义变量，与终结符语义变量，与终结符i i相关联相关联 表示表示 i 对应的标识符字符串对应的标识符字符串i i 具体表示什么？具体表示什么？ id.id语义变量和语义函数

24、Zhou, Erqiang34School of Information and Software Engineering2) 2) E.place: : 语义变量，与语义变量，与非终结符非终结符E E相关联相关联 表示变量表示变量E 在在符号表的位置符号表的位置 或或整数编码整数编码( (临时变量临时变量) ) 采用采用变量名变量名或或临时变量临时变量名表示名表示产生式：产生式：EE1+E2 emit( E.place, E1.place, op, E2.place) 语句：语句： a = b + c 生成的三地址代码：生成的三地址代码： t1 = b + c； a = t1 ;表示非终结符

25、表示非终结符E E 对应变量对应变量 的的地址地址 及及 相应的值相应的值语义变量和语义函数Zhou, Erqiang35School of Information and Software Engineering3) 3) newtemp(): :语义函数语义函数 产生一个新的临时变量产生一个新的临时变量 返回其地址返回其地址 即：符号表的位置即：符号表的位置 采用临时变量名表示：采用临时变量名表示：t t1 1, t, t2 2, , 语义变量和语义函数Zhou, Erqiang36School of Information and Software Engineering4) 4) en

26、try( i ): : 语义函数语义函数 对对名字为名字为i i的变量查符号表，的变量查符号表， 返回返回i i在在符号表中的位置符号表中的位置 采用采用变量名变量名表示表示 未查到，未查到，则则 ？ 表示该变量没有定义表示该变量没有定义返回返回名字为名字为i i的变量的的变量的地址地址和和对应的值对应的值语义变量和语义函数Zhou, Erqiang37School of Information and Software Engineering5) 5) emit(RESULT, ARG1, oper, ARG2) 或或 emit(oper, ARG1, ARG2, RESULT) 语义函数语

27、义函数 产生四元式并填入四元式表中产生四元式并填入四元式表中 同时四元式编号增加同时四元式编号增加1 1简单赋值语句的翻译Zhou, Erqiang38School of Information and Software Engineering简单赋值语句简单赋值语句 只有简单变量只有简单变量 变量类型相同变量类型相同E id 归约时，归约时，i id d 的语义信息已经获取的语义信息已经获取 归约后，归约后，i id d 的语义需要传递给的语义需要传递给 E E E.place = entry( id.NAME ); 查找出错？查找出错？A id:=EE (E1)E -E1 E E1 op

28、E2E idop+ | - | * | /简单赋值语句的翻译Zhou, Erqiang39School of Information and Software EngineeringE id P = entry( ); if (P != 0) E.place = P; else error(); A id:=EE (E1)E -E1 E E1 op E2E idop+ | - | * | /简单赋值语句的翻译Zhou, Erqiang40School of Information and Software EngineeringE E1 op E2 E.place = newt

29、emp(); emit(E.place, E1.place, op, E2.place) E -E1 E.place = newtemp(); emit(E.place, uminus, E1.place) 为什么需要为什么需要newtemp()?newtemp()?A id:=EE (E1)E -E1 E E1 op E2E idop+ | - | * | /简单赋值语句的翻译Zhou, Erqiang41School of Information and Software EngineeringE (E1) E.place = E1.place;A id := E P = entry( i

30、) ; if ( P != 0 ) emit( P, =, E.place) else error(); A id:=EE (E1)E -E1 E E1 op E2E idop+ | - | * | /简单赋值语句的翻译示例Zhou, Erqiang42School of Information and Software Engineeringa:= -b*(c+d)的归约过程的归约过程 ida := -idb * (idc + idd) ida := -E1 * (idc + idd)* ida := E2 * (E3 + E4) ida := E2 * (E5) ida :=

31、E2 * E6 ida := E7 AA id:=EE (E1)E -E1 E E1 op E2E idop+ | - | * | /E -E1 E.place = newtemp(); emit(E.place, uminus, E1.place) + id)#简单赋值语句的翻译示例Zhou, Erqiang43School of Information and Software Engineering ia := -ib * (ic + id)# := -ib * (ic + id)#ia -ib * (ic + id)#ia:= ib * (ic + id)#ia:= - * (ic +

32、 id)#ia:= -ib * (ic + id)#ia:= -E1 # # # # b 语义栈语义栈符号栈符号栈输入串输入串E i P = entry( ); if (P != 0) E.place = P; else error(); * (ic + id)#ia:= E2 # t1 t1 = uminus b (ic + id)#ia:= E2* # t1 ic + id)#ia:= E2*( # t1 + id)#ia:= E2*(ic # t1 #ia:= E2*(E3 # t1 c id)#ia:= E2*(E3+ # t1 c )#ia:= E2*(E3+id #

33、t1 c 1)i i 表示表示 idid简单赋值语句的翻译示例Zhou, Erqiang44School of Information and Software Engineering语义栈语义栈符号栈符号栈输入串输入串t1 = uminus b )#ia:= E2*(E3+id # t1 c )#ia:= E2*(E3+E4 # t1 c d )#ia:= E2*(E5 # t1 t2E E1 op E2 E.place = newtemp(); emit(E.place, E1.place, op, E2.place) t2 = c + d #ia:= E2*(E5) # t1 t2 E

34、(E1) E.place = E1.place; #ia:= E2*E6 # t1 t2 #ia:= E7 # t3t3 = t1 * t2 A i := E P = entry( ) ; if ( P != 0 ) emit( P, =, E.place) else error(); #A #aa = t3 2)3)4)1)简单赋值语句的翻译Zhou, Erqiang45School of Information and Software Engineering简单赋值语句简单赋值语句 只有简单变量只有简单变量 变量类型相同变量类型相同变量类型不同呢？变量类型不同呢？ 整型与实型

35、运算整型与实型运算 允许？结果类型？允许？结果类型？简单赋值语句的翻译Zhou, Erqiang46School of Information and Software Engineering类型转换方法类型转换方法(整型转实型整型转实型) 对表达式对表达式 E E 增加语义属性增加语义属性E.typeE.type 引进类型转换指令引进类型转换指令(t, i2r, x) i i2 2r r为一元运算为一元运算 x x为整型值为整型值 t t为转换后实型值为转换后实型值 修改修改EEE E1 1 op E op E2 2的语义子程序的语义子程序简单赋值语句的翻译Zhou, Erqiang47Sc

36、hool of Information and Software EngineeringE E1 op E2 t1 = newtemp(); E.Type = REAL; /默认类型默认类型 if (E1.Type = INT & E2.Type = INT) emit(E.place, E1.place, opi, E2.place); E.Type = INT; else if(E1.Type = REAL & E2.Type = REAL) emit(E.place, E1.place, opr, E2.place);enum c_type REAL, INT, 简单赋值语句的翻译Zho

37、u, Erqiang48School of Information and Software Engineering else if(E1.Type = INT & E2.Type = REAL) t2 = newtemp(); emit( t2, itr, E1.place); emit( t1, t2, opr, E2.place); else if(E1.Type = REAL & E2.Type = INT) t2 = newtemp(); emit( t2, itr, E2.place); emit( t1, E2.place, opr, t2); else error(); E.P

38、lace = t1; 简单赋值语句的翻译Zhou, Erqiang49School of Information and Software Engineering问题：问题： 变量的信息变量的信息何时何时记录到符号表？记录到符号表？ 处理执行语句？处理执行语句？ 处理说明语句？处理说明语句？ 记录属性信息（填表）记录属性信息（填表）简单说明语句的翻译Zhou, Erqiang50School of Information and Software Engineering简单说明语句的文法简单说明语句的文法 DD1;D2id:T T integerrealarraynum of T1T1非终结符

39、非终结符D D产生一系列产生一系列 i id d:T:T形式的说明语句形式的说明语句简单说明语句的翻译Zhou, Erqiang51School of Information and Software EngineeringDD1;D2id:TT integerrealarraynum of T1 T1翻译的主要工作翻译的主要工作 “不产生不产生”中间代码中间代码 负责填表负责填表 填表的内容？填表的内容？ 类型类型 简单说明语句的翻译Zhou, Erqiang52School of Information and Software Engineering关于关于存储位置存储位置 变量的存放区

40、域变量的存放区域全局变量、静态全局变量、静态局部变量全局变量、静态全局变量、静态局部变量 静态存储区静态存储区 如果没有手工初始化，则由编译器初始化为如果没有手工初始化，则由编译器初始化为0 0局部变量局部变量 栈区；如不初始化，值不可知栈区；如不初始化，值不可知 函数被调用时，在栈区分配内存，返回后消函数被调用时，在栈区分配内存，返回后消失失简单说明语句的翻译Zhou, Erqiang53School of Information and Software Engineering函数栈帧函数栈帧(stack frame)(stack frame) 函数的每次执行都独立的对应一个栈函数的每次执

41、行都独立的对应一个栈 当前被执行函数对应的栈在当前被执行函数对应的栈在栈帧的顶部栈帧的顶部 通过通过基址指针基址指针 与与 变量的偏移变量的偏移访问临时变量访问临时变量 void MyFunction()void MyFunction() int a, b, c; int a, b, c; a = 10; a = 10; b = 5; b = 5; c = 2; c = 2;_MyFunction:_MyFunction: push push ebp ; ebp ; 保存保存“基址指针基址指针” ebpebp mov mov ebp, esp ; ebp, esp ; “基址指针基址指针” e

42、bpebp指向栈顶指向栈顶 sub sub esp, 12 ; esp, 12 ; 在栈中为临时变量分配空间在栈中为临时变量分配空间mov ebp - 4, 10 ; mov ebp - 4, 10 ; 将将1010保存至变量保存至变量 a amov ebp - 8, 5 ; location of bmov ebp - 8, 5 ; location of bmov ebp - 12, 2 ; location of cmov ebp - 12, 2 ; location of c简单说明语句的翻译Zhou, Erqiang54School of Information and Softwa

43、re Engineering函数每次运行，局部变量的函数每次运行，局部变量的地址地址如何确定？如何确定？ 起始地址：起始地址：offsetoffset，针对当前栈，初值为，针对当前栈，初值为0 0 变量的变量的“宽度宽度”：widthwidth，因类型而定，因类型而定下一个变量地址：下一个变量地址：offset+widthoffset+width简单说明语句的翻译Zhou, Erqiang55School of Information and Software Engineeringoffsetoffset初始值为初始值为0 0 何时进行初始化？何时进行初始化？DD1;D2i:TT integ

44、errealarraynum of T1 T1每个函数运行时有自己栈帧每个函数运行时有自己栈帧 对每个函数的对每个函数的变量声明时变量声明时进行初始化进行初始化 如何体现在文法上？如何体现在文法上？int fun1() a: int; b: real; c: int;int fun2() d: int; e: real; f: int;简单说明语句的翻译方案Zhou, Erqiang56School of Information and Software Engineering文法改造文法改造 SMD M DD1;D2i:T T integerrealarraynum of T1 T1语义子程

45、序语义子程序 SMD M offset = 0;简单说明语句的翻译方案Zhou, Erqiang57School of Information and Software EngineeringDD1;D2i:T DD1;D2 Di:T enter(,T.type,offset); offset:=offset+T.width T integerrealarraynum of T1 T1 Tinteger T.type:=integer; T.width:=2 Treal T.type:=real; T.width:=4 enter( Name, Type, Offset ) 将将语

46、义信息语义信息记入符号表记入符号表简单说明语句的翻译方案Zhou, Erqiang58School of Information and Software EngineeringT integerrealarraynum of T1 T1 Tarraynum of T1 T.type := (array, num.val, T1.type); T.width:=num.val * T1.width; TT1 T.type:= (pointer, T1.type ); T.width:=4 ; 常见说明语句的翻译(一)Zhou, Erqiang59School of Information an

47、d Software Engineering说明语句的形式说明语句的形式 int a, b, c ; real d, e, f ;文法文法 D integer namelist ;real namelist ; namelist namelist, ii改写改写: S MD M DD,iinteger ireal i常见说明语句的翻译(二)Zhou, Erqiang60School of Information and Software Engineering说明语句的形式说明语句的形式 a, b, c : int; d, e, f: real;文法文法 Dnamelist integer ;

48、 | namelist real ; namelistnamelist, i | i需引进语义变量需引进语义变量 队列队列 namelist.QUEUE 存放变量名存放变量名对控制语句的翻译Zhou, Erqiang61School of Information and Software Engineering三种语句级控制结构：三种语句级控制结构： 顺序、选择、重复顺序、选择、重复顺序：指令指针自动加一顺序：指令指针自动加一 以获取下一条指令以获取下一条指令选择和重复：显示修改指令指针的值选择和重复：显示修改指令指针的值 以获取下一条指令以获取下一条指令对控制语句的翻译Zhou, Erqia

49、ng62School of Information and Software Engineering常见控制语句常见控制语句 条件转移条件转移 “if B then S” “if B then S1 else S2” 循环循环 while语句语句 for语句语句控制语句中简单布尔表达式的翻译Zhou, Erqiang63School of Information and Software Engineering控制语句中的控制语句中的布尔表达式布尔表达式 if B then S if B then S else S while B do S是是 选择选择语句语句 和和 迭代迭代语句语句 的早期

50、句柄的早期句柄控制语句中简单布尔表达式的翻译Zhou, Erqiang64School of Information and Software Engineering文法及其分析文法及其分析 Bi （i为为true、false或逻辑变量）或逻辑变量） Bi1 rop i2 (i 为变量或者常量，为变量或者常量，rop为为关系运算关系运算符符)表达式为真或假，分别转移到不同的地址表达式为真或假，分别转移到不同的地址 转移到转移到“真真出口出口” 和和“假假出口出口” 分别对应相应的分别对应相应的“转移代码转移代码” 归约时产生两个三地址代码归约时产生两个三地址代码控制语句中简单布尔表达式的翻译Z

51、hou, Erqiang65School of Information and Software Engineering涉及到两类地址：涉及到两类地址： 本身地址本身地址 和和 目标地址目标地址本身的地址本身的地址 产生的两个产生的两个“转移指令转移指令”的地址（编号）的地址（编号）目标地址目标地址 转移指令的一部分转移指令的一部分 何时能确定目标地址？何时能确定目标地址？ 布尔表达式归约时能否确定下来？布尔表达式归约时能否确定下来？ YN控制语句中简单布尔表达式的翻译Zhou, Erqiang66School of Information and Software EngineeringBS

52、if B then S1 else S2if B then SBS1S2YN布尔表达式归约到布尔表达式归约到B时还未处理时还未处理S的代码的代码归约时目标地址归约时目标地址未知未知 需要记录转移指令的地址需要记录转移指令的地址 以便回填目标地址以便回填目标地址控制语句中简单布尔表达式的翻译Zhou, Erqiang67School of Information and Software Engineering归约时的动作归约时的动作 1）产生两个转移指令）产生两个转移指令 真真出口出口 和和 假假出口出口 2）记录两转移指令的地址）记录两转移指令的地址 引入两个语义变量引入两个语义变量 B.T

53、记录真出口的地址记录真出口的地址 B.F记录假出口的地址记录假出口的地址控制语句中简单布尔表达式的翻译Zhou, Erqiang68School of Information and Software Engineering翻译方案翻译方案B i 转移指令：转移指令： ip: if b goto 0; ip+1: goto 0; 记录转移指令的地址，以便回填目标地址记录转移指令的地址，以便回填目标地址 B.T = ip; B.F = ip+1; 控制语句中简单布尔表达式的翻译Zhou, Erqiang69School of Information and Software Engineerin

54、g翻译方案翻译方案B i B.T = ip; B.F = ip+1; emit( if b goto 0 ); emit( goto 0 ); 控制语句中简单布尔表达式的翻译Zhou, Erqiang70School of Information and Software Engineering翻译方案翻译方案B i1 rop i2 B.T = ip; B.F = ip+1; emit( if i1 rop i2 goto 0); emit( goto 0 ); 选择语句的翻译Zhou, Erqiang71School of Information and Software Engineeri

55、ng文法文法 S if B then S1 S if B then S1 else S2YNBSBS1S2YN选择语句的翻译Zhou, Erqiang72School of Information and Software EngineeringS if B then S归约到归约到B B时，产生两条指令时，产生两条指令 B.T: if B goto 0; B.F: goto 0;问题：何时回填这两条指令？问题：何时回填这两条指令？ B.T: S的第一条指令地址确定时的第一条指令地址确定时 B.F: “S的最后一条指令地址的最后一条指令地址确定确定时时”YNBS选择语句的翻译Zhou, Erq

56、iang73School of Information and Software EngineeringS if B then S1中间代码结构中间代码结构 B.T: if B goto 0 B.F : goto 0 /语句语句S S1 1对应的中间代码对应的中间代码YNBSB_TrueB_True:after_S1:S_EndB.F 指令中的目标地址指令中的目标地址一定是一定是S1之后的代码吗？之后的代码吗？选择语句的翻译Zhou, Erqiang74School of Information and Software Engineering B.T: if B goto 0 B.F : g

57、oto 0 /语句语句S S1 1对应的中间代码对应的中间代码 /语句语句S S2 2对应的中间代码对应的中间代码B_True:S2_First:S2_FirstB_Truegoto S_Endif B1 then S1 else S2 after_S2:S_End 一定是一定是S2之后的代码吗？之后的代码吗？选择语句的翻译Zhou, Erqiang75School of Information and Software Engineeringif B1 then if B2 then S1 else S2 else S3if B1 then if B2 then S1 else S2 els

58、e S3S1之后的之后的goto S_End 未必指向未必指向S2之后的代码之后的代码这又意味着什么呢？这又意味着什么呢？ 在在“控制语句控制语句”归约到归约到S S后后 部分部分指令中的指令中的最终转移地址最终转移地址仍不确定仍不确定 选择语句的翻译Zhou, Erqiang76School of Information and Software Engineering S if B then S1 S if B then S1 else S2引入语义变量引入语义变量S.ChainS.Chain 记录条件语句归约后记录条件语句归约后未完成指令未完成指令的地址的地址 未完成指令缺少未完成指令缺

59、少哪个哪个地址？地址？ S S1 1和和S S2 2都有相应的都有相应的 未完成指令未完成指令“链链”翻译的关键是如何处理这些链翻译的关键是如何处理这些链 处理方法？处理方法？选择语句的翻译Zhou, Erqiang77School of Information and Software Engineering多个链的多个链的转移地址相同转移地址相同 引入语义函数引入语义函数 merge(P1, P2) 合并两个链为一个，返回新链合并两个链为一个，返回新链P P2 2当当转移地址确定转移地址确定后，回填转移指令后，回填转移指令 引入语义函数引入语义函数backpatch(P, address)

60、 将将address 回填到链回填到链P P中的所有指令中的所有指令选择语句的翻译Zhou, Erqiang78School of Information and Software Engineering S if B then S1 B B为假为假BS1?B B为真为真S S1 1的第一条指令编号的第一条指令编号用以回填真出口用以回填真出口需要拉链需要拉链选择语句的翻译Zhou, Erqiang79School of Information and Software Engineering if B then if B2 then S1 B B2 2为假为假B B2 2为真为真B B1 1为