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

1,第四章语法制导翻译生成中间代码,语法制导翻译是处理语义的基本方法，它以语法分析为基础，在语法分析得到语言结构的结果时，对附着于此结构的语义进行处理，如计算表达式的值、生成中间代码等。与语法分析部分的讨论不同，本章的内容更注重于实际方法的讨论。主要内容包括：语法制导翻译的基本概念中间代码简介符号表简介典型声明语句与可执行语句的翻译,2,4.1语法制导翻译简介4.1.1语法与语义,语法与语义的关系语法是指语言的结构、即语言的“样子”；语义是指附着于语言结构上的实际含意，即语言的“意义”。对于语法和语义：语义不能离开语法独立存在；语义远比语法复杂；同一语言结构可以包含多种含意，不同语言结构表示相同含意；语法与语义之间没有明确的界线。,例1：猫吃老鼠与老鼠吃猫例2：程序设计语言中的分情况结构：,1caseconditioniscase1:stat1;case2:stat2;.endcase;,2switch(condition)casecondition1:stat1;casecondition2:stat2;.,break;break;,3,4.1.1语法与语义(续1),语义分析的两个作用检查是否结构正确的句子所表示的意思也合法；执行规定的语义动作，如：表达式求值符号表填写中间代码生成等语义分析的方法语法制导翻译,(2004年3月31日在此结束),4,4.1.2属性与语义规则,语法制导翻译的基本思想通俗地讲：以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。具体方法：1将文法符号所代表的语言结构的意思，用附着于该文法符号的属性表示；2用语义规则规定产生式所代表的语言结构之间的关系(即属性之间的关系)，即用语义规则实现属性计算。语义规则的执行：在语法分析的适当时刻(如推导或归约)执行附着在对应产生式上的语义规则，以实现对语言结构语义的处理，如计算、查填符号表、生成中间代码、发布出错信息等。,5,4.1.2属性与语义规则(续1),属性的抽象表示.attr例如：E.val(值)E.type(类型)E.code(代码序列)E.place(存储空间)对文法的约定本章关注的是语法分析的基础上的语义处理，忽略语法分析。为了简单，本章的文法一般为二义文法。默认解决二义的方法是规定常规意义下的优先级和结合性。,6,4.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是中某文法符号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+E2E.val:=E1.val+E2.val,EE1+E2print(E.val),7,4.1.3语义规则的两种形式,语法制导定义用抽象的属性和运算符号表示的语义规则；(公式，做什么)翻译方案用具体属性和运算表示的语义规则。(程序段，如何做)语义规则也被习惯上称为语义动作。忽略实现细节，二者作用等价。(设计与实现),8,例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;post(k):=lexval;k:=k+1;,翻译方案中需要考虑的问题：1采用什么样的语法分析方法；2为属性分配存储空间；3考虑计算次序。,产生式翻译方案2LEEE1+E2print(+);Enumprint(lexval);,语法制导定义算法翻译方案程序实现，多种方法,翻译方案1，自下而上计算，LR分析。(以3+5+8为例，归约时翻译),post:(35+8+),9,4.1.3语义规则的两种形式(续2),属性作为分析树的注释将属性附着在分析树对应文法符号上，形成注释分析树。,产生式语法制导定义翻译方案LEprint(E.post);EE1+E2E.post:=E1.postprint(+);|E2.post|+;EnumE.post:=num.lexval;print(lexval);,例4.23+5+8的分析树和注释分析树：,.post=3,.post=5,.post=8,.post=35+,.post=35+8+,(print(35+8+),10,4.1.3语义规则的两种形式(续3),注释分析树上看继承属性与综合属性继承属性是自上而下计算的综合属性是自下而上计算的提醒：除非特别提醒，本章讨论的语法制导翻译是综合属性。,11,4.1.4LR分析翻译方案的设计,LR分析中的语法制导翻译实质上是对LR语法分析的扩充：扩充LR分析器的功能：当执行归约产生式的动作时，也执行产生式对应的语义动作。由于是归约时执行语义动作，因此限制语义动作仅能放在产生式右部的最右边；扩充分析栈：增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值。,例如：EE1+E2valtop:=valtop+valtop+2;,对于表达式：5+3,当归约为左部E时，同时也得到了值8。,12,4.1.4LR分析翻译方案的设计(续1),例4.33+5*8的语法制导翻译。,语法制导定义print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val*E2.val;E.val:=n.lexval;,翻译方案print(valtop);valtop:=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;valtop:=valtop*valtop+2;#E+E#3?40#EE1+E2，valtop:=valtop+valtop+2;#E#43#acc,13,4.1.5递归下降分析翻译方案的设计,递归下降方法是用程序实现对非终结符的展开和对终结符的匹配。翻译方案的设计需要解决两个问题：1如何在递归下降子程序中嵌入语义动作：产生式右部的任何位置；2如何为文法符号的属性设计存储空间：函数返回值、参数、变量等。,例函数绘图语言的解释器中语法制导翻译的设计：1递归子程序可以设计为函数，用于返回必要的属性值；2适当设计子程序中的临时变量，用于保存属性值；3将语义动作嵌入在子程序的适位置，正确计算属性值。(第三次上机课介绍),14,4.2.中间代码简介,编译器各阶段的完整输出，均可以被认为是源程序的某种中间表示。本章讨论的是中间代码生成器输出的中间表示，称之为中间代码。中间代码实际上应起一个编译器前端与后端分水岭的作用。要求中间代码具有如下特性，以便于编译器的开发移植和代码的优化：1便于语法制导翻译；2既与机器指令的结构相近，又与具体机器无关。中间代码的主要形式：树、后缀式、三地址码等。,15,4.2.1后缀式,后缀式的特征操作符在前，操作数紧随其后，无需用括号限制运算的优先级和结合性。计算后缀式的虚拟机,算法4.1后缀式计算输入后缀式输出计算结果方法采用下述过程进行计算，最终结果留在栈中。,x:=first_token;whilenotend_of_exploopifxinoperatorsthenpushx;-操作数进栈elsepop(operators);-算符，弹出操作数push(evaluate);-计算，并将结果进栈endif;next(x);endloop;,16,后缀式计算4.2.1后缀式(续1),算术表达式3+5+8的后缀式为35+8+。算法4.1的计算：(#35+8+#进栈)(#35+8+#进栈)(#35+8+#弹出3和5，计算3+5，结果进栈)(#88+#进栈)(#88+#弹出8和8，计算8+8，结果进栈)(#16#),x:=first_token;whilenotend_of_exploopifxinoperatorsthenpushx;-操作数进栈elsepop(operators);-算符，弹出操作数push(evaluate);-计算，并将结果进栈endif;next(x);endloop;,17,将后缀式推广到其他语句4.2.1后缀式(续2),后缀式并不局限于二元运算的表达式，可以推广到任何语句，只要遵守操作数在前，操作符紧跟其后的原则即可。语句：ifethenxelsey它的后缀式可以写为：exyif-then-else(1)上述表示中，e、x和y均需计算。而实际上，根据条件e的取值，x和y不能都计算：ep1jezxp2jumpp1:yp2:(2)其中：p1和p2分别是标号；p1jez表示e的结果为0(假)则转向p1；p2jump表示无条件转向p2。与(1)比较，(2)中的if-then-else被分解，首先计算e，根据e的结果是否为真，决定计算x还是计算y。,18,4.2.2三地址码,三地址码的直观表示语法：语义：,例如：赋值句x:=a+b*c的三地址码序列：T1:=b*cT2:=a+T1x:=T2注意：直观表示与源程序中赋值句的区别。,result:=arg1oparg2或result:=oparg1或oparg1,结果存放在result中的二元运算arg1oparg2结果存放在result中一元运算oparg1一元运算oparg1,19,三地址码的种类,序号三地址码四元式(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:=emit(:=，E.code,A.code)emit(:=，E.code,entry(id.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),25,4.2.3图形表示,树作为中间代码语法树真实反映句子结构，对语法树稍加修改(加入语义信息)，即可以作为中间代码的一种形式(注释语法树)。例4.8赋值句x:=(a+b)*(a+b)的树的中间代码表示：,T1/(1),T2/(2),T3/(3),T4/(4),26,树的语法制导翻译,(1)Aid:=E(2)EE1+E2(3)EE1*E2(4)E(E1)(5)E-E1(6)Eid,A.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(op，nptr1，nptr2)：生成一个根或内部节点，节点数据是op，nptr1和nptr2分别指向的左右孩子的子树。若仅有一个孩子，则nptr2为空；函数mkleaf(node)：生成一个叶子节点。,27,树的优化表示DAG,如果树上若干个节点有完全相同的孩子，则这些节点可以指向同一个孩子，形成一个有向无环图(DirectedAcyclicGraph,DAG)。DAG与树的唯一区别是多个父亲可以共享同一个孩子，从而达到资源(运算、代码等)共享的目的。,DAG的语法制导翻译与树的语法制导翻译相似，仅需要在mknode和mkleaf中增加相应的查询功能。首先查看所要构造的节点是否已经存在，若存在则无需构造新的节点，直接返回指向已存在节点的指针即可。,28,树与其他中间代码的关系,树表示的中间代码与后缀式和三地址码之间有着内在的联系。对树进行深度优先的后序遍历，得到的线性序列就是后缀式，或者说后缀式是树的一个线性化序列。树的每个内部节点和它的孩子，对应一个三元式或四元式。,例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,T3)(4)(:=,x,T3,T4),因此，现代的编译器基础架构均用语法树作为中间表示。,29,4.3符号表简介,符号表的作用：连接声明与引用的桥梁，记住每个符号的相关信息，如作用域和绑定等，帮助编译的各个阶段正确有效地工作。符号表设计的基本要求：目标是合理存放信息和快速准确查找。正确存储各类信息。适应不同阶段的需求；便于有效地进行查找、插入、删除和修改等操作；空间可以动态扩充；,30,4.3.1符号表条目,逻辑上讲：每个声明的名字在符号表中占据一栏，称为一个条目，用于存放名字的相关信息。符号表中的内容：保留字、标识符、特殊符号(包括算符、分隔符等)等等。不同类别的符号存放在不同的子表中，如变量名表、过程名表、保留字表等。存放方式：关键字属性。关于组合关键字：,.intx;doublex;structxfloaty,z;,为C+构造的符号表中，组合关键字至少应该包括三项：名字作用域类型。当一个名字x在同一作用域中允许有多于一个的声明，则对x的引用时需要根据上下文确定x到底属于哪个对象。因此程序设计语言在语法上规定了不允许这样的声明，以简化编译时的处理。,31,4.3.2构成名字的字符串的存储,定长数据变长数据直接存放间接存放,名字(直接存储)属性sortproc,.aint,.readarrayproc,.draw_a_red_line_for_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,间接存储的方法实际上解决了复杂信息的存储问题，将其推广到属性，则任何一个复杂的属性，均可以为其另辟空间(空间本身可以是复杂结构，如数组的内情向量等)，而仅需要将指向此空间的指针放在此属性在符号表中的对应位置即可。,32,4.3.3名字的作用域,程序设计语言的名字可以出现在不同的范围内，并且可以具有不同的意义。两种划分范围的方式：并列的和嵌套的。不同的语言采用不同的方式：如Pascal的过程定义可以是嵌套的，而C的过程定义是并列的，但是C允许程序块是嵌套的。,名字的作用域：名字在哪个范围内起作用。并列的两个范围内的名字作用域互不相干，但是分别在嵌套的两个范围内的名字，其作用域的问题就需要制定规则来限定，以使得任何一个名字在任何范围内涵义都是无二义的。,名字的作用域规则：规定一个名字在什么样的范围内应该表示什么意义。,33,4.3.3名字的作用域(续1),静态作用域原则(static-scoperule)：编译时就可以确定名字的作用域，也可以说，仅从静态读程序就可确定名字的作用域。最近嵌套原则(mostcloselynested)：以程序块为例，也适用于过程。程序块B中声明的作用域包括B；如果名字x不在B中声明，那么B中x的出现是在外围程序块B的x声明的作用域中，使得(a)B有x的声明，并且(b)B比其它任何含x声明的程序块更接近被嵌套的B。,通俗地讲，名字的声明在离其最近的内层起作用，即在名字引用处从内向外看，它处在所遇到的第一个该名字声明的作用域。例子：找人张三；软件学院的张三；计算机学院的张三；西电软件学院的张三,34,4.3.3名字的作用域(续2),例4.10说明符合作用域规则的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=3B3,35,4.3.4线性表,线性表应是一个栈，以正确反映名字的作用域，即符号的加入和删除，均在线性表的一端进行。,线性表上的操作：关键字：名字作用域；查找：从表头(栈顶)开始，遇到的第一个名字；插入：先查找，再插入在表头；,1voidmain()2inta=0,b=0;/B03intb=1;/B14inta=2,c=4,d=5;/B27intb=3;/B311,36,4.3.4线性表(续1),1voidmain()2inta=0,b=0;/B03intb=1;/B14inta=2,c=4,d=5;/B27intb=3;/B311,线性表上操作的效率(n个条目)：一个名字的查找：成功查找(平均)：(n+1)/2；不成功查找：n+1建立n个条目的符号表(最坏)：=(n+1)(n+2)/2,删除：(a)暂时：将在同一作用域的名字同时摘走，适当保存；(b)永久：将在同一作用域的名字同时摘走，不再保存。修改：与查找类似，修改第一个遇到的名字的信息。修改可以用插入删除代替。,37,4.3.5散列表,散列表的构成将线性表分成m个小表。构造hash函数，使名字均匀地散布在m个子表中。如果散列均匀，则时间复杂度会降到原线性表的1/m。,每个名字挂在两个链上(便于删除操作)：哈希链(hashlink)：链接所有具有相同hash值的元素，表头在表头数组中；作用域链(scopelink)：链接所有在同一作用域中的元素，表头在作用域链中。,其中：S1、S2、S4在同一作用域S3在另一作用域,38,散列表上的操作4.3.5散列表(续1),1查找：首先计算散列函数，然后从散列函数所指示的入口进入某个线性表，在线性表中沿hashlink，象查找单链表中的名字一样进行查找。2插入：首先查找，以确定要插入的名字是否已在表中，若不在，则要分别沿hashlink和scopelink插入到两个链中，方法均是插在表头，即两个表均可看作是栈。3删除：把以作用域链连在一起的所有元素从当前符号表中删除，保留作用域链所链的子表，为后继工作使用(如果是临时删除，则下次使用时直接沿作用域链加入到散列链中即可)。,39,4.3.5散列表(续2),设：hash(s)=ord(s)-ord(a),1voidmain()2inta=0,b=0;/B03intb=1;/B14inta=2,c=4,d=5;/B27intb=3;/B311,分析在B2中：,退出B2进入B3：,40,散列函数的计算hash:stringinteger,减少冲突，分布均匀充分考虑程序设计语言的特点若有变量：V001,V002,V300，且首字母的值作为hash值。会发生什么？,一种可行的hash函数计算方法：从串s=c1c2ck的字符ci确定正整数h：令：h0=0,计算：hi=hi-1+ci,1ik,得到：h=hk=1或是素数，如=65599。,思考题：根据上述方法，设计一个hash函数并测试之。根据测试结果讨论各参数值对函数结果的影响。,取一素数m,令h=hmodm。,41,散列函数的计算(续1),思考题(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，试给出返回值。,42,4.4声明语句的翻译,声明语句的作用是为可执行语句提供信息，以便于其执行。对声明语句的处理，主要是将所需要的信息正确地填写进合理组织的符号表中。,4.4.1变量的声明变量的类型定义与声明,类型定义：为编译器提供存储空间大小的信息变量声明：为变量分配存储空间组合数据的类型定义和变量声明：定义与声明在一起，定义与声明分离。,定义确定存储空间，声明分配存储空间简单数据类型的存储空间是已经确定的，如integer可以占4个字节，real可以占8个字节，char可以占1个字节等。组合数据类型变量的存储空间，需要编译器根据程序员提供的信息计算而定。,43,变量的类型定义与声明,例：在Pascal程序中的类型定义与变量声明：先定义后声明：typeplayer=array1.2ofinteger;matrix=array1.24ofchar;varc,p:player;winner:boolean;display:matrix;movect:integer;定义与声明同时：varc,p:array1.2ofinteger;display:array1.24ofchar;,强调：简单变量声明中类型是预定义的；组合变量声明中类型需自己定义。(定义的两种形式),44,变量声明的语法制导翻译,(a)变量声明的文法：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的声明形式可以是：A:arrayd1ofarrayd2of.arraydnofinteger,多维数组以行为主存储。因为：第一维是有d1个元素的一维数组，每个元素又是一个n-1维的数组；依此类推。,45,变量声明的语法制导翻译(续1),(b)填写符号表信息的语法制导翻译,全程量offset：记录当前被处理符号存储的偏移量，初值设为0属性.type和.width：变量的类型和所占据的存储空间过程enter(name,type,offset)：为type类型的变量name建立符号表条目，并为其分配存储空间(位置)offset,(1)DD;D(2)Did:T(3)Tint(4)Treal(5)TarraynumofT1(6)TT1,enter(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;,46,变量声明的语法制导翻译(续2),例声明序列的语法制导翻译：a:array10ofint;x:int;,序号归约使用的产生式语义处理结果(1)T1intT1.type=integerT1.width=4(2)T2arraynumofT1T2.type=array(10,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=44,(2)Did:Tenter(id.name,T.type,offset);offset:=offset+T.width;(3)TintT.type:=integer;T.width:=4;(5)TarraynumofT1T.type:=array(num.val,T1.type);T.width:=num.val*T1.width;(6)TT1T.type:=pointer(T1.type);T.width:=4;,47,4.4.3过程的定义与声明,1过程(procedure)：过程头(做什么)过程体(怎么做)；函数；主程序2过程的三种形式：过程定义、过程声明和过程调用。,例：Ada过程定义：procedureswap(x,y:inoutinteger)is-规格说明temp:integer;-体中的声明begintemp:=x;x:=y;y:=temp;-可执行语句序列endswap;,声明与引用：procedureswap(x,y:inoutinteger);-过程声明swap(a,b);-过程调用,3先声明后引用原则过程定义可以写在对它的引用之后，或者引用时看不到的地方。在这样的情况下，引用前必须先声明。而若引用前已经定义，则声明可省略，因为定义已包括了声明。,48,4.4.3.1左值与右值,形式上，出现在赋值号左边的对象称为左值，右边的称为右值；实质上，左值必须具有存储空间，而右值可以仅是一个值，没有存储空间。形象地讲，左值是容器，右值是内容。,(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+two:=x+two;-表达式的值不能作为左值,49,4.4.3.2参数传递,1形参与实参定义时的参数称为形参(parameter或formalparameter)引用时的参数称为实参(argument或actualparameter)2常见的参数传递形式：(不同的语言提供不同的形式)值调用(callbyvalue)引用调用(callbyreference)复写恢复(copy-in/copy-out)换名调用(callbyname)3参数传递方法的实质：实参是代表左值、右值、还是实参本身的正文。,50,值调用,值调用的特点：实参的特点：参数传递和过程内对参数的使用原则：,过程内部对参数的修改，不影响作为实参的变量原来的值。,任何可以作为右值的对象均可作为实参。,(1)过程定义时形参被当作局部名看待，并在过程内部为形参分配存储单元；,(3)过程内部对形参单元中的数据直接访问。,(2)调用过程前，首先计算实参并将值(实参的右值)放入形参的存储单元；,51,值调用举例：值调用(续1),programreference(input,output);vara,b:integer;begina:=1;b:=2;swap(a,b);writeln(a=,a);writeln(b=,b)end.,procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend;,运行结果：a=1b=2,52,等价的C+程序值调用(续2),/-值调用参数传递的演示程序#includevoidswap(intx,inty)inttemp;temp=x;x=y;y=temp;voidmain()inta(1),b(2);coutbefore:a=ab=bendl;swap(a,b);coutafter:a=ab=bendl;,53,引用调用,引用调用的特点：实参的特点：参数传递和过程内对参数的使用原则：,过程内部对形参的修改，等价于直接对实参的修改。,必须是左值。,(1)定义时形参被当作变量地址看待，并在过程内部为形参分配存储单元；,(2)调用过程前，将作为实参的变量的地址放进形参的存储单元；,(3)过程内部把形参单元中的数据当作地址，进行间接访问。,54,引用调用举例：引用调用(续1),programreference(input,output);vara,b:integer;begina:=1;b:=2;swap(a,b);writeln(a=,a);writeln(b=,b)end.,procedureswap(varx,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend;,procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend;,运行结果：a=2b=1,55,等价的C+程序引用调用(续2),/-引用调用参数传递的演示程序#includevoidswap(int,56,值调用模拟引用调用引用调用(续3),/-值调用模拟引用调用参数传递的演示程序#includevoidmain()inta(1),b(2);coutbefore:a=ab=bendl;swap(,注意：C语言只有值调用因此：只能用值调用形式模拟引用调用的效果同样：过程式程序设计语言可以模拟面向对象的继承机制结论：语言与程序设计范型(方法)不是一对一的关系,voidswap(int*x,int*y)inttemp;temp=*x;*x=*y;*y=temp;,57,复写-恢复,/-引用调用的副作用的程序实例#includeinta=2;voidmain()coutbefore:a=aendl;add_one(a);coutafter:a=aendl;,引用调用的副作用,本意：a=3结果：a=4原因：实参与非本地量共用一个存储空间，使得在过程内改变参数值的同时，也改变了非本地量的值。,voidadd_one(int,58,复写-恢复(续1),复写-恢复的特点：(值调用和引用调用的结合)实参的特点：参数传递和过程内对参数的使用原则：,过程内部对参数的修改，不直接影响实参，避免了副作用；返回时将形参内容恢复给实参，实现了参数的返回。,必须是左值。,(1)过程定义时形参被当作局部名看待，并在过程内部为形参分配单元(复写)；(2)调用过程前，首先计算实参并将值(实参的右值)放入形参的存储单元；(3)过程内部对形参单元中的数据直接访问；(4)过程返回前，将形参的右值重新放回实参的存储单元(恢复)。,59,复写-恢复举例：复写-恢复(续2),proceduretestis-Ada源程序a:integer;begina:=2;a:=add_one(a);put_line(a=,a);endtest;,procedureadd_one(x:inoutinteger);-复写-恢复调用begina:=x+1;x:=x+1;endadd_one;,/-引用调用模拟复写-恢复参数传递的演示程序#includeinta=2;voidadd_one(int,60,换名调用,严格讲，换名调用并不能算作真正的过程调用和参数传递。,换名调用由Algol的复写规则定义：(1)过程被认为宏，每次对过程的调用，实质上是用过程体替换过程调用，替换中用实参的文字替换体中的形参。这样的替换方式被称为宏替换或宏展开；(2)应区分被调用过程的局部名和调用过程名。可以认为在宏展开前被调用过程的每个局部名系统地重新命名成可区别的名字；(3)当需要保持实参的完整性时，可以为实参加括弧。,换名调用在C+中的形式是宏定义(#define)，宏定义是采用预处理的方法，在预处理时进行宏替换。宏替换将过程体直接展开在它被调用的地方，因此经过宏替换之后的程序中，已经不存在过程的调用与参数传递，它的特点是运行速度快。,61,正文替换与函数调用的不一致性换名调用(续1),/-换名调用副作用的演示程序#includeinttemp;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;,vari,j:integer;begin.a.;.v.;.exchange(i,j);.endpartition;,65,过程的作用域(续2),sorta,x,1readarrayi2exchange2quicksorti,v2partitioni,j3,符号表中的作用域信息嵌套过程中名字作用域信息的保存，可以用具有嵌套结构的符号表来实现，每个过程可以被认为是一个子符号表，或者是符号表中的一个节点。嵌套的节点之间可以用双向的链表连接，正向的链指示过程的嵌套关系，而逆向的链可以用来实现按作用域对名字的访问。,过程过程中的变量嵌套深度,66,符号表中的作用域信息,例4.15忽略参数的快排序程序的符号表：,双向链表：正向嵌套定义关系逆向作用域与可见性关系,问题：参数如何处理？,67,语法制导翻译生成符号表(a)简化的过程定义文法(忽略了参数)：,PD(1)DD;D(2)|id:T(3)|procid;D;S(4),问题：如何在处理产生式(1)和(4)的语言结构时正确地填写符号表信息(双向链表)？,修改文法，使得在定义D之前生成符号表(LR分析)：PMD(1)DD;D(2)|id:T(3)|procid;ND;S(4)M(5)N(6),68,(b)全程量、属性与语义函数,全程量：有序对栈(tblptr,offset),其中，tblptr保存指向符号表节点的指针，offset保存当前节点所需宽度。栈上的操作：push(t,o)、pop、top(stack),语义函数与过程：函数mktable(previous)：建立一个新的节点，并返回指向新节点的指针。参数previous是逆向链，指向该节点的前驱，或者说是外层。过程enter(table,name,type,offset)：在table指向的节点中为名字name建立新的条目，包括名字的类型和存储位置等。过程addwidth(table,width)：计算table节点中所有条目的累加宽度，并记录在table的头部信息中。过程enterproc(table,name,newtable)：为过程name在table指向的节点中建立一个新的条目。参数newtable是正向链，指向name过程自身的节点。,69,(c)语义规则,(1)PMD(2)M(4)Did:T(5)Dprocid;ND1;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);pop;,70,(d)语法制导翻译的过程,procsort;a:array10ofint;x:int;readarray,procreadarry;i:int;read(a);,71,(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)T2array10ofT2T2.type=array(10,int),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)D4procreadarrayN2D3;St:=top(tblptr);addwidth(t,top(offset);pop;enterproc(top(tblptr),readarray,t);(13)D7procsortN1D6;St:=top(tblptr);addwidth(t,top(offset);pop;enterproc(top(tblptr),sort,t);(14)PM1D7addwidth(top(tblptr),top(offset);pop;,构造的符号表：,72,4.5简单算术表达式与赋值句,简单算术表达式和赋值句，是指表达式和赋值句中变量是不可再分的简单变量。,讨论所基于的文法：,Aid:=EEE+E|E*E|-E|(E)|id,73,4.5.1简单变量的语法制导翻译,属性.place：存放E的变量名地址(符号表中地址或临时变量的编码)；过程emit(result:=arg1oparg2)：生成“result:=arg1oparg2”的三地址码。,(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.place:=E1.place*E2.place),E.place:=newtemp；emit(E.place:=-E1.place),E.place:=E1.place,emit(entry(id.name):=E.place),74,4.5.2变量的(内部)类型转换,强制(coercion)：按照一定的原则，将不同类型的变量在内部转换为相同的类型，然后进行同类型变量的计算。,运算的转换原则：,赋值的转换原则：,属性.mode：取值int或real表达式的类型判定树：,75,4.5.2变量的(内部)类型转换(续1),三地址码：T:=itrE：将E从整型变为实型，结果存放T中T:=rtiE：将E从实型变为整型，结果存放T中语义规则：,Aid:=E,tmode:=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(entry(id.name):=T);endif;,76,4.5.2变量的(内部)类型转换(续2),EE1opE2,T:=newtemp；E.mode:=real;ifE1.mode=intthenifE2.mode=intthenemit(T:=E1.placeOPiE2.place);E.mode:=int;elseU:=newtemp;emit(U:=itrE1.place);emit(T:=UOPrE2.place);endif;elseifE2.mode=intthenU:=newtemp;emit(U:=itrE2.place);emit(T:=E1.placeOPrU);elseemit(T:=E1.placeOPrE2.place);endif;endif;E.place:=T;,其他语义规则看教材P128129,77,4.5.2变量的(内部)类型转换(续3),例4.17x:=-a*b+c的语法制导翻译，x、a、b是整型数，c是实型数。,序号产生式中间代码(1)E1a(2)E2-E1t1:=-a(3)E3b(4)E4E2*E3t2:=t1*ib(5)E5c(6)E6E4*E5t4:=itrt2t3:=t4+rc(7)Ax:=E6t5:=rtit3x:=t5,78,4.6数组元素的引用,确定数组空间的存储分配：以第一个元素地址为首地址，分配一个连续空间。多维数组到一维存储空间的映射方法：以行为主，以列为主考虑三行、三列的二维数组a0.2,2.4：,a0,2a0,3a0,4a1,2a1,3a1,4a2,2a2,3a2,4,以行为主存放时的元素排列：,a0,2a0,3a0,4,a1,2a1,3a1,4,a2,2a2,3a2,4,以列为主存放时的元素排列：,a0,2a1,2a2,2,a0,3a1,3a2,3,a0,4a1,4a2,4,确定数组元素地址的两个要素：首地址和相对首地址的偏移量,不同的映射方式，使得同一个数组元素相对首地址的偏移量不同例如：a1,4，偏移量分别是5和7,79,确定映射方式的两种方法,1由声明时的语法确定映射方式：a:arrayd1ofarrayd2of.arraydnofinteger;引用方式：ai1,i2,.,in或ai1i2.in2由编译器确定映射方式：a:arrayd1,d2,.,dnofinteger;引用方式：ai1,i2,.,in,数组元素引用时地址的确定：1根据映射方式求出计算公式；2根据计算公式设计语义规则。,80,4.6.1数组元素的地址计算,三个假设条件：数组元素以行为主存放，推广到n维，就是数组的第i维中每个成员是di个n-i维的数组，其中di是第i维成员的个数；数组每维的下界均为1；每个元素仅占一个标准存贮单元(可以认为是一个字或者一个字节)。约定：数组的声明：Ad1,d2,.,dn数组元素的引用：Ai1,i2,.,in,一维数组元素的地址计算：addr(Ai)=a+(i-1)*w,二维数组元素的地址计算：addr(Ai1,i2)=a+(i1-1)*d2+(i2-1)*w,81,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+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,82,n维数组元素的地址计算(续1),c=(.(d2+1)*d3+1)*d4.+1)*dn+1v=(.(i1*d2+i2)*d3+i3)*d4.+in-1)*dn+in,令：v1=i1则：v2=i1*d2+i2=v1*d2+i2v3=(v1*d2+i2)*d3+i3=v2*d3+i3.于是有：v1=i1vj=vj-1*dj+ij(j=2，3，.,n)(4.4)同理可得：c1=1cj=cj-1*dj+1(j=2，3，.,n)(4.3),最终得到数组元素引用的地址计算公式：addr(Ai1，i2，.，in)=a-c+v=CONSPART+VARPART,83,4.6.2数组元素引用的语法制导翻译,数组元素的寻址：CONSPARTVARPART，或者T1T