华东师范大学计算机科学技术系.ppt

2020/7/29,华东师范大学计算机科学技术系,1,第五章 语法制导翻译和中间代码生成,5.1 概述 语义分析包含静态语义检查和语义识别，并在此基础上对源程序（单词串形式）进行等价转换，转换为中间代码（目标代码）。 在后面的讨论中总是认为词法、语法分析已经完成，读入的是（语法正确）句子！而不关心用什么方法进行语法分析的（以后主要讨论自底向上的句法分析方法），关心的是如何在语法分析的同时正确地插入语义子程序进行翻译（语法制导翻译） 。,2020/7/29,华东师范大学计算机科学技术系,2,一、静态语义检查,称在编译时刻进行的语义检查为静态语义检查，通常可包含如下内容： 类型检查。 检查运算的合法性和参与运算的运算分量类型的一致性（相容性）。必要时进行相应的类型转换。 (2) 控制流检查。 以保证控制语句有合法的转向点，如C语言中的break语句，需寻找包含它的最小的switch、while或for语句，方可找到转向点，否则出错。不允许循环外控制转入循环内。,2020/7/29,华东师范大学计算机科学技术系,3,(3) 有关名字的匹配检查。 可以对某些程序段命名，该名字出现在程序段的开始和结束处，如同语句括号一般，应检查它们的配对。 (4) 一致性检查。 如在相同作用域中标识符只能说明一次（重复定义），case语句的标号不能相同，枚举类型的元素不能重复，没有定义数据类型等。,2020/7/29,华东师范大学计算机科学技术系,4,二、语法制导翻译,例1：对算术表达式文法G的一个翻译方案 +print “1” print “2” *print “3” print “4” ()print “5” iprint “6” 其中 括起的称为该产生式的语义子程序。 对输入串W=(i+i)*i则W是G的一个句子。,2020/7/29,华东师范大学计算机科学技术系,5,若采用自底向上的句法分析，规定当用产生式归约时，调用相应的语义子程序，则翻译结束后输出 64264154632。 若采用自顶向下的句法分析，规定当用产生式推导时，调用相应的语义子程序，则翻译结束后输出 23451246466。 应根据输出（翻译）目标，配备适当的语义子程序，这就是所要做的工作。,2020/7/29,华东师范大学计算机科学技术系,6,三、翻译要解决的问题,翻译成什么样的目标语言的代码？ 将源语言程序翻译成中间语言的程序。中间语言与机器无关，而语句颗粒度又与机器语言相当，于是带来了诸多好处： 编译逻辑结构简单明确，与机器相关的工作集中到目标代码生成阶段，难度和工作量下降； 便于移植和维护。 利于优化，代码优化将分成与机器无关的中间代码优化及与机器相关的目标代码优化两个阶段，使优化更有效。,2020/7/29,华东师范大学计算机科学技术系,7,2. 何时进行这种翻译？,如例1所示，如果作为句柄所对应的产生式，都配有一个相应的翻译子程序，则每当按句柄归约时，就调用相应的翻译子程序（语义子程序）完成局部的翻译，则一个句子，一段代码，按它们的归约次序，将所有翻译子程序依次执行，就完成了这个句子、这段代码的翻译。这种翻译与语法分析紧密相关，称之为语法制导翻译：每当归约时，调用相应的语义子程序，这就是翻译的时机。,2020/7/29,华东师范大学计算机科学技术系,8,3. 如何实现这种翻译？,语法制导翻译的关键，是为每个产生式编写翻译子程序。例1中产生式所带有的这种语义子程序只能输出这类数字串。现在，要对一个有穷表示的文法的无穷多个语句，按所给出的语义子程序要完成不同语句的翻译任务，输出各自的目标代码。难点自然就集中在如何写这些语义子程序了。 采用属性翻译文法（属性文法），这是一种形式化的语义分析方法。,2020/7/29,华东师范大学计算机科学技术系,9,结论,语法制导的翻译方法就是在语法分析的同时（制导下）插入一系列的语义动作（由语义子程序提供），将源程序（单词形式）翻译成等价的中间代码。 主要考虑自底向上句法分析的方法（在归约时调用语义子程序），设计翻译方案（形成属性文法）。,2020/7/29,华东师范大学计算机科学技术系,10,5.2 中间语言,常见的中间语言有很多种，一般可单独或混合使用。 一、后缀表示（逆波兰表示） 是由波兰数学家卢卡西维奇(Lukasiewicz)提出的。它是将a op b中运算量a、b依次写在算符op之前，即a b op，可以形式地给出表达式E的后缀表示的递归定义： (1) 如果E是变量或常数，则E的后缀表示即E本身。 (2) 如果E为E1 op E2形式，则它的后缀表示为E1 E2 op， 其中op是二元算符，E1，E2分别是E的后缀表示(op为一元运算时E2为空)。 (3) 如果E为(E1)形式，则E1后缀表示即为E的后缀表示。,2020/7/29,华东师范大学计算机科学技术系,11,后缀表示可以机械地计算。 中缀表示可以机械地转换为后缀表示。（E.W.Dijkstra) 例2： (-a*b+c)-d的后缀表示为：a b* uminus c+d- 其中uminus表示一元运算-。 后缀表示的推广： O1，O2，On，其中是n元的运算符，Oi为运算对象 i=1,2n。 假定：后缀表示存放在一维数组S中，Si是一个单词,2020/7/29,华东师范大学计算机科学技术系,12,例3：赋值语句 := 若V，E分别为、的后缀表示，赋值语句的后缀表示为：V E:= 如：A:=B*C+D则为ABC*D+:= 例4：条件语句 ifthenelse的后缀表示为：E i1 BZ S1 i2 BR S2 其中： E, S1, S2分别是，的后缀表示。 i1是S2的首符号在S数组中的下标 i2是S2的尾符号在S数组中的下标加1 BZ是运算符表示“零转” BR是运算符表示“无条件转”,2020/7/29,华东师范大学计算机科学技术系,13,试将语句if x5 then x:=a;else x:=b;表示成逆波兰表示 引入二元运算符BZ、一元运算符BR。逆波兰表示 T,i,BZ的含义为若T的值为零，则转到位置为i处执行。i,BR的含义为无条件转移到位置i处执行。 假定上述语句的逆波兰表示存放在一维数组S中，用数组的下标表示转向的位置。S数组可描述为：,2020/7/29,华东师范大学计算机科学技术系,14,二、图(树、抽象句法树）表示,通过对分析树的简化得到 例5：对算术表达式文法G，输入串W=(i+i)*i 的分析树见前。而树表示为： 反映了一种运算顺序 内结点表示运算及运算结果 见P82。亦可以使用无环路有向图dag(directed acyclic graph)。,*,+,i,i,i,2020/7/29,华东师范大学计算机科学技术系,15,三、三地址代码,三地址代码语句的一般形式为：x:=y op z 其中x、y和z为名字、常量或编译时产生的临时变量，op为运算符如定点运算符、浮点运算符、逻辑运算符等。由于三地址语句只含一个运算符，故多个算符组成的表达式必须用三地址语句序列表示。 例如表达式x+y*z的三地址代码为： t1:=y*z t2:=x+t1 其中t1和t2是编译时需要的临时变量。,2020/7/29,华东师范大学计算机科学技术系,16,三地址语句通常包含三个地址，两个用来存放运算对象，一个用来存放运算结果。在实现时，用户定义的名字将由指向符号表中该名字项的指针所代替。,2020/7/29,华东师范大学计算机科学技术系,17,四、三地址语句的种类,三地址语句有多种表示形式，常见的有： x:=y op z 赋值语句，其中op为二目的算术运算符或逻辑运算符。 (2) x:=op y 赋值语句，其中op为一目运算符，如一目减uminus，逻辑否定not，移位算符及将定点数转换成浮点数的类型转换符。 (3) x:=y复写语句，将y的值赋给x。,2020/7/29,华东师范大学计算机科学技术系,18,(4) goto L 无条件转移语句，下一个将被执行的语句是标号为L的语句。 (5) if x relop y goto L 或 if x goto L 条件转移语句, relop为关系运算符如、=等，若x和y满足关系relop就转而执行标号为L的语句，否则顺序执行本语句的下一语句。,2020/7/29,华东师范大学计算机科学技术系,19,(6) param X 和 call P，n 过程调用语句，源程序中的过程调用语句 call P(x1, x2, , xn)可以用下列三地址代码表示： param x1 param x2 param xn call P, n 其中整数n为实参个数。 过程返回语句为return y，其中y为返回值。,2020/7/29,华东师范大学计算机科学技术系,20,(7) 变址赋值： x:=yi，表示将从地址y开始的第i个地址单元的值赋给x。 xi:=y，表示将y的值赋给从地址x开始的第i个地址单元。 (8) 地址和指针赋值： x:= 1id, 2 2.dtype:=1.dtype; set_type(id.p, 1.dtype); id set_type(id.p, .dtype); 属性.dtype是继承属性 。,2020/7/29,华东师范大学计算机科学技术系,42,例2. S-属性翻译文法的例子,将中缀表达式翻译为抽象语法树的翻译文法。 简单算术表达式文法G ： 1+ .ptr:=Node(+,1.ptr,.ptr .ptr:= .ptr 1*.ptr:=Node(*,1.ptr,.ptr .ptr:= .ptr ().ptr:= .ptr c .ptr:=Node(/,c.class,c.value 其中属性X.ptr的值是树结点的地址，函数Node(x,y,z)的功能是：申请一块空间，将x、y、z写入，并返回该空间的首地址。,2020/7/29,华东师范大学计算机科学技术系,43,对单词串（c.3+c.9)*(c.2+c.15)经过分析与翻译后转换为：,*,+,+,c.3,c.9,c.2,c.15,2020/7/29,华东师范大学计算机科学技术系,44,说明,在本章的讨论中，总使用S-属性翻译文法，采用自底向上的句法分析（不关心用哪种方法）。 主要的工作是： 设计文法符号带有的综合属性；编制语义子程序。 翻译的目标是：三地址代码。 2. 为了实现这种翻译方法，要求： 词法分析程序在返回所识别的单词时，总带有一个值（该值是数值或符号表中该单词（标识符）所在的地址或该单词的内部码）。,2020/7/29,华东师范大学计算机科学技术系,45,句法分析时遵循： i)将非终结符移入栈时，将其所带的属性一起入栈。 ii)使用产生式归约后，调用与该产生式相关的语义子程序。 3. 注意：“当非终结符出现在栈顶，那么与该非结符有关的中间代码已经生成” 。为什么？,2020/7/29,华东师范大学计算机科学技术系,46,习题,P129，习题5 5.1 5.2,2020/7/29,华东师范大学计算机科学技术系,47,5.4 说明语句,一、增加存储地址分配的说明语句的翻译方案 对说明语句a,b,c:real 语义为： 设编译程序用于存储地址分配的变量是offset，将标识符id的数据类型及由offset指出的存储地址送入符号表相应的登记项中。 考虑文法G: ;|i:|i, int|real|arraynumof|,2020/7/29,华东师范大学计算机科学技术系,48,令属性.type、.width分别表示数据类型和该类型所需的存储字节数，i.name表示变量名（地址），num.val表示数值。 设过程enter(x,y,z)的功能为：将y,z送入x所指出的地址中。 属性翻译文法为： - offset:=0 ;- i:enter(i.name,.type,offset); offset:=offset+.width int.type:=int,.width:=4 real.type:=real,.width:=8,2020/7/29,华东师范大学计算机科学技术系,49,arraynumof1 .type:=array(num.val,1.type); .width:=num.val*1.width 1 .type:=pointer(1.type); .width:=4,2020/7/29,华东师范大学计算机科学技术系,50,说明,这儿采用了“插因子”技术（以后还将讨论“拆因子”）即将 改写为等价的 的形式。为什么要这样做呢？ 答案：为了在使用 归约前插入语义动作offset:=0! 工作的原则是：归约时调用相应的语义子程序。 问题：采用教科书P115中的语义变量.bcode能够解决吗？ 例如：对句子a:int两种方法的推导树为：,2020/7/29,华东师范大学计算机科学技术系,51,如果不插入一个因子，则无法将offset初始化。 对数组arraynumof，这儿是一种最简单的形式，省略了维数、上下界等。后面将详细讨论。 如还要指出标识符的种类（如变量、常量、过程等，可以在产生式i:加入语义动作.kind:=VAR;及enter(i.name,.kind,）,i,:,int,:,i,int,及,2020/7/29,华东师范大学计算机科学技术系,52,二、嵌套过程中的说明语句,过程说明语句的翻译 过程（分程序）嵌套是程序设计语言中常见的结构，一般有如下几种形态： 过程嵌套、分程序嵌套，如ALGOL、Ada语言 过程嵌套、无分程序，如Pascal语言 过程不嵌套、分程序嵌套，如C语言 满足不能交叉的原则，即只能平行或嵌套。 满足先调用后返回的栈式原则。 变量作用域最近嵌套原则。 平行过程（分程序）可使用相同的存储区。,2020/7/29,华东师范大学计算机科学技术系,53,符号表的组织形式,对过程嵌套的语言，其符号表的组织（以过程为单位）应满足： 对数据对象的说明，应核实该对象名是否已在当前程序中说明过，若无则进入，否则报错。 对数据对象的使用，是与其联系的最内层过程中说明的（不一定是当前的），因此应从本层逐层向外搜索。 进入过程应做好初始化工作：重置offset、建立新的符号表等。 退出过程应保证在本过程中的数据对象不会被访问到。 因此：符号表组织的形式应是栈式管理。见P88、89,2020/7/29,华东师范大学计算机科学技术系,54,过程说明的语义,在文法G中增加过程说明的产生式： proc i;1; （注：省略了参数说明） 其语义为： 过程说明引入了新过程i,过程i局部于紧外层过程，因此i应出现在紧外层过程的符号表中。 暂停紧外层过程的处理，为i过程创建新的符号表（初始化），将1中说明的数据对象登记在符号表中。 由于外层过程中的数据对象全局于i过程，因此i过程的符号表中有一指针指向紧外层过程符号表。,2020/7/29,华东师范大学计算机科学技术系,55,编译程序使用的数据结构与语义过程： tblptr：栈式符号表，top(tblptr)栈顶指针 offset：栈式存储区， top(offset)栈顶指针 语义函数mktable(x)的功能：创建新的符号表；指针参数x指向紧外层的符号表，返回值是新的符号表的地址。 语义过程enter(t,n,ty,off)的功能：在t表的n地址中登记ty和off。 语义过程addwidth(t,w)的功能为：将w（该过程总的存储量）记录在t表的表头。 语义过程enterproc(t,n,nt)的功能：将n、nt（过程名、符号表首址）登录到t所指的紧外层过程符号表中。（弹出过程，返回到紧外层过程，使平行过程可使用相同的存储区。 ）。,2020/7/29,华东师范大学计算机科学技术系,56,说明语句的翻译方案,嵌套过程中说明语句的翻译方案： addwidth(top(tblptr),top(offset); pop(tblptr);pop(offset); t:=mktable(nil); push(t,tblptr);push(0,offset) ; proc i; t:=top(tblptr); addwidth(t,top(offset); pop(tblptr);pop(offset); enterproc(top(tblptr),i.name,t) ,2020/7/29,华东师范大学计算机科学技术系,57, t:=mktable(top(tblptr); push(t,tblptr);push(0,offset) i: enter(top(tbltop),i.name,.type,top(offset); top(offset):=top(offset)+.width ,2020/7/29,华东师范大学计算机科学技术系,58,5. 5 赋值语句,赋值语句的一般形式为a:=e;a是变量，e是表达式，即 a:= 一 简单变量赋值语句的翻译 考虑如下表达式文法G： 1 op 2 | -1 | (1)| i 其中op可以是+、-、*、/，增加了定义一目运算uminus的产生式 -1。若规定了优先级、结合律，文法G是SLR（1）文法。 文法G的语义是十分清楚的。,2020/7/29,华东师范大学计算机科学技术系,59,语义过程和属性的说明,属性i.name为简单变量i的标识符字符串，.place为表达式的值所分配的存储位置。 语义函数lookup（a）为名字a查符号表，若查到，返回a在符号表中的位置，若查不到，返回nil。 语义函数newtemp，每调用一次就返回一个可用的临时变量地址。 语义过程emit（n1,n2,nm)，根据指定的参数，产生一个三地址语句并传输到输出文件的nextq的位置，然后nextq自动加。 error( )是错误处理的语义过程.,2020/7/29,华东师范大学计算机科学技术系,60,简单表达式翻译方案, i := P:=lookup (i.name); if Pnil then emit(P, :=,.place) else error( ) 1 op 2 .place:=newtemp; emit(.place, :=,1.place, op,2.place) -1 .place:=newtemp; emit(.place,:=,uminus,1.place) (1) .place:=1.place i P:=lookup(i.name); if Pnil then .place:=P else error( ),2020/7/29,华东师范大学计算机科学技术系,61,例1： 赋值语句 a:=-b*c+d 100：t1:=uminus b 101：t2:=t1*c 102：t3:=t2+d 103：a:=t3,:=,i.a,+,*,-,i.b,i.c,i.d,2020/7/29,华东师范大学计算机科学技术系,62,二、类型转换,上述翻译方案没有考虑运算对象的类型，在后面的讨论时也往往忽略类型检查与转换，这儿简单给予讨论。 对赋值语句，可考虑： 引入属性i.type与.type，记录表达式的类型。 引入一些类型转换运算符，如：itor等，对程序设计语言允许的相容的类型间进行转换。 进行类型检查，若出现不允许的类型间的运算则报错。 对语句 i := 翻译时应注意以i的类型为主。,2020/7/29,华东师范大学计算机科学技术系,63,三、含数组元素的赋值语句的翻译,在赋值语句和表达式中，如果除了简单变量外还允许出现数组元素（即下标变量），则为了引用这些下标变量，必须先计算出数组元素的地址。 下标变量的地址计算 一般程序设计语言中数组定义有二类： 静态数组：维数确定，上下界是常量，编译时可以确定大小（体积）。如C、FORTRAN等 动态数组：维数确定，上下界是变量，运行时确定体积。 考虑较复杂的情况： 一个n维数组的一般形式为： array Al1: u1, l2:u2, , ln:un: integer,2020/7/29,华东师范大学计算机科学技术系,64,一个物理的存储空间是一个一维的线性空间，一个n维的数组必须存储在A0开始的一片连续的存储空间中。因此，就有按行存放和按列存放两种选择，有些语言如PL/1，规定按行存放，有些语言如FORTRAN，规定按列存放，不少语言则不作规定，由编译程序决定取何种存储方式。我们只讨论按行存放。 一维数组 array al1:u1 设下标变量ai所在的地址用 if Pnil then begin .array:=P;/得到信息向量表首址传下去 .place:=.place;/赋初值 .dim:=1 end else error ,2020/7/29,华东师范大学计算机科学技术系,72,1, t:=newtemp; k:=1.dim+1; emit(t:=1.place*limit(1.array,k); emit(t:=t+.place); .array:=1.array; /传下去 .place:=t; /传下去 .dim:=k /传下去 .place:=getc(.array); .offset:=.place ,2020/7/29,华东师范大学计算机科学技术系,73,注意：这儿数组元素的数据类型的宽度W=1，当 W 1时，还需要生成 .offset:=.place*W的三地址语句。即为： .place:=getc(.array); .offset:=.place t:=newtemp emit(t, “ := ”,.offset,*,W) 例见P126 例2：对赋值语句a:=Ab,c+d的推导树和三地址码为：,2020/7/29,华东师范大学计算机科学技术系,74,:=,+,a,d,c,A,b,100: t1:=b*20 101: t1:=t1+c 102: t2:=t1*4 103: t3:=a0t2 104: t4:=t3+d 105: a:=t4,问题： i. 为什么要传递？如何传递？ ii. 在归约时，哪些属性是可以使用的？为什么？,2020/7/29,华东师范大学计算机科学技术系,75,5.6 控制流语句,一、布尔表达式 考虑下列布尔表达式文法： and | or |not |()| id relop id|id|true|false 消除上述文法的二义性规则为： or、and为左结合的，优先级为not，and，or。 relop是关系运算符，它们的优先级均相同，不允许结合。 算术运算符优先级最高，关系运算符其次，布尔运算符最低。,2020/7/29,华东师范大学计算机科学技术系,76,布尔表达式两种基本作用： 参于逻辑运算，如 and 或not 。 作为控制语句的条件表达式， 如if then 或 while do 。 布尔表达式的两种翻译方法 数值表示法：以0表示false，1(非零）表示true，采用计算算术表达式的方法计算表达式的逻辑值。 解释法（优化方法）：由于对布尔表达式E1 or E2，只要E1为true则不管E2的值如何布尔表达式肯定为true，只有E1为false时，E2的值即为布尔表达式E的值。 将A or B 解释为 if A then true else B； 将A and B解释为 if A then B else false； 将not A 解释为 if A then false else true。,2020/7/29,华东师范大学计算机科学技术系,77,二、数值法翻译方案,基本思想：像算术表达式那样计算布尔表达式的值。 引入and、or、not等运算符 对关系运算符确定它们计算后的逻辑值 例3：a or b and not c 的三地址码为： 100: t1:=not c 101: t2:=b and t1 102: t3:=a or t2 而 ab 则为：100: if ab goto 103 101: t:=0 102: goto 104 103: t:=1,2020/7/29,华东师范大学计算机科学技术系,78,翻译方案为： 1 or 2 .place:=newtemp; emit(.place, “ :=”,1.place “or”,2.place) id1 relop id2 .place:=newtemp; emit(“if”,id1.place,relop.op,id2.place, “goto”,nextq+3); emit(.place, “ :=”,0); emit(“goto”, nextq+2); emit(.place, “ :=”,1) ,2020/7/29,华东师范大学计算机科学技术系,79,三、解释法的翻译方案,基本思想与采用的技术 由于按解释法布尔表达式的最终结果是真、假二个出口。因此，将所有的子表达式的真出口组成真出口链，用属性.true指出真链链首，用属性.false指出假链链首。 链的表示形式为： L1： goto 0; L2: goto L1; Ln: goto Ln-1,其中：Li为三地址语句序 号，0表示是链尾。,2020/7/29,华东师范大学计算机科学技术系,80,语义函数makelist(x)的功能为：生成一根链，在第一个元素中填入x（x可以为空），并返回链首。,1.code,to 1.false,to 1.true,2.code,.code,1.false:,to 2.false,to 2.true,to .true,to .false,见P113 例如：对产生式 1 or 2,2020/7/29,华东师范大学计算机科学技术系,81,按解释法将所有的布尔运算解释为转移语句，为便于生成三地址码，将if A then Tcode else Fcobe改写为：if A goto Tcode goto Fcode 其中Tcode、Fcode是三地址语句序号，由nextq给出。特别地，序号0不存在。 采用“回填”技术 例如：对产生式 1 or 2, 1 or 2,.true,.false,2020/7/29,华东师范大学计算机科学技术系,82,子表达式1中的.true转向语句已生成，但2的代码尚未生成，而且2将生成多少个三地址语句不可能确定，所以无法确定转向何处！ 因此，只有当确定了转向点后“回填”。这由语义过程backpatch(x,y)来完成，其功能为：将x指出的链首的链上所有的语句的转向点都填上y。 可表示为： while x0 do begin t:=getL(x); L(x):=y; x:=t end,getL(x)的功能取得x的转向地址 L(x)是序号x的语句中goto后的位置,2020/7/29,华东师范大学计算机科学技术系,83,合并技术 将各子表达式的真、假链合并成一条链，这由语义函数merge(x,y)完成，其功能为：合并分别由x、y为链首的二条链，可描述为： T1:=y;T2:=getL(T1); while T2 0 do begin T1:=T2; T2:=getL(T1); end L(T2):=x；return(y);,2020/7/29,华东师范大学计算机科学技术系,84,插（拆）因子技术 对产生式 1 or 2 如1为假，则转向点已经确定，是2的第一个三地址语句序号（即计算2)，若同时归约，将无法完成回填假链的工作。,注意：采用教科书P115中的语义变量.bcode的 方法为：在 i 加入 .bcode=nextq; 在1 or 2 直接使用 .bcode=nextq,2020/7/29,华东师范大学计算机科学技术系,85,实现,id .true:=makelist(nextq); emit(if id.place goto 0); .false:=makelist(nextq); emit(goto 0) 1 or 2 backpatch(1.false,.code); .true:=merge(1.true,2.true); .false:=2.false .code:=nextq,2020/7/29,华东师范大学计算机科学技术系,86,拆因子方法： 1 or backpatch(1.false,nextq); .true:=1.true 2 .true:=merge(.true,2.true); .false:=2.false ,2020/7/29,华东师范大学计算机科学技术系,87,例见P117 例4 用解释法完成ab or cd and not ef 的翻译，设nextq为100。,100: if ab goto 0 101: goto 102 102: if cd goto 104 103: goto 0 104:if ef goto 103 105: goto 100,2020/7/29,华东师范大学计算机科学技术系,88,四、控制流语句的翻译,条件语句的翻译 文法产生式为： (1) if then 1 (2) if then 1 else 2 语义可描述为： (1) t:=e; if not t then goto L1 1 L1:,(2) t:=e; if not t then goto L1 1 goto L2; L1:2 L2:,2020/7/29,华东师范大学计算机科学技术系,89,由于布尔表达式可以按照数值法、解释法来计算，因此，在控制结构中可以分别采用两种方法来设计翻译方案。 数值法 让带有属性.place表示的值，.type表示的类型。 根据.place的值决定转向。 具体实现留给大家，后面的讨论是针对解释法的。,2020/7/29,华东师范大学计算机科学技术系,90,让带有属性.true和.false分别指出 真、假链首。 为了正确、及时地生成回填地址，采用插（拆） 因子的方法。,插因子方法 (1)if then 1 (2)if then 1 else (3) 2 (4) 拆因子方法 if then 1 else 2,2020/7/29,华东师范大学计算机科学技术系,91,条件语句的属性文法,if then 1 bakpatch(.true,.code); .nextlist:=merge(.false,1.nextlist) (2) if then 1 else backpatch(.truet,.code); t:=makelist(nextq); emit(goto,0); .nextlist:=merge(1.nextlist,t); backpatch(.false,nextq) (3) 2 .nextlist:=merge(.nextlist,1.nextlist) (4) .code:=nextq,2020/7/29,华东师范大学计算机科学技术系,92,后续语句问题,控制流语句中有一个共同的问题，后续语句的转向目标。一般 if-then语句中的 goto L1 if-then-else语句中的 goto L2 不一定是紧跟在这些语句中的三地址代码后的语句 例如： if 1 then if 2 then S1 else S2 else S3 为解决该问题，引入语句出口链，让属性.nextlist指出的正确出口。由表示语句表的产生式 ; 归约时完成。,goto L2,2020/7/29,华东师范大学计算机科学技术系,93, 1; backpatch(1.nextlist, .code); .nextlist:=.nextlist .nextlist:=.nextlist,2020/7/29,华东师范大学计算机科学技术系,94,不考虑后续语句(IF),if then 1 bakpatch(.true,.code); bakpatch(.false,nextq); (2) if then 1 else backpatch(.true,.code); .next:=nextq; emit(goto,0); backpatch(.false,nextq) (3) 2 backpatch(.next,nextq (4) .code:=nextq,2020/7/29,华东师范大学计算机科学技术系,95,while语句的翻译,产生式为： while do 1 语义描述为：L1: t:=e; if not t then goto L2; 1； goto L1; L2: 属性文法为： while 1 do 2 1 backpatch(.true,2.code); backpatch(1.nextlist,1.code); emit(goto, 1.code); .nextlist:=.false ,2020/7/29,华东师范大学计算机科学技术系,96,注意：这儿1、2的值是不同的。 问题：a) 采用拆因子的方法，属性文法如何给出？ b) 如不考虑后续语句，属性文法如何给出？ 例1：给出语句while x10 do x:=x+1;的句法制导 的翻译过程。,while,.100,T=100F=101,do,.102,.,x,10,.x,:=,.x,.x,+,.1,x,x,1,100：if x10 goto 102 104: goto 100 101: goto 0（105） 105: 102: t:=x+1 103: x:=t,2020/7/29,华东师范大学计算机科学技术系,97,五、转向语句和语句标号,转向语句的产生式为: goto L称为标号L的应用性出现 L： 称为标号L的定义性出现 标号的定义性出现可以在使用性出现的前或后。 若标号的定义性出现在前，应用性出现在后，即先定值后引用(称为向后引用)，则填入符号表在前，生成转向目标在后，是容易实现的。若标号的应用性出现在前，定义性出现在后，即先引用后定值(称为向前引用)，则应用时不能从符号表中获得标号的值，只能生成待转指令，待标号的定义性出现后，得到转向目标后回填。,2020/7/29,华东师范大学计算机科学技术系,98,标号定义性出现只能一次（在同一程序段中），否则报错。标号的使用性出现可以有多次，因此要建立转向链。 注意goto语句中L的特殊性，L一般不是nextq的值，而是符号表的入口地址。而将转向点的三地址语句序号存放在L的符号表登记项中。 在讨论了符号表的结构后将再仔细地讨论转向语句和语句标号的实现。,2020/7/29,华东师范大学计算机科学技术系,99,六、其他语句,仅讨论for语句。 for语句的产生式为： for i:=1 to N do 1 其中i为循环变量，它的循环初值和终值分别为和N，都是常量，其语义为： i:=1; again: if i1; i:=i+1; goto again end,L:,L+1:,i:=1,if iN goto .nextlist,1.code,L+2:,M:,i:=i+1,M+1:,goto L+1,2020/7/29,华东师范大学计算机科学技术系,100,采用“拆因子”、“传递”技术，产生式为： for i:=1 to N do 1 相应的属性翻译文法为： for i:=1 to N do p:=lookup(i.name); emit(p, :=, 1); .again:=nextq; emit(if p, , N, goto 0); .place:=p 1 emit(.place,:=.place,+,1); emit(goto, .again, nextq-2); backpatch(1.nextlist,); .nextlist:=.again,2020/7/29,华东师范大学计算机科学技术系,101,习题,P130 5.4 补充题 1. 对布尔表达式：（1）a OR b OR NOT c （2）（a OR NOT b） AND （NOT c OR d） 试分别用： 1）类似于算术表达式那样求值的数值方案； 2）带有真、假两个出口的优化方案； 给出三地址代码的表示。 2. 写出语句repeat1until的属性翻译文法。,2020/7/29,华东师范大学计算机科学技术系,102,3. 考察Pascal语言中如下形式定义的for语句： for V:=1 to 2 do 1 若上述形式的for语句等价于： begin t1:=1；t2:=2； if t1t2 then begin V:=t1； L1: 1； V:=SUCC(V)；/V的后继 if Vt2 then goto L1； end end 试写出符合上述规定的属性翻译文法。,2020/7/29,华东师范大学计算机科学技术系,103,4.条件语句的产生式为： if then 1 else 2 语义可描述为: t:=; if t then goto L1; 1; goto L2; L1:2; L2: 1）让带有属性.type（值为Bool指明是布尔表达式）和.val（值为零表示假，非零为真）。 2）让带有属性.type和属性.false、.true（分别指出了假链与真链的链首地址）。 试分别给出符合上述语义规定的条件语句的属性翻译文法。,2020/7/29,华东师范大学计算机科学技术系,104,7 符号表,符号表是编译程序的一个重要组成部分。在词法分析阶段，当识别出一个新的名字时，便将此名字登入符号表。与之关联的其他属性值，可在词法分析、语法分析、语义分析及中间代码生成等各阶段陆续填入。而在编译各阶段将不断地查询、确认这些信息。因此，对符号表的访问相当频繁，所需的时间开销占了编译时间的不小的比例。如何组织好符号表，为符号表上的操作选择好的算法，是提高编译效率的不可忽视的问题。,2020/7/29,华东师范大学计算机科学技术系,105,一、符号表的组织,抽象地看：符号表是一个对偶（实体名、实体描述）或（名字、信息）组成的集合。 名字：字符串（标识符），信息索引的关键字 信息：由一系列的登记项所组成，记录该实体 的全部信息。 信息的来源： 源程序的说明与定义。 程序中该实体出现的位置（上下文）。 隐含的约定。,2020/7/29,华东师范大学计算机科学技术系,106,名字存储形式：a)直接的、b)间接的,2020/7/29,华东师范大学计算机科学技术系,107,信息的主要内容：各数据实体运行时的特征 种属用type1表示 如：变量、标号、数组 数据类型 type如：整型、实型、字符型 存储单元大小 storage 以byte为单位 值 value 存储地址 存储区级别 storage-class 区分局部量、全局量等 已定义标志 define 所属过程的静态嵌套深度 P-level 其他信息 如过程：形实参数 记录：域名、存储区大小,2020/7/29,华东师范大学计算机科学技术系,108,二、符号表的操作,将符号表视为一个抽象数据类型，则对该ADT所进行的操作主要有： 初始化 Init生成表及表格的初始化 结束化 Exit 结束后的善后处理 插入与搜索lookup(symbol) 在表中查找symbol，如存在，则返回地址，否则插入或报错。 信息的登录enter_desc(entry,desc) 在entry处登录信息desc。 信息的读取 get_desc(entry) 将entry处的信息读取并回送。,2020/7/29,华东师范大学计算机科学技术系,109,实现,符号表的结构： 可以组织成一张大表，或者分成若干张小表。不同的表可以以不同的数据结构组织。 数据结构 线性表 栈式、队式、树式表 散列（Hash)表,2020/7/29,华东师范大学计算机科学技术系,110,三、分程序结构语言的符号表,分程序语言又称为块结构语言，类ALGOL语言，其基本特征是：过程嵌套、分程序嵌套。 满足： 只能嵌套，不能交叉原则 分程序中可以定义、说明数据实体 最近嵌套规则 静态作用域规则和嵌套树规则 对符号表及其操作的要求： 见前（第54张）,2020/7/29,华东师范大学计算机科学技术系,111,实现 采用栈式数据结构组织符号表，对应的操作为： Newlookup(symbol) 功能为54的i. Oldlookup(symbol) 功能为54的ii. Unitentry( ) 记录紧外层最后一个地址，表示新一层的开始。 Unitexit( ) 根据保存的紧外层分程序地址，把本层弹出。 记：tabletop(tt)为符号表栈顶地址 unittop(ut)为分程序表栈顶地址,2020/7/29,华东师范大学计算机科学技术系,112,例1： Unit A; a1,a2:int; Unit B; a3,a4:int; end B; Unit C; a5,a6; end C; end A;,a) 进入B之前为：,tt,ut,b) 退出B之前为：,tt,ut,2020/7/29,华东师范大学计算机科学技术系,113,c) 退出C之前为：,tt,ut,2020/7/29,华东师范大学计算机科学技术系,114,如何计算、保存与存储分配有关的信息 在分程序表中除保存tabletop外，还应保存与存储分配有关的信息，至少应有： offset的当时值（分配地址的工作单元） unitlevel(该分程序的静态层号） 若存储分配以过程为单位，即offset的值为0。则需要完成两件事： 计算各过程所需的最大存储量pstorage值（所有局部于该过程的变量，数组是其信息向量表的大小） 平行分程序中定义的实体可以分配在同一存储空间。如例1中的a5,a6与a3,a4。,2020/7/29,华东师范大学计算机科学技术系,115,工作过程： 在过程的登记项中设立plevel、offset、tabletop、pstorage、unitlevel等内容。 初始时置offset,pstorage,unitlevel为零。 进入分程序，保存当时的tabletop,pstorage,offset, unitlevel+1的值。 退出分程序时，计算pstorage:=Max(pstorage,offset);恢复保存的tabletop,offset,unitlevel-1的值。 这样，在结束分析，退出过程时，pstorage的值即为该过程的最大的存储量。,2020/7/29,华东师范大学计算机科学技术系,116,例2：以过程为单位 存储分配概况： procedure A Unit A1; L1 Unit A2; L2 end A2; R2 Unit A3; L3 end A3; R3 end A1; R1.,R2 L2 0,R3 L3 L1,Ps=R3 offset=L3 Ps=R2 offset=L3=L2 Ps=R2 offset=L2 Ps=0 offset=L2 Ps=0 offset=0,2020/7/29,华东师范大学计算机科学技术系,117,转向语句、标号的处理 问题：分程序结构语言，标号不仅可以先使用，后定义，而且可以从分程序中转出，如何确定l：在哪一层？ 例如：Unit A; Unit B; goto l； end B; l: end A;,2020/7/29,华东师范大学计算机科学技术系,118,解决方法： 在标号使用性出现（goto l;)时，调用newlookup(symbol);这样只查当前分程序，若未查到，则进入符号表。（不报错） 在标号的登记项中设立二个域declared和referenced用于指出标号的定义和引用。初始时都为“No”，当遇到goto l;时在ref中填“Yes”，当遇到l：时在del中填“Yes”。 在退出分程序时，ref和del二个域中可能的情形为： del=“Yes”ref=“No” 表明：l在本层中定义，但未使用，报错。 因为不允许转入本层！,2020/7/29,华东师范大学计算机科学技术系,119,del=“No”ref=“Yes” 表明：本层无定义，但使用了l，goto l;应转至外层同名标号，处理过程为： 将该登记项（可能有多个）勾链在紧外层分程序的符号表中。 若紧外层有同名标号，则转向确定，否则继续1)。 del=“Yes”ref=“Yes” 本层定义，本层使用。,