编译器设计之路.docx

目录出版说明前言第 1 章 概述11.1 编译技术概述11.1.1 程序设计语言基础11.1.2 程序设计语言的翻译机制41.1.3 编译器的基本结构51.2 Pascal 语言基础81.2.1 Pascal 语言简介81.2.2 Pascal 程序基本组成91.2.3 Pascal 的声明部分101.2.4 Pascal 的类型121.2.5 Pascal 的运算符151.2.6 Pascal 的语句171.3 开发环境与 Delphi 基础181.3.1 开发环境与文件列表181.3.2 Delphi 基础191.4 深入学习241.5 实践与思考251.6 大师风采Niklaus Wirth25第 2 章 词法分析262.1 词法分析概述262.1.1 词法分析的任务262.1.2 单词的分类282.2 词法分析器的设计282.2.1 识别单词282.2.2 转换图292.2.3 构造词法分析器312.3 词法分析器的实现352.3.1 词法定义352.3.2 构造转换图与转换表362.3.3 相关数据结构382.3.4 源代码实现402.4 深入学习442.5 实践与思考452.6 大师风采Dennis M. Ritchie45第 3 章 语法分析473.1 程序设计语言的语法描述473.1.1 上下文无关文法473.1.2 推导523.1.3 语法树543.1.4 归约简介573.2 语法分析概述583.2.1 语法分析的任务583.2.2 自上而下的语法分析法593.2.3 构造语法分析器643.3 语法分析器的实现713.3.1 文法定义713.3.2 语法分析表763.3.3 源代码实现863.4 深入学习903.5 实践与思考913.6 大师风采Edsger WybeDijkstra92第 4 章 符号表系统934.1 语义分析概述934.1.1 程序设计语言的语义934.1.2 语义分析与 IR 生成的任务944.1.3 语法制导翻译954.2 符号表设计984.2.1 符号表概述984.2.2 符号表的逻辑结构994.2.3 符号表的实例分析1094.3 声明部分的实现1114.3.1 相关数据结构1114.3.2 主程序首部声明1134.3.3 包含文件声明部分1144.3.4 标号声明部分118编译器设计之路4.3.5 常量声明部分1194.3.6 类型声明部分1204.3.7 变量声明部分1494.3.8 过程、函数声明部分1524.4 深入学习1544.5 实践与思考1554.6 大师风采John Backus155第 5 章 中间表示1565.1 IR 概述1565.1.1 IR 的作用1565.1.2 IR 设计及其级别1575.1.3 设计 IR 的重要意义1595.2 IR 生成1605.2.1 三地址代码概述1605.2.2 Neo Pascal三地址代码的实现1645.2.3 翻译机制概述1685.3 语句翻译概述1705.3.1 语句翻译基础1705.3.2 翻译辅助函数及其实现1735.4 if 语句1765.4.1 if 语句的翻译1765.4.2 源代码实现1775.5 while/repeat 语句1815.5.1 while 语句的翻译1815.5.2 源代码实现1815.5.3 repeat 语句的翻译1845.6 for 语句1845.6.1 for 语句的翻译1845.6.2 源代码实现1865.7 case 语句1925.7.1 case 语句的翻译1925.7.2 源代码实现1935.8 其他语句1995.8.1 break、continue 语句的翻译1995.8.2 goto 语句的翻译2015.8.3 asm 语句的翻译2045.9 深入学习2085.10 实践与思考2085.11 大师风采Kenneth E.Iverson209第 6 章 表达式语义2106.1 表达式概述2106.2 类型系统基础2116.2.1 类型基础2116.2.2 类型系统2126.2.3 类型转换2176.3 类型系统的实现2186.3.1 类型系统的设计2186.3.2 IR 的操作数2216.3.3 类型相容的实现2226.3.4 类型推断的实现2236.4 表达式翻译2266.4.1 表达式翻译基础2266.4.2 深入表达式翻译2296.4.3 表达式翻译的实现2306.5 操作数翻译2476.5.1 操作数的地址与形态2476.5.2 操作数翻译基础2486.5.3 简单变量操作数的翻译2526.5.4 记录字段操作数的翻译2626.5.5 数组翻译基础2656.5.6 数组元素操作数的翻译2706.5.7 指针运算的翻译2806.6 深入学习2866.7 实践与思考2866.8 大师风采Alan Kay287第 7 章 优化技术2887.1 优化概述2887.1.1 什么是优化2887.1.2 优化级别2897.2 控制流分析2907.2.1 流图与基本块2907.2.2 流图的数据结构2927.2.3 流图的构造2937.2.4 优化的分类2977.3 数据流分析2987.3.1 数据流的相关概念298VIII7.3.2 数据流分析的策略2987.3.3 活跃变量分析2997.3.4 ud 链与 du 链3017.3.5 更多数据流问题3027.4 数据流分析的实现3037.4.1 定值点与引用点分析的基础3037.4.2 定值点、引用点分析的相关数据结构3057.4.3 定值点、引用点分析的实现3077.4.4 活跃变量分析的实现3127.4.5 ud 链、du 链分析的实现3147.5 常量传播与常量折叠3217.5.1 常量传播基础3217.5.2 常量传播的实现3247.6 复写传播3287.6.1 复写传播的基础3287.6.2 复写传播的实现3307.7 代数简化3337.7.1 代数简化基础3337.7.2 代数简化的实现3347.8 跳转优化3397.8.1 跳转优化基础3397.8.2 条件跳转优化的实现3417.8.3 连续跳转优化的实现3437.9 冗余代码删除3457.9.1 冗余代码删除基础3457.9.2 死代码删除的实现3467.9.3 不可到达代码删除的实现3487.10 深入学习3507.11 实践与思考3507.12 大师风采Richard Stallman351第 8 章 运行时刻的存储管理3528.1 存储管理概述3528.1.1 存储区域3528.1.2 存储布局3548.1.3 存储分配基础3568.2 栈式存储分配3578.2.1 栈式存储分配基础3578.2.2 i386 栈式存储分配3608.2.3 深入理解栈式存储分配3658.3 存储分配的实现3688.4 存储优化3728.4.1 存储优化基础3728.4.2 存储优化的实现3748.5 深入学习3818.6 实践与思考3828.7 大师风采BjarneStroustrup382第 9 章 目标代码生成3839.1 目标代码生成概述3839.1.1 目标代码生成基础3839.1.2 指令选择3849.1.3 寄存器分配3859.2 目标机简介3869.2.1 目标机结构3869.2.2 浮点处理单元3879.2.3 操作数寻址方式3919.2.4 ptr 操作符3929.2.5 一个完整的汇编程序3939.3 构造代码生成器3939.3.1 自动代码生成器基础3939.3.2 指令模板3949.3.3 寄存器描述3979.3.4 寄存器分配3989.3.5 代码生成器的基本结构4029.4 深入学习4139.5 实践与思考4139.6 大师风采Peter Naur413第 10 章 GCC 内核与现代编译技术概述41410.1 编译技术的现状及发展41410.2 GCC 内核分析41510.2.1 GCC 的基本结构41510.2.2 GENERIC41610.2.3 GIMPLE41610.2.4 SSA42610.2.5 RTL 概述428IX编译器设计之路10.2.6 RTX43010.3 动态编译技术简介43610.3.1 动态编译技术基础43610.3.2 运行时特定化43710.3.3 动态二进制翻译43910.4 并行编译技术简介44110.4.1 并行编译技术基础44110.4.2 并行计算机及其编译系统44310.5 深入学习44610.6 大师风采Alan Perlis447参考文献448X第 1 章 概述Reliable and transparent programs are usually not in the interest of the designer.Niklaus Wirth1.1 编译技术概述1.1.1 程序设计语言基础Intel 公司的 David Kuck 院士曾经将编译器誉为“计算机科学与技术的皇后”，它是应用与系统之间的一座桥梁。在国内，由于计算机基础科学相对薄弱，人们通常更多投身于应用领域的研究，编译技术并不太受到人们的关注。因此，基于这方面的研究成果也相对较少。除了早期一些大型机的 Fortran、Algol 编译器之外，并没有真正的产品级编译器。不过，这并不意味着研究编译技术是毫无价值可言的。事实上，作为计算机科学的组成部分之一，编译技术有着极其崇高的地位，其辉煌的历史可能是其他许多学科无法比拟的。众所周知，图灵奖被誉为“计算机界的诺贝尔奖”，自 1966 年设立至今，54 位获奖者中就有 16 位是由于程序设计语言或编译技术的研究成果而获此殊荣的，见表 1-1。虽然有些大师的身影已经渐渐远去，但是他们的研究成果却为人津津乐道。表 1-1 因程序设计语言或编译技术而获图灵奖的科学家年份获 奖 者获 奖 原 因1966Alan J. Perlis先进编程技术和编译架构方面的贡献1971John McCarthyLisp 语言、程序语义、程序理论、人工智能方面的贡献1972E. W. Dijkstra对开发 Algol 做出了原理性贡献1977John Backus在高级语言方面所做出的具有广泛和深远意义的贡献，特别是在 Fortran 语言方面1979Kenneth E. Iverson在编程语言的理论和实践方面（特别是 APL）所进行的开创性的工作1980C. A. R. Hoare在编程语言的定义和设计方面的贡献，如 case 语句、公理语义学等1983Ken Thompson， Dennis M. Ritchie在通用操作系统理论研究，特别是UNIX 操作系统的实现上的贡献。开发实现了C 语言1984Niklaus Wirth开发了 Euler、Algol-W、Modula 和 Pascal 一系列崭新的计算语言1991Robin Milner在可计算函数逻辑（LCF）、ML 和并行理论（CCS）这三个方面突出的贡献2001Ole-Johan Dahl、Kristen Nygaard面向对象编程始发于他们基础性的构想，这些构想集中体现在他们所设计的编程语言Simula I 和 Simula 67 中2003Alan Kay在面向对象语言方面的原创性思想，领导了 Smalltalk 的开发团队，以及对 PC 的基础性贡献2005Peter Naur在设计 Algol 60 程序设计语言上的贡献。Algol 60 语言定义清晰，是许多现代程序设计语言的原型2006Frances Allen对于优化编译器技术的理论和实践做出的开创性贡献，这些技术为现代优化编译器和自动并行执行打下了基础2008Barbara Liskov在计算机程序语言设计方面的开创性工作。开发了面向对象编程语言 CLU注：见ACM 图灵奖：计算机发展史的缩影（1966-2006）（第三版），吴鹤龄，崔林，高等教育出版社。概述从 20 世纪 50 年代到 80 年代末，一些程序设计语言的兴起，为编译技术的发展提供了新的契机。Ada、Fortran、Algol、Pascal、C、C+等高级语言编译器如雨后春笋一般诞生。作为编译领域的经典之作，“龙书”也是撰写于这一时期的，它的出现将原先模糊的理论体系与实现技巧完全梳理清晰了。正在人们隐约感到编译技术（尤其是前端技术）已相对成熟之际，一个崭新的时代正悄然来临。自 20 世纪 90 年代至今，计算机硬件体系的飞速发展，把编译技术的研究推向了新的高峰。编译器是将一种程序设计语言编写的源程序等价地转换为另一种程序设计语言编写的源程序的系统软件。习惯上，将前者称为源语言，而将后者称为目标语言。读者应该对语言并不陌生，汉语、英语、C、Java 等都是语言。那么，它们的联系与区别是什么呢？大千世界的语言一般可以分为两类，即自然语言和人工语言。自然语言就是日常生活中使用的语言，如汉语、英语。自然语言通常是在交流过程中逐渐完善的，并不是刻意定义的。人工语言则是为了特定目的、用途，而人为创造出来的语言。例如，在计算机程序设计中使用的语言、工程技术中的符号、图形语言等。实际上，读者可以将人工语言理解成为解决某一特殊问题而定义的一种语言，例如 C、Java 等就是为了解决计算机程序设计而定义的人工语言。不过，自然语言与人工语言之间并非如人们所想象的那样存在着严格的界限。虽然自然语言没有太多的人为主观因素，但是它确实也是由人类创造的。因此，读者只需了解这两个概念即可，不必过多深究。早在 20 世纪 50 年代，计算机科学家就开始对语言处理进行了深入的研究，其中包含最重要的两个领域：一是自然语言理解与处理，二是程序设计语言及其编译技术。前者主要研究计算机如何才能正确识别与处理自然语言及其语义。而后者主要研究如何设计一种人工语言，使之有效地完成人与计算机之间的无障碍交流，计算机之所以能普及到千家万户与程序设计语言的发展是分不开的。不过，两者的研究至今仍然尚待完善，例如，至今人类还无法使用计算机自动完成英语句子到汉语句子准确无误的翻译。这主要是由于无法让计算机准确理解输入英语句子的语义，同时，也无法让计算机将预定语义使用汉语表达输出。这就需要在自然语言理解与处理领域的继续探索。自然语言理解与处理不是本书的研究对象，笔者不多作讨论。下面，来谈谈程序设计语言及其编译技术的话题。这方面的研究主要包括：程序设计语言设计与定义、高级语言编译器设计、编译优化技术、并行编译技术、嵌入式编译技术、动态编译技术等。读者阅读完本书之后，可以根据个人兴趣选择其中某些领域作深入学习与研究。程序设计语言是一种人工语言，而人工语言的一个重要特点就是人们可以对语言作一些严格的规定，从而不必过多关注语言表达形式的不确定性。例如，在 C 语言中，表达式 a= =10 只能用于描述“变量 a 是否等于 10”这一种语义。然而，在自然语言中，一个句子存在两种以上语义的情况并不罕见。例如，“我看见他太激动了。”这个句子表达的含义到底是什么？可以理解为： 我看见他后，我太激动了。也可理解为： 我看见他时，他非常激动。这里“看见”的宾语选择使句子存在二义性。然而，同样的问题在程序设计语言中却很罕见。例如，在 C 语言中，对于 a+b 这样的表达式，读者可能会疑惑运算结果到底应该25是 （a+） +b 还是 a+ （+b）。但根据 C 语言的约定，运算结果一定是（a+）+b。由此可见，在设计一门程序语言及其编译器时，避免二义性是设计者考虑的首要因素。至于为什么一定是这样的结果呢？当学习完第 2 章，读者一定会了解 C 语言这一约定的现实意义与必要性。当然，这并不意味着程序设计语言中是绝对不存在二义性的。以 C 语言为例，（+a）+（+a）的取值就将因编译器而异。迄今为止，程序设计语言仍是人类与计算机交流的主要途径，它的应用领域也仅限于操纵与控制计算机。从第一台计算机诞生之日起，人类就始终在探索一种有效的方式与计算机进行对话交流，使之能为人类服务。虽然时隔数十年，计算机能识别与处理的语言仍然是二进制形式的机器语言描述的源程序。当然，不可否认二进制机器语言的优点非常多，但机器语言的易用性差也是不可回避的。即使是计算机专家想直接使用机器语言与计算机进行交流也是非常困难的。在 20 世纪 50 年代，计算机科学家们就已经意识到必须解决这一棘手的问题，否则计算机将无法得到普及。经过多年努力，汇编语言、C、Pascal等程序设计语言终于横空出世。根据语言的形式与特点，习惯上，将机器语言与汇编语言（一种比较接近机器语言的程序设计语言）称为低级语言，将其余的C、Pascal 之类的语言称为高级语言。读者必须注意，低级语言与高级语言之分并不是说明语言本身的优劣，仅仅是说明语言的形式与机器语言的相似程度。所谓低级语言指的是与机器语言比较类似的语言，而高级语言指的是与机器语言差别较大而与自然语言比较类似的语言。由于这些非机器语言的诞生，也就出现了将非机器语言等价翻译成机器语言的需求。显然，将非机器语言翻译成机器语言的工作不能由手工完成，否则，非机器语言的产生就没有任何意义了。因此，人们试图借助于一个程序工具自动完成翻译工作。根据语言不同，翻译工具的复杂程度也不尽相同。比如，汇编语言比较接近机器语言，所以其翻译工具较易实现。而高级语言与机器语言差别较大，所以其翻译工具的实现也较为复杂。习惯上，将前者称为汇编器，而将后者称为编译器。当然，有些书上对于汇编器与编译器并没有严格区分，都将其称为编译器，反正这只是一个名词而已，读者不必深究。编译器的源语言是一种较为高级的程序设计语言，而目标语言可以是汇编语言、机器语言或者另一种高级语言。笔者必须澄清一点，人们普遍认为编译器的目标语言就是低级语言，这个观点的确没有错，但并不完整。实际上，有些编译器的目标语言可能是某一种已存在的高级语言，例如，第一个由 Bjarne Stroustrup 开发的 C+编译器的目标语言就是当时的 C 语言。假设未来的计算机 CPU 能直接处理 C 或者 Java 语言，那么，低级语言、高级语言及编译器的概念也将被重新诠释。今天，虽然计算机的 CPU 可以达到天文级的处理速度，但是识别的指令数量却不会超过 1000 条（PC 的指令规模一般只有 300500 条左右）。无论多么深奥、华丽的高级语言源代码最终必将被这近千条机器指令等价替换。相对于自然语言而言，程序设计语言的表达能力要小得多。不过，程序设计语言也有其自身的特性，比如，程序设计语言必须简单易学。不可能要求程序员用十年磨一剑的精神像学习英语一样去学习 C 语言。过于复杂的语言并不是经典的程序设计语言，更不能广为流传。在程序设计语言发展的历程中，这种例子并不罕见。以上主要讨论了语言及程序设计语言的一些基本常识。程序设计语言的设计是一门技术， 更是一门艺术，优秀的程序设计语言可以广为流传数十年之久。实际上， Algol 、 Lisp 、 Fortran 、 Pascal 、 C 、 Smalltalk 、 APL 、 ML 、 Simula 、 Modula-1/2 、 PL360 等经典语言都是历经了时间的考验才传承至今的。设计程序设计语言及编译器是一项富有挑战性且能带来无限成就感的工作，希望本书能引领读者进入程序设计语言的殿堂。1.1.2 程序设计语言的翻译机制在日常生活中，对于两个不同体系的自然语言而言，翻译工作可能是相当复杂的。众所周知，在语法、语义等体系上，不同的自然语言之间都存在着巨大差异，因此，至今自然语言的翻译工作仍然是以手工完成为主。当然，随着对自然语言理解的深入研究，或许在不久的将来计算机准确翻译自然语言会成为可能。那么，作为一种人工语言，程序设计语言的翻译又是如何进行的呢？程序设计语言的复杂性远不及自然语言，因此，试图让计算机完成程序设计语言的翻译的想法并非奢望。从 20 世纪 60 年代开始，许多计算机大师就着眼于高级程序设计语言及其翻译工具的研究，成就了不少优秀的程序语言，例如读者熟知的 C、Pascal 等。在没有任何理论基础的情况下，大师们进行了艰苦的探索，构造了程序设计语言翻译体系的雏型。在经典编译技术中，程序设计语言的翻译模型主要有两种：解释与编译。首先，笔者简单介绍一下“解释”。运用解释方法进行翻译的高级语言工具被称为解释程序。解释程序是高级语言翻译程序的一种，它将某一高级语言源程序作为输入，解释一句后就提交计算机执行一句，直至源程序读取完毕。解释程序在计算机应用中并不少见，例如，早期的 BASIC 语言的翻译程序就是解释程序。另外，网络浏览器也是一种解释程序，它是将 HTML 以及 JavaScript 等脚本程序进行解释执行的。再如，UNIX/Linux 的 Shell 也是解释执行的。下面，再来谈谈“编译”。运用编译方法进行翻译的高级语言翻译器称为编译器（或称为编译程序），这也是本书讨论的重点。虽然编译器的目标语言并不唯一，但是，汇编语言或机器语言是最为常用的目标语言。通常，编译器指的就是把用高级语言源程序翻译成等价的计算机汇编语言或机器语言的目标程序的翻译程序。编译器把高级语言源程序作为输入，而以汇编语言或机器语言的目标程序作为输出。因此，在编译完成后，编译器会生成相应的目标程序。编译器是程序设计语言翻译中应用极广的软件，例如，早期的 Turbo C、Turbo Pascal，现代的 Delphi、VC+等都是编译器。这里，笔者必须指出，“解释”与“编译”只是两种翻译方法或者说是方案，并不能直接与某种程序设计语言挂钩。例如，有些书认为 BASIC 语言是解释语言、C 语言是编译语言。严格地说，这种说法并不正确。笔者认为程序设计语言本身并不存在解释、编译之分， C 语言一样可以运用解释的方法设计它的翻译程序，BASIC 语言同样可以运用编译方法设计它的翻译程序。随着人们对程序设计语言翻译技术的不断深入研究，有一种新的翻译方法逐步被人们接受，就是编译与解释相结合的方法。这种翻译方法的思路是先通过编译生成一个目标程序，但这一目标程序并不是真正的机器语言程序，而是一种编译器设计人员定义的一个较低级语言描述的程序（可能近似于汇编语言）。这一程序再经过相应的解释器解释执行，如图 1-1所示。早期的 Lisp 语言就是应用这种翻译方式实现的，它使用一种类似于语法树形式的语言作为目标程序的描述语言。图 1-1 “编译+解释”翻译过程近年来，人们热衷于编译与解释相结合的方法探索，提出了两种改进方案：即时编译、动态编译。即时编译：先把源程序翻译成一种比较低级的内部语言描述的程序，然后，在执行装载程序时，即时地将程序编译为目标机器的本地机器语言程序，然后直接执行机器语言程序。这种实现方案被广泛应用，例如，Java 语言编译器和微软的.NET 开发平台都是应用这种方法实现的。Java 生成的目标程序是称为字节码的一种较低级语言的程序。而.NET 开发平台生成的目标程序是面向 CLR（Common Language Runtime）的程序。动态编译：为了避免即时编译的运行代价，开始时正常解释执行，在执行中，检查执行的热点（如循环、递归调用等），发现热点后动态编译这部分代码，生成本机的机器语言程序以提高执行效率。关于三种翻译方式的优缺点在学术界争论已久，本书不进行深入分析，只是列出几个公认的观点，见表 1-2。笔者认为，作为一位有志于深入学习与研究编译技术的读者，了解翻译方式的基本知识还是有必要的。表 1-2 翻译方式的特点执 行 效 率执行过程中的灵活性源代码保密性纯“解释”方式慢高完全公开纯“编译”方式快低保密“编译+解释”方式一般一般一般1.1.3 编译器的基本结构作为系统软件，编译器的设计与实现是非常复杂的。对于一个相对复杂的系统，通常的解决方法是将系统分解成若干较小且便于处理的小系统，分别实现后将其组织成一个完整的复杂系统，这就是“分治法”的思想。实际上，计算机科学家正是运用这种思想来设计与实现编译器、操作系统、网络通信协议等复杂的大型系统软件的。编译器的翻译过程是非常复杂的，但就过程本身而言，与自然语言翻译却有不少相近之处。例如，把英语句子翻译为汉语句子时，通常需要经过下列几个步骤：1） 对句子中的每个英语单词进行识别。2） 对句子的语法结构进行分析。3） 分析句子的基本含义，进行初步翻译。4） 修饰译文，使之更加符合汉语的表达习惯。5） 将译文整理书写记录。编译器的工作过程与自然语言翻译过程比较类似，亦可划分为五个阶段：词法分析、语法分析、语义分析与中间表示生成、代码优化、代码生成。1. 词法分析词法分析的任务就是对输入的源程序进行扫描分析，识别出一个个的单词（Token），并进行归类。这里的“单词”可以理解为源程序中具有独立含义的不可分割的字符序列，与自然语言中的单词概念有一定区别。一般而言，根据程序设计语言的特点，单词可以分为五类：关键字、标识符、常量、运算符、界符。以一个 C 语言的条件语句为例：if （aa && 10=0） aa=100；词法分析的结果是识别出如下的单词符号：关键字界符标识符运算符常量运算符if（aa&&10=常量界符标识符运算符常量界符0）aa=100；这里，读者只需了解词法分析的任务即可。其算法实现将在第 2 章中详述。2. 语法分析语法分析的任务就是在词法分析的基础上，根据程序设计语言的语法规则（文法），把单词流分解成各类语法单位（语法范畴），如“语句”、“表达式”等。理论上讲，通过语法分析，编译器可以准确无误地判断输入源程序是否满足语言的语法规则。例如，语法分析可以判断如下语句是错误的。if aa % 10=9 aa=100； for（i<0） i+；不过，实际情况并非完全如此，这主要与文法定义的细化程度有直接的关系。当程序设计语言的设计人员把文法定义得比较宽泛时，也就意味着依据此语法规则，编译器不能在语法分析阶段发现所有的语法错误，只能将错误遗留给后续阶段处理。表面上看，语法分析并不像词法分析有直观的输出结果，而仅仅完成了输入源程序的语法判定工作。实际上，语法分析是编译器前面三个阶段（合称为前端）的主控模块。语法分析的设计思想与算法实现是经典编译理论重点讨论的话题，将在第 3 章中详述。3. 语义分析与中间表示生成语义分析与中间表示生成的任务就是在语法分析的基础上，分析各语法单位的含义，并进行初步的翻译，即生成中间表示形式。有时，这两个任务是密不可分的，故通常将其合并为一个阶段讨论。语义分析主要是检查输入源程序的语义是否正确，例如，变量使用前是否定义、同一作用域内变量是否重名等。中间表示生成将根据输入源程序的语义生成语义等价中间表示形式。中间表示是一种由编译器设计人员定义、使用的形式，对于用户是完全透明的。中间表示形式的定义是值得深入研究的，因为它直接决定了编译器前、后端的设计复杂度，也决定了编译器前端与目标语言之间的耦合程度。中间表示的形式也非常多，包括四元组、三元组、语法树、DAG 图等，并不一定是读者理解的通常的代码形式。例如，lcc 的中间表示就是一种 DAG 的形式。当然，近似于汇编指令形式的四元组、三元组可能是最为常见的中间表示形式。由于这个阶段的内容繁多，笔者将以符号表系统、中间表示、表达式语义三个主题予以介绍。相关内容分布在本书的第 46 章中。4. 代码优化代码优化的任务就是对生成的中间表示进行优化处理，得到占用空间较小、执行效率较高的目标代码。由于中间表示是由计算机自动生成的，不可能像手工编码那样精炼，因此，编译器需要借助优化处理对目标代码进行精简。随着前端技术的相对成熟，优化技术逐渐成为编译技术领域的核心研究课题之一。第 7 章将详细讨论优化的相关话题。5. 代码生成代码生成的任务就是将中间表示形式翻译成目标语言描述的程序代码。本阶段是与目标计算机硬件系统结构密切相关的，其工作也非常复杂，如寄存器的调度、指令的选择、指令的调度等。并且，这个阶段还涉及许多与目标计算机硬件系统有关的优化技术，称为“指令级优化”。通常，目标代码的形式可以是汇编语言代码、机器语言代码、其他语言的代码。早期，目标代码多为机器语言代码。然而，随着汇编器、链接器的成熟，汇编语言代码逐渐取代了机器语言代码，成为目标代码的首选。近年来，随着虚拟机技术的出现与发展，目标代码的概念可能还会改变。例如，由于.NET Framework 的盛行， 许多编译器（ 如 Delphi .NET、ML、SmallTalk 等）都可以生成面向 CLR 的目标程序。第 89 章将详细讨论运行时环境与代码生成的相关技术。以上五个阶段是一种典型的分类观点。事实上，并非所有的编译器都包含这五个阶段。例如，有些简单语言的编译器完全可以省去中间表示形式，直接生成目标代码。再如，一些并不苛求优化的编译器完全可以省去优化阶段。这里所提及的五个阶段只是大多数编译器的设计经验而已。除了以上五个阶段之外，有些编译器还包括两个非常重要的组成部分：符号表管理、出错处理。6. 符号表管理符号表是一系列用于记录各个分析阶段所获取信息（如变量名、作用域、函数形参等）的数据表格，这些表格的维护贯穿于整个编译过程。显然符号表的设计和管理是编译器构造过程中的一项极其重要的任务。这里，设计者更多关注的是表格的完整性与访问效率。第 4章将详细讨论符号表的构造。7. 出错处理对于输入源程序的各种错误，编译器必须给出比较准确的出错报告，以便用户及时准确地定位、修改。编译过程的每一个阶段都可能检测出错误，其中，绝大多数错误可以在编译的前三个阶段检测出来。当然，真正的商用编译器并不限于此，可能还涉及更复杂的出错恢复。出错恢复主要是当编译器检测到错误之后，尽可能按照语义修正错误。注意，出错恢复的目的并不在于真正修复用户程序，而只是试图一次检测更多的错误。当然，这是基于编译器预测机制实现的。图 1-2 描述了编译器各个阶段之间的关系，读者只需参考结构图了解各个阶段的任务及其输入、输出情况即可。图 1-2 编译器结构图这里，还有必要了解一个比较重要的概念：端（End）。根据完成任务不同，可以将编译器的组成部分划分为前端（Front End）与后端（Back End）。前端主要指与源语言有关但与目标机无关的部分，包括词法分析、语法分析、语义分析与中间表示生成。后端主要指与目标机有关的部分，包括代码优化和目标代码生成等。 “端”概念的提出对于编译技术的发展起到了至关重要的作用，它使编译器的框架更明晰，更利于集成与构造。1.2 Pascal 语言基础1.2.1 Pascal 语言简介本书描述的编译器是笔者开发的 Neo Pascal，这是一个基于标准 Pascal 的实际编译器。 Pascal 是由瑞士苏黎士理工学院 Niklaus Wirth 教授在 1971 年设计实现的，它的语法结构源于 Algol 语言。Wirth 教授以 17 世纪法国著名数学家 Pascal 的名字为这种优美严谨的程序设计语言命名。Pascal 盛行 30 年，成为 PC 平台上最受欢迎的程序设计语言之一。不过，随着 C 语言体系（C 语言、C+、Java 等）的不断成熟壮大，对于某些读者而言，Pascal 语言可能已经渐渐淡出了人们的视野。笔者之所以仍然选择标准 Pascal 语言作为设计蓝本，主要有如下几个原因：（1） Pascal 语言是一门严谨且优美的程序设计语言。（2） Pascal 语言功能非常强大，适合各种系统软件、应用软件设计。（3） Pascal 语言数据类型非常丰富。例如，集合类型、函数类型、指针类型等。（4） Pascal 语言的语义复杂度不如 C 语言，故有利于编译器设计与实现。同时，便于初学者学习理解。正由于上述优点，Pascal 仍然是算法设计的主要描述语言，也是 IOI（国际奥林匹克信息学竞赛）三种参赛程序设计语言之一。相信读者读完本书后，一定能够领略到 Pascal 的优美。下面简单介绍一下 Pascal 语言，有 Pascal 语言基础的读者可以跳过这些内容。不过， Pascal 语言程序设计并不是本书的主题，因此，不可能花大量篇幅详述。笔者将对照 C 语言进行讲解，以便读者快速入门。当然，读者也可以参考Pascal 语言程序设计、Turbo Pascal 用户手册等。1.2.2 Pascal 程序基本组成请读者先阅读下列两段程序，比较计算圆周长程序的 C 与Pascal 的描述。例 1-1计算圆的周长，代码见表 1-3。表 1-3 C 与Pascal 程序的比较C 语言程序Pascal 语言程序1234567891011float r，c；float Calc（float r）return 2*r*3.1416；main（）scanf（"%f"，&r）； c=Calc（r）； printf（"%f"，c）；1234567891011program main