语法制导翻译生成中间代码.ppt

资源描述

《语法制导翻译生成中间代码.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译生成中间代码.ppt（116页珍藏版）》请在金锄头文库上搜索。

1、第四章语法制导翻译生成中间代码语法制导翻译是处理语义的基本方法，它以语法分析为基础，在语法分析得到语言结构的结果时，对附着于此结构的语义进行处理，如计算表达式的值、生成中间代码等。与语法分析部分的讨论不同，本章的内容更注重于实际方法的讨论。主要内容包括：语法制导翻译的基本概念中间代码简介符号表简介典型声明语句与可执行语句的翻译14.1 语法制导翻译简介4.1.1 语法与语义语法与语义的关系语法是指语言的结构、即语言的“样子”；语义是指附着于语言结构上的实际含意，即语言的“意义”。对于语法和语义：语义不能离开语法独立存在；语义远比语法复杂；同一语言结构可以包含多种含意，

2、不同语言结构表示相同含意；语法与语义之间没有明确的界线。例1：猫吃老鼠与老鼠吃猫例2：程序设计语言中的分情况结构：1case condition is case1: stat1; case2: stat2; . end case; 2switch (condition) case condition1:stat1; case condition2:stat2; . break;break;24.1.1 语法与语义(续1) 语义分析的两个作用检查是否结构正确的句子所表示的意思也合法；执行规定的语义动作，如：表达式求值符号表填写中间代码生成等语义分析的方法语法制导翻译(2004年3月3

3、1日在此结束)34.1.2 属性与语义规则语法制导翻译的基本思想通俗地讲：以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。具体方法： 1将文法符号所代表的语言结构的意思，用附着于该文法符号的属性表示； 2用语义规则规定产生式所代表的语言结构之间的关系(即属性之间的关系)，即用语义规则实现属性计算。语义规则的执行：在语法分析的适当时刻(如推导或归约)执行附着在对应产生式上的语义规则，以实现对语言结构语义的处理，如计算、查填符号表、生成中间代码、发布出错信息等。44.1.2 属性与语义规则(续1) 属性的抽象表示.attr例如：E.val(值) E.type(类型)E.

4、code(代码序列)E.place(存储空间) 对文法的约定本章关注的是语法分析的基础上的语义处理，忽略语法分析。为了简单，本章的文法一般为二义文法。默认解决二义的方法是规定常规意义下的优先级和结合性。54.1.2 属性与语义规则(续2) 属性的定义*定义4.1 对于产生式A，其中是由文法符号X1X2.Xn组成的序列，它的语义规则可以表示为(4.1)所示关于属性的函数： b := f(c1, c2, ., ck) (4.1)语义规则中的属性存在下述性质与关系。 (1) 若b是A的属性，c1, c2, ., ck是中文法符号的属性，或者A的其它属性，则称b是A的综合属性。 (2) 若b是中某

5、文法符号Xi的属性，c1, c2, ., ck是A的属性，或者是中其它文法符号的属性，则称b是Xi的继承属性。 (3) 称(4.1)中属性b依赖于属性c1, c2, ., ck。 (4) 若语义规则的形式如下述(4.2)，则可将其想像为产生式左部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性上依然存在。 f(c1, c2, ., ck) (4.2) (4.1)中属性之间的依赖关系，实质上反映了属性计算的先后次序，即所有属性ci被计算之后才能计算属性b。 EE1+E2 E.val:=E1.val+E2.valEE1+E2 print(E.val)64.1.3 语义规则的两种形式语法制

6、导定义用抽象的属性和运算符号表示的语义规则；(公式，做什么) 翻译方案用具体属性和运算表示的语义规则。(程序段，如何做) 语义规则也被习惯上称为语义动作。忽略实现细节，二者作用等价。(设计与实现)7例4.1 将中缀形式的算术表达式转换为后缀表示的语法制导定义和翻译方案。虚拟属性print(E.post)可想象为L.p:=print(E.post)。产生式LEEE1+E2Enum 语法制导定义print(E.post)E.post:=E1.post |E2.post|+;E.post:=num.lexval; 翻译方案1print_post(post);post(k):=+; k:=k+1

7、;post(k):=lexval; k:=k+1; 翻译方案中需要考虑的问题：1采用什么样的语法分析方法；2为属性分配存储空间；3考虑计算次序。产生式翻译方案2LE EE1+E2 print(+);Enum print(lexval); 语法制导定义算法翻译方案程序实现，多种方法翻译方案1，自下而上计算，LR分析。(以3+5+8为例，归约时翻译)post:(3 5 + 8 +)84.1.3 语义规则的两种形式(续2) 属性作为分析树的注释将属性附着在分析树对应文法符号上，形成注释分析树。产生式语法制导定义翻译方案LE print(E.post);EE1+E2 E.post:=E1.

8、post print(+); |E2.post|+;Enum E.post:=num.lexval; print(lexval); 例4.2 3+5+8的分析树和注释分析树： .post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+)94.1.3 语义规则的两种形式(续3) 注释分析树上看继承属性与综合属性继承属性是自上而下计算的综合属性是自下而上计算的提醒：除非特别提醒，本章讨论的语法制导翻译是综合属性。104.1.4 LR分析翻译方案的设计 LR分析中的语法制导翻译实质上是对LR语法分析的扩充：扩充LR分析器的功能：当执行归约产生式的

9、动作时，也执行产生式对应的语义动作。由于是归约时执行语义动作，因此限制语义动作仅能放在产生式右部的最右边；扩充分析栈：增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值。例如： EE1+E2 valtop:=valtop+valtop+2; 对于表达式： 5+3当归约为左部E时，同时也得到了值8。114.1.4 LR分析翻译方案的设计(续1)例4.3 3+5*8的语法制导翻译。语法制导定义print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val*E2.val;E.val:=n.lexval;翻译方案print(valtop);valt

10、op:=valtop+valtop+2;valtop:=valtop*valtop+2;valtop:=lexval; 产生式LEEE1+E2EE1*E2En分析栈语义栈输入语义动作# # 3+5*8#shift#n #3 +5*8#En，valtop:=lexval#E #3 +5*8#shift#E+ #3? 5*8#shift#E+n #3?5 *8#En，valtop:=lexval#E+E #3?5 *8#shift #E+E* #3?5? 8# shift #E+E*n #3?5?8 # En，valtop:=lexval#E+E*E #3?5?8 # EE1*E2; valt

11、op:=valtop*valtop+2;#E+E #3?40 # EE1+E2，valtop:=valtop+valtop+2;#E #43 #acc 124.1.5 递归下降分析翻译方案的设计递归下降方法是用程序实现对非终结符的展开和对终结符的匹配。翻译方案的设计需要解决两个问题：1如何在递归下降子程序中嵌入语义动作：产生式右部的任何位置；2如何为文法符号的属性设计存储空间：函数返回值、参数、变量等。例函数绘图语言的解释器中语法制导翻译的设计： 1递归子程序可以设计为函数，用于返回必要的属性值；2适当设计子程序中的临时变量，用于保存属性值；3将语义动作嵌入在子程序的适位置，正确计算

12、属性值。 (第三次上机课介绍)134.2. 中间代码简介编译器各阶段的完整输出，均可以被认为是源程序的某种中间表示。本章讨论的是中间代码生成器输出的中间表示，称之为中间代码。中间代码实际上应起一个编译器前端与后端分水岭的作用。要求中间代码具有如下特性，以便于编译器的开发移植和代码的优化：1便于语法制导翻译；2既与机器指令的结构相近，又与具体机器无关。中间代码的主要形式：树、后缀式、三地址码等。 144.2.1 后缀式后缀式的特征操作符在前，操作数紧随其后，无需用括号限制运算的优先级和结合性。计算后缀式的虚拟机算法4.1 后缀式计算输入后缀式输出计算结果方法采用下述过程进

13、行计算，最终结果留在栈中。x := first_token;while not end_of_exp loop if x in operators then push x; - 操作数进栈 else pop(operators); - 算符，弹出操作数 push(evaluate); - 计算，并将结果进栈 end if; next(x);end loop; 15 后缀式计算 4.2.1 后缀式(续1)算术表达式3+5+8的后缀式为35+8+。算法4.1的计算：(#35+8+#进栈)(#3 5+8+#进栈)(#35 +8+#弹出3和5，计算3+5，结果进栈)(#8 8+#进栈)(#88 +#弹

14、出8和8，计算8+8，结果进栈)(#16 # )x := first_token;while not end_of_exp loop if x in operators then push x; - 操作数进栈 else pop(operators); - 算符，弹出操作数 push(evaluate); - 计算，并将结果进栈 end if; next(x);end loop; 16 将后缀式推广到其他语句 4.2.1 后缀式(续2) 后缀式并不局限于二元运算的表达式，可以推广到任何语句，只要遵守操作数在前，操作符紧跟其后的原则即可。语句：if e then x else y 它的后缀式可

15、以写为： e x y if-then-else(1)上述表示中，e、x和y均需计算。而实际上，根据条件e的取值，x和y不能都计算：e p1 jez x p2 jump p1: y p2:(2)其中：p1和p2分别是标号；p1 jez表示e的结果为0(假)则转向p1；p2 jump表示无条件转向p2。与 (1)比较，(2)中的if-then-else被分解，首先计算e，根据e的结果是否为真，决定计算x还是计算y。 174.2.2 4.2.2 三地址码三地址码三地址码的直观表示三地址码的直观表示语法：语法：语义：语义：例如：例如：赋值句赋值句x := a + b * cx := a + b

16、* c的三地址码序列：的三地址码序列：T1 := b * cT1 := b * cT2 := a + T1T2 := a + T1x := T2 x := T2 注意：注意：直观表示与源程序中赋值句的区别。直观表示与源程序中赋值句的区别。result := arg1 op arg2 result := arg1 op arg2 或或result := op arg1result := op arg1 或或 op arg1op arg1结果存放在结果存放在resultresult中的二元运算中的二元运算arg1 op arg2arg1 op arg2结果存放在结果存放在resultresult中

17、一元运算中一元运算op arg1op arg1一元运算一元运算op arg1op arg118 三地址码的种类三地址码的种类序号序号三地址码三地址码四元式四元式(1) x := y op z(op, y, z, x)(2) x := op y(op, y, , x)(3) x := y(:=, y, , x)(4) goto L(j, , , L)(5) if x goto L(jnz, x, , L)(6) if x relop y goto L(jrelop, x, y, L)(7) param x(param, , , x)(8) call n, P(call, n, , P)(9)

18、 return y(return, , , y)(10) x := yi(=, yi, , x)(11) xi := y(=, y, , xi)(12) x := &y(=&, y, , x)(13) x := *y(=*, y, , x)(14) *x := y(*=, y, , x) 19 三地址码的实现：三元式与四元式三地址码的实现：三元式与四元式三元式三元式三元式：三元式： (i) (op, arg1, arg2) 三地址码：三地址码：(i) := arg1 op arg2例例4.5 表达式表达式x:=a+b*c 的三元式：的三元式： (1) (*， b， c ) (2) (+，

19、a，(1) (3) (:=，x，(2) 标识符标识符a，b，c，x分别表示它们的存储位置，分别表示它们的存储位置，序号序号(1)、(2)、(3)分别是它们在三元式表中的位置。分别是它们在三元式表中的位置。1.序号的双重含义：序号的双重含义：既代表此三元式，又代表三元式存放的结果。既代表此三元式，又代表三元式存放的结果。2.存放方式：存放方式：数组结构，三元式在数组中的位置由下标决定。数组结构，三元式在数组中的位置由下标决定。3.弱弱点点：给给代代码码的的优优化化带带来来困困难难。因因为为代代码码优优化化常常使使用用的的方方法法是是删删除除某某些些代代码码或或将将某某些些代代码码移移动动位位置

20、置，而而一一旦旦进进行行了了代代码码的的删删除除或或移移动动，则则表表示示某某三三元式的序号就会发生变化，从而使得其他三元式中对原序号的引用无效。元式的序号就会发生变化，从而使得其他三元式中对原序号的引用无效。20 三元式的语法制导翻译三元式的语法制导翻译属性属性 .code：三元式代码，指示标识符的存储单元或三元式表中的序号；三元式代码，指示标识符的存储单元或三元式表中的序号；属性属性 .name：标识符的名字；标识符的名字；函数函数trip( op，arg1，arg2 )：生成一个三元式，返回三元式的序号；生成一个三元式，返回三元式的序号；函数函数 entry(id.name)：返回标识符

21、在符号表中的位置或存储位置。返回标识符在符号表中的位置或存储位置。产生式与语义规则：产生式与语义规则：(1) Aid:=E(2) EE1+E2(3) EE1*E2(4) E(E1)(5) E-E1(6) EidA.code:=trip(:=，entry(id.name)，E.code)E.code:=trip(+，E1.code，E2.code)E.code:=trip(*，E1.code，E2.code)E.code:=E1.codeE.code:=trip(，E1.code， )E.code:=entry(id.name) 21例例4.6 生成生成x:=a+b*c的三元式的三元式(LR分

22、析分析)(1) Aid:=E A.code:=trip(:=，entry(id.name)，E.code)(2) EE1+E2 E.code := trip(+，E1.code，E2.code)(3) EE1*E2 E.code := trip(*，E1.code，E2.code)(4) E(E1) E.code := E1.code(5) E-E1 E.code := trip(，E1.code， )(6) Eid E.code := entry(id.name) .code=a .code=b .code=c .code=(1)(*,b,c) .code=(3)(:=,x,(2) .cod

23、e=(2)(+,a,(1) 三元式序列：三元式序列： (1) (*, b, c ) (2) (+, a,(1) (3) (:=,x,(2)22 四元式四元式四四元元式式是是对对三三元元式式的的改改进进，在在将将表表示示计计算算结结果果的的三三元元式式序序号号用用一一个个显显示示的的变变量量表表示示，从从而而避避免免了了三三元元式式的的值值与与三三元元式式在在三三元元组组中中的位置相关的弱点。的位置相关的弱点。四元式的语法：四元式的语法： (op，arg1，arg2，result)所表示的计算：所表示的计算： result := arg1 op arg2 四四元元式式与与三三元元式式的的唯唯一

24、一区区别别是是将将由由序序号号所所表表示示的的运运算算结结果果改改为为了了由临时变量来表示。由临时变量来表示。这一改变使得四元式具有了运算结果与四元式在四元式序列中这一改变使得四元式具有了运算结果与四元式在四元式序列中的位置无关的特点，它为代码的优化提供了极大的方便，因为这的位置无关的特点，它为代码的优化提供了极大的方便，因为这样可以删除或移动四元式而不会影响运算的结果。样可以删除或移动四元式而不会影响运算的结果。三地址码与四元式形式的一致性。三地址码与四元式形式的一致性。三元式：三元式： (i) (op, arg1, arg2)(i) := arg1 op arg223 四元式的语法制

25、导翻译四元式的语法制导翻译属性属性.code：表示存放运算结果的变量；表示存放运算结果的变量；函数函数newtemp：返回一个新的临时变量，如返回一个新的临时变量，如T1，T2，.等。等。过程过程emit( op，arg1，arg2, result)：生成一个四元式。若一元，则生成一个四元式。若一元，则arg2可空；可空；产生式与语义规则：产生式与语义规则：(1)Aid:=E (2)EE1+E2(3)EE1*E2(4)E(E1)(5)E-E1(6)EidA.code:=newtemp; emit(:=，E.code, , A.code) emit(:=，E.code, , entry(id.

26、name)E.code:=newtemp; emit(+，E1.code,E2.code,E.code)E.code:=newtemp; emit(*，E1.code,E2.code,E.code)E.code:=E1.codeE.code:=newtemp; emit(,E1.code, , E.code)E.code:=entry(id.name) 244.2.3 图形表示树作为中间代码语法树真实反映句子结构，对语法树稍加修改(加入语义信息)，即可以作为中间代码的一种形式(注释语法树)。例4.8 赋值句x:=(a+b)*(a+b)的树的中间代码表示： T1/(1)T2/(2)T3/(

27、3)T4/(4)25 树的语法制导翻译 (1) A id := E (2) E E1 + E2(3) E E1 * E2(4) E ( E1 )(5) E - E1(6) E idA.nptr:= mknode(:=,mkleaf(entry(id.name),E.nptr)E.nptr:=mknode(+,E1.nptr,E2.nptr)E.nptr:=mknode(*,E1.nptr,E2.nptr)E.nptr:=E1.nptrE.nptr:=mknode(,E1.nptr, )E.nptr:=mkleaf(entry(id.name) 属性.nptr：指向树节点的指针；函数mknode

28、(op，nptr1，nptr2)：生成一个根或内部节点，节点数据是op， nptr1和nptr2分别指向的左右孩子的子树。若仅有一个孩子，则nptr2为空；函数mkleaf(node)：生成一个叶子节点。 26 树的优化表示DAG 如果树上若干个节点有完全相同的孩子，则这些节点可以指向同一个孩子，形成一个有向无环图(Directed Acyclic Graph, DAG)。 DAG与树的唯一区别是多个父亲可以共享同一个孩子，从而达到资源(运算、代码等)共享的目的。 DAG的语法制导翻译与树的语法制导翻译相似，仅需要在mknode和mkleaf中增加相应的查询功能。首先查看所要构造的节点是

29、否已经存在，若存在则无需构造新的节点，直接返回指向已存在节点的指针即可。 27 树与其他中间代码的关系树表示的中间代码与后缀式和三地址码之间有着内在的联系。对树进行深度优先的后序遍历，得到的线性序列就是后缀式，或者说后缀式是树的一个线性化序列。树的每个内部节点和它的孩子，对应一个三元式或四元式。例4.9 赋值句x:=(a+b)*(a+b)的注释语法树：后缀式：xab+ab+*:=三元式： (1)(+, a, b )(2)(+, a, b )(3)(*,(1),(2)(4)(:=,x, (3)四元式：(1)(+, a, b, T1)(2)(+, a, b, T2)(3)(*, T1,T2

30、,T3)(4)(:=,x, T3,T4) 因此，现代的编译器基础架构均用语法树作为中间表示。284.3 符号表简介符号表的作用：连接声明与引用的桥梁，记住每个符号的相关信息，如作用域和绑定等，帮助编译的各个阶段正确有效地工作。符号表设计的基本要求：目标是合理存放信息和快速准确查找。正确存储各类信息。适应不同阶段的需求；便于有效地进行查找、插入、删除和修改等操作；空间可以动态扩充； 294.3.1 符号表条目逻辑上讲：每个声明的名字在符号表中占据一栏，称为一个条目，用于存放名字的相关信息。符号表中的内容：保留字、标识符、特殊符号(包括算符、分隔符等)等等。不同类别的符号存放在不同的子表

31、中，如变量名表、过程名表、保留字表等。存放方式：关键字属性。关于组合关键字：.int x; double x; struct x float y, z; ; 为C+构造的符号表中，组合关键字至少应该包括三项：名字作用域类型。当一个名字x在同一作用域中允许有多于一个的声明，则对x的引用时需要根据上下文确定x到底属于哪个对象。因此程序设计语言在语法上规定了不允许这样的声明，以简化编译时的处理。304.3.2构成名字的字符串的存储定长数据变长数据直接存放间接存放名字(直接存储)属性sort proc, .a int, .readarray proc, .draw_a_red_line_for

32、_object_aboolean, .名字(间接存储)属性101 (或101/4) proc, .106 (或105/1)int, .108 (或106/9)proc, .118 (或105/28)boolean, . sort#a#readarray#draw_a_red_line_for_object_a#101 sortareadarraydraw_a_red_line_for_object_a101 间接存储的方法实际上解决了复杂信息的存储问题，将其推广到属性，则任何一个复杂的属性，均可以为其另辟空间(空间本身可以是复杂结构，如数组的内情向量等)，而仅需要将指向此空间的指针放在此属性在

33、符号表中的对应位置即可。 314.3.3 名字的作用域程序设计语言的名字可以出现在不同的范围内，并且可以具有不同的意义。两种划分范围的方式：并列的和嵌套的。不同的语言采用不同的方式：如Pascal的过程定义可以是嵌套的，而C的过程定义是并列的，但是C允许程序块是嵌套的。名字的作用域：名字在哪个范围内起作用。并列的两个范围内的名字作用域互不相干，但是分别在嵌套的两个范围内的名字，其作用域的问题就需要制定规则来限定，以使得任何一个名字在任何范围内涵义都是无二义的。名字的作用域规则：规定一个名字在什么样的范围内应该表示什么意义。 324.3.3 名字的作用域(续1) 静态作用域原则(static

34、-scope rule)：编译时就可以确定名字的作用域，也可以说，仅从静态读程序就可确定名字的作用域。最近嵌套原则(most closely nested)：以程序块为例，也适用于过程。程序块B中声明的作用域包括B；如果名字x不在B中声明，那么B中x的出现是在外围程序块B的x声明的作用域中，使得(a) B有x的声明，并且(b) B比其它任何含x声明的程序块更接近被嵌套的B。通俗地讲，名字的声明在离其最近的内层起作用，即在名字引用处从内向外看，它处在所遇到的第一个该名字声明的作用域。例子：找人张三；软件学院的张三；计算机学院的张三；西电软件学院的张三 334.3.3 名字的作用域(

35、续2)例4.10 说明符合作用域规则的C+程序。void main() int a=0, b=0;/* B0层 */ int b=1;/* B1层，被B0嵌套 */ int a=2, c=4, d=5;/* B2层，被B1嵌套 */ printf(%d %dn, a, b);/* 结果为：2，1 */ int b=3; /* B3层，与B2并列 */ printf(%d %dn, a, b); /* 结果为：0，3 */ printf(%d %dn, a, b);/* 结果为：0，1 */ printf(%d %dn, a, b); /* 结果为：0，0 */声明与作用域：声明作用域int

36、 a=0 B0-B2int b=0 B0-B1int b=1B1-B3int a=2 B2int b=3B3 344.3.4 线性表线性表应是一个栈，以正确反映名字的作用域，即符号的加入和删除，均在线性表的一端进行。线性表上的操作：关键字：名字作用域；查找：从表头(栈顶)开始，遇到的第一个名字；插入：先查找，再插入在表头；1 void main()2 int a=0, b=0; / B03 int b=1; / B14 int a=2, c=4, d=5; / B27 int b=3; / B311 354.3.4 线性表(续1)1 void main()2 int a=0, b=0;/

37、B03 int b=1;/ B14 int a=2, c=4, d=5; / B27 int b=3; / B311 线性表上操作的效率(n个条目)：一个名字的查找：成功查找(平均)：(n+1)/2；不成功查找：n+1建立n个条目的符号表(最坏)： = (n+1)(n+2)/2删除：(a) 暂时：将在同一作用域的名字同时摘走，适当保存；(b) 永久：将在同一作用域的名字同时摘走，不再保存。修改：与查找类似，修改第一个遇到的名字的信息。修改可以用插入删除代替。364.3.5 散列表散列表的构成将线性表分成m个小表。构造hash函数，使名字均匀地散布在m个子表中。如果散列均匀，则时间复杂度会降

38、到原线性表的1/m。每个名字挂在两个链上(便于删除操作)：哈希链(hash link)：链接所有具有相同hash值的元素，表头在表头数组中；作用域链(scope link)：链接所有在同一作用域中的元素，表头在作用域链中。其中： S1、S2、S4在同一作用域 S3在另一作用域37 散列表上的操作 4.3.5 散列表(续1)1查找：首先计算散列函数，然后从散列函数所指示的入口进入某个线性表，在线性表中沿hash link，象查找单链表中的名字一样进行查找。2插入：首先查找，以确定要插入的名字是否已在表中，若不在，则要分别沿hash link和scope link插入到两个链中，方法均是插

39、在表头，即两个表均可看作是栈。3删除：把以作用域链连在一起的所有元素从当前符号表中删除，保留作用域链所链的子表，为后继工作使用(如果是临时删除，则下次使用时直接沿作用域链加入到散列链中即可)。384.3.5 散列表(续2)设：hash(s)=ord(s)-ord(a)1 void main()2 int a=0, b=0; / B03 int b=1; / B14 int a=2, c=4, d=5; / B27 int b=3; / B311 分析在B2中：退出B2进入B3：39 散列函数的计算 hash: string integer 减少冲突，分布均匀充分考虑程序设计语言的特点若有变

40、量：V001,V002,V300，且首字母的值作为hash值。会发生什么？一种可行的hash函数计算方法：从串s=c1c2ck的字符ci确定正整数h：令： h0=0, 计算：hi=hi-1+ci, 1ik,得到：h=hk =1或是素数，如=65599。思考题：根据上述方法，设计一个hash函数并测试之。根据测试结果讨论各参数值对函数结果的影响。取一素数m, 令 h=h mod m。 40 散列函数的计算(续1)思考题(P108)：对于下列函数：#include const int PRIME=211;const int EOS=0;int hashpjw(char *s) char

41、*p; unsigned h=0, g; for (p=s; *p!=EOS; p+) h=(h24); h=hg; return h%PRIME; (1) 为每行语句写注释；(2) 写出此函数的计算公式；(3) 若参数是abcd，试给出返回值。414.4 声明语句的翻译声明语句的作用是为可执行语句提供信息，以便于其执行。对声明语句的处理，主要是将所需要的信息正确地填写进合理组织的符号表中。 4.4.1 变量的声明变量的类型定义与声明类型定义：为编译器提供存储空间大小的信息变量声明：为变量分配存储空间组合数据的类型定义和变量声明：定义与声明在一起，定义与声明分离。定义确定存储空间，声

42、明分配存储空间简单数据类型的存储空间是已经确定的，如integer可以占4个字节，real可以占8个字节，char可以占1个字节等。组合数据类型变量的存储空间，需要编译器根据程序员提供的信息计算而定。 42 变量的类型定义与声明例：在Pascal程序中的类型定义与变量声明：先定义后声明：type player = array1.2 of integer; matrix = array1.24 of char;var c, p : player; winner : boolean; display : matrix; movect : integer;定义与声明同时：var c, p :

43、array1.2 of integer; display : array1.24 of char;强调：简单变量声明中类型是预定义的；组合变量声明中类型需自己定义。(定义的两种形式)43 变量声明的语法制导翻译(a) 变量声明的文法： D D ; D (1) | id : T (2) T int (3) | real (4) | array num of T (5) | T (6) 产生式(5)是数组类型的声明，其中的数组元素个数由num表示，如num可以是5或10等，这是一个简化了的表示方法，它等价于1.5或1.10。产生式(6)是指针类型的声明，它的宽度(大小)是一个常量。数组元素的

44、类型和指针所指对象的类型可以是任意合法的类型。此文法可以声明多维数组，如数组A的声明形式可以是：A : array d1 of array d2 of . array dn of integer多维数组以行为主存储。因为：第一维是有d1个元素的一维数组，每个元素又是一个n-1维的数组；依此类推。 44 变量声明的语法制导翻译(续1) (b)(b) 填写符号表信息的语法制导翻译填写符号表信息的语法制导翻译全程量offset：记录当前被处理符号存储的偏移量，初值设为0属性.type和.width：变量的类型和所占据的存储空间过程enter(name, type, offset)：为type类型

45、的变量name建立符号表条目，并为其分配存储空间(位置)offset(1)DD;D(2)Did:T(3)Tint(4)Treal(5)Tarray num of T1(6)TT1enter(id.name, T.type, offset); offset:=offset+T.width;T.type:=integer; T.width:=4;T.type:=real; T.width:=8;T.type:=array(num.val, T1.type); T.width:=num.val*T1.width;T.type:=pointer(T1.type); T.width:=4; 45 变量声

46、明的语法制导翻译(续2)例声明序列的语法制导翻译： a : array 10 of int; x : int;序号归约使用的产生式语义处理结果(1) T1intT1.type=integer T1.width=4(2) T2arraynumof T1 T2.type=array(10,integer)T2.width=10*4=40(3) D1id:T2enter(a,array(10),0) offset=40(4) T3intT3.type=integer T3.width=4(5) D2id:T3enter(x,integer,40) offset=44 (2)Did:T enter

47、(id.name, T.type, offset); offset:=offset+T.width;(3)Tint T.type:=integer; T.width:=4;(5)Tarray num of T1 T.type:=array(num.val, T1.type); T.width:=num.val*T1.width;(6)TT1 T.type:=pointer(T1.type); T.width:=4; 464.4.3 过程的定义与声明 1过程(procedure)：过程头(做什么)过程体(怎么做)；函数；主程序2过程的三种形式：过程定义、过程声明和过程调用。例：Ada过程定义：

48、procedure swap(x,y:in out integer) is - 规格说明 temp : integer; - 体中的声明begin temp := x; x := y; y := temp; - 可执行语句序列end swap; 声明与引用：procedure swap(x, y: in out integer); - 过程声明swap(a, b); - 过程调用3先声明后引用原则过程定义可以写在对它的引用之后，或者引用时看不到的地方。在这样的情况下，引用前必须先声明。而若引用前已经定义，则声明可省略，因为定义已包括了声明。 474.4.3.1 左值与右值形式上，出现在

49、赋值号左边的对象称为左值，右边的称为右值；实质上，左值必须具有存储空间，而右值可以仅是一个值，没有存储空间。形象地讲，左值是容器，右值是内容。 (1) const two = 2;- 声明一个值为2的常量two(2) x : integer;- 声明一个类型为整型数的变量x(3) function max(a, b : integer) return integer;- 声明一个返回值类型是整型数的函数max(4) x := two;- 赋值句执行后，x当前值为2(5) x := two + x;- 赋值句执行后，x当前值变为4(6) x := max(two,x)+x; - 赋值句执行后

50、，x当前值变为8(7) 4 := x;- 字面量不能作为左值(8) two := x;- 常量不能作为左值(9) max(two,x) := two; - 函数返回值不能作为左值(10) x+two := x+two;- 表达式的值不能作为左值484.4.3.2 参数传递 1形参与实参定义时的参数称为形参(parameter或formal parameter)引用时的参数称为实参(argument或actual parameter)2常见的参数传递形式：(不同的语言提供不同的形式)值调用(call by value)引用调用(call by reference)复写恢复(copy-in/cop

51、y-out)换名调用(call by name)3参数传递方法的实质：实参是代表左值、右值、还是实参本身的正文。 49 值调用值调用的特点：实参的特点：参数传递和过程内对参数的使用原则：过程内部对参数的修改，不影响作为实参的变量原来的值。任何可以作为右值的对象均可作为实参。 (1) 过程定义时形参被当作局部名看待，并在过程内部为形参分配存储单元；(3) 过程内部对形参单元中的数据直接访问。 (2) 调用过程前，首先计算实参并将值(实参的右值)放入形参的存储单元；50值调用举例：值调用(续1) program reference ( input, output); var a, b :

52、 integer;begin a:=1; b:=2; swap(a, b); writeln(a=, a); writeln(b=, b)end. procedure swap(x, y : integer); var temp : integer; begin temp:=x; x:=y; y:=temp end;运行结果：a=1b=251等价的C+程序值调用(续2)/ - 值调用参数传递的演示程序#include void swap(int x, int y) int temp; temp=x; x=y; y=temp;void main () int a(1), b(2); coutb

53、efore: a=a b=bendl; swap(a, b); coutafter: a=a b=bendl;52 引用调用引用调用的特点：实参的特点：参数传递和过程内对参数的使用原则：过程内部对形参的修改，等价于直接对实参的修改。必须是左值。 (1) 定义时形参被当作变量地址看待，并在过程内部为形参分配存储单元；(2) 调用过程前，将作为实参的变量的地址放进形参的存储单元；(3) 过程内部把形参单元中的数据当作地址，进行间接访问。 53引用调用举例：引用调用(续1)program reference ( input, output); var a, b : integer;begin

54、a:=1; b:=2; swap(a,b); writeln(a=, a); writeln( b=, b)end. procedure swap(var x, y:integer); var temp : integer; begin temp:=x; x:=y; y:=temp end; procedure swap(x, y : integer); var temp : integer; begin temp:=x; x:=y; y:=temp end;运行结果：a=2b=154等价的C+程序引用调用(续2)/ - 引用调用参数传递的演示程序#include void swap(int

55、 &x, int &y) int temp; temp=x; x=y; y=temp;void main () int a(1), b(2); coutbefore: a=a b=bendl; swap(a, b); coutafter: a=a b=bendl;55值调用模拟引用调用引用调用(续3)/ - 值调用模拟引用调用参数传递的演示程序#include void main () int a(1), b(2); coutbefore: a=a b=bendl; swap(&a, &b); coutafter: a=a b=bendl;注意：C语言只有值调用因此：只能用值调用形式模拟引用

56、调用的效果同样：过程式程序设计语言可以模拟面向对象的继承机制结论：语言与程序设计范型(方法)不是一对一的关系void swap(int *x, int *y) int temp; temp=*x; *x=*y; *y=temp;56 复写-恢复 / - 引用调用的副作用的程序实例#include int a=2;void main () coutbefore: a=aendl; add_one(a); coutafter: a=aendl;引用调用的副作用本意：a=3结果：a=4原因：实参与非本地量共用一个存储空间，使得在过程内改变参数值的同时，也改变了非本地量的值。void add_one(

57、int &x) a=x+1; x=x+1; 57 复写-恢复(续1)复写-恢复的特点：(值调用和引用调用的结合)实参的特点：参数传递和过程内对参数的使用原则：过程内部对参数的修改，不直接影响实参，避免了副作用；返回时将形参内容恢复给实参，实现了参数的返回。必须是左值。 (1) 过程定义时形参被当作局部名看待，并在过程内部为形参分配单元(复写)；(2) 调用过程前，首先计算实参并将值(实参的右值)放入形参的存储单元；(3) 过程内部对形参单元中的数据直接访问；(4) 过程返回前，将形参的右值重新放回实参的存储单元(恢复)。 58复写-恢复举例：复写-恢复(续2)procedure test

58、is - Ada源程序 a : integer;begin a:=2; a:=add_one(a); put_line(a=, a); end test; procedure add_one(x:in out integer); - 复写-恢复调用begin a:=x+1; x:=x+1; end add_one;/ - 引用调用模拟复写-恢复参数传递的演示程序#include int a=2;void add_one(int &x) int local_x=x; a=local_x+1; local_x+; x=local_x;void main () coutbefore: a=aendl

59、; add_one(a); coutafter: a=aendl;59 换名调用严格讲，换名调用并不能算作真正的过程调用和参数传递。换名调用由Algol的复写规则定义： (1) 过程被认为宏，每次对过程的调用，实质上是用过程体替换过程调用，替换中用实参的文字替换体中的形参。这样的替换方式被称为宏替换或宏展开； (2) 应区分被调用过程的局部名和调用过程名。可以认为在宏展开前被调用过程的每个局部名系统地重新命名成可区别的名字； (3) 当需要保持实参的完整性时，可以为实参加括弧。换名调用在C+中的形式是宏定义(#define)，宏定义是采用预处理的方法，在预处理时进行宏替换。宏替换将过程

60、体直接展开在它被调用的地方，因此经过宏替换之后的程序中，已经不存在过程的调用与参数传递，它的特点是运行速度快。 60正文替换与函数调用的不一致性换名调用(续1)/ - 换名调用副作用的演示程序#include int temp;void main () int a(1), b=0,0; coutbefore: a=a b=b0 b1endl; swap(a, ba); coutafter: a=a b=b0 b1endl;#define swap(x, y) temp=x; x=y; y=temp; / 宏定义void swap(int &x, int &y)/ 引用调用 int temp;

61、 temp=x; x=y; y=temp; 61一种折中的方法换名调用(续2) C+的内联函数(inline)：与宏替换一样高效(避免了函数调用)；消除了宏替换的副作用(模拟函数调用的效果)。/- 宏定义#define macro_swap(x, y) temp=x; x=y; y=temp; /- 内联函数inline void inline_swap(int &x, int &y)int temp; temp=x; x=y; y=temp;/- 引用调用void procedure_swap(int &x, int &y)int temp; temp=x; x=y; y=temp;624

62、.4.3.3 作用域信息的保存过程的作用域与程序块类似，在允许嵌套定义过程的程序设计语言中，相同的名字可以同时出现在不同的作用域中，因此有必要讨论如何设计符号表来存放它们。此处讨论的过程作用域，同样遵守的是静态作用域和最近嵌套原则。定义4.2 设主程序(最外层过程)的嵌套深度dmain=1，则若过程A直接嵌套定义过程B，则dB=dA+1；变量声明时所在过程的嵌套深度，被认为是该变量的嵌套深度。与程序块相比，有两点不同，使得过程声明的处理复杂： 1. 过程头(即界面)是一个名字，可象引用变量一样被调用； 2. 程序块的执行(控制流)与静态一致，而过程不一致。63 过程的作用域(续1)例

63、4.14 快排序的Pascal程序： program sort(input,output); var a:array0.10of integer; x:integer; procedure readarray; procedure exchange(i,j:integer); procedure quicksort (m,n:integer );begin a0:=-9999; a10:=9999; readarray; quicksort(1,9)end sort. var i:integer; begin for i:=1 to 9 do read(ai)endreadarray;begi

64、n x:=ai; ai:=aj; aj:=x; endexchange; var i,v:integer; function partition(y,z:integer):integer;begin if (nm) then begin i:=partition(m,n); quicksort(m,i-1); quicksort(i+1,n) end;endquicksort;var i,j:integer;begin .a.; .v.; .exchange(i,j);.endpartition;64 过程的作用域(续2)sorta, x, 1readarrayi2exchange 2quic

65、ksorti, v2partitioni, j3 符号表中的作用域信息嵌套过程中名字作用域信息的保存，可以用具有嵌套结构的符号表来实现，每个过程可以被认为是一个子符号表，或者是符号表中的一个节点。嵌套的节点之间可以用双向的链表连接，正向的链指示过程的嵌套关系，而逆向的链可以用来实现按作用域对名字的访问。过程过程中的变量嵌套深度65 符号表中的作用域信息例4.15 忽略参数的快排序程序的符号表：双向链表：正向嵌套定义关系逆向作用域与可见性关系问题：参数如何处理？66 语法制导翻译生成符号表(a) 简化的过程定义文法(忽略了参数)： P D(1)D D ; D (2) | id : T(3

66、) | proc id ; D; S(4) 问题：如何在处理产生式(1)和(4)的语言结构时正确地填写符号表信息(双向链表)？修改文法，使得在定义D之前生成符号表(LR分析)：P M D(1)D D ; D (2) | id : T(3) | proc id ; N D; S(4)M (5)N (6)67(b) 全程量、属性与语义函数全程量：有序对栈(tblptr, offset)其中，tblptr保存指向符号表节点的指针，offset保存当前节点所需宽度。栈上的操作：push(t, o)、pop、top(stack)语义函数与过程：函数mktable(previous)：建立一个新的节点，并

67、返回指向新节点的指针。参数previous是逆向链，指向该节点的前驱，或者说是外层。过程enter(table, name, type, offset)：在table指向的节点中为名字name建立新的条目，包括名字的类型和存储位置等。过程addwidth(table, width)：计算table节点中所有条目的累加宽度，并记录在table的头部信息中。过程enterproc(table, name, newtable)：为过程name在table指向的节点中建立一个新的条目。参数newtable是正向链，指向name过程自身的节点。68(c) 语义规则(1) P M D(2) M (4) D

68、 id : T(5) D proc id ; N D1; S(6) N t:=mktable(null); push(t, 0,); t:=mktable(top(tblptr); push(t,0); enter(top(tblptr),id.name,T.type,top(offset); top(offset):=top(offset)+T.width; t:=top(tblptr); addwidth(t, top(offset); pop; enterproc(top(tblptr), id.name, t); addwidth(top(tblptr),top(offset); po

69、p; 69(d) 语法制导翻译的过程proc sort; a : array10 of int; x : int;readarray proc readarry; i : int;read(a);70(d) 语法制导翻译的过程(续1)序号产生式语义处理结果(1) M1t1 := mktable(null); push(t1, 0); (2) N1t2 := mktable(top(tblptr); push(t2, 0);(3) T1intT1.type=integer, T1.width=4(4) T2array 10of T2 T2.type=array(10,int),

70、 T2.width=40(4) D1a:T2 (a,arr,0)填进t2所指节点，top(offset):=40(5) T3intT2.type=integer, T2.width=4(6) D2x:T3 (x,int,40)填进t2所指节点，top(offset):=44(7) N2t3:=mktable(top(tblptr); push(t3,0);(8) T4intT4.type=integer, T4.width=4(9) D3i:T4 (i,int,0)填进t3所指节点，top(offset):=4(10) D4proc readarray N2 D3 ; S t:=top(tbl

71、ptr); addwidth(t,top(offset); pop; enterproc(top(tblptr),readarray,t);(13) D7proc sort N1 D6 ; St:=top(tblptr); addwidth(t,top(offset);pop; enterproc(top(tblptr),sort,t);(14) PM1 D7 addwidth(top(tblptr),top(offset); pop; 构造的符号表：714.5 简单算术表达式与赋值句简单算术表达式和赋值句，是指表达式和赋值句中变量是不可再分的简单变量。讨论所基于的文法：A id:=EE

72、E+E | E*E | -E | (E) | id724.5.1 简单变量的语法制导翻译属性.place：存放E的变量名地址(符号表中地址或临时变量的编码)；过程emit(result := arg1 op arg2)：生成“result:= arg1 op arg2”的三地址码。(1) Aid:=E(2) EE1+E2(3) EE1*E2(4) E-E1(5) E(E1)(6) Eid E.place:=entry(id.name) E.place:=newtemp； emit(E.place := E1.place + E2.place) E.place:=newtemp； emit(E

73、.place := E1.place * E2.place) E.place:=newtemp； emit(E.place := - E1.place) E.place:= E1.place emit(entry(id.name) := E.place) 734.5.2 变量的(内部)类型转换强制(coercion)：按照一定的原则，将不同类型的变量在内部转换为相同的类型，然后进行同类型变量的计算。运算的转换原则：赋值的转换原则：属性.mode：取值int或real表达式的类型判定树：744.5.2 变量的(内部)类型转换(续1)三地址码：T := itr E：将E从整型变为实型，结果存

74、放T中T := rti E：将E从实型变为整型，结果存放T中语义规则：A id := E tmode:=entry(id.name).mode; if tmode=E.mode then emit(entry(id.name) := E.place); else T := newtemp; if tmode=int then emit(T := rti E.place); else emit(T := itr E.place); end if; emit(entry(id.name) := T); end if; 754.5.2 变量的(内部)类型转换(续2)EE1 op E2 T:=newt

75、emp；E.mode:=real; if E1.mode=int then if E2.mode=int then emit(T := E1.place OPi E2.place); E.mode := int; else U:=newtemp; emit(U := itr E1.place); emit(T := U OPr E2.place); end if; else if E2.mode=int then U:=newtemp; emit(U := itr E2.place); emit(T := E1.place OPr U); else emit(T := E1.place OPr

76、 E2.place); end if; end if; E.place:=T;其他语义规则看教材P128129764.5.2 变量的(内部)类型转换(续3)例4.17 x:=-a*b+c的语法制导翻译，x、a、b是整型数，c是实型数。序号产生式中间代码(1)E1a(2)E2-E1 t1:=-a(3)E3b(4)E4E2*E3 t2:=t1*ib(5)E5c(6)E6E4*E5 t4:=itr t2 t3:=t4+rc(7)Ax:=E6 t5:=rti t3 x := t5774.6 数组元素的引用确定数组空间的存储分配：以第一个元素地址为首地址，分配一个连续空间。多维数组到一维存储空间的

77、映射方法：以行为主，以列为主考虑三行、三列的二维数组 a0.2, 2.4 ： a0,2 a0,3 a0,4a1,2 a1,3 a1,4a2,2 a2,3 a2,4 以行为主存放时的元素排列： a0,2 a0,3 a0,4 a1,2 a1,3 a1,4 a2,2 a2,3 a2,4以列为主存放时的元素排列： a0,2 a1,2 a2,2 a0,3 a1,3 a2,3 a0,4 a1,4 a2,4确定数组元素地址的两个要素：首地址和相对首地址的偏移量不同的映射方式，使得同一个数组元素相对首地址的偏移量不同例如：a1,4，偏移量分别是5和778确定映射方式的两种方法 1由声明时的语法确定映射方式：

78、a:arrayd1 of arrayd2of.arraydn of integer; 引用方式：ai1,i2, .,in或ai1i2.in2由编译器确定映射方式：a : array d1, d2, ., dn of integer;引用方式：ai1,i2, .,in 数组元素引用时地址的确定：1根据映射方式求出计算公式；2根据计算公式设计语义规则。 794.6.1 数组元素的地址计算三个假设条件：数组元素以行为主存放，推广到n维，就是数组的第i维中每个成员是di个n-i维的数组，其中di是第i维成员的个数；数组每维的下界均为1；每个元素仅占一个标准存贮单元(可以认为是一个字或者一个字节

79、)。约定：数组的声明：Ad1, d2, ., dn数组元素的引用：Ai1, i2, ., in一维数组元素的地址计算：addr(Ai)=a+(i-1)*w二维数组元素的地址计算：addr(Ai1,i2)=a+(i1-1)*d2+(i2-1)*w80n维数组元素的地址计算addr(Ai1，i2，.，in)=a+(i1-1)*d2*d3*.*dn+(i2-1)*d3*d4*.*dn+.+ (in-1)*w=a-(d2*d3*.*dn+d3*d4*.*dn+.+dn+1)*w +(i1*d2*d3*.*dn+i2*d3*d4*.*dn+.+in-1*dn+in)*w=ac*w+v*w根据假设条件，

80、w=1:addr(Ai1，i2，.，in)=ac+v 其中：c = d2*d3*d4.*dn+d3*d4*d5.*dn+ *d4*d5*d6.*dn.+dn+1 = (d2+1)*d3*.*dn+d4*d5.*dn+.+dn+1 =(d2+1)*d3+1)*d4*d5.*dn+.+dn+1 . = (.(d2+1)*d3+1)*d4.+1)*dn+1同理：v = (.(i1*d2+i2)*d3+i3)*d4.+in-1)*dn+in 81n维数组元素的地址计算(续1)c=(.(d2+1)*d3+1)*d4.+1)*dn+1v=(.(i1*d2+i2)*d3+i3)*d4.+in-1)*dn+i

81、n 令： v1 = i1则： v2 = i1*d2+i2 = v1*d2+i2 v3 = (v1*d2+i2)*d3+i3 = v2*d3+i3.于是有： v1 = i1 vj = vj-1*dj+ij (j=2，3，., n)(4.4)同理可得： c1 = 1 cj = cj-1*dj+1 (j=2，3，., n)(4.3) 最终得到数组元素引用的地址计算公式：addr(Ai1，i2，.，in)=a-c+v=CONSPART+VARPART 824.6.2 数组元素引用的语法制导翻译数组元素的寻址：CONSPARTVARPART，或者T1T取值的三地址码：X:=T1T 赋值的三地址码：T1

83、：存放vj=vj-1*dj+ij (j=2，3，., n)的临时变量，简单变量id：仍然表示简单变量的地址，数组元素idEL：存放不变部分，一般可以是一个临时变量。属性.offset：保存数组元素的可变部分，简单变量的offset为空，可记为null。函数limit(array, k)：计算并返回数组array中第k维成员个数dk。 84语义规则(4) ELidE EL.place:=E.place; EL.dim :=1; EL.array:=entry(id.name);(5) ELEL1,E T:=newtemp; k:=EL1.dim+1;dk:=limit(EL1.array,

84、k);emit(T :=EL1.place * dk);emit(T := E.place + T);EL.array:=EL1.array; EL.place:=T; EL.dim:=k; (3) VEL V.place:=newtemp; emit(V.place := EL.array - c); V.offset:=newtemp;emit(V.offset := EL.place * w);(2) Vid V.place:=entry(id.name); V.offset:=null; (1) AV:=E if V.offset=null then emit(V.place := E

85、.place); else emit(V.placeV.offset := E.place); end if; 85语义规则(续1)(6) EE1+E2 T:=newtemp; emit(T := E1.place + E2.place); E.place:=T; (7) E(E1) E.place:=E1.place;(8) EV if V.offset=null; then E.place:=V.place;else T:=newtemp; emit(T := V.place V.offset)； E.place:=T;end if; 86 分析举例例4.18：对于数组：arr:arra

86、y10,20 of int 赋值句arri+x,j+y:=m+n的语法制导翻译(令w=4)。解：c=(c1*d2+1)*w=(1*20+1)*4=84。分析树：87主要分析步骤：分析举例(续1)产生式属性计算结果中间代码V1iV1.place=i, V.offset=nullE1V1E1.place=V1.place=iE2V2E2.place=V2.place=xE3E1+E2E3.place=t1t1:=i+xEL1arrE3EL1.place=t1, EL1.dim=1EL1.array=arrE6E4+E5E6.place=t2t2:=j+yEL2EL1,E6EL2.array=a

87、rr, EL2.dim=2t3:=t1*20EL2.place=t3, d2=20t3:=t2+t3V5EL2V5.place=t4, V5.offset=t5t4:=arr-84t5:=t3*4E9E7+E8E9.place=t6t6:=m+nA V5:=E9t4t5:=t6 884.7 布尔表达式4.7.1 布尔表达式的作用与结构布尔表达式的应用：逻辑运算，如：x:=a or b 控制语句的控制条件，如if C then .，while C do .等布尔表达式与其他表达式的关系(优先级与结合性)： BEBE or BE|BE and BE|not BE|(BE)|RE|true|fa

88、lse RERE relop RE|(RE)|E E E op E|-E|(E)|id|num 布尔运算的优先级与结合性(从高到低)：not and or例如： a*by or not z等价于： (a*b)y) or (not z)简化的布尔表达式文法： EE or E|E and E|not E|(E)|id relop id|id|true|false 894.7.2 布尔表达式的计算方法数值表示的直接计算1表示true， 0表示false。or、and、not与+、*、-(一元)对应：T1 := not CT2 := B and T1T3 := A or T2 对于关系运算的表达式a

89、b的计算，可以翻译成如下固定的三地址码序列：(1) if ab goto (4)(2) t1 := 0(3) goto (5)(4) t1 := 1(5) .90 逻辑表示的短路计算短路计算以if-then-else的方式解释布尔表达式，具体控制逻辑如下： A or B ：if A then true else B A and B ：if A then B else false(4.7) not A ：if A then false else true 对布尔表达式A or B and not C采用短路计算，则等价于下述解释： if A then trueelse if Bthen if

90、C then false else true else false91 短路计算的必要性对于语句： while ptrnil and ptr.data=x do . 短路计算可以回避对ptr.data=x的判断，从而避免程序运行时错误。可以用语法规定短路计算。例如， Ada语言中提供两组运算： and 和 and then or 和 or else 短路计算时使用and then和or else，否则使用and和or。于是上述语句可以改写为： while ptr/=null and then ptr.data/=x loop . 924.7.3 数值表示与直接计算的语法制导翻译全程量nex

91、tstat：可用三地址码序号，调用一次emit，加1。语义规则：(1)EE1 or E2 E.place := newtemp; emit(E.place := E1.place or E2.place);(2) |E1 and E2 E.place := newtemp; emit(E.place := E1.place and E2.place);(3) |not E1 E.place := newtemp; emit(E.place := not E1.place);(4) |(E1) E.place := E1.place;(5) |id1 relop id2 E.place :=

92、newtemp; emit(if id1.place relop.op id2.place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place := 1); (1) if ab goto (4)(2) t1 := 0(3) goto (5)(4) t1 := 1(5) .934.7.3 数值表示与直接计算的语法制导翻译(续1)(6) |id E.place := entry(id.name);(7) |true E.place := newtemp; emit(E.place := 1);(8) |

93、false E.place := newtemp; emit(E.place := 0); 944.7.3 数值表示与直接计算的语法制导翻译(续2)布尔表达式ab or cd and ef的直接计算序号产生式三地址码(1) E1ab(1) if ab goto (4)(2) t1 := 0(3) goto (5)(4) t1 := 1(2) E2cd(5) if cd goto (8)(6) t2 := 0(7) goto (9)(8) t2 := 1(3) E3ef(9) if ef goto (12)(10) t3 := 0(11) goto (13)(12) t3 := 1(4) E

94、4E2 and E3(13) t4 := t2 and t3(5) E5E1 or E4(14) t5 := t1 or t4 954.7.4 短路计算的语法制导翻译属性 .true：表达式的真出口，它指向表达式为真时的转向；属性 .false：表达式的假出口，它指向表达式为假时的转向；函数 newlable：与newtemp相似，但它产生的是一个标号而不是一个临时变量。三地址码序列与.true、.false的关系：考虑布尔表达式EE1 or E2，它应该有下述代码序列：E1.code E1.false: E2.code 根据布尔表达式短路计算的逻辑(4.7)，上述表达式真、假出口之间存在下

95、述关系：E1.true = E2.true = E.true 和E2.false = E.false 即首先生成计算表达式E1的中间代码，然后在计算表达式E2的中间代码之前设置一个标号E1.false，使得当表达式E1为假时，转而计算表达式E2。96语义规则： 4.7.4 短路计算的语法制导翻译(续1) (1)EE1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code :=E1.code|emit(E1.false :|E2.code;(2) |E1 and E2 E1.fa

96、lse:=E.false; E1.true:=newlabel; E2.false:=E.false; E2.true:=E.true; E.code := E1.code|emit(E1.true :|E2.code; (3) |not E1 E1.false:=E.true; E1.true:=E.false;(4) |(E1) E1.false:=E.false; E1.true:=E.true; (5) |id1 relop id2 E.code:=emit(ifid1.place relop.op id2.placegotoE.true) |emit(goto E.false);(6

97、) |id E.code:=emit(if id.place goto E.true) |emit(goto E.false);(7) |true E.code:=emit( goto E.true);(8) |false E.code:=emit( goto E.false); 974.7.4 短路计算的语法制导翻译(续2)例4.20：再考虑布尔表达式ab or cd and ef的短路计算： if ab goto LT goto L2L2: if cd goto L1 goto LFL1: if ef goto LT goto LF drive me crazy!分析树：注释分析树：三地址

98、码序列：984.7.5 拉链与回填翻译方案需要解决的两个问题：如何实现表达式的真、假出口；如何在语法分析的同时正确生成三地址码序列，即所有的转向均可确定。换句话讲，设计一种什么样的翻译方案，使得仅对分析树进行一次遍历(LR分析中就是对分析树的一次自下而上的遍历)即可生成所需的中间代码序列。拉链与回填的基本思想：当三地址码中的转向不确定时，将所有转向同一地址的三地址码拉成一个链；一旦所转向的地址被确定，则沿此链将所有的三地址码中回填入此地址。 99短路计算的翻译方案新增函数与属性：属性.tc：真出口链，链接所有转向真出口的三地址码；属性.fc：假出口链，链接所有转向假出口的三地址码。

99、函数mkchain(i)：为序号为i的三地址码构造一个新链，且返回指向该链的指针；函数merg(P1，P2)：合并链P1和P2，且P2成为合并后的链头，并返回链头指针；过程backpatch(P，i)：将P链中相应域中的所有链域均回填为i值。 100例4.21：三地址码： (i) goto - .(j) goto - .(k) p1:=mklist(i)和p2:=mklist(j)操作之后： p2:=merge(P1, P2)操作之后： backpatch(P2, k)操作之后的三地址码： (i) goto k .(j) goto k .(k) 101属性与语义规则：属性.stat：记录当前第

100、一个可用三地址码的序号。短路计算的翻译方案(增加M产生式，以适应LR分析)： (1)M(2)EE1 or M E2 (3) |E1 and M E2(4) |not E1(5) |(E1) M.stat:=nextstat; backpatch(E1.fc, M.stat); E.tc:=mrge(E1.tc, E2.tc); E.fc:=E2.fc; E1.tc:=E.fc; E1.fc:=E.tc;E1.tc:=E.tc; E1.fc:=E.fc;(将或产生式中的.tc与.fc交换即得)下一张102属性与语义规则(续1)(7) |id E.tc:=mkchain(nextstat); E

101、.fc:=mkchain(nextstat+1); emit(if id.place goto -); emit(goto -); (8) |true E.tc:=mkchain(nextstat); emit(goto -);(9) |falseE.fc:=mkchain(nextstat); emit(goto -); (6) Eid1 relop id2 E.tc:=mkchain(nextstat); E.fc:=mkchain(nextstat+1); emit(if id1.place relop.op id2.place goto -); emit(goto -); 上一张下一张

102、103再考虑布尔表达式ab or cd and ef序号产生式三地址码(1) E1ab(1) if ab goto -(2) goto 3(2) M1(3) E2cd(3) if cd goto 5(4) goto -(4) M2(5) E3ef(5) if ef goto -(6) goto -(6) E4E2 and M2 E3(7) E5E1 or M1 E4 上一张1044.8 控制语句四类控制语句：无条件转移：goto (转向某标号所在位置) exit、break(退出某个范围)条件转移：if_then_else，while_do：判断布尔表达式循环：for_loop：设定下限、

104、.false: .(1) Sif E then S1 E.true:=newlabel; E.false:=S.next; S1.next:=S.next; S.code:=E.code|emit(E.true :)|S1.code; 已有属性： .true .false107 三地址码序列和语法制导定义(续1)Sif E then S1 else S2 ： E.codeE.true: S1.code goto S.nextE.false: S2.codeS.next: .(2) Sif E then S1 else S2 E.true :=newlabel; E.false:=newlabe

105、l; S1.next:=S.next; S2.next:=S.next; S.code :=E.code | emit(E.true :) | S1.code | emit(goto S.next)| emit(E.false :) | S2.code; 108 三地址码序列和语法制导定义(续2)Swhile E do S1 ：S.begin: E.codeE.true: S1.code goto S.beginE.false: . (3) Swhile E do S1 S.begin := newlabel; E.true := newlabel; E.false := S.next; S1

106、.next := S.begin; S.code := emit(S.begin :) | E.code | emit(E.true :) | S1.code | emit(goto S.begin); | emit(E.false :) 109 条件转移的控制流与翻译方案问题：一条语句的多个出口例1：if E1 then if E2 then S1 else S2 else S3 的控制流：S1、S2、S3的结束均使得整个条件语句结束。采用什么方法，让S1、S2、S3结束后均转向条件语句的结束？换句话说，如何在一遍分析中确定语句中所有可能的正确转向？110 条件转移的控制流与翻译方案(续1)

107、例2：while E3 do while E4 do S4的控制流：同样的问题：如何在一遍分析中确定语句中所有可能的正确转向？解决方案：拉链与回填 111 条件转移的控制流与翻译方案(续2)属性.nc：语句结束后的转向。未确定时拉链，确定后回填。属性.begin：语句(如while)的三地址码序列首地址。语义规则：(1)M M.stat:=nextstat;(2)Sif E then M S1 backpatch(E.tc,M.stat);S.nc:= merge(E.fc,S1.nc);(3)N N.nc:=mklist(nextstat); emit(goto -);(4)Sif E t

108、hen M1 S1 N else M2 S2 backpatch(E.tc,M1.stat); backpatch(E.fc,M2.stat); S.nc:=merge(S1.nc,merge(N.nc,S2.nc); (5)Swhile M1 E do M2 S1 backpatch(S1.nc,M1.stat); backpatch(E.tc,M2.stat); S.nc:=E.fc; emit(goto M1.stat); (6)A S.nc := mklist(); 112 条件转移的控制流与翻译方案(续3)例4.23：if ab then while ab do a := a+b的语

109、法制导翻译 (1) if ab goto (3)(2) goto -(3) if ab goto (5)(4) goto -(5) t1 := a+b(6) a := t1(7) goto (3) 1134.10 本章小结本章讨论的重点是程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。语法制导翻译的基本概念1.语法与语义；2.属性与属性的计算；3.语义规则的两种表现形式。中间代码1.为什么生成中间代码；2.中间代码的特征；3.各种形式的中间代码及它们之间的关系；4.最常用中间代码形式。符号表的组织1.符号表的条目与信息的存储直接存储与间接存

110、储；2.作用域信息的保存线性表与散列表，表上的操作，散列函数的计算。 1144.10 本章小结(续1) 声明语句的翻译1.定义与声明：类型定义与变量声明，过程定义与过程声明2.变量声明：符号表信息的填写；3.过程声明：(a)左值与右值；(b) 参数传递：参数传递的不同形式，各种参数传递形式的处理方式；(c) 名字的作用域：静态作用域与最近嵌套原则；(d) 声明中作用域信息的保存。可执行语句的翻译1.简单算术表达式和赋值句的翻译：语法制导翻译的设计，类型转换；2.数组元素的引用：数组元素地址计算的递推公式，地址的可变部分与不变部分，可变部分计算的语法制导翻译；3.布尔表达式短路计算的翻译：为什么需要短路计算，短路计算的控制流，真出口与假出口，真值链与假值链；4.控制语句的翻译：控制语句的分类，无条件转移与条件转移，拉链/回填技术。 1154.10 本章小结(续2) 基本设计方法1.声明性语句：需要保存什么信息，这些信息有哪些特征，设计什么样的数据结构存放这些信息；2.可执行语句：语句的结构应生成什么样的中间代码序列，根据中间代码序列设计语法制导定义，根据序列的特点设计翻译方案。以身作则：想要计算机做什么，自己先做一遍。勤动手：好记性不如烂笔头(天才不如勤奋)。自觉、认真、坚持：在海滩上写字，在悬崖上刻字。结束116

展开阅读全文

语法制导翻译生成中间代码.ppt

最新文档