第六章 中间代码生成.pptx

1、编译原理Principle of Compiler,第六章 中间代码生成 黄孝喜,在编译器的“分析-综合”模型中，前端对源程序进行分析并产生中间表示，而关于目标机器的细节则在后端处理。 本章内容涉及中间代码表示、静态类型检查和中间代码生成。,2,引子,语法 分析器,静态检查程序,中间代码生成器,代码 生成器,中间代码,前端,后端,“中间代码生成”的任务把经过语法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。 不同的编译器对中间表示的选择和设计各有不同。 中间表示可以是一种真正的语言，也可以是各个处理阶段共享的多个内部数据结构。 早期的C+编译器就把C语言作为中间表示 方法: 语法制导

2、翻译 采用独立于机器的中间代 码的好处 1. 便于编译系统建立和编译系统的移植； 2. 便于进行独立于机器的代码优化工作。,3,引子,中间语言 语法树 有向非循环图DAG 三地址代码表示 类型检查 常用语句的中间代码生成方法 说明语句 赋值语句 布尔表达式与控制流语句 回填,4,提纲,常用的中间代码(语言) 语法树 后缀式(逆波兰式) 三地址代码表示 特点 形式简单、语义明确、便于翻译 独立于目标语言,5,6.1 中间语言,抽象语法(Abstract Syntax) 从具体语法中抽象出语言结构的本质性的东西，而不考虑语言的具体符号表示，从而可简化语义的形式描述。 在不同的语言中赋值语句有不同的

3、写法 x=y; x:=y; yx 等等 可以用抽象形式 assignment(variable, expression) 把前面各种具体形式统一起来。,6,6.1.1图表示法,抽象语法(Abstract Syntax) 抽象语法树(AST)反映了抽象的语法结构，而分析树反映的是具体语法结构。语法树是分析树的抽象形式或压缩形式。 在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。抽象语法树不同于分析树，它展示了一个操作过程并同时描述了源程序的层次结构。,7,6.1.1图表示法,语法规则中包含的某些符号可能起标点符号作用，也可能起解释作用。 回顾前述的

4、赋值语句，其产生式规则是 SV = e 其中的赋值号“=”仅仅起标点符号作用，目的是把V和e分隔开 而条件语句的产生式规则: Sif B then S1 else S2 其中的关键字if、then、else起注释作用，说明当布尔表达式B为真时执行S1语句，否则执行S2,8,抽象语法树,赋值语句的本质部分是V和e 条件语句的本质部分是B, S1和S2 把语法规则中本质部分抽象出来而将非本质部分去掉后，便得到抽象语法规则 这种去掉不必要信息的做法可以获得高效的源程序中间表示。上述语句的抽象语法规则为: (1) 赋值语句: 左部 表达式 (2) 条件语句: 表达式 语句1 语句2,9,抽象语法树,根

5、据这种方法得到两种语句的语法树如下:,10,抽象语法树,assignment,variable,expression,if-then-else,B,S1,S2,赋值语句语法树,条件语句语法树,在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。,赋值语句x=a+b*c的抽象语法树和分析树,11,抽象语法树,抽象语法树,分析树,表达式的语法树构建方法(利用语法制导定义) 辅助函数: 1. mknode(op, left, right) 建立一个运算符号结点，标号是op,两个域left和right指向运算分量结点的指针。 2. mkleaf(id,entry) 建立一个标识符结点,由标

6、号id标识，一个域entry指向标识符符号表中相应的项。 3. mkleaf(num,val) 建立一个数结点，标号为num，域val用于存放数的值。返回新建立结点的指针。,12,抽象语法树,建立表达式语法树的语法制导定义,13,抽象语法树,表达式a-4+c的语法树建立过程,14,id,to entry for a,id,to entry for c,num 4,id1,T1.nptr,E2.nptr,E1.nptr,T2.nptr,T3.nptr,id2,E.nptr,num,+,表达式a-4+c的语法树建立过程,15,id,to entry for a,id,to entry for c,

7、num 4,建立赋值语句语法树的语法制导定义,16,抽象语法树,赋值语句a := b *c的语法树构建过程,17,id1,S.nptr,E1.nptr,:=,E2.nptr,*,E3.nptr,id2,E4.nptr,id3,id,to entry for b,id,to entry for c,id,to entry for a,uminus,*,:=,赋值语句a := b *c的语法树构建过程,18,id,to entry for b,id,to entry for c,id,to entry for a,uminus,*,:=,表达式的有向非循环图表示(DAG，Directed Acyc

8、lic Graphs) 用途: 提取表达式中的公共子表达式，以取得目标程序的局部优化。 方法：执行mknode和mkleaf时，检查是否已有相同的结点，若有，则返回相应结点的指针。 与语法树的区别：语法树中公共子表达式由重复的子树表示，而 DAG 中只用一个子树表示，因此代表公共子表达式的结点有多个父节点,19,6.1.1图表示法,表达式a+a*(b-c)+(b-c)*d的语法树和DAG,20,6.1.1图表示法,id,to entry for a,id,to entry for a,id,to entry for b,id,to entry for c,*,id,id,to entry fo

9、r b,to entry for c,*,id,to entry for d,表达式a+a*(b-c)+(b-c)*d的语法树和DAG,21,6.1.1图表示法,p1:=mkleaf(id, entry-a); p2:=mkleaf(id, entry-a); p3:=mkleaf(id, entry-b); p4:=mkleaf(id, entry-c); P5:=mknode(-, p3, p4); P6:=mknode(*, p2, p5); P7:=mknode(+, p1, p6); P8:=mkleaf(id, entry-b); P9:=mkleaf(id, entry-c);

10、P10:=mknode(-, p8, p9); p11:=mkleaf(id, entry-d); P12:=mknode(*, p10, p11); P13:=mknode(+, p7, p12),修改建立表达式语法树的语法制导定义，产生表达式的 DAG,在构造结点前检查现有结点，若存在相同结点则返回该结点的指针,表达式a+a*(b-c)+(b-c)*d的语法树和DAG,22,6.1.1图表示法,id,to entry for a,id,to entry for b,id,to entry for c,*,*,id,to entry for d,1,2,3,4,5,6,7,8,9,10,11

11、,12,13,波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示法。 这种表示法把运算量(操作数)写在前面，把运算符写在后面，因而又称后缀表示法。例如，把a+b写成ab+，把a*(b+c)写成abc+*。 一般，若e1,e2为任意的后缀表达式， 为任意双目运算符，则用作用于e1和e2所代表的结果用后缀式e1e2 表示。 推而广之， 为k目运算符，则作用于e1e2ek的结果用 e1e2ek 来表示。,23,6.1.2逆波兰式表示法,中缀式: a*d + b*c + e,24,由抽象语法树生成后缀式,抽象语法树,后根遍历生成后缀式: a d * b c * + e +,25,由语法制导

12、定义生成后缀式,属性code表示生成的代码,后缀表示法的优点：易于计算机处理表达式。 常用的算法：使用一个栈，自左至右扫描算术表达式(后缀表示)： 扫描到运算对象，就把它推进栈； 扫描到运算符: 若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈； 若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈。 最后的结果留在栈顶,26,后缀式的求值,ab+c*的求值(a=1,b=3,c=5),27,后缀式的求值,1 3 + 5 *,1,3,+,4,1+3=4,5,*,4*5=20,20,计算完毕，结果为20,一般形式 x:y op z 一般含三

13、个地址(名字、常数、临时变量):两个操作分量和一个结果的抽象地址 为方便起见, 通常用变量名代替抽象地址 如，源语言表达式x+y*z可以被翻译为: t1:=y * z t2:= x+t1 其中t1和t2是编译时产生的临时变量,28,6.1.3 三地址代码,三地址代码与语法树、DAG 的关系 三地址代码是语法树或DAG 的线性表示 表达式a+a*(b-c)+(b-c)*d的语法树和DAG对应的三地址代码,29,6.1.3 三地址代码,t1:=b c t2:=a * t1 t3:=a + t2 t4:=b c t5:= t4 * d t6:=t3 + t5,根据语法树,t1:=b c t2:=a

14、* t1 t3:=a + t2 t4:= t2 * d t5:= t3 + t4,根据DAG,三地址代码的类型 (1)赋值语句 x:y op z，op为二目算术算符或逻辑算符 (2)赋值语句 x:op y ，op为一目算符，如一目减uminus、逻辑非not、移位算符及转换算符 (3)无条件转移语句goto L (4)条件转移语句 if x relop y goto L，关系运算符号relop( ，=，= 等等) (5)复制语句 x:y,30,6.1.3 三地址代码,三地址代码的类型 (6)过程调用语句 param x 和 call p, n 。过程调用语句p(x1, x2, xn)产生如下三

15、地址代码: param x1 param x2 param xn call p, n 过程返回语句 return y,31,6.1.3 三地址代码,三地址代码的类型 (7)索引赋值语句： x:=yi xi:=y (8)地址和指针赋值语句 x:= while (ai v);的三地址翻译,33,6.1.3 三地址代码,L:t1= i +1 i =t1 t2 = i * 8 t3 = a t2 if (t3 v) goto L,100:t1= i +1 101:i =t1 102:t2 = i * 8 103:t3 = a t2 104:if (t3 v) goto 100,用标签形式,用标号形式,

16、假设数组a中每个元素占用存储单元为8,语法制导翻译生成三地址代码 定义几个属性: (1)E.place表示存放E值的名字。 (2)E.code表示对E求值的三地址语句序列。 (3) newtemp是个函数，对它的调用将产生一个新的临时变量。,34,6.1.3 三地址代码,35,语法制导翻译生成三地址代码,三地址语句序列是语法树的线性表示，用临时变量代替语法树中的结点。 实际实现中，三地址语句序列往往是被存放到一个输出文件中，而不是将三地址语句序列置入code属性之中,36,语法制导翻译生成三地址代码,三地址代码的具体实现 1. 四元式 op, arg1, arg2, result 2. 三元式

17、 op, arg1, arg2 3. 间接三元式 间接码表+三元式表,37,6.1.3 三地址代码,三地址代码的具体实现 四元式有四个字段，分别称为op, arg1, arg2, result。字段op包含一个运算符的内部编码，如对于三地址指令x=y+z的相应四元式中，op字段存放+，arg1中为y，arg2中为z，result中为x。 对于形如x=op y的单目运算符指令和赋值指令x=y，不使用arg2。像param这样的运算既不使用arg2也不使用result。条件或非条件转移指令将目标标号放入result字段,38,6.1.3 三地址代码,对于语句a:=b*-c+b*-c 的三种表示方法

18、,39,三地址代码的具体实现,t1 = uminus c t2 = b * t1 t3 = uminus c t4 = b * t3 t5 = t2 + t4 a = t5,三地址代码,四元式,对于语句a:=b*-c+b*-c 的三种表示方法,40,三地址代码的具体实现,四元式,三元式,三元式中使用指向三元式语句的指针。,对于语句a:=b*-c+b*-c 的三种表示方法,41,三地址代码的具体实现,间接三元式表示,三地址代码三种实现形式的比较 代码优化时，经常因调整计算次序而要移动三地址语句 四元式调整顺序方便，但引入的临时变量多，需存储空间大 三元式需存储空间最小，但调整顺序不便 间接三元式

19、优化方便，在有公共子表达式时，需存储空间比四元式小 中间代码优化处理时，四元式比三元式方便的多,间接三元式与四元式同样方便，两种实现方式需要的存储空间大体相同。,42,6.1.3 三地址代码,例 : a + b * ( c - d ) + e / ( c - d) n 求: 1.后缀式 2.四元式 3.三元式 4.间接三元式,43,中间语言练习,例 : a + b * ( c - d ) + e / ( c - d) n 后缀式 a b c d - * + e c d n / + 三地址代码 t1 = c d t2 = b * t1 t3 = a + t2 t4 = c d t5 = t4 n

20、 t6 = e / t5 t7 = t3 + t6,44,中间语言练习,例 : a + b * ( c - d ) + e / ( c - d) n 四元式,45,中间语言练习,t1 = c d t2 = b * t1 t3 = a + t2 t4 = c d t5 = t4 n t6 = e / t5 t7 = t3 + t6,例 : a + b * ( c - d ) + e / ( c - d) n 三元式,46,中间语言练习,例 : a + b * ( c - d ) + e / ( c - d) n 间接三元式,47,中间语言练习,中间语言 语法树 有向非循环图DAG 三地址代码表示

21、 类型检查 常用语句的中间代码生成方法 说明语句 赋值语句 布尔表达式与控制流语句 回填,48,提纲,每个程序设计语言都有自己的类型机制，包括类型说明和使用。 类型检查是编译器语义分析的重要组成部分。编译器首先根据类型说明，确定每一个变量和常量的类型，计算其使用存储空间的大小，从而建立其到存储空间的映射。进而，编译器要确定每个语言结构的类型，以完成下面的主要任务: (1)判定重载算符(函数)在程序中代表的是哪一个运算 (2)进行类型转换 (3)对语言结构进行类型检查。如: Pascal语言中对数据类型的使用要进行同一、相容和赋值相容检查,49,6.2 类型检查,类型表达式 语言结构的类型由类型

22、表达式表示。类型表达式依赖于程序语言的类型体制。 类型表达式: 或者是简单类型表达式，或者是通过类型构造符作用于类型表达式而得到，具体定义如下: (1)类型名和基本类型是类型表达式。integer, char, real, boolean是(Pascal语言)基本类型，所以是类型表达式。void表示“无类型”， type_error表示“出错类型”，也是类型表达式。,50,6.2 类型检查,可以把这一条看作是类型表达式定义的核，然后通过下面的类型构造符来生成更复杂的类型表达式,(2)类型构造符作用于类型表达式的结果仍然是类型表达式。类型构造符包括: a) 数组构造符ARRAY。如果T是一个类型

23、表达式，则ARRAY(I, T)是类型表达式，指称一个数组类型，T为其成分类型，I是下标值集合 b)笛卡尔乘积: 若T1，T2是类型表达式，则T1T2也是类型表达式，其中是左结合的。 c) 记录类型构造符RECORD: 若有标识符N1，N2，Nn和类型表达式T1，T2，Tn，则RECORD(N1T1)(N2T2)(NnTn)是类型表达式，指称了一个记录类型。,51,类型表达式,(2)类型构造符作用于类型表达式的结果仍然是类型表达式。类型构造符包括: d) 指针类型构造符POINTER: 若T是一个类型表达式，则POINTER(T)是类型表达式，指称一个指针类型。 e)函数类型构造符: 若D1,

24、 D2, , Dn和R是类型表达式，则D1D2DnR是类型表达式，其中的优先级高于，它指称了一个从定义域类型为D1D2Dn到值域类型为R的映射(函数) (3) 类型表达式中可以出现类型变量，其值也是类型表达式,52,类型表达式,例1,53,类型表达式,设有Pascal 程序片段： TYPE stype=RECORD name:ARRAY 1.8 OF char; score:integer END; VAR table:ARRAY 1.50 OF stype; p: stype;,则stype代表的类型表达式 RECORD(nameARRAY(1.8, char)(score integer)

25、 和table绑定的类型表达式 ARRAY(1.50,stype) 和p绑定的类型表达式 POINTER(stype),例2 设有下面的函数定义 FUNCTION f(P1:T1; P2:T2; ;Pn:Tn):T; BEGIN END; 和f绑定的类型表达式 T1T2 TnT 如定义函数 FUNCTION f(a, b: char): integer; BEGIN END; F绑定的类型表达式为charcharPOINTER(integer),54,类型表达式,例3 在函数式语言中可如下定义恒等函数 fun f(x)=x x可以是任何类型的语言结构。因此x可以是任何类型。f的类型表达式为 为

26、类型变量，其值是任何类型表达式。,55,类型表达式,静态类型检查: 由编译器完成的检查 动态类型检查: 目标程序运行时完成的检查 如果目标代码把每个对象的类型和该对象的值一起保存，那么任何检查都可以动态完成。 如果一种语言的编译器能够保证它所接受的程序不会有运行时的类型错误，则称这种语言是强类型语言。 有些检查只能动态完成 table: array0.255 of char; i: integer; 计算tablei 类型检查的内容包括: 表达式、语句、函数,56,6.2 类型检查,变量标识符类型的确定 程序是由说明序列和语句序列组成 语句序列是计算，说明部分建立计算环境，其中说明了每个变量标

27、识符以及与之绑定的类型 文法GP是一个简单的程序语言语法，该程序由一系列声明D和随后的表达式E组成，假设数组的下标从1开始，产生式如下: PD; E DD; D|id:T Tchar | integer | ARRAYnum OF T | T Enum | id | E MOD E | EE | E,57,6.2 类型检查,语义分析程序首先处理类型说明，建立类型表达式，然后处理变量说明，建立变量和类型表达式的绑定。具体实现是把变量标识符的类型信息记录在其符号表的表项中，过程addtype(id.entry,T.type)完成这个任务，引入综合属性T.type，记录类型表达式。其翻译模式如下:,

28、58,6.2 类型检查,PD;E DD;D Did:Taddtype(id.entry, T.type) TcharT.type:=char Tinteger T.type:=integer TT1 T.type:=POINTER(T1.type) TARRAYnum OF T1 T.type:=ARRAY(num.val, T1.type),表达式的类型检查 检查运算对象之间类型是否满足相容条件。引入综合属性E.type来表示E的类型表达式。,59,6.2 类型检查,Enum E.type:=integer Eid E.type:=lookup(id.entry),函数lookup(e)取符

29、号表中保存在条目e中的类型。,表达式的类型检查 检查运算对象之间类型是否满足相容条件。引入综合属性E.type来表示E的类型表达式。,60,6.2 类型检查,Enum E.type:=integer Eid E.type:=lookup(id.entry) EE1 MOD E2 E.type:=IF (E1.type=integer) AND (E2.type=integer) THEN integer ELSE type_error,一致性检查，假设 MOD 的运算分量必须是integer，结果也是integer,表达式的类型检查 检查运算对象之间类型是否满足相容条件。引入综合属性E.typ

30、e来表示E的类型表达式。,61,6.2 类型检查,Enum E.type:=integer Eid E.type:=lookup(id.entry) EE1 MOD E2 E.type:=IF (E1.type=integer) AND (E2.type=integer) THEN integer ELSE type_error EE1E2 E.type:=IF (E2.type=integer) AND (E1.type=ARRAY(s, t) THEN t ELSE type_error EE1 E.type:=IF E1.type=POINTER(t) THEN t ELSE type_

31、error,语句的类型检查 语句的类型检查主要包括：赋值语句类型的相容性，控制表达式的结果类型检查。 指派给语句的类型是基本类型void，如果在语句中发现类型错误， 指派给语句的类型是type_error。 由于语句中嵌入了表达式，所以在语句的类型检查中总是需要对表达式进行类型检查,62,6.2 类型检查,检查语句类型的翻译模式,63,6.2 类型检查,Sid:=E S.type:=IF id.type=E.type THEN void ELSE type_error SIF E THEN S1 S.type:=IF E.type=boolean THEN S1.type ELSE type_

32、error SWHILE E DO S1 S.type:=IF E.type=boolean THEN S1.type ELSE type_error SS1;S2 S.type:=IF (S1.type=void)AND(S2.type=void) THEN void ELSE type_error,函数引用的类型检查 函数引用的两种情况: 标准函数，或者在说明部分定义的函数 对说明部分的分析，应该能知道被引用函数的类型，翻译模式为 TT1T2 T.type:=T1.typeT2.type 函数引用可以看作是一个表达式作用于另一个表达式，其类型检查可表示为: EE1(E2) E.type:=

33、IF (E2.type=s) AND (E1.type=st) THEN t ELSE type_error ,64,6.2 类型检查,函数引用的类型检查 函数引用的两种情况: 标准函数，或者在说明部分定义的函数 对说明部分的分析，应该能知道被引用函数的类型，翻译模式为 TT1T2 T.type:=T1.typeT2.type 函数引用可以看作是一个表达式作用于另一个表达式，其类型检查可表示为: EE1(E2) E.type:=IF (E2.type=s) AND (E1.type=st) THEN t ELSE type_error ,65,6.2 类型检查,把单个参数推广到多个参数,类型为

34、T1、T2、Tn的n个变元可以看成类型为T1T2 Tn的一个变元。,类型转换 一般的程序设计语言中都规定了某些类型之间的转换关系：比如说整数量可以被当作实数量参与运算，并且不需要程序员显式说明。 不同类型的常数在计算机中有不同的表示。当一个值需要转换成为其它类型使用的时候，需要使用某些代码进行转换。 因此，编译程序要识别需要进行类型转换的地方，并相应地生成代码。 程序设计语言的设计者需要考虑什么情况下需要和可以进行转换。,66,6.2 类型检查,表达式: x+i，x为real，i为integer 整型数和实型数在计算机中的表示不同，运算的机器指令也不同 编译程序必须首先转换一个操作数，以保证类

35、型相同 语言定义指出什么转换是必需的 赋值语句: 把赋值号右边的对象转换成左边对象的类型 表达式: 把整数转换成实数，然后在这一对实型对象上进行实数运算 类型检查器在源程序的中间表示里插入这些转换操作 x+i的后缀式可能是：x i inttoreal real+,67,类型转换,如果从一种数据类型转换成另一种数据类型可以由编译器自动完成，则这种类型转换是隐式的，隐式转换也叫做强制转换。 一般要求隐式转换原则上不丢失信息 如果转换必须由程序员显式地写在源程序中，则这种转换叫做显式转换。 显式的类型转换对类型检查器来说好象函数调用,68,类型转换,69,从整型到实型的类型检查规则,说明(声明)语句

36、的翻译 作用: 说明语句(Declarations)用于对程序中规定范围内使用的各类变量、常数、过程进行说明 编译要做的工作 在符号表中建立相应的表项，填写有关的信息。如类型、嵌套深度、相对地址等。 相对地址:相对静态数据区基址或活动记录中局部数据区基址的一个偏移值。,70,6.3 常用语句的翻译,过程中的说明语句 一个过程中的说明语句作为一个类集来处理。用一个全程变量offset来记录下一个数据在符号表中的相对地址。,71,说明(声明)语句的翻译,类型说明和数组说明的文法和翻译方案,PD DD; D Did ：T Tinteger Treal Tarraynumof T T T,引入: 全局

37、变量offset，记录下一个可用单元的相对地址 T.width：记录名字的域宽 T.type：记录名字的类型 enter(，T.type，offset): 为名字name建立一个符号表表项,72,说明(声明)语句的翻译,P D DD;D Did:T Tinteger Treal Tarray num of T1 TT1, offset:=0 ;, enter(, T.type, offset); offset:=offset+T.width , T.type:=integer; T.width:=4 , T.type:=real; T.width:=8 , T.ty

38、pe:=array(num.val, T1.type); T.width:=num.valT1.width , T.type:=pointer(T1.type); T.width:=4 ,P MD M offset:=0 ,M称为标记非终结符,73,处理说明语句 id1: real; id2: integer,P,offset:=0,D,D1,;,D2,id1,:,T1,real,id2,:,T2,T3,integer, T1.type:=real; T1.width:=8 ,offset:=8,id1,real,0,enter(id1, real, 0) offset:=offset+8,7

39、4,处理说明语句 id1: real; id2: integer,P,offset:=0,D,D1,;,D2,id1,:,T1,real,id2,:,T2,T3,integer, T1.type:=real; T1.width:=8 , T3.type:=integer; T3.width:=4 ,offset:=8,offset:=12, T2.type:=pointer(T3.type); T2.width:=4 ,id1,real,0,id2,pointer(integer),8,enter(id2, pointer(integer), 8) offset:=offset+4,D T t

40、 = T.type; w = T.width id A id.type = A.type; id.width=A.width T int T.type := int; T.width := 4 T double T.type := real; T.width := 8 A A.type = t; A.width = w; A num A1 A.type=array(num.value, A1.type; A.width := num.value A1.width T T1 * T.type := pointer (T1.type); T.width := 4 ,75,C语言简单类型声明翻译,保

41、留作用域信息 一般的语言中，标识符的作用在程序正文中有一个确定的范围。 因此，同一个标识符在不同的程序正文中可能标识不同的对象， 具有不同的性质，要求分配不同的存储空间。 提出问题: 如何组织符号表，使得同一个标识符在不同的作用域中得到正确的引用而不产生混乱 特别是在允许嵌套过程的语言，如Pascal中。我们来考察一下具有嵌套过程说明的程序结构,76,说明(声明)语句的翻译,77,带嵌套过程的程序,(1) program sort( input，output); (2) var a: array0.10 of integer； (3) x: integer; (4) procedure rea

42、darray； (5) var i : integer;(6) begin a end readarray; (7) procedure exchange(i, j: integer); (8) begin (9) x:= ai ; ai:=aj; aj:x (10) end exchange; (11) procedure quicksort(m, n: integer); (12) var k, v:integer； (13) function partition(y, z: integer) : integer; (14) var i, j: integer;(15) begin a (

43、16) v (17) exchange(i，j); (18) end partition ; (19) begin end quicksort; (20) begin end. sort,(2)-(19)都是说明部分,过程说明的层次关系:,sort,readarray,exchange,quicksort,partition,78,嵌套说明的文法,文法 PD DD; D Did: T Dproc id; D; S 其中T用于产生类型，S用于产生语句 嵌套说明的程序结构首先要解决的问题是局部数据和非局部数据的访问 解决方法:为每一个过程建立一张符号表 所有正在翻译过程的符号表组成整个源程序的符号

44、表。翻译语句部分时查找符号表，查找过程的符号表的路线相当于当前被 翻译过程的静态链。,79,保留作用域信息,具体翻译时，每当碰到过程说明Dproc id;D1;S时,便创建一张符号表,并且把D1中的所有说明都填入此符号表中 新表中有一个指针，指向其直接外围过程符号表,用于解决非局部数据的访问 过程名id 作为直接外围过程的局部名字记录在直接外围过程符号表中； 同时还要在直接外围过程符号表中增加一个指向该过程D1符号表的指针,80,嵌套过程的符号表,sort,readarray,exchange,quicksort,partition,81,嵌套过程的翻译,作用域信息的保存 文法 P D D D

45、;D D id:T D proc id; D;S Tinteger Treal Tarray num of T1 TT1,创建主程序的符号表、初始化,记录主程序所需空间,定位操作：为子过程id创建符号子表，并初始化,重定位操作：记录子过程所需要空间，返回到外围过程,82,嵌套过程的翻译,翻译过程的辅助操作 1. mktable( previous）创建一张新符号表 2. enter(table，name，type，offset)插入表项 3. addwidth（table，width）记录总域宽 4. enterproc（table,name, newtable） 翻译过程用到的数据结构 ta

46、bleptr是一个栈，用于存放指向嵌套外层过程的符号表指针 offset是一个栈，用于存放变量的相对地址，当过程结束时，offset里记录的是过程占用的所有字节数。,83,嵌套过程中的说明语句翻译方案,P M D M D D;D D id:T D proc id; N D;S N, t:= mktable(nil); push(t，tableptr); push(0，offset) , enter(top(tableptr)，，T.type，top(offset); top(offset):=top(offset)+T.width , t:=mktable(top(tablept

47、r); push(t，tableptr)； push(0，offset) , t:=top(tableptr); addwidth(t，top(offset); pop(tableptr)； pop(offset); enterproc(top(tableptr)，，t) , addwidth(top(tableptr)，top(offset); pop(tableptr); pop(offset) ,84,a:array10 of integer ; x:integer ; proc readarray; i:integer ; begin a end ; proc excha

48、nge; begin a end ; proc quicksort; k:integer ; v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,M t:= mktable(nil); push(t，tableptr); push(0，offset) ,sort,tableptr offset,0,85,a:array10 of integer ; x:integer ; proc readarray; i:integer ; begin a end ; proc exchange

49、; begin a end ; proc quicksort; k:integer ; v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,0,D id:T enter(top(tableptr)，，T.type，top(offset); top(offset):=top(offset)+T.width ,a,x,0,40,40,44,86,a:array10 of integer ; x:integer ; proc rea

50、darray; i:integer ; begin a end ; proc exchange; begin a end ; proc quicksort; k:integer ; v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,0,a,x,0,40,40,44,N t:=maketable(top(tableptr); push(t，tableptr)； push(0，offset) ,readarray,0,87,a:array10

51、 of integer ; x:integer ; proc readarray; i:integer ; begin a end ; proc exchange; begin a end ; proc quicksort; k:integer ; v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,0,a,x,0,40,40,44,readarray,0,D id:T enter(top(tableptr)，，T.type，

52、top(offset); top(offset):=top(offset)+T.width ,0,i,4,88,a:array10 of integer ; x:integer ; proc readarray; i:integer ; begin a end ; proc exchange; begin a end ; proc quicksort; k:integer ; v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,0,a,x,

53、0,40,40,44,readarray,D proc id; N D;S t:=top(tableptr); addwidth(t，top(offset); pop(tableptr)； pop(offset); enterproc(top(tableptr)，，t) ,0,i,4,(4),readarray,89,a:array10 of integer ; x:integer ; proc readarray; i:integer ; begin a end ; proc exchange; begin a end ; proc quicksort; k:integer ;

54、 v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,0,a,x,0,40,40,44,readarray,0,i,0,(4),readarray,N t:=maketable(top(tableptr); push(t，tableptr)； push(0，offset) ,exchange,90,a:array10 of integer ; x:integer ; proc readarray; i:integer ; begin a e

55、nd ; proc exchange; begin a end ; proc quicksort; k:integer ; v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,0,a,x,0,40,40,44,readarray,0,i,0,(4),readarray,exchange,D proc id; N D;S t:=top(tableptr); addwidth(t，top(offset); pop(tableptr)； pop(

56、offset); enterproc(top(tableptr)，，t) ,(0),exchange,91,a:array10 of integer ; x:integer ; proc readarray; i:integer ; begin a end ; proc exchange; begin a end ; proc quicksort; k:integer ; v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,0

57、,a,x,0,40,40,44,readarray,0,i,0,(4),readarray,exchange,(0),exchange,N t:=maketable(top(tableptr); push(t，tableptr)； push(0，offset) ,quicksort,92,a:array10 of integer ; x:integer ; proc readarray; i:integer ; begin a end ; proc exchange; begin a end ; proc quicksort; k:integer ; v:integer ; proc part

58、ition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,0,a,x,0,40,40,44,readarray,0,i,0,(4),readarray,exchange,(0),exchange,quicksort,D id:T enter(top(tableptr)，，T.type，top(offset); top(offset):=top(offset)+T.width ,k,0,4,4,v,8,93,a:array10 of integer ; x:integer ; proc readarray; i:integer ; begin a end ; proc exchange; begin a end ; proc quicksort; k:integer ; v:integer ; proc partition; i:integer ; j:integer ; begin exchange end ; begin end,sort,tableptr offset,