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

资源描述

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

1、1第四章第四章第四章第四章语法制导翻译生成中间代码语法制导翻译生成中间代码语法制导翻译生成中间代码语法制导翻译生成中间代码语法制导翻译是处理语义的基本方法，它以语法分析为基础，在语法分析得到语言结构的结果时，对附着于此结构的语义进行处理，如计算表达式的值、生成中间代码等。与语法分析部分的讨论不同，本章的内容更注重于实际方法的讨论。主要内容包括：1.语法制导翻译的基本概念2.中间代码简介3.符号表简介4.典型声明语句与可执行语句的翻译5.上机：DBMS的设计与实现SQL的执行24.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介F语法与法与语义1.语法与语义的关系语

2、法是指语言的结构、即语言的“样子”；语义是指附着于语言结构上的实际含意，即语言的“意义”。语义不能离开语法独立存在；语义远比语法复杂；同一语言结构可包含多种含意，不同语言结构可表示相同含意；语法与语义之间没有明确的界线。例1猫吃老鼠与老鼠吃猫，晒被子与晒太阳例2程序设计语言中的分情况结构34.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介caseconditioniscase1:stat1;case2:stat2;.endcase;2.语义分析的两个作用检查是否结构正确的句子所表示的意思也合法；执行规定的语义动作，如：表达式求值符号表填写中间代码生成等3.语义分析

3、的方法语法制导翻译switch(condition)casecondition1:stat1;casecondition2:stat2;.break;break;44.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介F属性与属性与语义规则 1.语法制导翻译的基本思想通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。具体方法：将文法符号所代表的语言结构的意思，用附着于该文法符号的属性属性表示；用语义规则规定产生式所代表的语言结构之间的关系（即属性之间的关系），即用语义规则实现属性计算。语义规则的执行：在语法分析的适当时刻（如推导或归约）执行附着在

4、对应产生式上的语义规则，以实现对语言结构语义的处理，如计算、查填符号表、生成中间代码、发布出错信息等。54.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介2.属性的抽象表示.attr如：E.val（值），E.type（类型），E.code（代码序列），E.place（存储空间）3.对文法的约定只关注语法分析基础上的语义处理，忽略语法分析。为了简单，讨论的文法一般为二义文法。默认解决二义的方法是规定常规意义下的优先级和结合性。4.属性的定义定定义4.1对于产生式A，其中是由文法符号X1X2.Xn组成的序列，它的语义规则可以表示为(4.1)所示关于属性的函数：b:=f

5、(c1,c2,.,ck)(4.1)64.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介b := f(c1, c2, ., ck)(4.1)语义规则中的属性存在下述性质与关系。若b是A的属性，c1,c2,.,ck是中文法符号的属性，或者A的其它属性，则称b是A的综合属性合属性。若b是中某文法符号Xi的属性，c1,c2,.,ck是A的属性，或者是中其它文法符号的属性，则称b是Xi的继承属性承属性。称(4.1)中属性b依依赖于于属性c1,c2,.,ck。若语义规则的形式如下述(4.2)，则可将其想像为产生式左部文法符号A的一个虚虚拟属性属性。属性之间的依赖关系，在虚拟属

6、性上依然存在。f(c1,c2,.,ck)(4.2)(4.1)中属性之间的依赖关系，实质上反映了属性反映了属性计算的先后次算的先后次序序，即所有属性ci被计算之后才能计算属性b。74.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介F语义规则的两种形式的两种形式1.语法制导定义用抽象抽象属性和运算符号表示的语义规则(公式，做什么)2.翻译方案用具体具体属性和运算表示的语义规则（程序段，如何做）语义规则也被习惯上称为语义动作。忽略实现细节，二者作用等价。语法制导定义适用于设计阶段段，翻译方案适用于实现阶段段。84.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译

7、简介语法制导翻译简介例4.1将中缀形式的算术表达式转换为后缀表示。其语法制导定义和翻译方案可分别表示如下。其中print(E.post)是L的虚拟属性，可以想象为L.p:=print(E.post)。翻译方案中的.lexval表示词法分析返回的记号num的值。产生式产生式语法制导定义语法制导定义翻译方案翻译方案1翻译方案翻译方案2LEprint(E.post)print_post(post);EE1+E2E.post:=E1.post|E2.post|+;post(k):=+;k:=k+1;print(+);EnumE.post:=num.lexval;post(k):=lexval;k:=k

8、+1;print(lexval);语法制导定义：算法翻译方案：程序实现，方法不唯一94.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介翻译方案中需要考虑的问题：采用什么样的语法分析方法，不同的分析方法对语义处理的次序不同；为属性分配存储空间；考虑计算次序。翻译方案1，自下而上计算，LR分析。以3+5+8为例，归约时翻译。产生式产生式翻译方案翻译方案1LEprint_post(post);EE1+E2 post(k):=+;k:=k+1;Enumpost(k):=lexval;k:=k+1;post:(35+8+)104.1 4.1 语法制导翻译简介语法制导翻译简

9、介语法制导翻译简介语法制导翻译简介3.属性作为分析树的注释将属性附着在分析树对应文法符号上，形成注注释分析分析树。例4.23+5+8的分析树和注释分析树：产生式产生式语法制导定义语法制导定义翻译方案翻译方案2LEprint(E.post)EE1+E2E.post:=E1.post|E2.post|+;print(+);EnumE.post:=num.lexval;print(lexval);.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+)114.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介4.注释分析树

10、上看继承属性与综合属性继承属性是自上而下计算的综合属性是自下而上计算的提醒：除非特别提醒，本章讨论的语法制导翻译是综合属性合属性。.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+)12上次课总结上次课总结上次课总结上次课总结F语法制导翻译的基本概念属性与语义规则语义规则的两种形式134.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介FLR分析翻分析翻译方案的方案的设计LR分析中的语法制导翻译实质上是对LR语法分析的扩充：扩充充LR分析器的功能分析器的功能：当执行归约产生式的动作时，也执行产生式对应的语义动

11、作。由于是归约时执行语义动作，限制语义动作仅能放在产生式右部的最右边；扩充分析充分析栈：增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值。例如：EE1+E2valtop:=valtop+valtop+2;对于表达式5+3当归约为左部E时同时也得到了值814例4.33+5*8的语法制导翻译。产生式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#

12、shift#E+E* #3?5?8#shift#E+E*n#3?5?8#En,valtop:=lexval#E+E*E#3?5?8#EE1*E2,valtop:=valtop*valtop+2#E+E#3?40#EE1+E2,valtop:=valtop+valtop+2#E#43#acc翻译方案print(valtop);valtop:=valtop+valtop+2;valtop:=valtop*valtop+2;valtop:=lexval;语法制导定义print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val*E2.val;E.val:=n.lexva

13、l;154.1 4.1 语法制导翻译简介语法制导翻译简介语法制导翻译简介语法制导翻译简介F递归下降分析翻下降分析翻译方案的方案的设计递归下降方法是用程序实现对非终结符的展开和对终结符的匹配。翻译方案的设计需要解决两个问题：1.如何在递归下降子程序中嵌入语义动作？产生式右部的任何位置；2.如何为文法符号的属性设计存储空间？函数返回值、参数、变量等。例如在上机作业中，函数绘图语言解释器语法制导翻译设计：1.递归子程序可以设计为函数，用于返回必要的属性值；2.适当设计子程序中的临时变量，用于保存属性值；3.将语义动作嵌入在子程序的适当位置，正确计算属性值。164. 4.2 2 中间代码简介中间代码简

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

15、first_token;whilenotend_of_exploopifxinoperatorsthenpushx;-操作数进栈elsepop(operators); -算符，弹出操作数push(evaluate); -计算，将结果进栈endif;next(x);endloop;184. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介loopifxinoperatorsthenpushx;-操作数进栈elsepop(operators); -算符，弹出操作数push(evaluate); -计算，将结果进栈endif;next(x);endloop;算术表达式3+5+8的后缀式为

16、35+8+。#35+8+#push(3)#35+8+#push(3)#35+8+#pop(3和5)，push(3+5)#88+#push(8)#88+#pop(8和8)，push(8+8)#16#194. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介后缀式并不局限于二元运算的表达式，可以推广到任何语句，遵守操作数在前，操作符紧跟其后的原则即可。对语句：if e then x else y后缀式可以写为：e x y if-then-else(1)此时e、x和y均需计算。实际上，根据条件e的取值，x和y不用都计算：e p1 jez x p2 jump p1: y p2:(2)其中：

17、p1和p2分别是标号；p1jez表示e的结果为0（假）则转向p1；p2jump表示无条件转向p2。与(1)比较，(2)中的if-then-else被分解，首先计算e，根据e的结果是否为真，决定计算x还是计算y。204. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介F三地址三地址码1.三地址码的直观表示语法：result:=arg1oparg2或result:=oparg1或oparg1语义：结果存放在result中的二元运算arg1oparg2结果存放在result中一元运算oparg1一元运算oparg1赋值句x:=a+b*c的三地址码序列：T1:=b*cT2:=a+T1x:

18、=T2214. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介2.三地址码的种类序号三地址码四元式（1） x:=yopz(op,y,z,x)（2） x:=opy(op,y,x)（3） x:=y(:=,y,x)（4） gotoL(j,L)（5） ifxgotoL(jnz,x,L)（6） ifxrelopygotoL(jrelop,x,y,L)（7） paramx(param,x)（8） calln,P(call,n,P)（9） returny(return,y)（10）x:=yi(=,yi,x)（11）xi:=y(=,y,xi)（12）x:=&y(=&,y,x)（13）x:=*y(

19、=*,y,x)（14）*x:=y(*=,y,x)224. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介3.三地址码的实现：三元式与四元式三元式三元式(i)(op,arg1,arg2)三地址码(i):=arg1oparg2例4.5表达式x:=a+b*c的三元式：(1)(*，b，c)(2)(+，a，(1)(3)(:=，x，(2)序号的双重含序号的双重含义：既代表此三元式，又代表三元式存放的结果存放方式存放方式：数组结构，三元式在数组中的位置由下标决定。弱点弱点：给代码的优化带来困难。因为代码优化常使用的方法是删除某些代码或移动某些代码位置，而一旦进行了代码的删除或移动，则表示某三元

20、式的序号会发生变化，从而使得其他三元式中对原序号的引用无效。234. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介语法制导翻译设计的基本步骤1.文法符号属性的设计2.必要的基本操作（函数等）的设计3.语义规则的设计三元式的语法制导翻译1.属性.code：三元式代码，指示标识符的存储单元或三元式表中的序号；2.属性.name：标识符的名字；3.函数trip(op，arg1，arg2)：生成一个三元式，返回三元式的序号；4.函数entry(id.name)：返回标识符在符号表中的位置或存储位置。244. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介产生式语义规则(1

21、)Aid:=EA.code:=trip(:=，entry(id.name)，E.code)(2)EE1+E2E.code:=trip(+，E1.code，E2.code)(3)EE1*E2E.code:=trip(*，E1.code，E2.code)(4)E(E1)E.code:=E1.code(5)E-E1E.code:=trip(，E1.code，)(6)EidE.code:=entry(id.name)例4.6生成x:=a+b*c的三元式(LR分析)254. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介四元式四元式是对三元式的改进，将表示计算结果的三元式序号用一个显式的变

22、量表示，从而避免了三元式的值与三元式在三元组中的位置相关的弱点。四元式的语法：(op，arg1，arg2，result)所表示的计算：result:=arg1oparg2四元式的特点：1.四元式与三元式的唯一区别：将由序号所表示的运算结果改为由临时变量来表示。2.此改进使得四元式的运算结果与其位置无关，为代码优化提供了极大方便：可以删除或移动四元式而不影响运算结果。3.三地址码与四元式形式的保持一致。四元式的种类三元式(i)(op,arg1,arg2)(i):=arg1oparg2264. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介四元式的语法制导翻译1.属性.code：表示

23、存放运算结果的变量；2.函数newtemp：返回一个新的临时变量，如T1，.等；3.过程emit(op，arg1，arg2,result)：生成一个四元式，若为一元运算，则arg2可空。产生式与语义规则：(1)Aid:=EA.code:=newtemp;emit(:=,entry(id.name),E.code,A.code)(2)EE1+E2E.code:=newtemp;emit(+,E1.code,E2.code,E.code)(3)EE1*E2E.code:=newtemp;emit(*,E1.code,E2.code,E.code)(4)E(E1)E.code:=E1.code(5)

24、E-E1E.code:=newtemp;emit(,E1.code,E.code)(6)EidE.code:=entry(id.name)274. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介F图形表示形表示1.树作为中间代码语法树真实反映句子结构，对语法树稍加修改(加入语义信息)，即可以作为中间代码的一种形式(注释语法树)。例4.8赋值句x:=(a+b)*(a+b)的树的中间代码表示：三元式：三元式：(1)(+,a,b)(2)(+,a,b)(3)(*,(1),(2)(4)(:=,x,(3)四元式：四元式：(1)(+,a,b,T1)(2)(+,a,b,T2)(3)(*,T1,T

25、2,T3)(4)(:=,x,T3,T4)284. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介2.树的语法制导翻译属性.nptr：指向树节点的指针；函数mknode(op，nptr1，nptr2)：生成一个根或内部节点，节点数据是op，nptr1和nptr2分别指向的左右孩子的子树。若仅有一个孩子，则nptr2为空；函数mkleaf(node)：生成一个叶子节点。(1)Aid:=EA.nptr:=mknode(:=,mkleaf(entry(id.name),E.nptr)(2)EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)(3)EE1*E2E.

26、nptr:=mknode(*,E1.nptr,E2.nptr)(4)E(E1)E.nptr:=E1.nptr(5)E-E1E.nptr:=mknode(,E1.nptr,)(6)EidE.nptr:=mkleaf(entry(id.name)三元式、四元式与树的语义规则设计是相似的。三元式、四元式与树的语义规则设计是相似的。294. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介3.树的优化表示DAG如果树上若干个节点有完全相同的孩子，则这些节点可以指向同一个孩子，形成一个有向无环图(DirectedAcyclicGraph,DAG)，与树的唯一区唯一区别是多个父亲可以共享同一个

27、孩子，从而达到资源(运算、代码等)共享的目的。DAG的语法制导翻译与树的语法制导翻译相似，仅需要在mknode和mkleaf中增加相应的查询功能：先查看所要构造的节点是否已经存在，若存在则无需构造新的节点，直接返回指向已存在节点的指针即可。304. 4.2 2 中间代码简介中间代码简介中间代码简介中间代码简介4.树与其他中间代码的关系树表示的中间代码与后缀式和三地址码之间有内在联系：对树进行深度优先后序遍历，得到的线性序列就是后缀式，或者说后缀式是树的一个线性化序列；树的每个内部节点和它的孩子对应一个三元式或四元式。例4.9赋值句x:=(a+b)*(a+b)的注释语法树：后缀式：xab+ab+

28、*:=三元式：(1)(+,a,b)(2)(+,a,b)(3)(*,(1),(2)(4)(:=,x,(3)四元式：(1)(+,a,b,T1)(2)(+,a,b,T2)(3)(*,T1,T2,T3)(4)(:=,x,T3,T4)现代的编译器基础架构均用语法树作为中间表示。31上次课总结上次课总结上次课总结上次课总结F中间代码后缀式三地址码三元式四元式图形表示324. 4.3 3 符号表简介符号表简介符号表简介符号表简介符号表的作用：符号表的作用：连接声明与引用的桥梁，记住每个符号的相关信息，如作用域和绑定等，帮助编译的各个阶段正确有效地工作。符号表符号表设计的基本要求：的基本要求：合理存放信息、快

29、速准确查找。正确存储各类信息；适应不同阶段的需求；便于有效地进行查找、插入、删除和修改等操作；空间可以动态扩充。334. 4.3 3 符号表简介符号表简介符号表简介符号表简介F符号表条目符号表条目逻辑上讲：每个声明的名字在符号表中占据一栏，称为一个条目，用于存放名字的相关信息。符号表中的内容：保留字、标识符、特殊符号(包括算符、分隔符等)等。多个子表：不同类别的符号可以存放在不同的子表中，如变量名表、过程名表、保留字表等。存放方式：关关键字属性字属性。组合关合关键字字：intx;doublex;structxfloaty,z;C符号表的组合关键字至少包括：名字作用域名字作用域类型型一个名字x在

30、同一作用域中允许有多个的声明，则引用时需要根据上下文确定x属于哪个对象。为简化编译，大多数语言在语法上不允许这样的声明344. 4.3 3 符号表简介符号表简介符号表简介符号表简介F构成名字的字符串的存构成名字的字符串的存储定长数据采用直接存放，变长数据采用间接存放。名字（直接存名字（直接存储）属性属性sortproc,.aint,.readarrayproc,.draw_a_red_line_for_object_aboolean,.名字（名字（间接存接存储）属性属性101(或101/4)proc,.106(或105/1)int,.108(或106/9)proc,.118(或115/28)b

31、oolean,.sort#a#readarray#draw_a_red_line_for_object_a#101sortareadarraydraw_a_red_line_for_object_a101354. 4.3 3 符号表简介符号表简介符号表简介符号表简介间接存储的特点：1.间接存储的方法实际上解决了复杂信息的存储问题；2.将其推广到属性，则任何一个复杂的属性，均可以为其另辟空间；3.空间本身可以是任何复杂结构，如数组的内情向量等。4.指向空间的指针存放于此属性在符号表中的对应位置。关键字关键字属性属性x.任何复任何复杂结构构364. 4.3 3 符号表简介符号表简介符号表简介符号表

32、简介F名字的作用域名字的作用域程序设计语言的名字可以出现在不同的范围内，并且可以具有不同的意义。1.两种划分范两种划分范围的方式的方式：并列的和嵌套的。2.不同的不同的语言采用不同的方式言采用不同的方式：如Pascal的过程定义可以是嵌套的，而C的过程定义是并列的，但是C允许程序块是嵌套的。（问题：过程与程序块的主要区别？）3.名字的作用域名字的作用域：名字在哪个范围内起作用。并列的两个范围内的名字作用域互不相干，但是分别在嵌套的两个范围内的名字，其作用域的问题就需要制定规则来限定，以使得任何一个名字在任何范围内涵义都是无二义的。4.名字的作用域名字的作用域规则：规定一个名字在什么样的范围内应

33、该表示什么意义。374. 4.3 3 符号表简介符号表简介符号表简介符号表简介1.静静态作用域作用域规则(static-scoperule)编译时就可以确定名字的作用域，即仅从静态读程序就可确定名字的作用域。2.最近嵌套最近嵌套规则(mostcloselynested)以程序块为例，也适用于过程。程序块B中声明的作用域包括B；如果名字x不在B中声明，那么B中x的出现是在外围程序块B的x声明的作用域中，使得a)B有x的声明，并且b)B比其它任何含x声明的程序块更接近被嵌套的B通俗地讲，名字声明在离其最近的内层起作用，即在名字引用处从内向外看，它处在所遇到的第一个该名字声明的作用域。38例4.10

34、符合作用域规则的C+程序。voidmain() inta=0,b=0;/*B0层*/intb=1;/*B1层，被B0嵌套*/inta=2,c=4,d=5;/*B2层，被B1嵌套*/printf(%d%dn,a,b);/*结果为：2，1*/intb=3;/*B3层，与B2并列*/printf(%d%dn,a,b);/*结果为：0，3*/printf(%d%dn,a,b);/*结果为：0，1*/printf(%d%dn,a,b);/*结果为：0，0*/声声明明作用域作用域inta=0B0-B2intb=0B0-B1intb=1B1-B3inta=2B2intb=3B3394. 4.3 3 符号表

35、简介符号表简介符号表简介符号表简介F线性表性表线性表应是一个栈，以正确反映名字的作用域，即符号的加入和删除，均在线性表的一端进行。关关键字字：名字作用域；线性表上的操作：查找：从表头(栈顶)开始，遇到的第一个名字；插入：先查找，再插入在表头；1voidmain()2inta=0,b=0;/B03intb=1;/B14inta=2,c=4,d=5;/B27intb=3;/B311404. 4.3 3 符号表简介符号表简介符号表简介符号表简介删除：(a)暂时：将在同一作用域的名字同时摘走，适当保存；(b)永久：将在同一作用域的名字同时摘走，不再保存修改：与查找类似，修改第一个遇到的名字的信息。修改

36、可以用删除插入代替。线性表上操作的效率（n个条目）成功查找(平均)：(n+1)/2；不成功查找：n+1建立n个条目的符号表(最坏)：i (n+1)n/2414. 4.3 3 符号表简介符号表简介符号表简介符号表简介F散列表散列表将线性表分成m个小表，构造hash函数，使名字均匀散布在子表中。若散列均匀，则时间复杂度会降到原线性表的1/m名字挂在两个链上(便于删除操作)：1.散列散列链(hashlink)：链接所有具有相同hash值的元素，表头在表头数组中；2.作用域作用域链(scopelink)：链接所有在同一作用域中的元素，表头在作用域链中。S1S2S4在同一作用域S3在另一作用域424.

37、4.3 3 符号表简介符号表简介符号表简介符号表简介散列表上的操作1.查找找：首先计算散列函数，然后从散列函数所指示的入口进入某个线性表，在线性表中沿hashlink，象查找单链表中的名字一样查找。2.插入插入：首先查找，以确定要插入的名字是否已在表中，若不在，则要分别沿hashlink和scopelink插入到两个链中，方法均是插在表头，即两个表均可看作是栈。3.删除除：把以作用域链连在一起的所有元素从当前符号表中删除，保留作用域链所链的子表，为后继工作使用(如果是临时删除，则下次使用时直接沿作用域链加入到散列链中即可)。431voidmain()2inta=0,b=0;/B03intb=1

38、;/B14inta=2,c=4,d=5;/B27intb=3;/B311设：hash(s)=ord(s)-ord(a)分析在B2中：退出B2进入B3：44上次课总结上次课总结上次课总结上次课总结F符号表符号表的条目名字的存储名字的作用域（静态与最近嵌套原则）线性表散列表（作用域链与散列链）454. 4.3 3 符号表简介符号表简介符号表简介符号表简介散列函数的计算hash:stringinteger1.减少冲突，分布均匀2.充分考虑程序设计语言的特点例：若有变量V001,V002,V300，且首字母的值作为hash值，会发生什么？一种可行的hash函数计算方法：1.从串s=c1c2ck的字符c

39、i确定正整数h：令：h0=0,计算：hi=hi-1+ci,1ik,得到：h=hk=1或是素数，如=65599。2.取一素数m,令h=hmodm。464. 4.3 3 符号表简介符号表简介符号表简介符号表简介思考思考题(P108)：对于下列函数#includeconstintPRIME=211;constintEOS=0;inthashpjw(char*s)char*p;unsignedh=0,g;for(p=s;*p!=EOS;p+)h=(h24);h=hg;returnh%PRIME;(1)为每行语句写注释；(2)写出此函数的计算公式；(3)若参数是abcd，试给出返回值。474.4 4.4

40、声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译声明语句的作用是为可执行语句提供信息，以便于其执行。对声明语句的处理，主要是将所需要的信息正确地填写进合理组织的符号表中。F变量的声明量的声明1.变量的类型定义与声明类型定型定义为编译器提供存储空间大小的信息，变量声明量声明为变量分配存储空间。组合数据合数据的类型定义和变量声明有两种情况：定义与声明在一起，定义与声明分离。定义确定存储空间，声明分配存储空间简单数据类型的存储空间是已经确定的，如integer可以占4个字节，real可以占8个字节，char可以占1个字节等组合数据类型变量的存储空间，需要编译器根据程序员提供的信息计算而定4

41、84.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译例：在Pascal程序中的类型定义与变量声明：先定先定义后声明后声明typeplayer=array1.2ofinteger;matrix=array1.24ofchar;varc,p:player;winner:boolean;display:matrix;movect:integer;定定义与声明同与声明同时varc,p:array1.2ofinteger;display:array1.24ofchar;强调：1.简单变量声明中类型是预定义的；2.组合变量声明中类型需自己定义。（定义的两种形式）494.4 4.4 声

42、明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译2.变量声明的语法制导翻译变量声明的文法：DD;D(1)|id:T(2)Tint(3)|real(4)|arraynumofT(5)|T(6)(5)是数组类型的声明，其中的数组元素个数由num表示，如num可以是5或10等，它等价于1.5或1.10。(6)是指针类型的声明，其宽度(大小)是一个常量。数组元素的类型和指针所指对象的类型可以是任意合法类型。声明多维数组：A:arrayd1ofarrayd2of.arraydnofint此多维数组以行为主存储。因为第一维是有d1个元素的一维数组，每个元素又是一个n-1维的数组；依此类推。504.4

43、 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译填写符号表信息的语法制导翻译1.全程量offset：记录当前符号存储的偏移量，初值设为02.属性.type和.width：变量的类型和所占据的存储空间3.过程enter(name,type,offset)：为type类型的变量name建立符号表条目，并为其分配存储空间(位置)offset(1)DD;D(2)Did:Tenter(id.name,T.type,offset);offset:=offset+T.width;(3)TintT.type:=integer;T.width:=4;(4)TrealT.type:=real;T

44、.width:=8;(5)TarraynumofT1T.type:=array(num.val,T1.type);T.width:=num.val*T1.width;(6)TT1T.type:=pointer(T1.type);T.width:=4;514.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译例声明的语法制导翻译：a:array10ofint;x:int;(无分号)序号序号归约使用的产生式归约使用的产生式语义处理结果语义处理结果(1)T1intT1.type=integerT1.width=4(2)T2arraynumofT1T2.type=array(10,

45、integer)T2.width=10*4=40(3)D1id:T2enter(a,array(10),0)offset=40(4)T3intT3.type=integerT3.width=4(5)D2id:T3enter(x,integer,40)offset=4452上次课总结上次课总结上次课总结上次课总结F变量声明类型定义与变量声明语法制导翻译534.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译F过程的定程的定义与声明与声明过程（procedure）：过程头过程体；函数；主程序过程的三种形式：过程定义、过程声明和过程调用Ada过程定义：procedureswap(

46、x,y:inoutinteger)is-规格说明temp:integer;-体中的声明begintemp:=x;x:=y;y:=temp;endswap;-可执行语句序列声明与引用：procedureswap(x,y:inoutinteger);-过程声明swap(a,b);-过程调用先声明后引用原则过程定义可以写在对它的引用之后或引用时看不到的地方。在这样的情况下，引用前必须先声明。而若引用前已定义，则声明可省略，因为定义已包括了声明。544.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译1.左值与右值形式上，出现在赋值号左边和右边的变量称为左值和右值实质上，左值必须具

47、有存储空间，右值可以仅是一个值，而没有存储空间。形象地讲，左值是容器，右值是内容。(1)consttwo=2;-声明一个值为2的常量two(2)x:integer;-声明一个类型为整型数的变量x(3)functionmax(a,b:integer)returninteger;-声明一个返回值类型是整型数的函数max(4)x:=two;-x当前值为2(5)x:=two+x;-x当前值变为4(6)x:=max(two,x)+x; -x当前值变为8(7)4:=x;-字面量不能作为左值(8)two:=x;-常量不能作为左值(9)max(two,x):=two; -函数返回值不能作为左值(10)x+tw

48、o:=x+two;-表达式的值不能作为左值554.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译2.参数传递形参与实参定义时的参数称为形参(parameter或formalparameter)引用时的参数称为实参(argument或actualparameter)常见的参数传递形式：（不同的语言提供不同的形式）值调用（callbyvalue）引用调用（callbyreference）复写恢复（copy-in/copy-out）换名调用（callbyname）参数传递方法的实质：实参是代表左值、右值、还是实参本身的正文。564.4 4.4 声明语句的翻译声明语句的翻译声明语

49、句的翻译声明语句的翻译值调用值调用的特点：过程内部对参数的修改，不影响作为实参的变量原来的值。实参的特点：任何可以作为右值的对象均可作为实参。参数传递和过程内对参数的使用原则：1.过程定义时形参被当作局部名看待，并在过程内部为形参分配存储单元；2.调用过程前，首先计算实参并将值（实参的右值）放入形参的存储单元；3.过程内部对形参单元中的数据直接访问。574.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译值调用举例：programreference(input,output);vara,b:integer;procedureswap(x,y:integer);vartemp

50、:integer;begintemp:=x;x:=y;y:=tempend;begina:=1;b:=2;swap(a,b);writeln(a=,a);writeln(b=,b)end.运行结果：a=1b=2/等价的C+程序#includevoidswap(intx,inty)inttemp;temp=x;x=y;y=temp;voidmain()inta(1),b(2);swap(a,b);couta=ab=b;584.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译引用调用引用调用的特点：过程内部对形参的修改，等价于直接对实参的修改。实参的特点：必须是左值。参数传递和

51、过程内对参数的使用原则：1.定义时形参被当作局部名看待，并在过程内部为形参分配存储单元；2.调用过程前，将作为实参的变量的地址放进形参的存储单元；3.过程内部把形参单元中的数据当作地址，进行间接访问594.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译引用调用举例：programreference(input,output);vara,b:integer;procedureswap(var x, y : integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend;begina:=1;b:=2;swap(a,b);writel

52、n(a=,a);writeln(b=,b)end.运行结果：a=2b=1/等价的C+程序#includevoidswap(int &x, int &y)inttemp;temp=x;x=y;y=temp;voidmain()inta(1),b(2);swap(a,b);couta=ab=b;604.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译值调用模拟引用调用#includevoidswap(int*x,int*y)inttemp;temp=*x;*x=*y;*y=temp;voidmain()inta(1),b(2);swap(&a,&b);couta=ab=b;注意

53、：C语言只有值调用因此：只能用值调用形式模拟引用调用的效果同样：过程式程序设计语言可以模拟面向对象的继承机制结论：语言与程序设计范型（方法）不是一一对应的关系614.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译复写恢复引用调用的副作用inta=2;voidadd_one(int&x)a=x+1;x=x+1;voidmain()coutbefore:a=aendl;add_one(a);coutafter:a=aendl;本意本意：a=3结果果：a=4原因原因：实参与非本地量共用一个存储空间，使得在过程内改变参数值的同时，也改变了非本地量的值。624.4 4.4 声明语句

54、的翻译声明语句的翻译声明语句的翻译声明语句的翻译复写-恢复的特点：(值调用和引用调用的结合)1.过程内部对参数的修改不直接影响实参，避免了副作用2.返回时将形参内容恢复给实参，实现了参数的返回。实参的特点：必须是左值。参数传递和过程内对参数的使用原则：1.过程定义时形参被当作局部名，在过程内部为形参分配单元(复写)；2.调用过程前，计算实参并将右值放入形参的存储单元；3.过程内部对形参单元中的数据直接访问；4.过程返回前，将形参右值放回实参的存储单元(恢复)。634.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译复写-恢复举例：proceduretestis-Ada源程序

55、a:integer;procedureadd_one(x:in out integer);-复写-恢复调用begina:=x+1;x:=x+1;endadd_one;begina:=2;a:=add_one(a);put_line(a=,a);endtest;/引用调用模拟复写-恢复参数传递的演示程序inta=2;voidadd_one(int &x) intlocal_x=x;a=local_x+1;local_x+;x=local_x;voidmain() add_one(a);coutafter:a=aendl;644.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译

56、换名调用严格讲，换名调用并不能算作真正的过程调用和参数传递。换名调用由Algol的复写规则定义：1.过程被认为宏，每次对过程的调用，实质上是用过程体替换过程调用，替换中用实参的文字替换体中的形参。这样的替换方式被称为宏替换或宏展开；2.区分被调用过程的局部名和调用过程的名字。宏展开前被调用过程的每个局部名被重新命名成可区别的名字；3.当需要保持实参的完整性时，可为实参加括弧。换名调用的C+形式是宏定义(#define)，在预处理时进行宏替换，将过程体直接展开在它被调用的地方，消除了过程调用和参数传递，运行速度快。654.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译正文替

57、换与函数调用的不一致性/换名调用副作用的演示程序#includeinttemp;#defineswap(x,y)temp=x;x=y;y=temp; /宏定义voidswap(int&x,int&y)/引用调用inttemp;temp=x;x=y;y=temp;voidmain()inta(1),b=0,0;coutbefore:a=ab=b0b1endl;swap(a,ba);coutafter:a=ab=b0b1m)thenbegini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)end;endquicksort;begina0:=-9

58、999;a10:=9999;readarray;quicksort(1,9)endsort.过程过程变量变量深度深度sorta, x1readarrayi2exchange2quicksorti, v2partitioni, j3694.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译符号表中的作用域信息嵌套过程中的名字作用域信息，使用有嵌套结构的符号表保存。每个过程被认为是一个子符号表，或者是符号表中的一个节点。嵌套的节点之间用双向链连接，正向链指示过程的嵌套关系，逆向链实现按作用域对名字进行访问。参数如何处理参数如何处理?70上次课总结上次课总结上次课总结上次课总结F

59、过程的定义与声明定义、声明与引用左值与右值参数传递：值调用、引用调用、复写恢复、换名调用嵌套定义的过程中信息的存储F作用域信息的保存过程的作用域符号表中的作用域信息语法制导翻译生成符号表714.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译语法制导翻译生成符号表a)简化的过程定义文法(忽略了参数)PD(1)DD;D(2)|id:T(3)|procid;D;S(4)修改文法，在定义D之前生成符号表(LR分析)PMD(1)DD;D(2)|id:T(3)|procid;ND;S(4)M(5)N(6)问题：如何在处理产生式(1)和(4)的语言结构时正确地填写符号表信息(双向链表)

60、？724.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译b)全程量、属性与语义函数1.全程量：有序对栈(tblptr,offset)(符号表节点的指针,符号表节点所需宽度)2.栈上的操作：push(t,o)、pop、top(stack)3.语义函数与过程：函数mktable(previous)：建立一个新的节点，返回指向新节点的指针。previous是逆向链，指向该节点的前驱(外层)。过程enter(table,name,type,offset)：在table指向的节点中为名字name建立新的条目，包括名字的类型和存储位置等。过程addwidth(table,width)

61、：计算table节点中所有条目的累加宽度，并记录在table的头部信息中。过程enterproc(table,name,newtable)：为过程name在table指向的节点中建立一个新的条目。参数newtable是正向链，指向name过程自身的符号表节点。734.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译c)语义规则(1)PMDaddwidth(top(tblptr),top(offset);pop;(2)Mt:=mktable(null);push(t,0,);(3)DD;D(4)Did:Tenter(top(tblptr),id.name,T.type,top

62、(offset);top(offset):=top(offset)+T.width;(5)Dprocid;ND1;St:=top(tblptr);addwidth(t,top(offset);pop;enterproc(top(tblptr),id.name,t);(6)Nt:=mktable(top(tblptr);push(t,0);744.4 4.4 声明语句的翻译声明语句的翻译声明语句的翻译声明语句的翻译d)语法制导翻译的过程procsort;a:array10ofint;x:int;procreadarry;i:int;read(a);readarray75(1)M1t1:=mkta

63、ble(null);push(t1,0);(2)N1t2:=mktable(top(tblptr);push(t2,0);(3)T1intT1.type=integer,T1.width=4(4)T2array10ofT1T2.type=array(10,int),T2.width=40(5)D1a:T2(a,arr,0)填进t2所指节点，top(offset):=40(6)T3intT2.type=integer,T2.width=4(7)D2x:T3 (x,int,40)填进t2所指节点，top(offset):=44(8)N2t3:=mktable(top(tblptr);push(t3

64、,0);(9)T4intT4.type=integer,T4.width=4(10)D3i:T4 (i,int,0)填进t3所指节点，top(offset):=4(11)D4procreadarrayN2D3;St:=top(tblptr);addwidth(t,top(offset);pop;enterproc(top(tblptr),readarray,t);(14)D7procsortN1D6;St:=top(tblptr);addwidth(t,top(offset);pop;enterproc(top(tblptr),sort,t);(15)PM1D7addwidth(top(tbl

65、ptr),top(offset);pop;764.5 4.5 简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句讨论所基于的文法：Aid:=EEE+E|E*E|-E|(E)|idF简单变量的量的语法制法制导翻翻译属性.place：存放E的变量名地址(符号表中地址或临时变量)过程emit()：生成result:=arg1oparg2的三地址码。(1)Aid:=Eemit(entry(id.name):=E.place)(2)EE1+E2 E.place:=newtemp；emit(E.place:=E1.place+E2.place)(3)EE1*E2 E

66、.place:=newtemp；emit(E.place:=E1.place*E2.place)(4)E-E1E.place:=newtemp；emit(E.place:=-E1.place)(5)E(E1)E.place:=E1.place(6)EidE.place:=entry(id.name)774.5 4.5 简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句 F变量的量的(内部内部)类型型转换强制(coercion)：按照一定的原则，将不同类型的变量在内部转换为相同的类型，然后进行同类型变量的计算。属性.mode：取值int或real表达式的类型

67、判定树：运算的转换原则赋值的转换原则 784.5 4.5 简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句三地址码：T:=itrE：将E从整型变为实型，结果存放T中T:=rtiE：将E从实型变为整型，结果存放T中语义规则：Aid:=Etmode:=entry(id.name).mode;iftmode=E.modethenemit(entry(id.name):=E.place);elseT:=newtemp;iftmode=intthenemit(T:=rtiE.place);elseemit(T:=itrE.place);endif;emit(en

68、try(id.name):=T);endif;794.5 4.5 简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句 EE1opE2 T:=newtemp；E.mode:=real;ifE1.mode=intthen ifE2.mode=intthenemit(T:=E1.placeOPiE2.place);E.mode:=int;elseU:=newtemp;emit(U:=itrE1.place);emit(T:=UOPrE2.place);endif;else ifE2.mode=intthenU:=newtemp;emit(U:=itrE2.pla

69、ce);emit(T:=E1.placeOPrU);elseemit(T:=E1.placeOPrE2.place);endif;endif;E.place:=T;其他语义规则看教材P128129804.5 4.5 简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句简单算术表达式与赋值句例4.17x:=-a*b+c的语法制导翻译，x、a、b是整型数，c是实型数。序号产生式中间代码(1)E1a(2)E2-E1 t1:=-a(3)E3b(4)E4E2*E3t2:=t1*ib(5)E5c(6)E6E4+E5t4:=itrt2t3:=t4+rc(7)Ax:=E6t5:=rtit3x

70、:=t5.int.int.int.int.int.int.real.real.int(itor.int(itor) ).real(rtoi).real(rtoi)814.6 4.6 数组元素的引用数组元素的引用数组元素的引用数组元素的引用确定数组空间的存储分配：以第一个元素地址为首地址，分配一个连续空间。多维到一维存储空间的映射方法：以行为主或以列为主三行三列的二维数组：a0.2,2.4以行为主存放时的元素排列：a0,2a0,3a0,4a1,2a1,3a1,4a2,2a2,3a2,4以列为主存放时的元素排列：a0,2a1,2a2,2a0,3a1,3a2,3a0,4a1,4a2,4确定数组元素地

71、址的两个要素：首地址和相对首地址的偏移量。不同的映射方式，使得同一个数组元素相对首地址的偏移量不同。a0,2a0,3a0,4a1,2a1,3a1,4a2,2a2,3a2,4824.6 4.6 数组元素的引用数组元素的引用数组元素的引用数组元素的引用确定映射方式的两种方法1.由声明时的语法确定映射方式：a:arrayd1ofarrayd2of.arraydnofinteger;引用方式：ai1,i2,.,in或ai1i2.in2.由编译器确定映射方式：a:arrayd1,d2,.,dnofinteger;引用方式：ai1,i2,.,in数组元素引用时地址的确定：1.根据映射方式求出计算公式；2.

72、根据计算公式设计语义规则。834.6 4.6 数组元素的引用数组元素的引用数组元素的引用数组元素的引用F数数组元素的地址元素的地址计算算三个假设条件：以行为主存放，推广到n维，就是数组的第i维中每个成员是di个n-i维的数组，其中di是第i维成员的个数；数组每维的下界均为1；每个元素占一个标准存贮单元(认为是一个字或者字节)。数组的声明：Ad1,d2,.,dn数组元素的引用：Ai1,i2,.,in假设首地址为a，一个元素占w个单元一维数组地址计算：addr(Ai)=a+(i-1)*w二维数组地址计算：addr(Ai1,i2)=a+(i1-1)*d2+(i2-1)*w844.6 4.6 数组元素

73、的引用数组元素的引用数组元素的引用数组元素的引用n维数组地址计算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根据假设条件w=1:addr(Ai1，i2，.，in)=ac+vF数数组元素引用的元素引用的语法制法制导翻翻译基本方法：F求c和v的递推计算公式；F修改文法以适应递推计算；85上次课总结上次课总结上次课总结上次课总结F作用域信

74、息的保存过程的作用域符号表中的作用域信息语法制导翻译生成符号表F简单算术表达式与赋值句的语法制导翻译内部类型转换F数组元素的引用地址两要素：首地址、偏移量地址计算公式：a-c+v864.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式F布布尔表达式的作用与表达式的作用与结构构布尔表达式的应用：1.逻辑运算，如：x:=aorb2.控制语句的控制条件，如ifCthen.，whileCdo.等布尔表达式与其他表达式的关系：BEBEorBE|BEandBE|notBE|(BE)|RE|true|falseRERErelopRE|(RE)|EEEopE|-E|(E)|id|num约定的优先级与结合性

76、表达式布尔表达式布尔表达式2.逻辑表示的短路计算短路计算以if-then-else的方式解释布尔表达式，控制逻辑如下AorB： ifAthentrueelseBAandB：ifAthenBelsefalsenotA： ifAthenfalseelsetrue布尔表达式AorBandnotC采用短路计算，等价于下述解释：if AthentrueelseifBthenifCthenfalseelsetrueelsefalse894.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式3.短路计算的必要性对于语句：whileptrnilandptr.data=xdo.短路计算可以回避对ptr.dat

77、a=x的判断，从而避免程序运行时错误。可以用语法规定短路计算。如Ada语言中提供两组运算：and和andthenor和orelse短路计算时使用andthen/orelse，否则使用and/or。于是上述语句可以改写为：whileptrnullandthenptr.data=xloop.但是许多的程序设计语言没有规定(怎么做？)904.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式F数数值表示与直接表示与直接计算的算的语法制法制导翻翻译全程量nextstat：可用的三地址码序号，调用一次emit加1语义规则：(1)EE1orE2 E.place:=newtemp;emit(E.plac

79、7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式(5)Eid1relopid2E.place:=newtemp;emit(ifid1.placerelop.opid2.placegotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1);(1) if ab goto (4)(2) t1 := 0(3) goto (5)(4) t1 := 1(5) .924.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式布尔表达式aborcdandef的直接计算(1)E1ab(1)ifabgoto(4)(2)t1:=0(

80、3)goto(5)(4)t1:=1(2)E2cd(5)ifcdgoto(8)(6)t2:=0(7)goto(9)(8)t2:=1(3)E3ef(9)ifefgoto(12)(10)t3:=0(11)goto(13)(12)t3:=1(4)E4E2andE3(13)t4:=t2andt3(5)E5E1orE4(14)t5:=t1ort4934.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式F短路短路计算的算的语法制法制导定定义属性.true：表达式的真出口，它指向表达式为真时的转向；属性.false：表达式的假出口，它指向表达式为假时的转向；函数newlabel：与newtemp相似，但产

81、生标号而不是临时变量三地址码序列与.true、.false的关系：考虑布尔表达式EE1orE2，它应该有下述代码序列：E1.codeE1.false:E2.code生成表达式E1的中间代码，在表达式E2的中间代码前设置标号E1.false，当表达式E1为假时，转而计算表达式E2。根据布尔表达式短路计算的逻辑，其真假出口间存在关系：E1.true=E2.true=E.true和 E2.false=E.false94语义规则：(1)EE1orE2E1.true:=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;E.code:=

83、rue)|emit(gotoE.false);(6)|idE.code:=emit(ifid.placegotoE.true)|emit(gotoE.false);(7)|trueE.code:=emit(gotoE.true);(8)|falseE.code:=emit(gotoE.false);954.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式例4.20再考虑布尔表达式aborcdandef的短路计算：分析树：注释分析树：ifabgotoLTgotoL2L2:ifcdgotoL1gotoLFL1:ifefgotoLTgotoLF三地址码序列：原理上的，不能执行！自下而上分析中计算

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

85、表达式新增函数与属性：1.属性.tc：真出口链，链接所有转向真出口的三地址码；2.属性.fc：假出口链，链接所有转向假出口的三地址码。3.函数mkchain(i)：为序号为i的三地址码构造一个新链，且返回指向该链的指针；4.函数merge(P1，P2)：合并链P1和P2，且P2成为合并后的链头，并返回链头指针；5.过程backpatch(P，i)：将P链中所有链域均回填为i值。(i) goto - .(j) goto - .(k) p1:=mkchain(i)、p2:=mkchain(j)p2:=merge(P1,P2)backpatch(P2,k)(i) goto k .(j) goto k

86、 .(k) 984.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式属性与属性与语义规则属性.stat：记录当前第一个可用三地址码的序号。短路计算的翻译方案(增加M产生式，以适应LR分析)：(1)MM.stat:=nextstat;(2)EE1orME2backpatch(E1.fc,M.stat);E.tc:=merge(E1.tc,E2.tc);E.fc:=E2.fc;(3)|E1andME2(将或产生式中的.tc与.fc交换即得)(4)|notE1E.tc:=E1.fc;E.fc:=E1.tc;(5)|(E1)E.tc:=E1.tc;E.fc:=E1.fc;994.7 4.7 布尔表

87、达式布尔表达式布尔表达式布尔表达式(6)Eid1relopid2E.tc:=mkchain(nextstat);E.fc:=mkchain(nextstat+1);emit(ifid1.placerelop.opid2.placegoto-);emit(goto-);(7)|idE.tc:=mkchain(nextstat);E.fc:=mkchain(nextstat+1);emit(ifid.placegoto-);emit(goto-);(8)|trueE.tc:=mkchain(nextstat);emit(goto-);(9)|falseE.fc:=mkchain(nextstat)

88、;emit(goto-);1004.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式布布尔表达式表达式ab or cd and ef1014.7 4.7 布尔表达式布尔表达式布尔表达式布尔表达式对照ifabgotoLTgotoL2L2:ifcdgotoL1gotoLFL1:ifefgotoLTgotoLF序号产生式三地址码(1)E1ab(1)ifabgoto-(2)goto3(2)M1(3)E2cd(3)ifcdgoto5(4)goto-(4)M2(5)E3ef(5)ifefgoto-(6)goto-(6)E4E2andM2E3回填(3)(7)E5E1orM1E4回填(2)102上次课总结

90、制语句控制语句控制语句控制语句F标号与无条件号与无条件转移移无条件转移的两个要素：标号所标记的位置和goto所转向的标号。起标记位置作用的标号称为标号的定义出现；goto转向的标号称为标号的引用出现。在一定的作用域内，标号仅可定义一次，而可引用多次。定义时将有关信息填写进符号表中，引用时根据符号表中的信息生成正确转移的三地址码。当引用先于定义时需要使用符号表的拉链与回填符号表中新增属性与函数：1.type：记录标识符的类型，如标号或未知；2.def：若是标号，记录是否已定义，如未定义或已定义3.addr：标号定义前为链头，定义后为对应三地址码序号4.过程fill(entry(id.name),

91、a,b,c)，填写.type、.def、.addr1054.8 4.8 控制语句控制语句控制语句控制语句(1)Sgotoidifentry(id.name).type=未知-标识符第一次出现then fill(entry(id.name),标号,未定义,nextstat);emit(goto-);else ifentry(id.name).type=标号-已出现且是标号thenemit(goto,entry(id).addr)；-addr有双重含义ifentry(id.name).def=未定义-尚未定义，需要更新链头为最新序号thenfill(entry(id.name),标号,未定义,ne

92、xtstat-1);endif;elseerror；-标识符已出现且类型不是标号，出错endif;endif;(2)SLABS 根据S是何种语句，进行相应的翻译1064.8 4.8 控制语句控制语句控制语句控制语句(3)LABid：ifentry(id.name).type=未知-标识符第一次出现then fill(entry(id.name),标号,已定义,nextstat);else ifentry(id.name).type=标号andentry(id.name).def=未定义-还未定义出现thenq:=entry(id.name).addr;fill(entry(id.name),标

93、号,已定义,nextstat);-更新条目backpatch(q,nextstat);elseerror;-其它情况均出错endif;endif;lab:x:=a+b;gotolab;结果：(1)goto -(2)goto 1 回填回填(1)(2)(3)t1:=a+b(4)x:=t1(5)goto3gotolab;gotolab;lab:x:=a+b;gotolab;结果：(1)t1:=a+b(2)x:=t1(3)goto11074.8 4.8 控制语句控制语句控制语句控制语句F条件条件转移移1.三地址码序列和语法制导定义属性.begin：语句S开始的三地址码序号属性.next：语句S结束后的

94、三地址码序号SifEthenS1E.codeE.true:S1.codeE.false:.(1)SifEthenS1E.true:=newlabel;E.false:=S.next;S1.next:=S.next;S.code:=E.code|emit(E.true:)|S1.code;1084.8 4.8 控制语句控制语句控制语句控制语句SifEthenS1elseS2E.codeE.true:S1.codegotoS.nextE.false:S2.codeS.next:.(2)SifEthenS1elseS2E.true:=newlabel;E.false:=newlabel;S1.nex

95、t:=S.next;S2.next:=S.next;S.code:=E.code|emit(E.true:)|S1.code|emit(gotoS.next)|emit(E.false:)|S2.code;1094.8 4.8 控制语句控制语句控制语句控制语句SwhileEdoS1S.begin:E.codeE.true:S1.codegotoS.beginE.false:.(3)SwhileEdoS1S.begin:=newlabel; E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=emit(S.begin:)|E.cod

96、e|emit(E.true:)|S1.code|emit(gotoS.begin)|emit(E.false:);1104.8 4.8 控制语句控制语句控制语句控制语句2.条件转移的控制流与翻译方案问题：一条语句的多个出口例1ifE1thenifE2thenS1elseS2elseS3S1、S2、S3的结束均使得整个条件语句结束。采用什么方法，让S1、S2、S3结束后均转向条件语句的结束？换句话说，如何在一遍分析中确定语句中所有可能的正确转向？1114.8 4.8 控制语句控制语句控制语句控制语句例2whileE3dowhileE4doS4如何在一遍分析中确定语句中所有可能的正确转向？解决方案

97、解决方案：拉链与回填1124.8 4.8 控制语句控制语句控制语句控制语句属性.nc：语句结束后的转向。未确定时拉链，确定后回填。属性.begin：语句(如while)的三地址码序列首地址。(1)MM.stat:=nextstat;(2)SifEthenMS1backpatch(E.tc,M.stat);S.nc:=merge(E.fc,S1.nc);(3)NN.nc:=mkchain(nextstat);emit(goto-);(4)SifEthenM1S1NelseM2S2backpatch(E.tc,M1.stat);backpatch(E.fc,M2.stat);S.nc:=merge

98、(S1.nc,merge(N.nc,S2.nc);(5)SwhileM1EdoM2S1backpatch(S1.nc,M1.stat);backpatch(E.tc,M2.stat);S.nc:=E.fc;emit(gotoM1.stat);(6)SAS.nc:=mkchain();1134.8 4.8 控制语句控制语句控制语句控制语句例4.23ifabthenwhileabdoa:=a+b的语法制导翻译(1)ifabgoto(3)(2)goto-(3)ifabgoto(5)(4)goto-(5)t1:=a+b(6)a:=t1回填(3)(7)goto(3)回填(1)1144.9 4.9 本章小

99、结本章小结本章小结本章小结重点是程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。F语法制导翻译的基本概念语法与语义属性与语义规则语义规则的两种形式F中间代码为什么生成中间代码常用形式：树、后缀式、三地址码(三元式、四元式)F符号表的组织条目与信息存储(直接/间接)作用域信息保存(线性表、散列表)1154.9 4.9 本章小结本章小结本章小结本章小结F声明语句的翻译定义与声明：类型定义与变量声明，过程定义与声明变量声明：填写符号表过程声明左值与右值值调用、引用调用、复写恢复、换名调用名字的作用域：静态作用域与最近嵌套原则嵌套定义的过程中信息的存储F可执行语句的翻译简单算术表达式和赋值句的翻译：类型转换数组元素的引用1164.9 4.9 本章小结本章小结本章小结本章小结布尔表达式短路计算的翻译：为什么需要短路计算，短路计算的控制流，真出口与假出口，真值链与假值链控制语句的翻译：控制语句的分类，无条件转移与条件转移，拉链/回填技术F基本设计方法声明性语句：需要保存什么信息，设计什么样的数据结构存放这些信息可执行语句：生成什么样的中间代码序列，如何设计语法制导定义，如何设计翻译方案第四章第四章第四章第四章语法制导翻译生成中间代码语法制导翻译生成中间代码语法制导翻译生成中间代码语法制导翻译生成中间代码F作作业四、3五、1，2，3，4117

展开阅读全文

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

最新文档