编译原理清华大学导论

1、课程简介课程简介 总学时：总学时： 72学时学时 4.5学分学分 课堂教学：课堂教学： 52学时学时 ； 课内实验：课内实验： 8学时学时课内实践：课内实践： 12学时学时 主讲：林泓主讲：林泓课程内容课程内容 v介绍编译器构造的一般原理和基本实现方法介绍编译器构造的一般原理和基本实现方法v理论知识：形式语言和自动机理论、语法制导翻译的定理论知识：形式语言和自动机理论、语法制导翻译的定义和属性文法等义和属性文法等v形式化描述技术形式化描述技术v对编译原理和技术的宏观理解，注意力无需分散到枝节对编译原理和技术的宏观理解，注意力无需分散到枝节算法，无需偏向于某种源语言或目标机器算法，无需偏向于某种

2、源语言或目标机器学习的意义学习的意义 v 对编程语言的设计和实现有深刻的理解，对和编程语言对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用。一个奠基的作用。v 从软件工程看，编译器是一个很好的实例，所介绍的概从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。念和技术能应用到一般的软件设计之中。v 大多数程序员同时是简单语言的设计者，有助于提高对大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平。这些语言的设计水平。v 在软件逆向工程、软

3、件的设计方法、程序理解和软件安在软件逆向工程、软件的设计方法、程序理解和软件安全等方面有着广泛的应用。全等方面有着广泛的应用。课程要求课程要求v讲课进展较快，平时要复习并加深理解。讲课进展较快，平时要复习并加深理解。v作业较多，要求独立完成。作业较多，要求独立完成。v实验和课内实践，每次验收检查。实验和课内实践，每次验收检查。v学期总评成绩学期总评成绩 = = 考试成绩考试成绩60% + 60% + 平时成绩平时成绩40%40% 平时成绩平时成绩40% = 40% = 作业实验考勤作业实验考勤30% + 30% + 课内实践课内实践10%10% 编译系统是现代计算机系统的基本组成之一，编译程序

4、编译系统是现代计算机系统的基本组成之一，编译程序构造的基本原理和技术不仅应用于编译程序的设计，也广泛构造的基本原理和技术不仅应用于编译程序的设计，也广泛应用于一般软件的设计和实现。本课程是计算机类专业的一应用于一般软件的设计和实现。本课程是计算机类专业的一门重要的核心专业课。门重要的核心专业课。先修课程：先修课程： 高级程序设计语言、汇编语言、高级程序设计语言、汇编语言、 离散数学、数据结构离散数学、数据结构学习要求：学习要求：不旷课，上课认真听讲，课上保持安静；不旷课，上课认真听讲，课上保持安静； 课后即时复习，认真完成作业；课后即时复习，认真完成作业； 实验课内实践程序独立设计及实现实验课

5、内实践程序独立设计及实现 。学习目标学习目标 通过本课程的学习，旨在使同学们掌握程序设计语言的形通过本课程的学习，旨在使同学们掌握程序设计语言的形式化描述和编译的基本理论、原理和技术，并对编译程序有较式化描述和编译的基本理论、原理和技术，并对编译程序有较为具体的认识。使同学们能运用所学过的基本知识、着手开发为具体的认识。使同学们能运用所学过的基本知识、着手开发系统程序，为今后的工作（理论研究和技术开发）打下基础。系统程序，为今后的工作（理论研究和技术开发）打下基础。具体为：具体为：（1 1）掌握编译程序基本结构及构造的基本原理和技术；）掌握编译程序基本结构及构造的基本原理和技术；（2 2）掌握

6、文法、形式语言及自动机的基本概念和在编译程序构造中的应用；）掌握文法、形式语言及自动机的基本概念和在编译程序构造中的应用；（3 3）掌握典型的几种语法分析方法的基本原理和实现方法；）掌握典型的几种语法分析方法的基本原理和实现方法；（4 4）掌握语法制导方法在语义分析中的应用和中间代码生成方法；）掌握语法制导方法在语义分析中的应用和中间代码生成方法；（5 5）掌握存储分配的基本思想和实现方法；）掌握存储分配的基本思想和实现方法；（6 6）掌握代码优化及代码生成的方法。）掌握代码优化及代码生成的方法。学习向导学习向导 编译原理编译原理课程是理论性较强的课程。其特点是概念多、课程是理论性较强的课程。

7、其特点是概念多、内容抽象。尤其是文法、形式语言及自动机的概念是计算机专内容抽象。尤其是文法、形式语言及自动机的概念是计算机专业的理论学习和研究的基础。掌握这些基本理论、原理和技术，业的理论学习和研究的基础。掌握这些基本理论、原理和技术，对于培养同学们对事物的抽象能力以及分析问题和解决问题的对于培养同学们对事物的抽象能力以及分析问题和解决问题的能力大有帮助。能力大有帮助。 编译原理与方法对于深刻理解程序设计语言、深入了解程编译原理与方法对于深刻理解程序设计语言、深入了解程序在计算机中的运行机制、掌握程序设计语言的翻译方法起到序在计算机中的运行机制、掌握程序设计语言的翻译方法起到不可替代的作用。同

8、时不可替代的作用。同时编译原理编译原理课程也是实践性很强的课课程也是实践性很强的课程，要求同学们在基本掌握了编译理论和技术的基础上，综合程，要求同学们在基本掌握了编译理论和技术的基础上，综合应用先修课程及本课程的知识，完成课程的实验和课程设计。应用先修课程及本课程的知识，完成课程的实验和课程设计。参考资料参考资料 教材：教材：11 编译原理编译原理（第三版）（第三版） 主编：王生原、董渊、张素琴、吕映芝主编：王生原、董渊、张素琴、吕映芝 出版社：清华大学出版社出版社：清华大学出版社 出版时间：出版时间：20152015年年参考书：参考书：11编译原理编译原理 主编：何炎祥主编：何炎祥 出版社：

9、华中理工大学出版社出版社：华中理工大学出版社 出版时间：出版时间：20102010年年1010月月22 程序设计语言编译原理（第程序设计语言编译原理（第3 3版）版） 主编：陈火旺、刘春林、谭庆平、赵克佳、刘越主编：陈火旺、刘春林、谭庆平、赵克佳、刘越 出版社：国防工业出版社出版社：国防工业出版社 出版时间：出版时间：2001220012年年8 8月月33编译原理技术与工具（英文版）编译原理技术与工具（英文版） Compilers:Principles,Techniques,and Compilers:Principles,Techniques,and ToolsTools 主编：主编：Alf

10、redAlfred V.Aho,RaviV.Aho,Ravi Sethi,JeffreySethi,Jeffrey D.UllmanD.Ullman 出版社：人民邮电出版社出版社：人民邮电出版社 出版时间：出版时间：20022002年年2 2月月 参考资料参考资料44编译原理与技术编译原理与技术（第二版）（第二版） 主编：陈意云主编：陈意云 出版社：中国科学技术大学出版社出版社：中国科学技术大学出版社 出版时间：出版时间：20022002年年1 1月月55编译程序构造原理和实现技术编译程序构造原理和实现技术 主编：金成植主编：金成植 出版社：高等教育出版社出版社：高等教育出版社 出版时间：出版

11、时间：20022002年年7 7月月66编译原理及编译程序构造编译原理及编译程序构造 主编：高仲仪、金茂忠主编：高仲仪、金茂忠 出版社：北京航空航天大学出版社出版社：北京航空航天大学出版社 出版时间：出版时间：20012001年年3 3月月77编译原理编译原理( (第第2 2版版) ) 主编：蒋立源主编：蒋立源, , 康慕宁康慕宁 出版社：西北工业大学出版社出版社：西北工业大学出版社 出版时间：出版时间：19991999年年4 4月月88编译原理编译原理 主编：张幸儿主编：张幸儿 出版社：科学出版社出版社：科学出版社 出版时间：出版时间：19991999年年4 4月月 第第1 1章章 引论引论

12、 本章主要内容：本章主要内容： v什么是编译程序什么是编译程序v编译过程和编译程序的结构编译过程和编译程序的结构v为什么要学习编译程序为什么要学习编译程序 本章的重点：本章的重点： 本章没有难以理解的内容本章没有难以理解的内容,主要主要是对编译程序的功能和结构做一综是对编译程序的功能和结构做一综合描述合描述1.1 1.1 什么叫编译程序什么叫编译程序 使用过现代计算机的人都知道，多数用户是应用高级语言使用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。现代计算机系统一般都含有不止来实现他们所需要的计算的。现代计算机系统一般都含有不止一个的高级语言编译程序，对有些高级语言

13、甚至配置了几个不一个的高级语言编译程序，对有些高级语言甚至配置了几个不同性能的编译程序，供用户按不同需要进行选择。同性能的编译程序，供用户按不同需要进行选择。 要在计算机上执行用高级语言（或汇编语言）编写的程序，要在计算机上执行用高级语言（或汇编语言）编写的程序，必须通过特定的途径来进行，也就是要通过翻译程序把用高级必须通过特定的途径来进行，也就是要通过翻译程序把用高级语言（或汇编语言）编写的程序语言（或汇编语言）编写的程序翻译翻译成为机器语言构成的程序，成为机器语言构成的程序，计算机才能执行。计算机才能执行。 在计算机上执行一个高级语言程序一般要分为两步：在计算机上执行一个高级语言程序一般要

14、分为两步： 第一步，用一个编译程序把高级语言翻译成机器语言程序；第一步，用一个编译程序把高级语言翻译成机器语言程序； 第二步，运行所得的机器语言程序求得计算结果。第二步，运行所得的机器语言程序求得计算结果。 （1 1）翻译程序（）翻译程序（TranslatorTranslator） 通常所说的翻译程序是指这样的一个程序，它能够把某通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序（称为一种语言程序（称为源语言程序或源程序源语言程序或源程序）转换成另一种语）转换成另一种语言程序（称为言程序（称为目标语言程序或目标程序目标语言程序或目标程序），而后者与前者在），而后者与前者在逻辑上是等价

15、的。逻辑上是等价的。 源程序源程序（source program）翻译程序翻译程序目标程序目标程序(target program)输入输入输出输出图图1.1 翻译程序翻译程序 翻译程序根据所处理的对象和实现的途径不同又分为：翻译程序根据所处理的对象和实现的途径不同又分为：汇编程序、编译程序和解释程序。汇编程序、编译程序和解释程序。 （2 2）. . 汇编程序（汇编程序（AssemblerAssembler） 如果源语言是某种汇编语言，而目标语言是某种计算机的机如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就称为汇编程序。器语言，这样的一个翻译程序就称为汇编程序。

16、源程序源程序（汇编语言）（汇编语言）翻译程序翻译程序（汇编程序）（汇编程序）目标程序目标程序（机器语言）（机器语言）输入输入输出输出图图1.2 汇编程序汇编程序（3 3）. . 编译程序（编译程序（CompilerCompiler） 如果源语言是某种高级语言，而目标语言是某种低级语言如果源语言是某种高级语言，而目标语言是某种低级语言（汇编语言或机器语言），这样的一个翻译程序就称为编译程（汇编语言或机器语言），这样的一个翻译程序就称为编译程序。序。 源程序源程序（高级语言）（高级语言）翻译程序翻译程序（编译程序）（编译程序）目标程序目标程序（低级语言）（低级语言）图图1.3 编译程序编译程序输入

17、输入输出输出（4 4）. . 解释程序（解释程序（Interpreter） 这是另外一种类型的翻译程序，在翻译过程它按照高级语这是另外一种类型的翻译程序，在翻译过程它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的（解释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。解释程序。 源程序源程序（高级语言）（高级语言）翻译程序翻译程序（解释程序）（解释程序）计

18、算结果计算结果输入输入输出输出图图1.4 解释程序解释程序初始数据初始数据根据不同的用途，编译程序可进一步分类根据不同的用途，编译程序可进一步分类:（1）诊断编译程序（）诊断编译程序（Diagnostic Compiler）：）： 专门用于帮助程序开发和调试的编译程序。专门用于帮助程序开发和调试的编译程序。（2）优化编译程序（）优化编译程序（Optimizing Compiler）：）： 着重于提高目标代码效率的编译程序。着重于提高目标代码效率的编译程序。（3）交叉编译程序）交叉编译程序(Cross Compiler)： 如果一个编译程序产生不同于其宿主机的机器代码。如果一个编译程序产生不同于

19、其宿主机的机器代码。（4）可变目标编译程序（可变目标编译程序（Retargetable Compiler）：）： 不需重写编译程序中与机器无关的部分就能改变目标机。不需重写编译程序中与机器无关的部分就能改变目标机。 宿主机宿主机（host machine）：）：运行编译程序的计算机。运行编译程序的计算机。目标机目标机(object machine) ：运行编译程序所产生目标代码的计算机。运行编译程序所产生目标代码的计算机。1.2 1.2 编译过程概述编译过程概述 编译程序的工作，从输入源程序开始到输出目标程序为止的编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。整个

20、过程，是非常复杂的。一段英文翻译为中文时，通常需经下列步骤：一段英文翻译为中文时，通常需经下列步骤：（1）识别出句子中的一个个单词；）识别出句子中的一个个单词；（2）分析句子的语法结构；）分析句子的语法结构；（3）根据句子的含义进行初步翻译；）根据句子的含义进行初步翻译；（4）对译文进行修饰；）对译文进行修饰；（5）写出最后的译文。）写出最后的译文。 类似地，编译程序的工作过程一般也可以划分为五个阶段：类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。代码生成。 第一阶段第一

21、阶段: : 词法分析词法分析 （Lexical analysisLexical analysis）词法分析的任务：词法分析的任务： 输入源程序，对构成源程序的字符串进行扫描和分解，输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。识别出一个个的单词。 保留字（保留字（beginbegin、endend、ifif、forfor、whilewhile等）、等）、 标识符（标识符（x1x1、s s等变量名）、等变量名）、 常数常数(3.14(3.14、100100等等) )、 算符（算符（+ +、- -、andand、oror等）、等）、 界符（标点符号、左右括号等）。界符（标点符

22、号、左右括号等）。 例如，对于例如，对于PascalPascal的循环语句：的循环语句： for I for I：1 to 100 do1 to 100 do词法分析的结果是识别出如下的单词符号：词法分析的结果是识别出如下的单词符号： 保留字保留字 forfor 标识符标识符 I I 赋值号：赋值号： ：= = 整常数整常数 1 1 保留字保留字 toto 整常数整常数 100100 保留字保留字 dodo 单词符号是语言的基本组成成分，是人们理单词符号是语言的基本组成成分，是人们理解和编写程序的基本要素。识别和理解这些要素解和编写程序的基本要素。识别和理解这些要素无疑也是翻译的基础。无疑也是

23、翻译的基础。 如同将英文翻译成中文的情形一样，如果你如同将英文翻译成中文的情形一样，如果你对英语单词不理解，那就谈不上进行正确的翻译。对英语单词不理解，那就谈不上进行正确的翻译。 在词法分析阶段的工作中所依循的是语言在词法分析阶段的工作中所依循的是语言的词法规则（或称构词规则）。描述词法规则的的词法规则（或称构词规则）。描述词法规则的有效工具是有效工具是正规式和有限自动机。正规式和有限自动机。第二阶段，语法分析第二阶段，语法分析(Syntax Analysis)(Syntax Analysis) 语法分析的任务是：语法分析的任务是： 在词法分析的基础上，根据语言的语法规则，把单词符号在词法分析

24、的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如串分解成各类语法单位（语法范畴），如“短语短语”、“子句子句”、“句子句子”（“语句语句”）、）、“程序段程序段”和和“程序程序”等。等。通过语法通过语法分析，确定整个输入串是否构成语法上正确的分析，确定整个输入串是否构成语法上正确的“程序程序”。 语法分析所依循的是语言的语法分析所依循的是语言的语法规则语法规则。语法规则通常用上。语法规则通常用上下文无关文法描述。下文无关文法描述。 词法分析是一种线性分析，而语法分析是一种层次结构分析。词法分析是一种线性分析，而语法分析是一种层次结构分析。例如，在很多语言中，符号串例

25、如，在很多语言中，符号串 z：=X十十0.618*Y代表一个代表一个“赋值语句赋值语句”，而其中的，而其中的 X0.618*Y代表一个代表一个“算术算术表达式表达式”。因而，语法分析的任务就是识别。因而，语法分析的任务就是识别 X0.618*Y为算术为算术表达式，同时，识别上述整个符号串属于赋值语句这个范畴。表达式，同时，识别上述整个符号串属于赋值语句这个范畴。 第三阶段，语义分析与中间代码产生第三阶段，语义分析与中间代码产生(Semantic (Semantic Analysis and Intermediate Generator)Analysis and Intermediate Gen

26、erator) 此阶段的任务是：此阶段的任务是： 对语法分析所识别出的各类语法范畴，分析其含义，并进对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。行初步翻译（产生中间代码）。 中间代码中间代码是一种独立于具体硬件的记号系统。是一种独立于具体硬件的记号系统。 常用的中间代码：三地址码，四元式，三元式、间接三常用的中间代码：三地址码，四元式，三元式、间接三元式、逆波兰式，树形表示等。元式、逆波兰式，树形表示等。 所谓所谓“中间代码中间代码”是一种含义明确、便于处理的记号系统，它通常是一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算

27、机的指令形式有某种独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。 四元式的形式是：四元式的形式是： （ 算符算符 左操作数左操作数 右操作数右操作数 结果）结果） 它的意义是：对它的意义是：对“左、右操作数左、右操作数”进行某种运算（由进行某种运算（由“算符算符”指明），把运算所得的值作为指明），把运算所得的值作为“结果结果”保留下来。保留下来。 例如例如 赋值语句赋值语句 Z：（：（X0.418）*YW 翻译为四元式序列：翻译为四元式序列： 序号序号 算

28、符算符 左操作数左操作数 右操作数右操作数 结果结果 1 十十 X 0.418 T1 2 * T1 Y T2 3 T2 W Z第四阶段，优化第四阶段，优化 (Optimization)(Optimization)优化的任务优化的任务: : 对产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效对产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。（省时间和空间）的目标代码。 优化的主要方面有：优化的主要方面有： 公共子表达式提取、循环优化、删除无用代码等等。有时，为了便于公共子表达式提取、循环优化、删除无用代码等等。有时，为了便于“并行运算并行运算”，还

29、可以对代码进行并行化处理。，还可以对代码进行并行化处理。优化所依循的原则优化所依循的原则: : 程序的等价变换规则。程序的等价变换规则。例如，有程序片断例如，有程序片断 for K:1 to 100 dobegin M:=I+10*K N:=J+10*Kend其中间代码为：其中间代码为： 序号序号OPARG1ARG2RESULT注注 解解（1）（2）（3）（4）（5）（6）（7）（8）（9）:=j*+*+j 110010I10JK KKT1KT21 K（9）T1MT2NK（2） K：1若若100K转至第转至第(9)个四元式个四元式T1 :二二10*K; T1为临时变量为临时变量M :IT1T2

30、 :10*k; T2为临时变量为临时变量N :J十十T2K :K十十1转至第（转至第（2）个四元式）个四元式 转换成如下的等价代码：转换成如下的等价代码： 序号序号OPARG1ARG2RESUL注注 解解（1）（2）（3）（4）（5）（6）（7）（8）（9）：=：=：=j+j IJ1100MNK K10101MNK（9）MNK（4） M：IN：JK：lif（100k）goto（9）M：M10N：N十十 10K：Klgoto（4） 优化后目标程序的执行效率提高很多。因为，对于前者，在循环中需优化后目标程序的执行效率提高很多。因为，对于前者，在循环中需做做300次加法和次加法和200乘法乘法；对于

31、后者，在循环中只需做；对于后者，在循环中只需做300次加法。次加法。第第五阶段，目标代码生成五阶段，目标代码生成(Code Generation)(Code Generation)这一阶段的任务是：这一阶段的任务是： 把中间代码（或经优化处理之后）变换成特定机器上的低级语言代把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。码。 例例 （*, id3, 10.0, t1） （+, id2, , t1, id1 ）目标代码：目标代码： （1）MOV id3, R2 （2）MUL #10.0, R2 （3）MOV id2, R1 （4）ADD R1, R2 （5）MOV R1, id1

32、 上述编译过程的五个阶段是一种典型的分法。上述编译过程的五个阶段是一种典型的分法。 事实上，并非所有编译程序都分成这五阶段。事实上，并非所有编译程序都分成这五阶段。 有些编译程序对优化没有什么要求，优化阶段就可省去。有些编译程序对优化没有什么要求，优化阶段就可省去。在某些情况下，为了加快编译速度，中间代码产生阶段也可以在某些情况下，为了加快编译速度，中间代码产生阶段也可以去掉。去掉。 有些最简单的编译程序是在语法分析的同时产生目标代码。有些最简单的编译程序是在语法分析的同时产生目标代码。但是，多数实用编译程序的工作过程大致都像上面所说的那五但是，多数实用编译程序的工作过程大致都像上面所说的那五

33、个阶段。个阶段。1.3 1.3 编译程序的结构编译程序的结构 1.3.1 1.3.1 编译程序总框编译程序总框 上述编译过程的五个阶段是编译程序工作时的动态特征。编译程序的上述编译过程的五个阶段是编译程序工作时的动态特征。编译程序的结构可以按照这五阶段的任务分模块进行设计。结构可以按照这五阶段的任务分模块进行设计。图图1.5 编译程序总框编译程序总框词法分析器词法分析器语法分析器语法分析器语义分析与中间代码生成器语义分析与中间代码生成器中间代码优化器中间代码优化器目标代码生成器目标代码生成器表表格格管管理理出出错错处处理理目标代码程序目标代码程序源程序源程序单词符号串单词符号串语法单位语法单位

34、中间代码串中间代码串中间代码串中间代码串 （1）词法分析器）词法分析器(lexical analyzer)，也称扫描器：，也称扫描器： 输入源程序，进行词法分析，输出单词符号。输入源程序，进行词法分析，输出单词符号。 （2）语法分析器）语法分析器(syntax analyzer)，简称分析器：，简称分析器： 对单词符号串进行语法分析（根据语法规则进行推导或对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出各类语法单位，最终判断输入串是否构成语法上归约），识别出各类语法单位，最终判断输入串是否构成语法上正确的正确的“程序程序”。 （3）语义分析与中间代码产生器）语义分析与中间代码产生

35、器(semantic analyzer and intermediate code generator)： 按照语义规则对语法分析器归约出（或推导出）的语法按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。单位进行语义分析并把它们翻译成一定形式的中间代码。 有的编译程序在识别出各类语法单位后，构造并输出一棵表示语法有的编译程序在识别出各类语法单位后，构造并输出一棵表示语法结构的语法树，然后，根据语法树进行语义分析和中间代码产生。结构的语法树，然后，根据语法树进行语义分析和中间代码产生。 （4）代码优化器）代码优化器(code optimizer)

36、： 对中间代码进行优化处理，以便得到高质量的目标代对中间代码进行优化处理，以便得到高质量的目标代码。码。 （5）代码生成器）代码生成器(code generator)： 将中间代码翻译成等价的目标程序。将中间代码翻译成等价的目标程序。 除了上述五个功能模块外，一个完整的编译程序还应包括除了上述五个功能模块外，一个完整的编译程序还应包括“表格管理表格管理”和和“出错处理出错处理”两部分。两部分。1.3.2 1.3.2 表格管理表格管理 (symbol-table manager)(symbol-table manager) 编译程序在工作过程中需要保存一系列的表格，以登记源程序的各类编译程序在工

37、作过程中需要保存一系列的表格，以登记源程序的各类信息和编译各阶段的进展状况。信息和编译各阶段的进展状况。 合理地设计和使用表格是编译程序构造的一个重要问题。合理地设计和使用表格是编译程序构造的一个重要问题。 在编译程序使用的表格中，最重要的是符号表。它用来登记源程序中在编译程序使用的表格中，最重要的是符号表。它用来登记源程序中出现的每个名字以及名字的各种属性。出现的每个名字以及名字的各种属性。 例如，一个名字是常量名、变量名，还是过程名等等；如果是变量名，例如，一个名字是常量名、变量名，还是过程名等等；如果是变量名，它的类型是什么、所占内存是多大、地址是什么等等。它的类型是什么、所占内存是多大

38、、地址是什么等等。 通常，编译程序在处理到名字的定义性出现时，要把名字的各种属性通常，编译程序在处理到名字的定义性出现时，要把名字的各种属性填入到符号表中；当处理到名字的使用性出现时，要对名字的属性进行查填入到符号表中；当处理到名字的使用性出现时，要对名字的属性进行查证。证。 当扫描器识别出一个名字（标识符）后，它把该名字填入到符号表中。当扫描器识别出一个名字（标识符）后，它把该名字填入到符号表中。但这时不能完全确定名字的属性，它的各种属性要在后续的各阶段才能填但这时不能完全确定名字的属性，它的各种属性要在后续的各阶段才能填入。入。 例如，名字的类型等要在语义分析时才能确定，而名字的地址可能要

39、例如，名字的类型等要在语义分析时才能确定，而名字的地址可能要到目标代码生成才能确定。到目标代码生成才能确定。由此可见，编译各阶段都涉及到构造、查找或更新有关的表格。由此可见，编译各阶段都涉及到构造、查找或更新有关的表格。 1.3.3 1.3.3 出错处理出错处理(error handler) (error handler) 一个编译程序不仅应能对书写正确的程序进行翻译，而且应能对出现一个编译程序不仅应能对书写正确的程序进行翻译，而且应能对出现在源程序中的错误进行处理。在源程序中的错误进行处理。 如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告如果源程序有错误，编译程序应设法发现错误

40、，把有关错误信息报告给用户。这部分工作是由专门的一组程序（叫做出错处理程序）完成的。给用户。这部分工作是由专门的一组程序（叫做出错处理程序）完成的。 一个好的编译程序应能最大限度地发现源程序中的各种错误，准确地一个好的编译程序应能最大限度地发现源程序中的各种错误，准确地指出错误的性质和发生错误的地点，并且能将错误所造成的影响限制在尽指出错误的性质和发生错误的地点，并且能将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，以便进一步可能小的范围内，使得源程序的其余部分能继续被编译下去，以便进一步发现其它可能的错误。发现其它可能的错误。 如果不仅能够发现错误，而且还能自

41、动校正错误，那当然就更好了。如果不仅能够发现错误，而且还能自动校正错误，那当然就更好了。但是，自动校正错误的代价是非常高的。但是，自动校正错误的代价是非常高的。 编译过程的每一阶段都可能检测出错误，其中，绝大多数编译过程的每一阶段都可能检测出错误，其中，绝大多数错误可以在编译的前三阶段检测出来。错误可以在编译的前三阶段检测出来。 源程序中的错误通常分为语法错误和语义错误两大类。源程序中的错误通常分为语法错误和语义错误两大类。 语法错误语法错误是指源程序中不符合语法（或词法）规则的错误，是指源程序中不符合语法（或词法）规则的错误，它们可在词法分析或语法分析时检测出来。它们可在词法分析或语法分析时

42、检测出来。 例如，词法分析阶段能够检测出例如，词法分析阶段能够检测出“非法字符非法字符”之类的错误；之类的错误；语法分析阶段能够检测出诸如语法分析阶段能够检测出诸如“括号不匹配括号不匹配”、“缺少；缺少；”之之类的错误。类的错误。 语义错误语义错误是指源程序中不符合语义规则的错误，这些错误是指源程序中不符合语义规则的错误，这些错误一般在语义分析时检测出来，有的语义错误要在运行时才能检一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。测出来。 语义错误通常包括：说明错误、作用域错误、类型不一致语义错误通常包括：说明错误、作用域错误、类型不一致等等。关于错误检测和处理方法，我们将穿插在

43、有关章节介绍。等等。关于错误检测和处理方法，我们将穿插在有关章节介绍。1.3.4 1.3.4 遍遍 (Pass(Pass） 前面介绍的编译过程的五个阶段仅仅是逻辑功能上的一种划前面介绍的编译过程的五个阶段仅仅是逻辑功能上的一种划分。具体实现时，受不同源语言、设计要求、使用对象和计算机分。具体实现时，受不同源语言、设计要求、使用对象和计算机条件（如主存容量）的限制，往往将编译程序组织为若干条件（如主存容量）的限制，往往将编译程序组织为若干遍遍（Pass）。 所谓所谓“遍遍”就是对源程序或源程序的中间结果从头到尾扫就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果

44、或目标程序。描一次，并作有关的加工处理，生成新的中间结果或目标程序。 通常，每遍的工作由从外存上获得的前一遍的中间结果开始通常，每遍的工作由从外存上获得的前一遍的中间结果开始（对于第一遍而言，从外存上获得源程序），完成它所含的有关（对于第一遍而言，从外存上获得源程序），完成它所含的有关工作之后，再把结果记录于外存。工作之后，再把结果记录于外存。 当一遍中包含若干阶段时，各阶段的工作是穿插进行的。当一遍中包含若干阶段时，各阶段的工作是穿插进行的。例如，我们可以把词法分析、语法分析及语义分析与中间代码例如，我们可以把词法分析、语法分析及语义分析与中间代码产生这三阶段安排成一遍。产生这三阶段安排成一

45、遍。 这时，语法分析器处于核心位置，当它在识别语法结构而这时，语法分析器处于核心位置，当它在识别语法结构而需要下一单词符号时，它就调用词法分析器，一旦识别出一个需要下一单词符号时，它就调用词法分析器，一旦识别出一个语法单位时，它就调用中间代码产生器，完成相应的语义分析语法单位时，它就调用中间代码产生器，完成相应的语义分析并产生相应的中间代码。并产生相应的中间代码。 一个编译程序究竟应分成几遍，如何划分，是与源语言、一个编译程序究竟应分成几遍，如何划分，是与源语言、设计要求。硬件设备等诸因素有关的，因此难于统一划定。设计要求。硬件设备等诸因素有关的，因此难于统一划定。 遍数多一点有个好处，即整个

46、编译程序的逻辑结构可能清遍数多一点有个好处，即整个编译程序的逻辑结构可能清晰一点。但遍数多势必增加输入输出所消耗的时间。因此，晰一点。但遍数多势必增加输入输出所消耗的时间。因此，在主存可能的前提下，一般还是遍数尽可能少一点为好。应当在主存可能的前提下，一般还是遍数尽可能少一点为好。应当注意的是，并不是每种语言都可以用单遍编译程序实现。注意的是，并不是每种语言都可以用单遍编译程序实现。 1.3.5 1.3.5 编译前端与后端编译前端与后端 前端前端主要由与源语言有关但与目标机无关的那些部分组成。主要由与源语言有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码

47、这些部分通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。产生，有的代码优化工作也可包括在前端。 后端后端包括编译程序中与目标机有关的那些部分，如与目标包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。通常，后端不依赖于源机有关的代码优化和目标代码生成等。通常，后端不依赖于源语言而仅仅依赖于中间语言。语言而仅仅依赖于中间语言。 可以取编译程序的前端，改写其后端以生成不同目标机上可以取编译程序的前端，改写其后端以生成不同目标机上的相同语言的编译程序。如果后端的设计是经过精心考虑的，的相同语言的编译程序。如果后端的设计是经过精心考虑的

48、，那么后端的改写将用不了太大工作量，这样就可实现编译程序那么后端的改写将用不了太大工作量，这样就可实现编译程序的目标机改变。也可以设想将几种源语言编译成相同的中间语的目标机改变。也可以设想将几种源语言编译成相同的中间语言，然后为不同的前端配上相同的后端，这样就可为同一台机言，然后为不同的前端配上相同的后端，这样就可为同一台机器生成不同语言的编译程序。然而，由于不同语言存在某些微器生成不同语言的编译程序。然而，由于不同语言存在某些微妙的区别，因此在这方面所取得的成果还非常有限。妙的区别，因此在这方面所取得的成果还非常有限。 为了实现编译程序可改变目标机，通常需要有一种定义良为了实现编译程序可改变

49、目标机，通常需要有一种定义良好的中间语言支持。好的中间语言支持。 著名的著名的AdaAda程序设计环境程序设计环境APSEAPSE中，使用的是一种称为中，使用的是一种称为DianaDiana的树形结构的中间语言。一个的树形结构的中间语言。一个AdaAda源程序通过前端编译转换为源程序通过前端编译转换为DianaDiana中间代码，由编译后端把中间代码，由编译后端把DianaDiana中间代码转换为目标代码。中间代码转换为目标代码。编译前端与不同的编译后端以编译前端与不同的编译后端以DianaDiana为界面，实现编译程序的为界面，实现编译程序的目标机改变。目标机改变。 在在JavaJava语言

50、环境中，为了使编译后的程序从一个平台移到语言环境中，为了使编译后的程序从一个平台移到另一个平台执行，另一个平台执行，JavaJava定义一种虚拟机代码定义一种虚拟机代码BytecodeBytecode。 只要实际使用的操作平台上实现了执行只要实际使用的操作平台上实现了执行BytecodeBytecode的的JavaJava解解释器，这个操作平台就可以执行各种释器，这个操作平台就可以执行各种JavaJava程序。这就是所谓程序。这就是所谓JavaJava语言的操作平台无关性。语言的操作平台无关性。 1.4 1.4 编译程序与程序设计环境编译程序与程序设计环境 编译程序无疑是实现高级语言的一个最重

51、要的工具。但支持程序设计编译程序无疑是实现高级语言的一个最重要的工具。但支持程序设计人员进行程序开发通常还需要一些其它的工具如编辑程序；连接程序；调人员进行程序开发通常还需要一些其它的工具如编辑程序；连接程序；调试工具等。编译程序与这些程序设计工具一起构成所谓的程序设计环境。试工具等。编译程序与这些程序设计工具一起构成所谓的程序设计环境。 在高级语言发展的早期，这些程序设计工具往往是独立的，缺乏整体在高级语言发展的早期，这些程序设计工具往往是独立的，缺乏整体性，而且也缺乏对软件开发全生命周期的支持。随着软件技术的不断发展，性，而且也缺乏对软件开发全生命周期的支持。随着软件技术的不断发展，现在人

52、们越来越倾向于构造集成化的程序设计环境。现在人们越来越倾向于构造集成化的程序设计环境。 一个集成化的程序设计环境的特点是，它将相互独立的程序设计工具一个集成化的程序设计环境的特点是，它将相互独立的程序设计工具集成起来，以便为程序员提供完整的、一体化的支持，从而进一步提高程集成起来，以便为程序员提供完整的、一体化的支持，从而进一步提高程序开发效率，改善程序质量。在一个好的集成化程序设计环境中，不仅包序开发效率，改善程序质量。在一个好的集成化程序设计环境中，不仅包含丰富的程序设计工具，而且还支持程序设计方法学，支持程序开发的全含丰富的程序设计工具，而且还支持程序设计方法学，支持程序开发的全生命周期

53、。有代表性的集成化程序设计环境有生命周期。有代表性的集成化程序设计环境有Ada语言程序设计环境语言程序设计环境APSE、LISP语言程序设计环境语言程序设计环境INTERLISP等。广大读者所熟悉的等。广大读者所熟悉的Turbo Pascal、Turbo C、Visual C+等语言环境也都可认为是集成化的程序设计环境。等语言环境也都可认为是集成化的程序设计环境。 下面以下面以Ada语言的程序设计环境语言的程序设计环境APSE为例，介绍程序设计环境的基本为例，介绍程序设计环境的基本构成和主要工具。构成和主要工具。 APSE是一个分层的程序设计环境，如图是一个分层的程序设计环境，如图1.6所示。

54、所示。 图图1.6 Ada程序设计环境程序设计环境 最内层（第最内层（第0层）是宿主计算机系统，它包括硬件、宿主操作系统和其层）是宿主计算机系统，它包括硬件、宿主操作系统和其它支持软件。第一层是核心它支持软件。第一层是核心APSE(KAPSE)。它包括环境数据库、通信及运。它包括环境数据库、通信及运行时支撑功能等。行时支撑功能等。 第二层，最小第二层，最小APSE(MAPSE)。它包括了。它包括了Ada程序开发及维护的基本工程序开发及维护的基本工具，这些工具包括编译程序、编辑程序、连接程序、调试程序、命令解释程具，这些工具包括编译程序、编辑程序、连接程序、调试程序、命令解释程序、配置管理程序、

55、美化打印程序、静态分析工具，动态分析工具等等。序、配置管理程序、美化打印程序、静态分析工具，动态分析工具等等。 第三层，第三层，APSE。在。在MAPSE外面再加上更广泛的工具就构成了完整的外面再加上更广泛的工具就构成了完整的APSE。对这一层没有精确规定工具的类型，它通常可以包括面向应用的工。对这一层没有精确规定工具的类型，它通常可以包括面向应用的工具和支持特定程序设计方法的工具等。可以是支持需求分析、设计、实现、具和支持特定程序设计方法的工具等。可以是支持需求分析、设计、实现、维护等软件开发全生命周期的工具。维护等软件开发全生命周期的工具。 在一个程序设计环境中，编译程序起着中心的作用。连

56、接程序、调试程在一个程序设计环境中，编译程序起着中心的作用。连接程序、调试程序、程序分析等工具的工作直接依赖于编译程序所产生的结果，而其它工具序、程序分析等工具的工作直接依赖于编译程序所产生的结果，而其它工具的构造也常常要用到编译的原理、方法和技术。的构造也常常要用到编译的原理、方法和技术。1.5 1.5 编译程序的生成编译程序的生成 以前人们构造编译程序大多是用机器语言或汇编语言作工具以前人们构造编译程序大多是用机器语言或汇编语言作工具的。为了充分发挥各种不同硬件系统的效率，为了满足各种不的。为了充分发挥各种不同硬件系统的效率，为了满足各种不同的具体要求，现在许多人仍然采用这种工具来构造编译

57、程序同的具体要求，现在许多人仍然采用这种工具来构造编译程序（或编译程序的（或编译程序的“核心核心”部分）。但是，越来越多的人已经使部分）。但是，越来越多的人已经使用高级语言作工具来编译程序。因为，这样可以大大节省程序用高级语言作工具来编译程序。因为，这样可以大大节省程序设计时间，而且所构造出来的编译程序易于阅读、维护和移植。设计时间，而且所构造出来的编译程序易于阅读、维护和移植。 为了便于说明，我们用一种为了便于说明，我们用一种T形图来表示源语言形图来表示源语言S S、目标语、目标语言言T和编译程序实现语言和编译程序实现语言I 之间的关系，如图之间的关系，如图1.7所示。所示。 STI图图1.

58、7 T型图型图 如果如果A机器上已有一个用机器上已有一个用A机器代码实现的某高级语言机器代码实现的某高级语言L1的的编译程序，则我们可以用编译程序，则我们可以用L1语言编写另一种高级语言编写另一种高级L2的编译程序，的编译程序，把写好的把写好的L2编译程序经过编译程序经过L1编译程序编译后就可得到编译程序编译后就可得到A机器代机器代码实现的码实现的L2编译程序，如图编译程序，如图1.8所示。所示。 图图1.8 用用L1语言编写编译程序语言编写编译程序L2AL1L1AAL2AAA机器有机器有C语言，希望实现语言，希望实现PASCAL语言的编译器的语言的编译器的T型图如型图如1.8 采用一种所谓的

59、采用一种所谓的“移植移植”方法，我们可以利用方法，我们可以利用A机器上已有的高级语言机器上已有的高级语言L编写一个能够在编写一个能够在B机器上运行的高级语言机器上运行的高级语言L的编译程序。做法是，先用的编译程序。做法是，先用L语语言编写出在言编写出在A机器上运行的产生机器上运行的产生B机器代码的机器代码的L编译程序源程序，然后把该编译程序源程序，然后把该源程序经过源程序经过A机器上的机器上的L编译程序编译后得到能在编译程序编译后得到能在A机器上运行的产生机器上运行的产生B机器机器代码的编译程序，用这个编译程序再一次编译上述编译程序源程序就得到了代码的编译程序，用这个编译程序再一次编译上述编译

60、程序源程序就得到了能在能在B机器上运行的产生机器上运行的产生B机器代码的编译程序。用机器代码的编译程序。用T形图表示为图形图表示为图1.9所示。所示。 图图1-9 编译程序编译程序“移植移植”LBLLAALBALBLLBB 我们还可以采用我们还可以采用“自编译方式自编译方式”产生编译程序。方法是，产生编译程序。方法是，先对语言的核心部分构造一个小小的编译程序（可用低级语先对语言的核心部分构造一个小小的编译程序（可用低级语言实现），再以它为工具构造一个能够编译更多语言成分的言实现），再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，就像滚雪球一样，越滚越大，较大编译程序。如此