编译原理与技术讲义 第9章 语法制导的中间代码翻译

1、编译原理与技术第9章语法制导的中间代码翻译青岛大学信息工程学院主要内容中间语言 声明语句的翻译赋值语句的翻译 基本控制结构的翻译转向语句的翻译 编译原理与技术29.1 语法制导的中间代码翻译引论 中间代码翻译在编译程序中的位置 使用中间代码的好处包括：（1）把源程序翻译成目标代码的工作分阶段进行，便于控制和管理开发工作的复杂度，集中地解决不同阶段的不同问题。例如，语义检查可以发现类型不匹配、缺乏类型等可能导致程序运行得错误。（2）便于把与机器特性密切相关的目标代码的生成尽可能的限制在编译的后端，有利于重定目标机器，使得一种中间代码可以为多种不同类型的目标机器服务。这是目前最流行的编程语言Jav

2、a以及.NET编程环境所采用的策略（当然，除了中间表示以外，它们的运行系统还需要虚拟机VM或通用语言运行时CLR等技术）。 语义分析器中间代码生成器代码优化器语法树中间代码语法树中间代码目标代码生成器编译原理与技术39.1 中间语言在编译过程中表示源程序的数据结构统称为中间表示（中间语言）。用中间语言表示的程序叫做中间代码。中间语言的设计既要包含足够的结构，可以支持高级程序语言的结构，如类型、模块、接口、安全机制、垃圾搜集等，又要便于到目标机器的的自动映射，有助于翻译成时空方面都高效的运行代码。编译原理与技术49.1 中间语言中间语言可以按照下列特性分类：抽象程度 中间语言可以非常抽象，像语法

3、树一样抽象地表示几乎所有的操作，也可以具体到接近于目标机器及其指令。抽象的中间语言如分析树、有向无环图，底层的中间语言包括字节代码，它们的语句集合类似于汇编语言或机器的符号指令，而三地址码介于这两类表示之间。现代计算机体系结构（存储管理、寄存器、指令）的发展对中间代码的设计产生了深刻的影响。例如，P-code和Java bytecode都属于字节代码，但是，它们的代码本身与支持环境存在很大的差异。运行时信息 中间语言可能使用目标机器和运行环境的详细信息（如数据类型、变量的位置），也可以不使用这些信息。抽象程度高的语言一般不包含目标机器的信息，而字节代码和三地址码通常都包含了数据类型以及相关的算

4、符。一般的字节码如P-code和Java bytecode都有相应特殊的虚拟机器来解释并运行字节代码。现代计算机技术的发展对程序的安全性、互操作性、并发性等严格要求，使得运行环境更加复杂。编译原理与技术59.1 中间语言使用编译的数据结构 中间语言可以包含符号表的全部信息，例如符号范围、嵌套层次和变量的偏移，目标代码的产生就可以完全倚赖于这样的中间代码。否则，产生目标代码时就需要查询符号表等数据结构。语法树、分析树和有向无环图通常需要符号表的信息才能完成分析和翻译的工作，三地址码也需要使用符号表，一般的字节码已经把这些信息转换成对应虚拟机的信息。互联、开放、异构等特性增加了编译系统数据结构与管

5、理的复杂性，例如，统一的命名空间，除了要包含一个程序的名字以外，还要处理甚至是用其它语言编写的构件中的各种名字。用途 编译过程包含了不同的阶段和任务，每个阶段和任务都有最合适的中间表示：分析树特别适合对源程序进行语法和语义分析，有向无环图适合代码优化和生成，后缀表示便于计算机的计算，字节码和三地址码由于更接近机器代码而最适宜目标码的生成和移植。但是，一个编译程序通常都不会使用太多的中间表示，以免各个中间表示之间的转换造成的效率损失。编译原理与技术69.1 中间语言后缀式后缀式定义9.1 后缀式的递归定义如下：（1）如果E是一个变量或常量，则E的后缀式就是E本身；（2）如果E是形如E1 op E

6、2的表达式，其中op是任意的二元运算符 ，那么， E的后缀式为E1 E2 op，其中E1和 E2分别是E1和E2的后缀式；（3）如果E是(E1)形式的表达式，那么，E1的后缀式就是E的后缀式。 上述定义容易扩充到含单目算符如负号“”或否“not”的表达式，也不难扩充到包含数组元素。 编译原理与技术79.1 中间语言后缀式后缀式的例子(a+b) (a+c) 的后缀式为ab+ac+a+b+c/d (a+c)的后缀式为abcd/ac+not A or not (C and not B)的后缀式为A not CB not and not or对于数组变量，把和分割维数的逗号“,”都看作是二目算符，那么

7、ai的后缀式可以表示成为a iai, j, k 的后缀式为aijk,编译原理与技术89.1 中间语言后缀式后缀式的两个特点（1）后缀式形式的表达式计算顺序唯一，无需使用括号来明确计算顺序；（2）只要直到每个算符的目数，计算参与运算数的个数，对于后缀式不论从左还是从右进行扫描，都能对它进行唯一的分解。例如abc/ 所代表的中缀表达式是 a/(bc)ab+cd+ 所代表的中缀表达式是 (a+b) (c+d)后缀式特别适合利用栈的结构进行计算：自左向右扫描表达式的后缀表示，每遇到一个对象就把它压入栈内；每遇到一个算符，就从栈顶取出相应个数的运算对象进行计算，再将结果压入栈顶。最后，栈顶元素就是表达式

8、的运算结果。 编译原理与技术99.1 中间语言后缀式后缀形式扩充到其它的语言结构 对于赋值表达式V=E，如果把赋值号看作是二目算符，那么，它的后缀形式为VE= ，其中V和E分别是V和E的后缀式。例如，赋值语句t = (a+b) /c (de)的后缀形式为t ab+c/de = 赋值语句ai = aj+m, k的后缀形式为a i ajm+k, =无条件转移语句goto L的后缀表达形式为L GOTO，其中GOTO看作是为单目运算符。编译原理与技术109.1 中间语言后缀式对于条件语句if E then S1 else S2，设E、S1和S2分别是E、S1和S2的后缀形式，L1对应语句S1的起点，

9、L2对应语句S2的起点，那么，上述条件语句的后缀形式可以表示为E L1 GOTO S1L2 GOTO S2。例如，条件语句if (a b) then max = b else max = a的后缀形式为ab 10 GOTO max b= 20 GOTO max a=其中10表示条件为真时转移到的标号，10表示条件为假时无条件转移到的标号处。编译原理与技术119.1 中间语言后缀式复合语句S1;S2的后缀形式可以简单的表示成S1S2，其中S1和S2分别时语句S1和S2的后缀形式。但是，如果像C、Java、Pascal等语言允许在程序块中增加声明语句，那么，就应改对程序块的标志“”或begin和e

10、nd分别引进相应的标志，如BLOCKBEGIN和BLOCKEND。这样，程序块 S1;S2的后缀式为BLOCKBEGIN S1S2 BLOCKEND 循环语句while E do S的后缀式可以下列语句：L1:if not E then goto L2 else S; goto L1L2:参照条件语句和复合语句，可以把while循环语句表示成E L2 GOTO S L1 GOTO 编译原理与技术129.1 中间语言后缀式例9.1 把下面的程序段写成后缀的形式 int i;float a, b, result;i = 1; a = 0;while ( i = 20 ) b = b + a; a

11、= b; i = i+1result = b; 它的后缀形式为BLOCKBEGIN i int a b result,float i 1= a 0 = i 20 = L2 GOTO b ba + = ab= i i 1+= L1 GOTO result b =BLOCKEND编译原理与技术139.1 中间语言后缀式例9.2 表9.1描述了把赋值语句转换成后缀形式的语法制导的翻译规则。其中综合属性code表示符号的后缀形式，属性表示标识符id的名字，num.lexva表示常数num的值；符号“|”表示把语义代码连接起来（读作“捻接”或“并置”）。运算符的属性“op”给出具体的算符，

12、如“+”、“*”或“and”。文法规则语义规则S id = ES.code := | E.code | “”E E1 bop E2E.code := E1.code | E2.code | bop.opE sop E1E.code := E1.code | sop.opE (E1)E.code := E1.codeE idE.code := E numE.code := num.lexval编译原理与技术149.1 中间语言图形表示 a := (b + cd) + cd的语法树如图9.2(a)所示，它的后缀式为abcd+cd+ =。有向无环图DAG也是一种中间表示

13、，和语法树相比，它以更紧凑的方式给出同样的信息，因为它把公共子表达式也标示出来。图9.2(b)的公共子表达式cd不止一个父结点。 :=a+ c b d c d 语法树和分析树都是常见的图形中间代码，语法树省略了语法的终结符号，描述了源程序在语义上的层次结构，是分析树的浓缩表示。语法树作为中间表示允许把翻译从分析中分离出来，形成先分析后翻译的方式。后缀式可以看作式语法树的一种线性表示，它是后序遍历或深度优先遍历语法得到结点的一个序列。:=a+ c d + b 图9.2(b)9.2(a)编译原理与技术159.1 中间语言图形表示例9.3 表9.2描述了把一个简化的赋值语句改造成语法树的翻译规则，使

14、用的是二义性文法，假定算符的优先性和结合性遵循通常的约定，二目运算+和是典型程序语言运算符号集合中选出的两个代表，其中mkunode(op, child)是构造单目运算结点的函数。按照这个定义，可以把输入a := (b + cd) + cd翻译成图9.2(a)形式的语法树。文法规则语义规则S id = ES.tree := mknode( , mkleaf(id, ), E.tree) E E1 + E2E.tree := mknode( +, E1 .tree, E2 .tree,)E E1 E2E.tree := mknode( , E1 .tree, E2 .tree,)

15、 E E1E.tree := mkunode(, E1 .tree)E (E1)E. tree := E1. treeE idE. tree := mkleaf(id, )E numF. tree := mkleaf(num, num.lexval):=a+ c b d c d 编译原理与技术169.1 中间语言图形表示可以修改构造结点的函数，仍然使用这个语义规则构造出有向无环图。它首先检查是否已经存在一个结点和要构造的结点相同，如果是就返回这个已经存在的结点，否则就构造并返回一个新的结点。例如，对mknode的修改如下：function mknode (op: OPKind,

16、lchild, rchild: SyntaxTree): SyntaxTreenode: SyntaxTree;begin for (每个已经产生的语法树的结点node) doif (node.operator = op and node.leftchild = lchild andnode.rightchild = rchild )then return node;return SyntaxTree(op, lchild, rchild);end;按照这个定义，从输入a := (b + cd) + cd构造的DAG如图9.2(b) 。 编译原理与技术179.1 中间语言字节代码字节代码通常就

17、是运行它的机器模型或体系结构的指令系统，与机器的符号指令或汇编语言类似，设计时考虑机器的字节特性以及存储方式、寻址方式、数据类型。 使用字节代码作为中间语言最著名的例子是在1970末和1980初许多Pascal语言编译器中的P-code，它的形式如同一个假想的栈式机器（称为P-机器）的汇编代码，从而省缺了寄存器。对于不同的实际机器需要为P-code构造一个解释程序，这样，就可以使Pascal语言及其编译方便地移植到新的平台上。编译原理与技术189.1 中间语言字节代码作为例子，我们考虑把一个表达式x := 2a+(b3)转换成P-code代码（分号后面是注释）：ldax; 把x的地址存入栈内l

18、dc2; 加载常数2到临时栈loda; 加载变量a的值到临时栈Mpi ; 把栈顶的两个数据2和a弹出，执行整数乘法运算，即2a，结果存放在栈内lodb; 加载变量b的值到临时栈ldc3; 加载常数3到临时栈Sbi ; 把栈顶的两个数据b和3弹出，执行整数减法运算，即b3，结果存放在栈内Adi ; 把栈顶的2a和b3结果弹出，完成整数加法，2a+(b3)，结果存放在栈顶Sto ; 把栈顶的值存入栈顶下地址所指向的变量存储区域中，同时弹出这两个元素上述的计算顺序正好对应了表达式的后缀形式：x2ab3 :=由于P-code被设计成是可以直接执行的，所以，它还隐含了一个特殊的运行时环，包括数据大小以及

19、很多P-机器的特殊信息。 编译原理与技术199.1 中间语言字节代码我们看一下如何使用语义规则把例9.3语言生成P-code。我们用综合属性pcode表示P-code串，用“|”表示在P-code串中插入一个换行。 文法规则语义规则S id = ES.pcode := “lda” | |E.pcode |“sto”E E1 + E2E.pcode := E1 .pcode | E2 .pcode |“adi”E E1 E2E.pcode := E1 .pcode | E2 .pcode |“mpi”E (E1)E. pcode := E1. pcodeE idE. pcode

20、:= ”lod” | E numE. pcode := ”ldc” | num.lexval编译原理与技术209.1 中间语言三地址代码三地址语句是由下列形式的指令x := y op z其中x、y和z是名字、常数或编译其产生的临时变量，op表示运算符如加法、减法、乘法或逻辑算符。它的含义是，对y和z的值施加op所代表的运算，结果存入x表示的地址。源语言的表达式2a+(b3)可以翻译成的三地址代码是：t1 := 2at2 := b3t3 := t1+t2其中t1、t2和t3是编译器产生的临时变量。三地址码是语法树或DAG的一种线性表示，其中新增的临时变量名对应树的内部结点。2a+(

21、b3)的分析树如图9.3所示 +*2a b图9.3 2a+(b3)的语法树编译原理与技术219.1 中间语言三地址代码把赋值语句翻译成三地址代码的语义规则综合属性E.place表示存放E值的名字，E. code表示三地址指令，函数gencode(p, :=, E.place)表示生成三地址语句p := E.place。函数newtemp在每次调用的时候，产生不同的临时变量名。 文法规则语义规则S id = ES.code := E.code | gencode(, :=, E.place)E E1 + E2E.place := newtemp;E.code := E1 .taco

22、de |E2.code |gencode (E.place, :=, E1.place, +, E2.place)E E1 E2E.place := newtemp;E.code := E1.code |E2.tacode |gencode (E.place, :=, E1.place, , E2.place)E E1E.place := newtemp;E.code := E1. code | gencode (E.place, := , uminus, E1.place)E (E1)E.place := newtemp;E. tacode := E1. tacodeE idE.place

23、:= ;E.code := E numE. code := num.lexval编译原理与技术229.1 中间语言三地址代码 下面是本书用到的三地址指令形式为x := y op z的赋值语句，其中op是二目算术或逻辑运算。形式为x := op z的赋值语句，其中op是单目算术或逻辑运算。形式为x := y的赋值语句，它把y的值赋给x。形式为goto L的无条件转移语句，即下一条将被执行的语句是带标号L的三地址语句。形式为if x relop y goto L或if b goto L的条件转移语句，第一中语句对x 和 y施加关系运算relop（如），如果关系成立则执行标号为L的三地

24、址语句，否则执行后续语句；第二种形式中，b为布尔变量或常量，若b为真，则执行标号为L的语句，否则执行后续语句。形式为param x和call p, n表示过程调用语句，其中x表示参数，n表示参数个数。源程序的过程调用语句p(x1, x2, ., xn)通常生成如下的三地址码：param x1.param xncall p, n编译原理与技术239.1 中间语言三地址代码返回语句return x表示过程返回值x，其中x也可以不出现。形式为x := yi和xi := y的索引赋值，第一条语句把相对于地址y后面第i的单元的值赋给x；第而条语句把y的值赋给相对于地址x后面第i的单元里。形式为x :=

25、&y，x:= *y 和*x := y的地址指针赋值。第一个语句把y的存储单元地址赋给x，假定y是一个名字或临时变量，代表一个具有左值的表达式，如Ai, j；而x是指针变量或临时变量，即x的右值是某个对象的值。第二条语句是把y的存储单元里的值赋给x，其中y是指针变量或右值为地址的临时变量。第三条语句把x所指向额对象的右值赋给y的左值。形式为read x的write x输入和输出语句，它们只有一个地址。没有地址的停机语句halt。编译原理与技术249.1 中间语言三地址指令的四元式实现三地址指令操作符运算数1运算数2结果书写形式x := y op zopyzx(op, y, z, x)x := o

26、p zopzx(op, z, , x)x := y:=yx( :=, y, , x)goto LjumpL(jump, , , L)if x relop y goto LjropxyL(jrop, x, y, L)if b goto LjnzbL(jnz, b, , L)param xparamx(param, x, , )call p, ncallpn(call, p, n, )return xreturnx(return, , , x)x := yi=yix(=, yi, , x)xi := y=yxi(=, y, , xi)x := &y&yx(&, y, , x)x:= *yyx(,

27、y, , x)*x := y:=yx(:=, y, , x)read xreadx(read, , , x)write xwritex(write, , , x)halthalt(halt, , , )编译原理与技术259.2 声明语句的翻译 过程中的声明 例如，对于一个C+的声明序列：int index;double sum;char token;如果该声明在内存中可以得到的首地址是1000，那么局部名字x的地址都可以按照下列公式计算：index的地址是 1000sum的地址是 1000+ index的字节宽度10041000 + 4token的地址是 1004+ sum的字节宽度10121

28、00 + 4 +8实际上，为声明语句中的名字分配存储的主要问题就是计算每个名字的相对地址，即相对于基址的偏移，再加上为该声明分配的基址（例如过程活动记录的首址），就可以在存储器中访问到每个名字。编译原理与技术269.2 声明语句的翻译非终结符P产生一系列形如“T id”的声明语句。全局变量offset记录下一个可用的相对地址初始化offset为0。以后每次遇到一个新的名字，将该名字连同类型和当前的offset填入符号表，然后使offset增加该名字所表示的数据的宽度。过程enter(name, type, offset)用来把名字为name的标识符填入符号表。综合属性type和width分别表

29、示非终结符T的类型和宽度。属性type的取值范围是基本类型integer和real以及应用类型构造器pointer和array得到的结构类型。假设整数的宽度是4，实数的宽度是8，指针类型的宽度是4，数组所占用的存储单元个数是数组元素的个数乘以基类型元素的宽度。 文法规则语义动作P Doffset := 0D D1 ; D2D id: Tenter(, T.type, offset);offset := offset + T.widthT integerT. type := integer;T.width := 4T realT. type := real;T.width := 8

30、T array num of T1T. type := array(num.val, T1.type);T.width := num.val * T1.widthT T1T. type := pointer(T1.type);T.width := 4编译原理与技术279.2 声明语句的翻译记录作用域信息 考虑像Pascal和Ada这样允许过程嵌套的语言，主要讨论如何保存声明的作用域信息（6.4）。所讨论的文法如下：P D SD D; D | id: T | proc id; D; S第一条产生式提供程序的规则，在声明D后面跟随语句序列S。声明语句允许嵌套地声明过程。为了简化讨论的问题，我们不考

31、虑递归调用的过程，也不考虑过程的参数说明，这是因为参数可以类似于表9.6的局部变量的处理技术。在处理嵌套过程时为每个过程都建立一张独立的符号表，每个符号表都有自己的符号表指针tableptr、基址base和自己的offset。这些符号表可以一边扫描源程序一边建立并且完成内存分配。每遇到D proc id; D1; S时，就创建一张新的符号表，把D1中的所有说明都添在该符号表；用一个指针记录包含D1的最近的外围过程D的符号表，id也是其中的一个局部名字。在最近的外围过程D的符号表中对于每个直接嵌入其中的过程，也都有一个指向它们符号表指针。编译原理与技术289.2 声明语句的翻译表9.7给出了多趟

32、扫描含有嵌套过程的语法制导翻译规则，它使用了两个数据结构：一个保存各外层过程的符号表指针的指针栈tblptr，一个对应的存放外层过程相对地址的偏移栈offset。指针栈tblptr的栈顶top(tblptr)总是指向当前层的符号表；偏移栈offset的栈顶保存了当前层已经处理的声明的偏移之和。整个翻译模式同时使用了下列操作：SymbolTable *mktable(SymbolTable *previous, integer base)创建一张新的符号表，填入基址，把参数指针previous放在该表的表头，表示指向已经创建好的一个符号表，比如刚好包围嵌入过程的符号表；返回指向这张新表的指针。符

33、号表的信息还可以包含局部变量所需要的存储单元个数等。void enter(SymbolTable *table, String name, DType type, Integer offset)在指针table指向的符号表中为变量名name建立一个新项，类型是type，在该表中的相对地址是offset。void addwidth(SymbolTable *table, Integer width)把符号表table的所有项的累加宽度记录在该表的首部。void enterproc(SymbolTable *table, String name, SymbolTable *newtable) 在t

34、able指向的符号表中为过程名name建立一个新项，指针newtable指向它的符号表。编译原理与技术299.2 声明语句的翻译对于P D S，首先要建立一张空的符号表，动作要在D S之前完成。为了使整个动作都在文法产生式的末尾，我们采取了的技术，引入一个非终结符M和产生式，以消除嵌入在产生式中的语义动作。M的语义动作是初始化外层符号表的指针栈tblptr和偏移栈offset：最外层过程没有包围的过程了，所以指针为空null，相对地址和基址都为0。这样，P M D S的语义动作就是把当前（栈顶）符号表top(tblptr)的所有项的累加宽度记录在该表的首部，表示该过程的局部变量、

35、过程等声明所需要的总的存储单元数；之后，退掉指针栈tblptr和偏移栈offset的栈顶。对嵌入过程说明D proc id; D; S做了类似的语法处理，改成D proc id; N D1; S。首先，在扫描到嵌入的过程D1之前，需要为它建立一个空的符号表，让它指向直接外围过程的符号表，初始化这个新过程的偏移为0，它的基址就是直接外围过程当前所有条目（变量、过程）宽度的总和。这些都由对应N 的语义动作完成。然后，执行D proc id; N D1; S右部的语义动作：首先把D1产生的所有声明的宽度存入它的符号表内（此时放在栈顶的都是有关D1的值），退掉指针栈tblptr和偏移栈offset的栈

36、顶表示结束嵌入过程的处理，继续处理外层过程的声明：把D的当前的条目宽度加上D1所有声明的宽度，为这个嵌入过程的名字id建立符号表条目。 文法规则语义动作P M D Saddwidth(top(tblptr), top(offset);pop (tblptr); pop(offset)M t := mktable(nil, 0);push(t, tblptr); push(0, offset)D D1 ; D2D proc id; N D1; St := top (tblptr);wide := top(offset);addwidth ( t, wide);pop (tblptr); pop(

37、offset);top(offset) := top(offset) + wide;enterproc(top(tblptr), , t)D id:Tenter ( top(tblptr), , T.type, top(offset);top(offset) := top(offset) + T.widthN t := mktable(top(tblptr), top(offset);push(t, tblptr); push(wide, offset)编译原理与技术309.2 声明语句的翻译program sort(input, output)var a: arr

38、ay1.10 of integer; x: integer; procedure readarray; var i: integer; begin . end;44tblptr栈顶offset栈顶1 扫描完sort局部变量的声明时2、扫描过程完readarray局部声明tblptr栈offset栈44tblptr栈顶offset栈顶nullaarray(1.10, integer)xinteger0404iintegerreadarray0sort00440nullaarray(1.10, integer)xinteger040sort00在符号表中，首部包含三个子域：左域是指向直接外围过程符

39、号表的指针，主程序sort的为空null；中域保存该表的基址，右域记录了该过程声明所占存储单元的总的个数（累加宽度之和）。符号表中记录了变量名、类型及其在过程中的相对地址：例如，变量a在sort中的相对偏移就是基址0，而x的相对偏移是在分配完10个整型数（4个字节）之后的地址，即10440。当扫描完readarray的局部变量声明时（对应图9.4中步骤2），首先执行就执行N 对应的动作，得到基址44，tblptr的栈顶是指向readarray符号表的指针；然后执行D id:T对应的动作，在这个符号表中存入i的信息，同时得到readarray符号表的局部声明的累加宽度4。 编译原理与技术319.

40、2 声明语句的翻译3、扫描完过程readarray48nullaarray(1.10, integer)xinteger040iintegerreadarray0sortreadarraytblptr栈顶offset栈顶00444program sort(input, output)var a: array1.10 of integer; x: integer; procedure readarray; var i: integer; begin . end;扫描完readarray过程时，用addwidth把对应readarray的offset值4存入该过程符号表的首部，把指向readarr

41、ay的指针及其偏移量之和分别从指针栈tblptr和偏移栈offset的栈顶删除，修改sort的当前总偏移为48，最后在sort中添加过程readarray的条目，填入一个指向readarray符号表的指针。编译原理与技术329.2 声明语句的翻译040484、扫描完程序sortnillaarray(1.10, integer)xinteger04044iintegerreadarray0sortreadarrayexchangequicksortexchangekintegerquicksortvintegerpartitioniintegerpartitionjinteger06444804

42、8568program sort(input, output)var a: array1.10 of integer; x: integer; procedure readarray; var i: integer; begin . end;procedure exchange(i, j: integer);begin . end;procrdure quicksort(m, n: integer);var k, v: integer;function partition(y,z: integer): integervar i, j: integer;begin . end;begin . e

43、nd quicksort ;begin . end sort;图9.4中的步骤4示意了处理完整个程序后所建立的符号表。最终得到sort中声明所占用的最大存储单元数量是64（= 44+4+8+8）。 编译原理与技术339.2 声明语句的翻译记录中的域名现在，我们可以对表9.6的语言文法增添一个新的产生式，构造程序语言的基本结构类型，记录类型：T record D end对记录的处理类似于对过程的处理。我们为每个记录建立一张符号表，保存每个域的名字及其类型等信息。由于在表9.7中的过程定义不影响域宽的计算，因此，允许上述产生式的D包含过程定义，这样做的目的是为了简化翻译模式 编译原理与技术349.

44、2 声明语句的翻译当编译扫描到关键子record的时候，与非终结符L所对应的动作是，为该记录中的各个域名创建一张新的记录符号表。把指向该表的指针压入指针栈tblptr，并把相对地址0压入偏移栈offset。根据表9.7可知，产生式D id:T的动作是把域名id的有关信息填入该记录的符号表。当记录中的所有域名都被检查之后，在offset的栈顶就存放着记录中的所有数据对象的总的宽度。在表9.8中end之后的动作是把offset栈顶的总的域宽度存入记录类型T的综合属性width，T的类型属性type值则是通过对指向本记录符号表的指针使用类型构造符record得到。 文法规则语义动作T record

45、L D endT.type := pointer (top(tblptr)；T.width := top (offset)L t := mktable (nil, 0);push(t, tblptr); push(0, offset)编译原理与技术359.3 赋值语句的翻译 赋值语句是命令式和面向对象语言改变存储器的内容以及程序状态的基本操作，它的一般语法定义是：V := E;V和E可以是简单类型的表达式，也可以是数组元素、记录中子域变量、指针变量的内容或地址等。赋值语句的语义是：把右部表达式的值赋给左部变量，对于许多语言还要求左部变量与右部表达式的类型相容。赋值语句的执行步骤包括： 计算右部

46、表达式E的值； 必要时对E的值进行类型转换，强制到V的类型； 计算做变量V的地址； 把E的值送入V的地址。这是设计翻译赋值语句的基础。 编译原理与技术369.3 赋值语句的翻译简单算术表达式及赋值语句我们在三地址代码中直接使用了表达式的名字，并将它理解为指向符号表中该名字的入口指针。现在，我们使用函数lookup()在符号表中查找名为的标识符的入口地址。表9.9给出了如何使用符号表把简单表达式及赋值语句翻译成三地址代码的语义动作。其中E的属性place表示E在符号表中的入口，使用输出代码的函数，emit(id.place, :=, E.place)表示把赋值语句的三

47、地址码按顺序地写在一个输出文件。文法规则语义规则S id : = Ep := lookup ();if p = null then errorelse emit (p, :=, E.place )E E1 + E2E.place := newtemp;emit (E.place, :=, E1.place, +, E2.place)E E1 E2E.place := newtemp;emit (E.place, :=, E1.place, , E2.place)E E1E.place := newtemp;emit (E.place, :=, uminus, E1.place)E

48、 (E1)E.place := E1. place;E idp := lookup ();if p = null then errorelse E.place := pE numE. place := num.lexval编译原理与技术379.3 赋值语句的翻译在嵌套结构中查询名字的函数lookup的一个实现。首先，设计使用的符号表的数据结构SymbolTable（参考图9.4），给出主要的结构和子域如下：struct Iditem String name; DType type; Address offset struct SymbolTable SymbolTable *pr

49、evious; Integer base, offset; Idlist ids;/* 名字项的表 */ Proclist procs;/* 过程项的表 */假设符号表中的变量项放在表结构类型Idlist的变量ids中，并且假设函数search（name, list）当前过程的符号表中查询name是否在局部标识符表list中：如果在就返回指向名字是name的标识符项，否则返回null。ditem *lookup ( String name, SymbolTable *table)SymbolTable *next, *p; next = table; while (next ! = null

50、) p = serach (name, next ids)； if p != null return p; next = next previous; return null;编译原理与技术389.3 赋值语句的翻译在翻译规则中对中间代码就有两种表示方法：利用生成函数gencode把中间代码存入符号的属性code中，并可以利用并置符号把代码段连接起来，形成更大的代码段直至程序，随时整理并输出到文件上。这个方法更适合多趟扫描的编译构造，允许在多次分析源程序的过程中多次访问和处理存在属性内的中间代码。一边分析和翻译源程序的语句，一边按照源程序的顺序把中间代码（用函数emit）写在一个输出文件中。这

51、个方法可以在一趟编译扫描过程中同时完成代码的翻译，但是，没有办法对产生的代码进行优化，因为函数emit通常是把中间代码输出在一个顺序文件中。 编译原理与技术399.3 赋值语句的翻译数组元素的引用数组的有关信息，如分配的基址、维数、每个维的上下界、维数的大小、成员数据占用的存储大小等，是存放在一个称作数组向量的符号表中。我们主要研究如何计算静态数组中一个数组元素的地址，并翻译成三地址代码。我们不讨论诸如数组的下标是否越界、类型是否合适等其它问题。 编译原理与技术409.3 赋值语句的翻译数组元素的引用假如一维数组A的下界是low，分配的相对地址是base，即Alow的相对地址，每个元素的宽度是

52、w，那么A的第i个元素Ai的起始地址是：base + ( i low)w(9.1)把它整理成iw + (base loww)这样，(base loww)就可以在编译时刻完成，从而减少了运行时的地址计算。编译原理与技术419.3 赋值语句的翻译二维数组的元素也必须转化为一维方式存储，通常有两种方式存储：以行为主或以列为主。对于多维数组的存储，FORTRAN使用以列为主，Pascal、C+和Java都以行为主。在行为主的两维数组的情况下，Ai, j的地址可以用下列公式计算：base + (i low1)n2+(j low2)w其中low1和low2分别是这两维的下界，n2是第2维的大小，即若hig

53、h2是j值的上界，则有n2 = high2low2+1。假定i和j的值在编译时不知道，而可以知道其它值，那么，把上式变换成(in2 + j )w +(base (low1n2)+low2)w)(9.2)同样，后一项子表达式(base (low1n2)+low2)w)可以在编译时计算。编译原理与技术429.3 赋值语句的翻译推广到k维数组，得到Ai1, i2, .,ik的地址表达式如下：(.(i1n2 + i2 )n3 + i3).)nk + ik)w +base (.(low1n2 + low2 )n3 + low3).)nk + lowk)w(9.3)假定对所有的j，nj = highjlo

54、wj+1是固定的，那么，公式(9.3)的第2行就可以在编译时计算出来，存放在数组A的信息域里Ai1, i2, .,ik地址的动态部分需要在运行时计算，必须设计出计算这个地址的代码。下面，我们考虑如何计算数组引用的动态部分(.(i1n2 + i2 )n3 + i3).)nk + ik (9.4)它可以用下列递推公式e1 = i1em = em-1nm + im (9.5)进行计算，直到m=k为止。然后将ek乘以数组元素的宽度w，再加上公式(9.3)的第2行就可以得到数组引用元素的地址。 编译原理与技术439.3 赋值语句的翻译从(9.5)的递推计算中可以看出，除了第一个下标i1以外，其它每个em

55、的计算都要访问数组的符号表项，以便得到各维的大小。如果在表9.9的文法中出现id的地方也允许出现下面产生式中L出现，则可以把数组元素引用加入到赋值语句中。L id Elist | idElist Elist, E | E如果仅用综合属性，在处理Elist Elist, E和Elist E的时候就访问不到数组L的有关信息，因为这是与数组名id关联的信息。因此把产生式等价地改写成L Elist | idElist Elist, E | id E即数组名与最左下标表达式连在一起，这样在翻译Elist的过程中都能知道符号表中相应于数组名id的信息。要生成数组引用的三地址代码，关键是把(9.5)的计算与

56、数组引用的文法联系起来。编译原理与技术449.3 赋值语句的翻译对Elist设置如下的综合属性：array表示指向符号表中相应数组名表项的指针，ndim保存已经分析过的下标表达式的个数，place保存根据下标表达式计算的值，即公式(9.5)中em的值。函数esizeof(array)给出数组元素的宽度，limit(array,j)返回array所指示数组的第j维的维数nj，base(array)给出符号表中array所指示数组的基址，即公式(9.3)中的base，函数adrconst(array)表示公式(9.3)第2行的减号之后的值。左值L有两个属性，place和offset。当L是简单名字

57、时，L.offset为null，L.place是指向符号表中对应此名字表项的指针；否则，L.place = base(array) adrconst(array)，表示公式(9.3)中第2行的值，L.offset表示某个数组元素的索引，等于Elist.placew。编译原理与技术459.3 赋值语句的翻译下面考虑在赋值语句中加入数组元素之后的一种翻译模式，把语义动作加入到下列文法中：（1）S L: = E（2）E E1 + E2（3）E (E1)（4）E L（5）L Elist （6）L id（7）Elist Elist, E （8）Elist id E编译原理与技术469.3 赋值语句的翻译

58、若L是个简单名字，则产生正常的赋值；否则，产生对L所指示地址的索引赋值：（1）S L: = Eif L.offset = null then emit (L.place, :=, E.place )else emit(L.place, , L.offset, , :=, E.place)算术表达式语义动作和表9.9一样：（2）E E1 + E2 E.place := newtemp;emit (E.place, :=, E1.place, +, E2.place) （3）E (E1) E.lpace := E1.lpace 编译原理与技术479.3 赋值语句的翻译若L是个简单名字，则产生正常的

59、赋值；否则，产生对L所指示地址的索引赋值：（1）S L: = Eif L.offset = null then emit (L.place, :=, E.place )else emit(L.place, , L.offset, , :=, E.place)算术表达式语义动作和表9.9一样：（2）E E1 + E2 E.place := newtemp;emit (E.place, :=, E1.place, +, E2.place) （3）E (E1) E.lpace := E1.lpace 编译原理与技术489.3 赋值语句的翻译若一个数组引用L归约到E时，即分析的源程序串中出现了a10或

60、b5,8这样的数组引用的时候，则需要L的右值，可以用索引得到存储单元地址L.placeL.offset的内容：（4）E L if L.offset = nullthen E.place := L.placeelse beginE.place := newtemp;emit (E.place, :=, L.place, , L.offset, )end 编译原理与技术499.3 赋值语句的翻译下面计算在这个归约中用到的L的属性值：（5）L Elist L.place := newtemp; L.offset := newtemp;emit (L.place, :=, base(Elist.arr