编译原理课件chap7.ppt

1、第七章 语义分析和中间代码产生,第七章 语义分析和中间代码的产生,本章我们将把上一章所介绍的方法和技术应用于语义分析和中间代码的生成中。 紧接在词法分析和语法分析之后，编译程序要做的工作是进行静态语义检查和翻译。静态语义检查通常包括：1。类型检查。2。控制流检查。3。一致性检查。4。相关名字检查。 翻译为中间语言的好处： （1）便于进行与机器无关的代码优化； （2）使编译程序改变目标机更容易； （3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。,第七章 语义分析和中间代码产生,7。1中间语言 首先要掌握几种中间语言的基本结构：逆波兰表示，图表示法（DAG

2、 和抽象语法树），三地址代码（四元式、三元式、间接三元式） 7。1。1后缀式 后缀式表示法有称逆波兰表示法。这种方法是，把运算量（操作数）写在前面，把算符写在后面（后缀）。 一个表达式的后缀式可以如下定义： （1）如果E是一个变量或常量，则E的后缀式是E自身。 （2）如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为 E1 E2op,这里E1 和E2分别为E1和E2的后缀式。 （3）如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。,第七章 语义分析和中间代码产生,7。1。2图表示法 我们要介绍的图表示法包括DAG与抽象语法树。 无循环有向图（Direct

3、ed Acyclic Graph , 简称 DAG ).与抽象语法树一样，对于表达式中的每个子表达式，DAG图中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。两者不同的是，在DAG图中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。 表7。2 和抽象语法树的两种表示法都应掌握。 7。1。3 三地址代码 三地址代码是由下面一般形式的语句构成的序列: X:=y op z 其中，x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号如定点运算符、浮点运算符、逻辑运算符等。每个语句的右边只能有一个运算符。,第七章 语义分析和中间代码产生

4、,表7。3（P171)是为赋值语句生成三地址代码的S属性文法定义。应在掌握之列 关于四元式，三元式，间接三元式都在必须掌握之列，参看P172173. 7。2说明语句 当考察一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。对每个局部名字，我们将在符号表中建立相应的表项，并填入相应的信息如类型、在存储器中的相对地址等。相对地址是指对静态数据区基地址的一个偏移量。 7。2。1 过程中的说明语句 在C、Pascal及FORTRAN等语言的语法中，允许在一个过程中的所有说明语句作为一个组来处理，把他们按排在一所数据区中。从而我们需要一个全程变量如offset来跟踪下一个可用的相

5、对地址的位置。,第七章 语义分析和中间代码产生,图7。6关于说明语句的翻译模式是应该掌握的，尤其是用产生式的标记非终结符号，改写产生式： P offset:=0 D 以便语义动作均出现整个产生似的右边。改写为： PMD M offset:= 0 7.2.2保留作用域信息 当遇到一个嵌入的过程说明时,则应当暂停包围此过程的外围过程说明语句的处理。这种方法可以通过加入下的语言把有关语义动作来说明。 PD PD;D|id:T | proc id ;D ;S （7。2）,第七章 语义分析和中间代码产生,这里与图7。6中相同，T有两个属性type和width. 为简化起见，我们假定对于式（7。2）的语言

6、的每一个过程都有一张独立的符号表。这种符号表可以用链表实现。当碰到过程说明Dproc id; D1 ;S 时，便创建一张新的符号表。并且把在D1中的所有说明项都填入此符号表内。新表有一个指针指向刚好包围该嵌入过程的外围过程的符号表，由id表示的过程名字作为该外围过程的局部名字。对图7。6 处理变量说明的唯一修改是，要告诉enter在哪个符号表填入一项。 在图7。8种的翻译模式给出了如何在一遍扫描中对数据进行处理，它使用了一个栈tblptr保存各外层过程的符号指针。如对于图7。7 所示的符号表，当处理过程partition中的说明语句时，栈tblptr中将包括指向sort,quicksort及p

7、artition的符号表的指针。指向当前符号表的指针在栈顶。另一个栈offset存放各嵌套过程的当前相对地址。Offset 的栈顶元素为当前被处理过程的下一个局部名字的相对地址。,第七章 语义分析和中间代码产生,对于 ABC action A 所有关于非终结符号B,C的语义动作均已先于 Action A完成。因此，在图7。8中将先做与标记非终结符号M相应的语义动作。 M的语义动作把栈tblptr初始化为仅含最外层作用域的符号表的指针，由mktable(nil)创建符号表，并把符号表的指针返回给t；同时还把相对地址0压入栈offset中。当出现一个过程说明时，非终结符起着类似的作用。它的语义动作

8、使用mktable(top(tblptr)来创建一个新符号表。这里参数top(tblptr)为指向刚好包围此嵌套过程的外围过程符号表的指针。把指向新表的指针压入栈tblptr的栈顶，同时把相对地址0压入offset栈顶。 每遇到一个变量说明id:T，就把id填入在当前符号表中。这是栈tnlptr保持不变，而栈offset的栈顶值增加T.width。当开始执行产生式 Dproc id; N D1;S,第七章 语义分析和中间代码产生,右边的语义动作时，由D1产生的所有名字占用的总宽度便是offset的栈顶值，它由过程addwidth记录下来；同时，栈tblptr及其offset的栈顶项值被弹出，我

9、们返回带外层过程中的说明语句继续处理。并在此时把过程的名字id填入到其外围过程的符号表中。 7。2。3 纪录中的域名 除了基本类型、指针、和数组外，下述产生式使非终结符号T产生纪录类型： Trecord D end 7。3 赋值语句的翻译 在本节中赋值语句中的表达式的类型可以是整型、实型、数组和纪录。作为翻译赋值语句为三地址代码的一部分，我们将讨论如何在符号表中查找名字及如何存取数组和纪录的元素。,第七章 语义分析和中间代码产生,7。3。1 简单算术表达式及赋值语句 课本P179图7。10给出了把简单算术表达式及赋值语句翻译为三地址代码的翻译模式。该翻译模式中说明了如何查找符号表的入口。属性i

10、表示id所代表的名字本身。过程lookup()检查是否在符号表中存在此名字的入口。如果有，则返回一个指向该表项的指针，否则，返回nil表示没找到。 在图7。10的语义动作中，调用过程emit将生成的三地址语句发送到输出文件中，而不是如表7。3中那样建造非终结符号的code属性。注意： 在考试中如果遇到赋值语句的翻译应以图7。10为准。 在有嵌套过程时如何使用图7。10，请参考课本P178-179,第七章 语义分析和中间代码产生,7.3.1数组元素的引用 现在讨论包括数组元素的表达式和赋值语句的翻译问题。 若数组A的元素存放在一片连续单元里，则可以较容易的访问数组的每个

11、元素。假定数组的每个元素的宽度为w，则一维数组Ai 这个元素的起始地址为： base + (i low)*w （7。4） 其中low为数组下标的下界， 并且base是分配给数组的相对地址，即base为A的第一个元素Alow的相对地址。 7。4式可以整理为： i*w + (base low*w) 其中：i*w 是随数组下标变量而变化的部分 （base low*w)是在数组中不变化的常数记为C,第七章 语义分析和中间代码产生,对于多维数组中二维的情况尤其应注意： 若二维数组A按行存放，则可用如下公式计算Ai1,i2的相对地址： base + ( i1 low1)*n2 + i1 low2) *w

12、其中，low1、low2分别为i1、i2的下界；n2是i2可取值得个数。即若high2为i2的上界，则n2=high2 low2 +1. 假定i1,i2是编译时唯一尚未知道的值，我们可以重写上述表达式为： ( (i1*n2) + i2) *w +( base （ (low1 *n2) + low2) *w） 后一项子表达式( base （(low1 *n2) + low2) *w ）的值是可以在编译时确定的,为常数。前一子项随i1, i2 而改变是一个变数。 特别是当low=1， 时有：V=(i1*n2+i2)*w C= base (n2+1)*w 应该牢记。,第七章 语义分析和中间代码产生,

13、要生成数组的引用代码，其主要问题是把常数C和变数V 的计算与数组引用的文法联系起来。如果在图 7。10的文法中 id 出现的地方也允许下面产生式中的L出现，则可把数组元素引用加入到赋值语句中。 Lid Elist | id ElistElist, E | E 为语句处理上的方便改写为： LElist | id Elist Elist, E | id E 即把数组的名字id与最左下标表达式E 相联系，而不是在形成L时与Elist相联系。其目的是使我们在整个下标表达式串Elist的翻译过程中随时都知道符号表中相应于数组名字id的全部信息。对于非终结符号Elist引进综合属性arry，用来纪录指向符

14、号表中相应数组名字表项的指针。,第七章 语义分析和中间代码产生,我们还利用Elist.ndim来纪录Elist中的下表表达式的个数，即维数。函数Limit(arry, j) 返回nj ，即由arry所指示的数组的第j 维的长度。最后，Elist.place表示临时变量，用来临时存放由Elist中的下标表达式计算出来的值。 一个Elist可以产生一个k- 维数组引用Ai1,i2,ik的前m维下标，并将生成计算下面式子的三地址代码。 （ ( ( i1*n2 +i2)n3)nm + im 利用如下的递归公式进行计算： e1 = i1, em = em-1* nm + im 于是 当m=k时将ek乘以

15、元素的宽度w便可计算出 （7。6）的第一个子项。 描述L的左值（基地值）用两个属性L.place和L.offset.如果L仅为一个简单名字，L.place就为指向符号表中相应此名字表项的指针，而offset为null，表示这个左只是一个简单名字而非数组的引用。,第七章 语义分析和中间代码产生,课本P181-183考虑在赋值语句中加入数组元素之后的翻译模式，并将语义动作加入到了文法中的内容是必须掌握。 例7。1设A为一个10X20的数组，即n1=10, n2=20并设w=4。对付值语句X:=Ay,z （1） 写出该赋值语句被翻译成三地址代码语句系列。 （2）画出该赋值语句的代注释语法分析树。 解

16、： 三地址代码： T1:=y*20 T1:=T1 + z T2:= A-84 为：A-(n2 +1 )*w T3:= 4* T1 T4:= T2 T3 x:= T4,第七章 语义分析和中间代码产生,代注释的语法树：其中每个变量，用其名字代替id.place.,第七章 语义分析和中间代码产生,在前面关于算术表达式和赋值语句的翻译中，我们假定所有的id 都是同一类型的。实际上，在表达式中可能出现各种类型的变量或常量。所以编译程序必须做到：或者拒绝接受某种混合运算，或者产生有关类型转换的指令。P183-184课本中给出了这种表达式和赋值语句的语义规则要掌握。 7。3。3 纪录中域的引用 7。4 布尔

17、表达式的翻译 在程序设计语言中，布尔表达式有两个基本作用： 一个使用作计算逻辑值；另一个是用作控制流语句如 if-then、if-then-else和 while-do等之中的条件表达式。 布尔表达式是用布尔运算符号（and、 or、not )作用到布尔变量或关系表达式上而组成的。关系表达式形式如E1 relop E2, 其中E1和E2是算术表达式， relop为关系运算符 （ , , =, ）。,第七章 语义分析和中间代码产生,在本节中我们考虑由下列文法产生的布尔表达式： EE or E | E and E | not E | (E) | id relop id |id 我们使用relop的

18、属性relop.op来确定relop所指的六中关系中的哪一个。按惯例，我们假定or和and 是左结合的，并且规定or 的优先级最低，其次是and, not的优先级最高。 7.4.1 数值表示法 首先考虑用1表示真，0表示假来实现布尔表达式的翻译。 一个形如 ab的关系表达式可等价的写成: if ab then 1 else 0 ,并将它翻译成如下三地址语句序列： 100： if ab goto 103 101 T:=0 102 goto 104 103 T:= 1 104,第七章 语义分析和中间代码产生,产生布尔表达式的三地址代码的翻译模式见课本P186的图7。13。 7。4。2 作为条件控制

19、的布尔式翻译 出现条件语句： if E then S1 else S2 （7。10） 中的布尔表达式E，它的作用仅在于控制对S1和S2的选择。只要能完成这一使命，E 的值就无需最终保留在某个临时单元中。因此，作为转移条件的布尔式 E，我们可以赋予它两种“出口”。 一个是“真”出口，出向S1；一个是“假”出口，出向S2。于是语句（7。10）可翻译成如图7。15所示的形式。,第七章 语义分析和中间代码产生,在这种翻译中，对于作为转移条件的布尔式，我们可以把它翻译成为一串跳转指令。 在翻译过程中，我们假定可以用符号标号来标识一条三地址语句，并且假定每次调用函数newlabel后都返回一个新的符号标号

20、。 对于一个布尔表达式E,我们引用两个标号：E.true是E为真时的控制流转项的标号； E.false是E为假时控制流转向的标号。 表7。7是按此方式将布尔表达式翻译成三地址代码的语义规则，应该掌握。 我们假设实现三地址代码时采用四元式形式实现，并且假定： （jnz , a ,- , p ) 表示 if a goto p (jrop, x , y, p ) 表示 if x rop y goto p (j , -, - , p ) 表示 goto p,第七章 语义分析和中间代码产生,课本P190讲的四元式链表翻译模式应该掌握。 7。5 控制语句的翻译 7。5。1 控制流语句 我们考虑文法： S

21、if E then S1 | if E then S1 else S2 | while E do S1 其中E 布尔表达式。 与上一节一样，我们先讨论对这些语句进行翻译的一般语义规则。然后讨论如何通过一遍扫描产生上述语句的代码，给出相应的翻译模式。,第七章 语义分析和中间代码产生,关于这三条语句的代码结构如图7。17所示。条件语句S的语义规则允许控制从S 的代码S.code之内转移到紧接S.code之后的那条三地址指令。但是，有时候此条紧接S.code之后的指令是一条无条件转移指令，它转移到标号为L的指令。通过使用继承属性S.next可以避免上述连续转移的发生，而从S.code之内直接转移到标

22、号为L的指令。S.next 之值是一个标号，他指出继S 的代码之后将被执行的第一条三地址指令。 图7。17：,第七章 语义分析和中间代码产生,在翻译if-then语句 Sif E then S1 时，我们建立了一个新的标号E.true，并且用它来标识S1的代码的第一条指令，如图7。17（a)所示。表7。8给出了一个属性文法。在E的代码中将有这样的转移指令：若E为真则转移到E.true,并且若E为假则转移到S.next.因为我们置E.false为S.next. 在翻译if-then-else 语句 S if E then S1 else S2时， 布尔表达式E的代码中有这样的转移指令：若E为真则

23、转移到S1的第一条指令， 若E为假则转移到S2的得一条指令。如图7。17（b）所示。,语句Swhile E do S1 的结构图如7。17（c) 与上边两个语句相似， 不再重述。,第七章 语义分析和中间代码产生,使用回填技术通过一遍扫描翻译控制流语句的翻译模式应该掌握。可参看课本P194-196 7。5。2 标号与goto语句 7。5。3 CASE语句的翻译 7。6 过程调用的处理 过程是程序设计语言中最常用的一种结构。我们这一节所讨论的过程也包括函数，实际上函数可以看作是返回结果值的过程。 我们考虑过程调用文法如下： （1） Scall id (Elist) (2) Elist Elist, E (3) Elist E 其传地址的翻译模式应掌握。 7。7 类型检查,第七章 语义分析和中间代码产生,例题与习题解答,例7。1写出下列各式的逆波兰表示 （1） -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C (D/E)/F 解： （1） abc*cd-/ba*+ - （2） ABCDE/*F/+ 例7。2 写出表达式 A+B*(C-D)-E/FG 逆波兰表示， 三元组表示， 四元组表示。 解：逆波兰表示： ABCD -*+EFG/ - 三元组表示：,第七章 语义分析和中间代码产生,( - , C, D ) (* , B, ) (+,A , )