1、编译原理与技术编译原理与技术第第9章章语法制导的中间代码翻译语法制导的中间代码翻译编译原理与技术编译原理与技术2主要内容主要内容u中间语言中间语言 u声明语句的翻译声明语句的翻译u赋值语句的翻译赋值语句的翻译 u基本控制结构的翻译基本控制结构的翻译u转向语句的翻译转向语句的翻译 编译原理与技术编译原理与技术39.1 语法制导的中间代码翻译引论语法制导的中间代码翻译引论 中间代码翻译在编译程序中的位置中间代码翻译在编译程序中的位置 使用中间代码的好处包括：使用中间代码的好处包括：（1）把源程序翻译成目标代码的工作分阶段进行，便于控制和管理）把源程序翻译成目标代码的工作分阶段进行，便于控制和管理开
2、发工作的复杂度，集中地解决不同阶段的不同问题。例如，语义开发工作的复杂度，集中地解决不同阶段的不同问题。例如，语义检查可以发现类型不匹配、缺乏类型等可能导致程序运行得错误。检查可以发现类型不匹配、缺乏类型等可能导致程序运行得错误。（2）便于把与机器特性密切相关的目标代码的生成尽可能的限制便于把与机器特性密切相关的目标代码的生成尽可能的限制在编译的后端，有利于重定目标机器，使得一种中间代码可以为多在编译的后端，有利于重定目标机器，使得一种中间代码可以为多种不同类型的目标机器服务。种不同类型的目标机器服务。这是目前最流行的编程语言这是目前最流行的编程语言Java以及以及.NET编程环境所采用的策编
3、程环境所采用的策略（当然，除了中间表示以外，它们的运行系统还需要虚拟机略（当然，除了中间表示以外，它们的运行系统还需要虚拟机VM或通用语言运行时或通用语言运行时CLR等技术）。等技术）。语义分析器中间代码生成器代码优化器语法树中间代码语法树中间代码目标代码生成器编译原理与技术编译原理与技术49.1 中间语言中间语言在编译过程中表示源程序的数据结构统称为在编译过程中表示源程序的数据结构统称为中间表示（中间语言）。中间表示（中间语言）。用中间语言表示的程序叫做中间代码。用中间语言表示的程序叫做中间代码。中间语言的设计既要包含足够的结构，可以中间语言的设计既要包含足够的结构，可以支持高级程序语言的结
4、构，如类型、模块、支持高级程序语言的结构，如类型、模块、接口、安全机制、垃圾搜集等，又要便于到接口、安全机制、垃圾搜集等，又要便于到目标机器的的自动映射，有助于翻译成时空目标机器的的自动映射，有助于翻译成时空方面都高效的运行代码。方面都高效的运行代码。编译原理与技术编译原理与技术59.1 中间语言中间语言中间语言可以按照下列特性分类：中间语言可以按照下列特性分类：l抽象程度抽象程度 中间语言可以非常抽象，像语法树一样抽象地表中间语言可以非常抽象，像语法树一样抽象地表示几乎所有的操作，也可以具体到接近于目标机器及其指令。示几乎所有的操作，也可以具体到接近于目标机器及其指令。抽象的中间语言如分析树
5、、有向无环图，底层的中间语言包抽象的中间语言如分析树、有向无环图，底层的中间语言包括字节代码，它们的语句集合类似于汇编语言或机器的符号括字节代码，它们的语句集合类似于汇编语言或机器的符号指令，而三地址码介于这两类表示之间。现代计算机体系结指令，而三地址码介于这两类表示之间。现代计算机体系结构（存储管理、寄存器、指令）的发展对中间代码的设计产构（存储管理、寄存器、指令）的发展对中间代码的设计产生了深刻的影响。例如，生了深刻的影响。例如，P-code和和Java bytecode都属于都属于字节代码，但是，它们的代码本身与支持环境存在很大的差字节代码，但是，它们的代码本身与支持环境存在很大的差异。
6、异。l运行时信息运行时信息 中间语言可能使用目标机器和运行环境的详细中间语言可能使用目标机器和运行环境的详细信息（如数据类型、变量的位置），也可以不使用这些信息。信息（如数据类型、变量的位置），也可以不使用这些信息。抽象程度高的语言一般不包含目标机器的信息，而字节代码抽象程度高的语言一般不包含目标机器的信息，而字节代码和三地址码通常都包含了数据类型以及相关的算符。一般的和三地址码通常都包含了数据类型以及相关的算符。一般的字节码如字节码如P-code和和Java bytecode都有相应特殊的虚拟机都有相应特殊的虚拟机器来解释并运行字节代码。现代计算机技术的发展对程序的器来解释并运行字节代码。现
7、代计算机技术的发展对程序的安全性、互操作性、并发性等严格要求，使得运行环境更加安全性、互操作性、并发性等严格要求，使得运行环境更加复杂。复杂。编译原理与技术编译原理与技术69.1 中间语言中间语言l使用编译的数据结构使用编译的数据结构 中间语言可以包含符号表的全部信息，例中间语言可以包含符号表的全部信息，例如符号范围、嵌套层次和变量的偏移，目标代码的产生就可以完如符号范围、嵌套层次和变量的偏移，目标代码的产生就可以完全倚赖于这样的中间代码。否则，产生目标代码时就需要查询符全倚赖于这样的中间代码。否则，产生目标代码时就需要查询符号表等数据结构。语法树、分析树和有向无环图通常需要符号表号表等数据结
8、构。语法树、分析树和有向无环图通常需要符号表的信息才能完成分析和翻译的工作，三地址码也需要使用符号表，的信息才能完成分析和翻译的工作，三地址码也需要使用符号表，一般的字节码已经把这些信息转换成对应虚拟机的信息。互联、一般的字节码已经把这些信息转换成对应虚拟机的信息。互联、开放、异构等特性增加了编译系统数据结构与管理的复杂性，例开放、异构等特性增加了编译系统数据结构与管理的复杂性，例如，统一的命名空间，除了要包含一个程序的名字以外，还要处如，统一的命名空间，除了要包含一个程序的名字以外，还要处理甚至是用其它语言编写的构件中的各种名字。理甚至是用其它语言编写的构件中的各种名字。l用途用途 编译过程
9、包含了不同的阶段和任务，每个阶段和任务都有编译过程包含了不同的阶段和任务，每个阶段和任务都有最合适的中间表示：分析树特别适合对源程序进行语法和语义分最合适的中间表示：分析树特别适合对源程序进行语法和语义分析，有向无环图适合代码优化和生成，后缀表示便于计算机的计析，有向无环图适合代码优化和生成，后缀表示便于计算机的计算，字节码和三地址码由于更接近机器代码而最适宜目标码的生算，字节码和三地址码由于更接近机器代码而最适宜目标码的生成和移植。但是，一个编译程序通常都不会使用太多的中间表示，成和移植。但是，一个编译程序通常都不会使用太多的中间表示，以免各个中间表示之间的转换造成的效率损失。以免各个中间表
10、示之间的转换造成的效率损失。编译原理与技术编译原理与技术79.1 中间语言后缀式中间语言后缀式u后缀式后缀式定义定义9.1 后缀式的递归定义如下：后缀式的递归定义如下：（1）如果）如果E是一个变量或常量，则是一个变量或常量，则E的后缀式就是的后缀式就是E本身；本身；（2）如果）如果E是形如是形如E1 op E2的表达式，其中的表达式，其中op是任意的二元是任意的二元运算符运算符，那么，那么，E的后缀式为的后缀式为E1 E2 op，其中，其中E1和和 E2分分别是别是E1和和E2的后缀式；的后缀式；（3）如果）如果E是是(E1)形式的表达式，那么，形式的表达式，那么，E1的后缀式就是的后缀式就是
11、E的的后缀式。后缀式。上述定义容易扩充到含单目算符如负号上述定义容易扩充到含单目算符如负号“”或否或否“not”的表达式，也不难扩充到包含数组元素。的表达式，也不难扩充到包含数组元素。编译原理与技术编译原理与技术89.1 中间语言后缀式中间语言后缀式u后缀式的例子后缀式的例子(a+b)(a+c)的后缀式为的后缀式为ab+ac+a+b+c/d (a+c)的后缀式为的后缀式为a bcd/ac+not A or not(C and not B)的后缀式为的后缀式为A not CB not and not or对于数组变量，把对于数组变量，把和分割维数的逗号和分割维数的逗号“,”都看作都看作是二目算符
12、，那么是二目算符，那么ai的后缀式可以表示成为的后缀式可以表示成为a iai,j,k 的后缀式为的后缀式为aijk,编译原理与技术编译原理与技术99.1 中间语言后缀式中间语言后缀式u后缀式的两个特点后缀式的两个特点（1）后缀式形式的表达式计算顺序唯一，无需使用括号来明确）后缀式形式的表达式计算顺序唯一，无需使用括号来明确计算顺序；计算顺序；（2）只要直到每个算符的目数，计算参与运算数的个数，对于）只要直到每个算符的目数，计算参与运算数的个数，对于后缀式不论从左还是从右进行扫描，都能对它进行唯一的分后缀式不论从左还是从右进行扫描，都能对它进行唯一的分解。例如解。例如ab c/所代表的中缀表达式
13、是所代表的中缀表达式是 a/(b c)ab+cd+所代表的中缀表达式是所代表的中缀表达式是 (a+b)(c+d)后缀式特别适合利用栈的结构进行计算：后缀式特别适合利用栈的结构进行计算：1.自左向右扫描表达式的后缀表示，每遇到一个对象就把它压入自左向右扫描表达式的后缀表示，每遇到一个对象就把它压入栈内；栈内；2.每遇到一个算符，就从栈顶取出相应个数的运算对象进行计算，每遇到一个算符，就从栈顶取出相应个数的运算对象进行计算，再将结果压入栈顶。再将结果压入栈顶。3.最后，栈顶元素就是表达式的运算结果。最后，栈顶元素就是表达式的运算结果。编译原理与技术编译原理与技术109.1 中间语言后缀式中间语言后
14、缀式u后缀形式扩充到其它的语言结构后缀形式扩充到其它的语言结构 对于赋值表达式对于赋值表达式V=E，如果把赋值号看作，如果把赋值号看作是二目算符，那么，它的后缀形式为是二目算符，那么，它的后缀形式为VE=，其中其中V和和E分别是分别是V和和E的后缀式。例如，的后缀式。例如，赋值语句赋值语句t=(a+b)/c (d e)的后缀形式为的后缀形式为t ab+c/de =赋值语句赋值语句ai=aj+m,k的后缀形式为的后缀形式为a i ajm+k,=无条件转移语句无条件转移语句goto L的后缀表达形式为的后缀表达形式为L GOTO，其中，其中GOTO看作是为单目运算符。看作是为单目运算符。编译原理与
15、技术编译原理与技术119.1 中间语言后缀式中间语言后缀式对于条件语句对于条件语句if E then S1 else S2，设，设E、S1和和S2分别是分别是E、S1和和S2的后缀形式，的后缀形式，L1对应语句对应语句S1的起点，的起点，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表示条件为真时转
16、移到的标号，表示条件为真时转移到的标号，10表示条件为假时表示条件为假时无条件转移到的标号处。无条件转移到的标号处。编译原理与技术编译原理与技术129.1 中间语言后缀式中间语言后缀式复合语句复合语句S1;S2的后缀形式可以简单的表示成的后缀形式可以简单的表示成S1S2，其中，其中S1和和S2分别时语句分别时语句S1和和S2的后缀形式。的后缀形式。但是，如果像但是，如果像C、Java、Pascal等语言允许在程序块等语言允许在程序块中增加声明语句，那么，就应改对程序块的标志中增加声明语句，那么，就应改对程序块的标志“”或或begin和和end分别引进相应的标志，如分别引进相应的标志，如BLOC
17、KBEGIN和和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 编译原理与技术编译原理与技术139.1 中间语言后缀式中间语言后缀式例例9.1 把下面的程序段写成后缀的形式把下面的程序段写成后缀的形式 int i;f
18、loat a,b,result;i=1;a=0;while(i=20)b=b+a;a=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编译原理与技术编译原理与技术149.1 中间语言后缀式中间语言后缀式例例9.2 表9.1描述了把赋值语句转换成后缀形式的语法制导的翻译规则。其中综合属性code表示符号的后缀形式，属性id.name表示标识符id的名字，num.lexva表示常数num的值；符号
19、“|”表示把语义代码连接起来（读作“捻接”或“并置”）。运算符的属性“op”给出具体的算符，如“+”、“*”或“and”。文法规则语义规则S id=ES.code:=id.name|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:=id.nameE numE.code:=num.lexval编译原理与技术编译原理与技术159.1 中间语言图形表示中间语言图形表示 a:=(b+c d)+c d的语法树如图的语法树如图9.2
20、(a)所示，它的后缀式为所示，它的后缀式为ab cd+cd+=。有向无环图有向无环图DAG也是一种中间表示，也是一种中间表示，和语法树相比，它以更紧凑的方式给和语法树相比，它以更紧凑的方式给出同样的信息，因为它把公共子表达出同样的信息，因为它把公共子表达式也标示出来。图式也标示出来。图9.2(b)的公共子表的公共子表达式达式c d不止一个父结点。不止一个父结点。:=a+c b d c d 语法树和分析树都是常见的图形中间代码，语法树省略了语法的终结符号，描述语法树和分析树都是常见的图形中间代码，语法树省略了语法的终结符号，描述了源程序在语义上的层次结构，是分析树的浓缩表示。语法树作为中间表示允
21、许了源程序在语义上的层次结构，是分析树的浓缩表示。语法树作为中间表示允许把翻译从分析中分离出来，形成先分析后翻译的方式。把翻译从分析中分离出来，形成先分析后翻译的方式。后缀式可以看作式语法树的一种线性表示，它是后序遍历或深度优先遍历语法得后缀式可以看作式语法树的一种线性表示，它是后序遍历或深度优先遍历语法得到结点的一个序列。到结点的一个序列。:=a+c d+b 图图9.2(b)9.2(a)编译原理与技术编译原理与技术169.1 中间语言图形表示中间语言图形表示例例9.3 表表9.2描述了把一个简化的描述了把一个简化的赋值语句改造成语法树的翻译规赋值语句改造成语法树的翻译规则，使用的是二义性文法
22、，假定则，使用的是二义性文法，假定算符的优先性和结合性遵循通常算符的优先性和结合性遵循通常的约定，二目运算的约定，二目运算+和和 是典型程是典型程序语言运算符号集合中选出的两序语言运算符号集合中选出的两个代表，其中个代表，其中mkunode(op,child)是构造单目运算结点的函数。是构造单目运算结点的函数。按照这个定义，可以把输入按照这个定义，可以把输入a:=(b+c d)+c d翻译成图翻译成图9.2(a)形形式的语法树。式的语法树。文法规则语义规则S id=ES.tree:=mknode(,mkleaf(id,id.name),E.tree)E E1+E2E.tree:=mknode(
23、+,E1.tree,E2.tree,)E E1 E2E.tree:=mknode(,E1.tree,E2.tree,)E E1E.tree:=mkunode(,E1.tree)E (E1)E.tree:=E1.treeE idE.tree:=mkleaf(id,id.name)E numF.tree:=mkleaf(num,num.lexval):=a+c b d c d 编译原理与技术编译原理与技术179.1 中间语言图形表示中间语言图形表示可以修改构造结点的函数，仍然使用这个语义规则构造出有向无环图。它首先检查是否已经存在一个结点和要构造的结点相同，如果是就返回这个已经存在的结点，否则就构
24、造并返回一个新的结点。例如，对mknode的修改如下：function mknode(op:OPKind,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构
25、造的DAG如图9.2(b)。编译原理与技术编译原理与技术189.1 中间语言字节代码中间语言字节代码字节代码通常就是运行它的机器模型或体系字节代码通常就是运行它的机器模型或体系结构的指令系统，与机器的符号指令或汇编结构的指令系统，与机器的符号指令或汇编语言类似，设计时考虑机器的字节特性以及语言类似，设计时考虑机器的字节特性以及存储方式、寻址方式、数据类型。存储方式、寻址方式、数据类型。使用字节代码作为中间语言最著名的例子是使用字节代码作为中间语言最著名的例子是在在1970末和末和1980初许多初许多Pascal语言编译器中的语言编译器中的P-code，它的形式如同一个假想的栈式机器，它的形式如
26、同一个假想的栈式机器（称为（称为P-机器）的汇编代码，从而省缺了寄机器）的汇编代码，从而省缺了寄存器。对于不同的实际机器需要为存器。对于不同的实际机器需要为P-code构构造一个解释程序，这样，就可以使造一个解释程序，这样，就可以使Pascal语言语言及其编译方便地移植到新的平台上。及其编译方便地移植到新的平台上。编译原理与技术编译原理与技术199.1 中间语言字节代码中间语言字节代码作为例子，我们考虑把一个表达式x:=2a+(b3)转换成P-code代码（分号后面是注释）：ldax;把x的地址存入栈内ldc2;加载常数2到临时栈loda;加载变量a的值到临时栈Mpi ;把栈顶的两个数据2和a
27、弹出，执行整数乘法运算，即2a，结果存放在栈内lodb;加载变量b的值到临时栈ldc3;加载常数3到临时栈Sbi ;把栈顶的两个数据b和3弹出，执行整数减法运算，即b3，结果存放在栈内Adi ;把栈顶的2a和b3结果弹出，完成整数加法，2a+(b3)，结果存放在栈顶Sto ;把栈顶的值存入栈顶下地址所指向的变量存储区域中，同时弹出这两个元素上述的计算顺序正好对应了表达式的后缀形式：x2ab3:=由于P-code被设计成是可以直接执行的，所以，它还隐含了一个特殊的运行时环，包括数据大小以及很多P-机器的特殊信息。编译原理与技术编译原理与技术209.1 中间语言字节代码中间语言字节代码我们看一下如
28、何使用我们看一下如何使用语义规则把例语义规则把例9.3语言语言生成生成P-code。我们用综合属性我们用综合属性pcode表示表示P-code串，用串，用“|”表示在表示在P-code串中插串中插入一个换行。入一个换行。文法规则语义规则S id=ES.pcode:=“lda”|id.name|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:=”lod”|id.nameE numE.pcode:
29、=”ldc”|num.lexval编译原理与技术编译原理与技术219.1 中间语言三地址代码中间语言三地址代码三地址语句是由下列形式的指令三地址语句是由下列形式的指令x:=y op z其中其中x、y和和z是名字、常数或编译其产生的临时变量，是名字、常数或编译其产生的临时变量，op表示运算表示运算符如加法、减法、乘法或逻辑算符。符如加法、减法、乘法或逻辑算符。它的含义是，对它的含义是，对y和和z的值施加的值施加op所代表的运算，结果存入所代表的运算，结果存入x表示的表示的地址。地址。源语言的表达式源语言的表达式2 a+(b 3)可以翻译成的三地址代码是：可以翻译成的三地址代码是：t1:=2 at
30、2:=b 3t3:=t1+t2其中其中t1、t2和和t3是编译器产生的临时变量。是编译器产生的临时变量。三地址码是语法树或DAG的一种线性表示，其中新增的临时变量名对应树的内部结点。2a+(b3)的分析树如图9.3所示+*2a b图9.3 2a+(b3)的语法树编译原理与技术编译原理与技术229.1 中间语言三地址代码中间语言三地址代码u把赋值语句翻译成三地把赋值语句翻译成三地址代码的语义规则址代码的语义规则综合属性综合属性E.place表示存表示存放放E值的名字，值的名字，E.code表示三地址指令，表示三地址指令，函数函数gencode(p,:=,E.place)表示生成三地址表示生成三地
31、址语句语句p:=E.place。函数函数newtemp在每次调在每次调用的时候，产生不同的用的时候，产生不同的临时变量名。临时变量名。文法规则语义规则S id=ES.code:=E.code|gencode(id.name,:=,E.place)E E1+E2E.place:=newtemp;E.code:=E1.tacode|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
32、 E1E.place:=newtemp;E.code:=E1.code|gencode(E.place,:=,uminus,E1.place)E (E1)E.place:=newtemp;E.tacode:=E1.tacodeE idE.place:=id.name;E.code:=E numE.code:=num.lexval编译原理与技术编译原理与技术239.1 中间语言三地址代码中间语言三地址代码 下面是本书用到的三地址指令下面是本书用到的三地址指令形式为形式为x:=y op z的赋值语句，其中的赋值语句，其中op是二目算术或逻辑运算。是二目算术或逻辑运算。形式为形式为x:=op z的赋
33、值语句，其中的赋值语句，其中op是单目算术或逻辑运算。是单目算术或逻辑运算。形式为形式为x:=y的赋值语句，它把的赋值语句，它把y的值赋给的值赋给x。形式为形式为goto L的无条件转移语句，即下一条将被执行的语句是带标号的无条件转移语句，即下一条将被执行的语句是带标号L的三的三地址语句。地址语句。形式为形式为if x relop y goto L或或if b goto L的条件转移语句，第一中语句对的条件转移语句，第一中语句对x 和和 y施加关系运算施加关系运算relop（如（如），如果关系成立则执行标号为），如果关系成立则执行标号为L的三的三地址语句，否则执行后续语句；第二种形式中，地址语
34、句，否则执行后续语句；第二种形式中，b为布尔变量或常量，若为布尔变量或常量，若b为为真，则执行标号为真，则执行标号为L的语句，否则执行后续语句。的语句，否则执行后续语句。形式为形式为param x和和call p,n表示过程调用语句，其中表示过程调用语句，其中x表示参数，表示参数，n表示参数表示参数个数。源程序的过程调用语句个数。源程序的过程调用语句p(x1,x2,.,xn)通常生成如下的三地址码：通常生成如下的三地址码：param x1.param xncall p,n编译原理与技术编译原理与技术249.1 中间语言三地址代码中间语言三地址代码返回语句返回语句return x表示过程返回值表
35、示过程返回值x，其中，其中x也可以不出现。也可以不出现。形式为形式为x:=yi和和xi:=y的索引赋值，第一条语句把相对于地的索引赋值，第一条语句把相对于地址址y后面第后面第i的单元的值赋给的单元的值赋给x；第而条语句把；第而条语句把y的值赋给相对于的值赋给相对于地址地址x后面第后面第i的单元里。的单元里。形式为形式为x:=&y，x:=*y 和和*x:=y的地址指针赋值。第一个语句的地址指针赋值。第一个语句把把y的存储单元地址赋给的存储单元地址赋给x，假定，假定y是一个名字或临时变量，代是一个名字或临时变量，代表一个具有左值的表达式，如表一个具有左值的表达式，如Ai,j；而；而x是指针变量或临
36、时变是指针变量或临时变量，即量，即x的右值是某个对象的值。第二条语句是把的右值是某个对象的值。第二条语句是把y的存储单元的存储单元里的值赋给里的值赋给x，其中，其中y是指针变量或右值为地址的临时变量。第是指针变量或右值为地址的临时变量。第三条语句把三条语句把x所指向额对象的右值赋给所指向额对象的右值赋给y的左值。的左值。形式为形式为read x的的write x输入和输出语句，它们只有一个地址。输入和输出语句，它们只有一个地址。没有地址的停机语句没有地址的停机语句halt。编译原理与技术编译原理与技术259.1 中间语言三地址指令的四元式实现中间语言三地址指令的四元式实现三地址指令操作符运算数
37、1运算数2结果书写形式x:=y op zopyzx(op,y,z,x)x:=op 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(,y,x)*x:=y:=yx(:=,
38、y,x)read xreadx(read,x)write xwritex(write,x)halthalt(halt,)编译原理与技术编译原理与技术269.2 声明语句的翻译声明语句的翻译 u过程中的声明过程中的声明 例如，对于一个例如，对于一个C+的声明序列：的声明序列：int index;double sum;char token;如果该声明在内存中可以得到的首地址是如果该声明在内存中可以得到的首地址是1000，那么局部名，那么局部名字字x的地址都可以按照下列公式计算：的地址都可以按照下列公式计算：index的地址是的地址是 1000sum的地址是的地址是 1000+index的字节宽度的
39、字节宽度10041000+4token的地址是的地址是 1004+sum的字节宽度的字节宽度1012100+4+8实际上，为声明语句中的名字分配存储的主要问题就是计算实际上，为声明语句中的名字分配存储的主要问题就是计算每个名字的相对地址，即相对于基址的偏移，再加上为该声每个名字的相对地址，即相对于基址的偏移，再加上为该声明分配的基址（例如过程活动记录的首址），就可以在存储明分配的基址（例如过程活动记录的首址），就可以在存储器中访问到每个名字。器中访问到每个名字。编译原理与技术编译原理与技术279.2 声明语句的翻译声明语句的翻译非终结符非终结符P产生一系列形如产生一系列形如“T id”的声的声
40、明语句。明语句。全局变量全局变量offset记录下一个可用的相对地记录下一个可用的相对地址初始化址初始化offset为为0。以后每次遇到一个。以后每次遇到一个新的名字，将该名字连同类型和当前的新的名字，将该名字连同类型和当前的offset填入符号表，然后使填入符号表，然后使offset增加该名增加该名字所表示的数据的宽度。字所表示的数据的宽度。过程过程enter(name,type,offset)用来把名字用来把名字为为name的标识符填入符号表。的标识符填入符号表。综合属性综合属性type和和width分别表示非终结符分别表示非终结符T的类型和宽度。属性的类型和宽度。属性type的取值范围是
41、的取值范围是基本类型基本类型integer和和real以及应用类型构造以及应用类型构造器器pointer和和array得到的结构类型。得到的结构类型。假设整数的宽度是假设整数的宽度是4，实数的宽度是，实数的宽度是8，指针类型的宽度是指针类型的宽度是4，数组所占用的存储，数组所占用的存储单元个数是数组元素的个数乘以基类型单元个数是数组元素的个数乘以基类型元素的宽度。元素的宽度。文法规则语义动作P Doffset:=0D D1;D2D id:Tenter(id.name,T.type,offset);offset:=offset+T.widthT integerT.type:=integer;T.
42、width:=4T realT.type:=real;T.width:=8T array num of T1T.type:=array(num.val,T1.type);T.width:=num.val*T1.widthT T1T.type:=pointer(T1.type);T.width:=4编译原理与技术编译原理与技术289.2 声明语句的翻译声明语句的翻译u记录作用域信息记录作用域信息 考虑像考虑像Pascal和和Ada这样允许过程嵌套的语言，主要讨论如何保存声明这样允许过程嵌套的语言，主要讨论如何保存声明的作用域信息（的作用域信息（6.4）。所讨论的文法如下：）。所讨论的文法如下：P
43、 D SD D;D|id:T|proc id;D;S第一条产生式提供程序的规则，在声明第一条产生式提供程序的规则，在声明D后面跟随语句序列后面跟随语句序列S。声明语。声明语句允许嵌套地声明过程。为了简化讨论的问题，我们不考虑递归调用句允许嵌套地声明过程。为了简化讨论的问题，我们不考虑递归调用的过程，也不考虑过程的参数说明，这是因为参数可以类似于表的过程，也不考虑过程的参数说明，这是因为参数可以类似于表9.6的的局部变量的处理技术。局部变量的处理技术。在处理嵌套过程时为每个过程都建立一张独立的符号表，每个符号表在处理嵌套过程时为每个过程都建立一张独立的符号表，每个符号表都有自己的符号表指针都有自
44、己的符号表指针tableptr、基址、基址base和自己的和自己的offset。这些符号表。这些符号表可以一边扫描源程序一边建立并且完成内存分配。可以一边扫描源程序一边建立并且完成内存分配。每遇到每遇到D proc id;D1;S时，就创建一张新的符号表，把时，就创建一张新的符号表，把D1中的所有中的所有说明都添在该符号表；用一个指针记录包含说明都添在该符号表；用一个指针记录包含D1的最近的外围过程的最近的外围过程D的的符号表，符号表，id也是其中的一个局部名字。在最近的外围过程也是其中的一个局部名字。在最近的外围过程D的符号表中的符号表中对于每个直接嵌入其中的过程，也都有一个指向它们符号表指
45、针。对于每个直接嵌入其中的过程，也都有一个指向它们符号表指针。编译原理与技术编译原理与技术299.2 声明语句的翻译声明语句的翻译表表9.7给出了多趟扫描含有嵌套过程的语法制导翻译规则，它使用了两个给出了多趟扫描含有嵌套过程的语法制导翻译规则，它使用了两个数据结构：数据结构：l一个保存各外层过程的符号表指针的指针栈一个保存各外层过程的符号表指针的指针栈tblptr，一个对应的存放外层过程，一个对应的存放外层过程相对地址的偏移栈相对地址的偏移栈offset。指针栈。指针栈tblptr的栈顶的栈顶top(tblptr)总是指向当前层的符总是指向当前层的符号表；偏移栈号表；偏移栈offset的栈顶保
46、存了当前层已经处理的声明的偏移之和。的栈顶保存了当前层已经处理的声明的偏移之和。整个翻译模式同时使用了下列操作：整个翻译模式同时使用了下列操作：lSymbolTable*mktable(SymbolTable*previous,integer base)创建一张新创建一张新的符号表，填入基址，把参数指针的符号表，填入基址，把参数指针previous放在该表的表头，表示指向已经放在该表的表头，表示指向已经创建好的一个符号表，比如刚好包围嵌入过程的符号表；返回指向这张新表的创建好的一个符号表，比如刚好包围嵌入过程的符号表；返回指向这张新表的指针。符号表的信息还可以包含局部变量所需要的存储单元个数等
47、。指针。符号表的信息还可以包含局部变量所需要的存储单元个数等。lvoid enter(SymbolTable*table,String name,DType type,Integer offset)在指针在指针table指向的符号表中为变量名指向的符号表中为变量名name建立一个新项，类型是建立一个新项，类型是type，在该，在该表中的相对地址是表中的相对地址是offset。lvoid addwidth(SymbolTable*table,Integer width)把符号表把符号表table的所有项的所有项的累加宽度记录在该表的首部。的累加宽度记录在该表的首部。lvoid enterproc
48、(SymbolTable*table,String name,SymbolTable*newtable)在在table指向的符号表中为过程名指向的符号表中为过程名name建立一个新项，指针建立一个新项，指针newtable指向它的符号表。指向它的符号表。编译原理与技术编译原理与技术309.2 声明语句的翻译声明语句的翻译对于P D S，首先要建立一张空的符号表，动作要在D S之前完成。为了使整个动作都在文法产生式的末尾，我们采取了7.3.3.3的技术，引入一个非终结符M和产生式，以消除嵌入在产生式中的语义动作。M的语义动作是初始化外层符号表的指针栈tblptr和偏移栈offset：最外层过程没
49、有包围的过程了，所以指针为空null，相对地址和基址都为0。这样，P M D S的语义动作就是把当前（栈顶）符号表top(tblptr)的所有项的累加宽度记录在该表的首部，表示该过程的局部变量、过程等声明所需要的总的存储单元数；之后，退掉指针栈tblptr和偏移栈offset的栈顶。对嵌入过程说明D proc id;D;S做了类似的语法处理，改成D proc id;N D1;S。首先，在扫描到嵌入的过程D1之前，需要为它建立一个空的符号表，让它指向直接外围过程的符号表，初始化这个新过程的偏移为0，它的基址就是直接外围过程当前所有条目（变量、过程）宽度的总和。这些都由对应N 的语义动作完成。然后
50、，执行D proc id;N D1;S右部的语义动作：首先把D1产生的所有声明的宽度存入它的符号表内（此时放在栈顶的都是有关D1的值），退掉指针栈tblptr和偏移栈offset的栈顶表示结束嵌入过程的处理，继续处理外层过程的声明：把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;
