编译原理 第五章语法制导翻译和中间 代码生成 上海交通大学 张冬茉 Email:Zhang-dm@cssjtu.edu.cn 2004年4月
1 编译原理 第五章 语法制导翻译和中间 代码生成 上海交通大学 张冬茉 Email:zhang-dm@cs.sjtu.edu.cn 2004年4月
本章目的 经过词法分析、语法分析后,源程 序在静态结构上的正确性得到了保证, 编译程序接着需作静态语义检查以及翻 译,真正实现不同程序语言的代码间的 等价变换
2 本章目的 经过词法分析、语法分析后，源程 序在静态结构上的正确性得到了保证， 编译程序接着需作静态语义检查以及翻 译，真正实现不同程序语言的代码间的 等价变换
第五章语法制导翻译称 中间代码生成 s5.1翻译概述 静态语义检查 如同词法分析,语法分析同时进行着词法检查、语法 检査一样。在语义分析时,必然要进行语义检查。动 态语义检查需要生成相应的目标代码,在运行时刻进 行,静态语义检查在编译时完成它,则涉及: 3
3 第五章 语法制导翻译和 中间代码生成 §5.1翻译概述 一、静态语义检查 如同词法分析，语法分析同时进行着词法检查、语法 检查一样。在语义分析时，必然要进行语义检查。动 态语义检查需要生成相应的目标代码，在运行时刻进 行，静态语义检查在编译时完成它，则涉及：
(1)类型检查,如参数运算的操作数的类型应相容 (2)控制流检查,以保证控制语句有合法的转向点, 如C语言中的 break语句,需寻找包含它的最小的 switch、whil或for语句,方可找到转向点,否则 出错。 (3)有关名字的匹配检查。可以对某些程序段命名, 该名字出现在程序段的开始和结束处,如同语句括 号一般,应检查它们的配对。 (4)一致性检查,如在相同作用域中标识符只能说 明一次,case语句的标号不能相同,枚举类型的元 素不能重复等。 4
4 (1) 类型检查，如参数运算的操作数的类型应相容。 (2) 控制流检查，以保证控制语句有合法的转向点， 如C语言中的break语句，需寻找包含它的最小的 switch、while或for语句，方可找到转向点，否则 出错。 (3) 有关名字的匹配检查。可以对某些程序段命名， 该名字出现在程序段的开始和结束处，如同语句括 号一般，应检查它们的配对。 (4) 一致性检查，如在相同作用域中标识符只能说 明一次，case语句的标号不能相同，枚举类型的元 素不能重复等
、语法制导翻译的例子。 讨论翻译前,先看一个例子: 图5.1展示了文法(4.2)的一个翻译方案 E→→E+T{ print“1”} E→→T{ print“2”} T→TF{ print“3”} T→F{ print“4”} F→→(E){ print“5”} { print“6”} 图51文法(42)的一个翻译方案 其实是在文法(42)的每个产生式后配了一个由{}扩起 来的语义子程序,不难证明终结符串(id+id)*id是文 法(4.2)的一个合法句子,它的分析树如图52所示:
5 二、语法制导翻译的例子。 讨论翻译前，先看一个例子： 图5.1 展示了文法（4.2）的一个翻译方案 E→E+T {print “1”} E→T {print “2”} T→T*F {print “3”} T→F {print “4”} F→(E) {print “5”} F→I {print “6”} 图5.1 文法(4.2)的一个翻译方案 其实是在文法（4.2）的每个产生式后配了一个由{ }扩起 来的语义子程序，不难证明终结符串（id+id）*id 是文 法（4.2）的一个合法句子，它的分析树如图5.2所示：
图52(计+i)*的分析树 6
6 E T T * F F ( E ) E + T T F F i i i 图5.2 (i+i)*i的分析树
按照这个句子向文法开始符E的归约次序,且 每当归约时调用该句柄的产生式所对应的语义子程 序,便可得到相应的输出串:64264154632。 这个例子表明:输入源语言的符号串(计i)输出目 标语言的数字串。这自然是一种变幻,而变换的规 则时每当(按句柄)归约时调用相应的语言子程序。 无疑这个例子是翻译的一个十分简单的模型。如果 将数字串这种目标代码定义为所需目标语言的目标 代码,如果每个产生式对应的语言子程序中的一系 列语义动作被描述成实现这种转换的动作的序列, 并最终生成所需目标语言的目标代码,那么作为程 序变换的翻译也就迎刃而解了
7 按照这个句子向文法开始符E的归约次序，且 每当归约时调用该句柄的产生式所对应的语义子程 序，便可得到相应的输出串： 64264154632。 这个例子表明：输入源语言的符号串(i+i)*i,输出目 标语言的数字串。这自然是一种变幻，而变换的规 则时每当（按句柄）归约时调用相应的语言子程序。 无疑这个例子是翻译的一个十分简单的模型。如果 将数字串这种目标代码定义为所需目标语言的目标 代码，如果每个产生式对应的语言子程序中的一系 列语义动作被描述成实现这种转换的动作的序列， 并最终生成所需目标语言的目标代码，那么作为程 序变换的翻译也就迎刃而解了
三、翻译要解决的问题 翻译是将源语言的程序等价变换为目标语言的 程序,于是有三个问题需解决 (一)、翻译成什么样的目标语言的代码? (二)、什么时候实现这种变换,即翻译? (三)、如何实现这种翻译?
8 三、翻译要解决的问题 翻译是将源语言的程序等价变换为目标语言的 程序，于是有三个问题需解决： （一）、翻译成什么样的目标语言的代码？ （二）、什么时候实现这种变换，即翻译？ （三）、如何实现这种翻译？
(1)如第一章引论中提到的那样,我们将源语言 程序翻译成中间语言的程序,中间语言与机 器无关,而语句颗粒度又与机器语言相当, 于是带来了诸多好处: ①编译逻辑结构简单明确,与机器相关的工 作集中到目标代码生成阶段,难度和工作量 下降。 ②便于移植和维护。 ③利于优化。代码优化将分成与机器无关的 中间代码优化及与机器相关的目标代码优化 两个阶段,是优化更有效。§52将讨论中间 语言
9 (1)如第一章引论中提到的那样，我们将源语言 程序翻译成中间语言的程序，中间语言与机 器无关，而语句颗粒度又与机器语言相当， 于是带来了诸多好处： ①编译逻辑结构简单明确，与机器相关的工 作集中到目标代码生成阶段，难度和工作量 下降。 ②便于移植和维护。 ③利于优化。代码优化将分成与机器无关的 中间代码优化及与机器相关的目标代码优化 两个阶段，是优化更有效。§5.2 将讨论中间 语言
(2)如例子所示,如果作为句柄所对应的产生式, 都配有一个相应的翻译子程序,则每当按句柄归 约时,就调用相应的翻译子程序(语义子程序) 完成局部的翻译,则一个句子,一段代码,按它 们的归约次序,将所有翻译子程序一次执行,就 完成了这个句子,这段代码的翻译。这种翻译与 语法分析紧密相关,称之为语法制导翻译:每当 归约时,调用相应的语义子程序,这就是翻译的 时机。 10
10 (2) 如例子所示，如果作为句柄所对应的产生式， 都配有一个相应的翻译子程序，则每当按句柄归 约时，就调用相应的翻译子程序（语义子程序） 完成局部的翻译，则一个句子，一段代码，按它 们的归约次序，将所有翻译子程序一次执行，就 完成了这个句子，这段代码的翻译。这种翻译与 语法分析紧密相关，称之为语法制导翻译：每当 归约时，调用相应的语义子程序，这就是翻译的 时机