编译原理清华大学导论课件.ppt

1、编译原理清华大学导论编译原理清华大学导论课程内容课程内容 v介绍编译器构造的一般原理和基本实现方法介绍编译器构造的一般原理和基本实现方法v理论知识：形式语言和自动机理论、语法制导翻译的定义和属性文法等理论知识：形式语言和自动机理论、语法制导翻译的定义和属性文法等v形式化描述技术形式化描述技术v对编译原理和技术的宏观理解，注意力无需分散到枝节算法，无需偏向于某种源语言或目标机对编译原理和技术的宏观理解，注意力无需分散到枝节算法，无需偏向于某种源语言或目标机器器学习的意义学习的意义 v对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程对编程语言的设计和实现有深刻的

2、理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用。语言来说，起一个奠基的作用。v从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。v大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平。大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平。v在软件逆向工程、软件的设计方法、程序理解和软件安全等方面有着广泛的应用。在软件逆向工程、软件的设计方法、程序理解和软件安全等方面有着广泛的应用。课程要求课程要求v讲课进展较快，平时

3、要复习并加深理解。讲课进展较快，平时要复习并加深理解。v作业较多，要求独立完成。作业较多，要求独立完成。v实验和课内实践，每次验收检查。实验和课内实践，每次验收检查。v学期总评成绩学期总评成绩 =考试成绩考试成绩60%+60%+平时成绩平时成绩40%40%平时成绩平时成绩40%=40%=作业实验考勤作业实验考勤30%+30%+课内实践课内实践10%10%编译系统是现代计算机系统的基本组成之一，编译程序构造的基本原理和技术不仅应用于编译程编译系统是现代计算机系统的基本组成之一，编译程序构造的基本原理和技术不仅应用于编译程序的设计，也广泛应用于一般软件的设计和实现。本课程是计算机类专业的一门重要的

4、核心专业课。序的设计，也广泛应用于一般软件的设计和实现。本课程是计算机类专业的一门重要的核心专业课。先修课程：先修课程：高级程序设计语言、汇编语言、高级程序设计语言、汇编语言、离散数学、数据结构离散数学、数据结构学习要求：学习要求：不旷课，上课认真听讲，课上保持安静；不旷课，上课认真听讲，课上保持安静；课后即时复习，认真完成作业；课后即时复习，认真完成作业；实验课内实践程序独立设计及实现实验课内实践程序独立设计及实现。学习目标学习目标 通过本课程的学习，旨在使同学们掌握程序设计语言的形式化描述和编译的基本理论、原理和技术，通过本课程的学习，旨在使同学们掌握程序设计语言的形式化描述和编译的基本理

5、论、原理和技术，并对编译程序有较为具体的认识。使同学们能运用所学过的基本知识、着手开发系统程序，为今后的工作并对编译程序有较为具体的认识。使同学们能运用所学过的基本知识、着手开发系统程序，为今后的工作（理论研究和技术开发）打下基础。（理论研究和技术开发）打下基础。具体为：具体为：（1 1）掌握编译程序基本结构及构造的基本原理和技术；）掌握编译程序基本结构及构造的基本原理和技术；（2 2）掌握文法、形式语言及自动机的基本概念和在编译程序构造中的应用；）掌握文法、形式语言及自动机的基本概念和在编译程序构造中的应用；（3 3）掌握典型的几种语法分析方法的基本原理和实现方法；）掌握典型的几种语法分析方

6、法的基本原理和实现方法；（4 4）掌握语法制导方法在语义分析中的应用和中间代码生成方法；）掌握语法制导方法在语义分析中的应用和中间代码生成方法；（5 5）掌握存储分配的基本思想和实现方法；）掌握存储分配的基本思想和实现方法；（6 6）掌握代码优化及代码生成的方法。）掌握代码优化及代码生成的方法。学习向导学习向导 编译原理编译原理课程是理论性较强的课程。其特点是概念多、内容抽象。尤其是文法、形式语言及自动机课程是理论性较强的课程。其特点是概念多、内容抽象。尤其是文法、形式语言及自动机的概念是计算机专业的理论学习和研究的基础。掌握这些基本理论、原理和技术，对于培养同学们对事物的的概念是计算机专业的

7、理论学习和研究的基础。掌握这些基本理论、原理和技术，对于培养同学们对事物的抽象能力以及分析问题和解决问题的能力大有帮助。抽象能力以及分析问题和解决问题的能力大有帮助。编译原理与方法对于深刻理解程序设计语言、深入了解程序在计算机中的运行机制、掌握程序设计语言编译原理与方法对于深刻理解程序设计语言、深入了解程序在计算机中的运行机制、掌握程序设计语言的翻译方法起到不可替代的作用。同时的翻译方法起到不可替代的作用。同时编译原理编译原理课程也是实践性很强的课程，要求同学们在基本掌握了课程也是实践性很强的课程，要求同学们在基本掌握了编译理论和技术的基础上，综合应用先修课程及本课程的知识，完成课程的实验和课

8、程设计。编译理论和技术的基础上，综合应用先修课程及本课程的知识，完成课程的实验和课程设计。参考资料参考资料 教材：教材：11编译原理编译原理（第三版）（第三版）主编：王生原、董渊、张素琴、吕映芝主编：王生原、董渊、张素琴、吕映芝 出版社：清华大学出版社出版社：清华大学出版社 出版时间：出版时间：20152015年年参考书：参考书：11编译原理编译原理 主编：何炎祥主编：何炎祥 出版社：华中理工大学出版社出版社：华中理工大学出版社 出版时间：出版时间：20102010年年1010月月22程序设计语言编译原理（第程序设计语言编译原理（第3 3版）版）主编：陈火旺、刘春林、谭庆平、赵克佳、刘越主编：

9、陈火旺、刘春林、谭庆平、赵克佳、刘越 出版社：国防工业出版社出版社：国防工业出版社 出版时间：出版时间：2001220012年年8 8月月33编译原理技术与工具（英文版）编译原理技术与工具（英文版）Compilers:Principles,Techniques,and Compilers:Principles,Techniques,and ToolsTools 主编：主编：AlfredAlfred V.Aho,RaviV.Aho,Ravi Sethi,JeffreySethi,Jeffrey D.UllmanD.Ullman 出版社：人民邮电出版社出版社：人民邮电出版社 出版时间：出版时间：2

10、0022002年年2 2月月 参考资料参考资料44编译原理与技术编译原理与技术（第二版）（第二版）主编：陈意云主编：陈意云 出版社：中国科学技术大学出版社出版社：中国科学技术大学出版社 出版时间：出版时间：20022002年年1 1月月55编译程序构造原理和实现技术编译程序构造原理和实现技术 主编：金成植主编：金成植 出版社：高等教育出版社出版社：高等教育出版社 出版时间：出版时间：20022002年年7 7月月66编译原理及编译程序构造编译原理及编译程序构造 主编：高仲仪、金茂忠主编：高仲仪、金茂忠 出版社：北京航空航天大学出版社出版社：北京航空航天大学出版社 出版时间：出版时间：20012

11、001年年3 3月月77编译原理编译原理(第第2 2版版)主编：蒋立源主编：蒋立源,康慕宁康慕宁 出版社：西北工业大学出版社出版社：西北工业大学出版社 出版时间：出版时间：19991999年年4 4月月88编译原理编译原理 主编：张幸儿主编：张幸儿 出版社：科学出版社出版社：科学出版社 出版时间：出版时间：19991999年年4 4月月 第第1 1章章 引论引论 本章主要内容：本章主要内容：v什么是编译程序什么是编译程序v编译过程和编译程序的结构编译过程和编译程序的结构v为什么要学习编译程序为什么要学习编译程序 本章的重点：本章的重点：本章没有难以理解的内容本章没有难以理解的内容,主要是对编译

12、程序的功能和结构做一综主要是对编译程序的功能和结构做一综合描述合描述1.1 1.1 什么叫编译程序什么叫编译程序 使用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。现代计算机系使用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。现代计算机系统一般都含有不止一个的高级语言编译程序，对有些高级语言甚至配置了几个不同性能的编译程序，供用统一般都含有不止一个的高级语言编译程序，对有些高级语言甚至配置了几个不同性能的编译程序，供用户按不同需要进行选择。户按不同需要进行选择。要在计算机上执行用高级语言（或汇编语言）编写的程序，必须通过特定的途径来进行，也就

13、是要通要在计算机上执行用高级语言（或汇编语言）编写的程序，必须通过特定的途径来进行，也就是要通过翻译程序把用高级语言（或汇编语言）编写的程序翻译成为机器语言构成的程序，计算机才能执行。过翻译程序把用高级语言（或汇编语言）编写的程序翻译成为机器语言构成的程序，计算机才能执行。在计算机上执行一个高级语言程序一般要分为两步：在计算机上执行一个高级语言程序一般要分为两步：第一步，用一个编译程序把高级语言翻译成机器语言程序；第一步，用一个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。第二步，运行所得的机器语言程序求得计算结果。（1 1）翻译程序（）翻译程序（Trans

14、latorTranslator）通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序（称为源语言程序或源程序）通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序（称为源语言程序或源程序）转换成另一种语言程序（称为目标语言程序或目标程序），而后者与前者在逻辑上是等价的。转换成另一种语言程序（称为目标语言程序或目标程序），而后者与前者在逻辑上是等价的。源程序源程序（source program）翻译程序翻译程序目标程序目标程序(target program)输入输入输出输出图图1.1 翻译程序翻译程序 翻译程序根据所处理的对象和实现的途径不同又分为：汇编程序、编译程序和解释程序。

15、翻译程序根据所处理的对象和实现的途径不同又分为：汇编程序、编译程序和解释程序。（2 2）.汇编程序（汇编程序（AssemblerAssembler）如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就称为汇编程序。如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就称为汇编程序。源程序源程序（汇编语言）（汇编语言）翻译程序翻译程序（汇编程序）（汇编程序）目标程序目标程序（机器语言）（机器语言）输入输入输出输出图图1.2 汇编程序汇编程序（3 3）.编译程序（编译程序（CompilerCompiler）如果源语言是某种高级语言，而目标语言是

16、某种低级语言（汇编语言或机器语言），这样的一个翻译如果源语言是某种高级语言，而目标语言是某种低级语言（汇编语言或机器语言），这样的一个翻译程序就称为编译程序。程序就称为编译程序。源程序源程序（高级语言）（高级语言）翻译程序翻译程序（编译程序）（编译程序）目标程序目标程序（低级语言）（低级语言）图图1.3 编译程序编译程序输入输入输出输出（4 4）.解释程序（解释程序（Interpreter）这是另外一种类型的翻译程序，在翻译过程它按照高级语言源程序在计算机上执行的动态顺序对源程这是另外一种类型的翻译程序，在翻译过程它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），边解

17、释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。行结果，这样的一个翻译程序就称为解释程序。源程序源程序（高级语言）（高级语言）翻译程序翻译程序（解释程序）（解释程序）计算结果计算结果输入输入输出输出图图1.4 解释程序解释程序初始数据初始数据根据不同的用途，编译程序可进一步分类根据不同的用途，编译程序可进一步分类:（1）诊断编译程序（）诊断编译程序（Diagnostic Compiler）：）：专门用于帮助程序开发和调试的编译程序。专门用于帮助程序

18、开发和调试的编译程序。（2）优化编译程序（）优化编译程序（Optimizing Compiler）：）：着重于提高目标代码效率的编译程序。着重于提高目标代码效率的编译程序。（3）交叉编译程序）交叉编译程序(Cross Compiler)：如果一个编译程序产生不同于其宿主机的机器代码。如果一个编译程序产生不同于其宿主机的机器代码。（4）可变目标编译程序（）可变目标编译程序（Retargetable Compiler）：）：不需重写编译程序中与机器无关的部分就能改变目标机。不需重写编译程序中与机器无关的部分就能改变目标机。宿主机（宿主机（host machine）：运行编译程序的计算机。）：运行编

19、译程序的计算机。目标机目标机(object machine)：运行编译程序所产生目标代码的计算机。：运行编译程序所产生目标代码的计算机。1.2 1.2 编译过程概述编译过程概述 编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。一段英文翻译为中文时，通常需经下列步骤：一段英文翻译为中文时，通常需经下列步骤：（1）识别出句子中的一个个单词；）识别出句子中的一个个单词；（2）分析句子的语法结构；）分析句子的语法结构；（3）根据句子的含义进行初步翻译；）根据句子的含义进行初步翻译；（4）对译文进行修

20、饰；）对译文进行修饰；（5）写出最后的译文。）写出最后的译文。类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义分析与中间代类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。码产生、优化、目标代码生成。第一阶段第一阶段:词法分析词法分析 （Lexical analysisLexical analysis）词法分析的任务：词法分析的任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。保留字（保留字（beginbegi

21、n、endend、ifif、forfor、whilewhile等）、等）、标识符（标识符（x1x1、s s等变量名）、等变量名）、常数常数(3.14(3.14、100100等等)、算符（算符（+、-、andand、oror等）、等）、界符（标点符号、左右括号等）。界符（标点符号、左右括号等）。例如，对于例如，对于PascalPascal的循环语句：的循环语句：for I for I：1 to 100 do1 to 100 do词法分析的结果是识别出如下的单词符号：词法分析的结果是识别出如下的单词符号：保留字保留字 forfor 标识符标识符 I I 赋值号：赋值号：=整常数整常数 1 1 保留

22、字保留字 toto 整常数整常数 100100 保留字保留字 dodo 单词符号是语言的基本组成成分，是人们理解和编写程序的基本要素。识别和理解这些要素无单词符号是语言的基本组成成分，是人们理解和编写程序的基本要素。识别和理解这些要素无疑也是翻译的基础。疑也是翻译的基础。如同将英文翻译成中文的情形一样，如果你对英语单词不理解，那就谈不上进行正确的翻译。如同将英文翻译成中文的情形一样，如果你对英语单词不理解，那就谈不上进行正确的翻译。在词法分析阶段的工作中所依循的是语言的词法规则（或称构词规则）。描述词法规则的有效在词法分析阶段的工作中所依循的是语言的词法规则（或称构词规则）。描述词法规则的有效

23、工具是正规式和有限自动机。工具是正规式和有限自动机。第二阶段，语法分析第二阶段，语法分析(Syntax Analysis)(Syntax Analysis)语法分析的任务是：语法分析的任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如“短短语语”、“子句子句”、“句子句子”（“语句语句”）、）、“程序段程序段”和和“程序程序”等。通过语法分析，确定整个输入串是否等。通过语法分析，确定整个输入串是否构成语法上正确的构成语法上正确的“程序程序”。语法分析所依循的是语言的

24、语法规则。语法规则通常用上下文无关文法描述。语法分析所依循的是语言的语法规则。语法规则通常用上下文无关文法描述。词法分析是一种线性分析，而语法分析是一种层次结构分析。例如，在很多语言中，符号串词法分析是一种线性分析，而语法分析是一种层次结构分析。例如，在很多语言中，符号串 z：=X十十0.618*Y代表一个代表一个“赋值语句赋值语句”，而其中的，而其中的 X0.618*Y代表一个代表一个“算术表达式算术表达式”。因而，语法分析的任务就是识别。因而，语法分析的任务就是识别 X0.618*Y为算术表达式，同时，识别上述整个符号串属于赋值语句这个范畴。为算术表达式，同时，识别上述整个符号串属于赋值语

25、句这个范畴。第三阶段，语义分析与中间代码产生第三阶段，语义分析与中间代码产生(Semantic Analysis and Intermediate Generator)(Semantic Analysis and Intermediate Generator)此阶段的任务是：此阶段的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。中间代码是一种独立于具体硬件的记号系统。中间代码是一种独立于具体硬件的记号系统。常用的中间代码：三地址码，四元式，三元式、间接三元式、逆波兰式，树形表示

26、等。常用的中间代码：三地址码，四元式，三元式、间接三元式、逆波兰式，树形表示等。所谓所谓“中间代码中间代码”是一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。这种记号是一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算机的系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。机器指令。四元式的形式是：四元式的形式是：（算符算符 左操作数左操作数 右操作数右操作数 结果）结果）它的意义是：对它的意义是：对“左、右操作数左、右操作数”进行某种运算

27、（由进行某种运算（由“算符算符”指明），把运算所得的值作为指明），把运算所得的值作为“结果结果”保留下来。保留下来。例如例如 赋值语句赋值语句 Z：（：（X0.418）*YW 翻译为四元式序列：翻译为四元式序列：序号序号 算符算符 左操作数左操作数 右操作数右操作数 结果结果 1 十十 X 0.418 T1 2 *T1 Y T2 3 T2 W Z第四阶段，优化第四阶段，优化 (Optimization)(Optimization)优化的任务优化的任务:对产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。对产生的中间代码进行加工变换，以期在最后阶段能产生出更为

28、高效（省时间和空间）的目标代码。优化的主要方面有：优化的主要方面有：公共子表达式提取、循环优化、删除无用代码等等。有时，为了便于公共子表达式提取、循环优化、删除无用代码等等。有时，为了便于“并行运算并行运算”，还可以对代码进，还可以对代码进行并行化处理。行并行化处理。优化所依循的原则优化所依循的原则:程序的等价变换规则。程序的等价变换规则。例如，有程序片断例如，有程序片断 for K:1 to 100 dobegin M:=I+10*K N:=J+10*Kend其中间代码为：其中间代码为：序号序号OPARG1ARG2RESULT注注 解解（1）（2）（3）（4）（5）（6）（7）（8）（9）:

29、=j*+*+j 110010I10JK KKT1KT21 K（9）T1MT2NK（2）K：1若若100K转至第转至第(9)个四元式个四元式T1:二二10*K;T1为临时变量为临时变量M:IT1T2: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：K

30、lgoto（4）优化后目标程序的执行效率提高很多。因为，对于前者，在循环中需做优化后目标程序的执行效率提高很多。因为，对于前者，在循环中需做300次加法和次加法和200乘法乘法；对于后；对于后者，在循环中只需做者，在循环中只需做300次加法。次加法。第第五阶段，目标代码生成五阶段，目标代码生成(Code Generation)(Code Generation)这一阶段的任务是：这一阶段的任务是：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。例例 （*,id3,10.0,t1）（+,id2,t1,id1）目标代码：目标

31、代码：（1）MOV id3,R2 （2）MUL#10.0,R2 （3）MOV id2,R1 （4）ADD R1,R2 （5）MOV R1,id1 上述编译过程的五个阶段是一种典型的分法。上述编译过程的五个阶段是一种典型的分法。事实上，并非所有编译程序都分成这五阶段。事实上，并非所有编译程序都分成这五阶段。有些编译程序对优化没有什么要求，优化阶段就可省去。在某些情况下，为了加快编译速度，中间代码有些编译程序对优化没有什么要求，优化阶段就可省去。在某些情况下，为了加快编译速度，中间代码产生阶段也可以去掉。产生阶段也可以去掉。有些最简单的编译程序是在语法分析的同时产生目标代码。但是，多数实用编译程序

32、的工作过程大致都有些最简单的编译程序是在语法分析的同时产生目标代码。但是，多数实用编译程序的工作过程大致都像上面所说的那五个阶段。像上面所说的那五个阶段。1.3 1.3 编译程序的结构编译程序的结构 1.3.1 1.3.1 编译程序总框编译程序总框 上述编译过程的五个阶段是编译程序工作时的动态特征。编译程序的结构可以按照这五阶段的任务分上述编译过程的五个阶段是编译程序工作时的动态特征。编译程序的结构可以按照这五阶段的任务分模块进行设计。模块进行设计。图图1.5 编译程序总框编译程序总框词法分析器词法分析器语法分析器语法分析器语义分析与中间代码生成器语义分析与中间代码生成器中间代码优化器中间代码

33、优化器目标代码生成器目标代码生成器表表格格管管理理出出错错处处理理目标代码程序目标代码程序源程序源程序单词符号串单词符号串语法单位语法单位中间代码串中间代码串中间代码串中间代码串 （1）词法分析器）词法分析器(lexical analyzer)，也称扫描器：，也称扫描器：输入源程序，进行词法分析，输出单词符号。输入源程序，进行词法分析，输出单词符号。（2）语法分析器）语法分析器(syntax analyzer)，简称分析器：，简称分析器：对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出各类语法单位，最终判断输入对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出各类语法

34、单位，最终判断输入串是否构成语法上正确的串是否构成语法上正确的“程序程序”。（3）语义分析与中间代码产生器）语义分析与中间代码产生器(semantic analyzer and intermediate code generator)：按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。中间代码。有的编译程序在识别出各类语法单位后，构造并输出一棵表示语法结构的语法树，然后，根据语法树有的编译程序在识别出各类语法单位后，构造并输出一棵表示语法结构的语法树，然后，根

35、据语法树进行语义分析和中间代码产生。进行语义分析和中间代码产生。（4）代码优化器）代码优化器(code optimizer)：对中间代码进行优化处理，以便得到高质量的目标代码。对中间代码进行优化处理，以便得到高质量的目标代码。（5）代码生成器）代码生成器(code generator)：将中间代码翻译成等价的目标程序。将中间代码翻译成等价的目标程序。除了上述五个功能模块外，一个完整的编译程序还应包括除了上述五个功能模块外，一个完整的编译程序还应包括“表格管理表格管理”和和“出错处理出错处理”两部分。两部分。1.3.2 1.3.2 表格管理表格管理 (symbol-table manager)(

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

37、一个名字是常量名、变量名，还是过程名等等；如果是变量名，它的类型是什么、所占内存是多大、地址是什么等等。多大、地址是什么等等。通常，编译程序在处理到名字的定义性出现时，要把名字的各种属性填入到符号表中；当处理到名字通常，编译程序在处理到名字的定义性出现时，要把名字的各种属性填入到符号表中；当处理到名字的使用性出现时，要对名字的属性进行查证。的使用性出现时，要对名字的属性进行查证。当扫描器识别出一个名字（标识符）后，它把该名字填入到符号表中。但这时不能完全确定名字的属当扫描器识别出一个名字（标识符）后，它把该名字填入到符号表中。但这时不能完全确定名字的属性，它的各种属性要在后续的各阶段才能填入。

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

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

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

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

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

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

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

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

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

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

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

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

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