内容简介

　　本书以作者实现的一个基于Intelx86指令集的编译系统为例，结合程序代码的主要部分详细阐述了编译系统的实现原理和过程。本书对编译器、汇编器、链接器、编译优化器涉及的关键算法、数据结构和程序实现流程，以及ELF文件的格式、Intel指令格式均作了详细的说明，并结合大量的图表，展示了编译系统工作过程中代码信息的流动和存储格式的变化。是一本“手把手”教读者实现编译系统的贴心手册。

作者简介

范志东　就职于腾讯数据平台部，负责腾讯大数据平台的产品化，涉及自动化部署、应用调度、交互分析、集群监控、性能调优等，对开源工具Ambari、Hadoop、Spark等有深入的了解。在校期间屡次获得国家奖学金和励志奖学金。独立开发了基于Intel x86指令集的自定义类C语言的编译系统，包括编译器、汇编器与链接器的实现，对计算机程序的加载和运行原理有深刻的认识。深入分析过Linux内核关于CPU功耗方面的代码。爱好广泛，对编程语言、操作系统、编译系统、计算机安全、分布式系统有着浓厚的兴趣。闲暇时会在技术博客上分享自己的学习心得，期望通过互联网把获得知识的快乐心情传递出去。参与了“十一五”校级立项正式出版教材《计算机操作系统原理》以及全国自学考试教材《计算机应用技术》编写的相关工作。

张琼声　湖北省松滋县人，中国石油大学（华东）计算机与通信工程学院副教授，硕士生导师。主讲课程:《操作系统》《操作系统课程实习》和《嵌入式操作系统》。主持的《计算机操作系统》课程被评为校级精品课，先后获得中国石油大学优秀教学研究成果一、二、三等奖各一项；曾获评中国石油大学优秀教师、山东省优秀学士论文指导教师；主持或参与科研、教研项目十四项。专业及研究兴趣为系统软件开发技术，包括：操作系统、编译系统、计算机系统安全性。发表科研、教学论文二十余篇。参与翻译《深入理解Linux内核》第3版，编著“十一五”校级立项正式出版教材《计算机操作系统原理》、主编全国自学考试教材《计算机应用技术》。

精彩书评

爱因斯坦曾说过：“好奇心是科学工作者产生无穷的毅力和耐心的源泉。”
对于实现一个编译系统来说，打通编译、汇编和链接的全部流程确非易事。然而，当我满怀新奇地将问题抽丝剥茧，最终触及本质的那一刻，才体会到所有的坚持和努力都是值得的。那些抱着和我当初一样好奇心的人，想必也是为了解开心中长埋的疑惑而翻开此书的吧。从对程序语言在计算机上如何运行的不解，到看到自己设计的程序语言执行出正确结果的兴奋，也许只有好奇心才能驱使我们在这条看似枯燥的探索道路上一步一个脚印地走下去。最后套用一句名言：“Stay curious, Stay patient.”希望看到本书的人，能找到心中一直想要的答案。
——范志东

本书介绍编译器设计与实现中的理论和技术，对构造编译器的基本知识与关键技术进行了全新的讲解，受众主要是计算机相关专业的本科生和研究生，以及需要相关知识的程序员，也可以作为教师的参考书。这是近年来在该领域比较全面的一本专业书籍。
—— 葛永文
科锐安网络公司全球副总裁兼大中国区总裁

本书*大的亮点是它具有很强的应用性和可读性。作者不是从复杂深奥的计算机编译理论入手，而是在各个章节中使用有代表性的程序模块作为范例，将它们放入编译系统中运行以描述它们的编译过程，然后对代码和结果给出详细的诠释。 这就像对编译过程进行细致解剖一样。我相信本书会大大降低编译系统理解的门槛，提高读者对编译系统的兴趣。
—— 梁红卫
南京大学少年班本科
中科院自动化所硕士
佐治亚理工学院PHD
定居美国，现就职于Maxim 集成芯片公司

本书知识量很大，作者叙述清晰。基于作者完整实现编译系统的*一手经验和体会，本书集合了所有的主要步骤，对编译原理课堂项目的选题、编程具有非常好的借鉴作用。完整的可运行示例代码使得专注于编译系统的一个特定模块的课堂项目实践更加真实。本书将有力地促进编译原理的实践教学。
—— Jian Cheng (程坚)
CEO, Analytic Measures Inc., Palo Alto, California, USA

正如作者在前言中所言，这本书既能帮助读者在学习编译原理时通过阅读分析这些代码从而加深理解，也能让有兴趣的读者在此基础上进一步进行实践。即便对普通的计算机编程人员而言，通过本书也能了解到不同方面的东西。就我个人而言，虽然熟知优化过程中的那些概念，但*一次看到了那些方法的具体实现仍让我很高兴。尤其是寄存器分配一节，让我更加理解了程序的局部性原则。总之，这是一本值得拥有的好书。
—— 王晓云
前Nokia高级软件架构师

目录

序
前言
第1章代码背后1
从编程聊起 1
历史渊源 2
GCC的工作流程 3
1.3.1预编译 4
1.3.2编译 5
1.3.3汇编 6
1.3.4链接 7
设计自己的编译系统 8
本章小结 9
第2章编译系统设计 11
2.1编译程序的设计 11
2.1.1词法分析 12
2.1.2语法分析 13
2.1.3符号表管理 14
2.1.4语义分析 15
2.1.5代码生成 16
2.1.6编译优化 16
2.2 x86指令格式 18
2.3 ELF文件格式 19
2.4汇编程序的设计 21
2.4.1汇编词法、语法分析 22
2.4.2表信息生成 23
2.4.3指令生成 24
2.5链接程序的设计 25
2.5.1地址空间分配 25
2.5.2符号解析 26
2.5.3重定位 27
2.6本章小结 27
第3章编译器构造 29
3.1词法分析 29
3.1.1扫描器 30
3.1.2词法记号 32
3.1.3有限自动机 36
3.1.4解析器 40
3.1.5错误处理 53
3.2语法分析 55
3.2.1文法定义 55
3.2.2递归下降子程序 65
3.2.3错误处理 70
3.3符号表管理 74
3.3.1符号表数据结构 75
3.3.2作用域管理 78
3.3.3变量管理 82
3.3.4函数管理 88
第4章编译优化147
第5章二进制表示191
第6章汇编器构造219
第7章连接器构造263
参考文献

前言/序言

Foreword序

小范从本科毕业设计开始写编译器的实现代码，为他选择这个题目的初衷是希望把编译系统与操作系统、计算机体系结构相关的结合点找出来、弄清楚，为教学提供可用的实例。本科毕业设计结束时小范完成了一个最简单的C语言子集的编译器，生成的汇编程序经过汇编和链接后可以正确执行。研究生期间我们决定继续编译系统实现技术方向的研究工作，主要完成汇编器和链接器这两大模块。小范用一颗好奇、求知的心指引自己，利用一切可以搜集到的资料，用“日拱一卒”的劲头一步一步接近目标。每天的日子都可能有不同的“干扰”——名企的实习、发论文、做项目、参加竞赛、考认证，身边的同学在快速积攒各种经历和成果的时候，小范要保持内心的平静，专注于工作量巨大而是否有回报还未曾可知的事情。三年的时间里，没有奖学金，没有项目经费，有的是没完没了的各种问题，各种要看的书、资料和要完成的代码，同时还要关注大数据平台、编程语言等新技术的发展。

“汇编器完成了”“链接器完成了”，好消息接踵而至。小范说，“把编译器的代码重写一下，加上代码优化吧？”我说“好”，其实，这个“好”说起来容易，而小范那里增加的工作量可想而知，这绝不是那么轻松的事情。优化的基本原理有了，怎么设计算法来实现呢？整个编译器的文法比本科毕业设计时扩充了很多。编译器重写、增加代码优化模块、完成汇编器和链接器，难度和工作量可想而知。每当小范解决一个问题，完成一个功能，就会非常开心地与我分享。看小范完成的一行行规范、漂亮的代码，听他兴奋地讲解，很难说与听郎朗的钢琴协奏曲《黄河之子》、德沃夏克的《自新大陆》比哪一个更令人陶醉，与听交响曲《嘎达梅林》比哪一个更令人震撼。当小范完成链接器后，我说：“小范，写书吧，不写下来太可惜了。”就这样，小范再次如一辆崭新的装甲车，轰隆前行，踏上了笔耕不辍的征程。2015年暑假，细读和修改这部30多万字的书稿，感慨万千，完成编译系统的工作量、四年的甘苦与共、超然物外的孤独都在这字里行间跳跃。写完这部原创书对一个年轻学生来说是极富挑战的，但是他完成了，而且完成得如此精致、用心。

小范来自安徽的农村，面对生活中的各种困惑、困难，他很少有沮丧、悲观的情绪，永远有天然的好奇心，保留着顽童的天真、快乐与坦率。他开始写本书时23岁，完成全书的初稿时25岁。写编译系统和操作系统内核并非难以企及，只是需要一份淡然、专注和坚持。

如果你想了解计算机是如何工作的，为什么程序会出现不可思议的错误？高级语言程序是如何被翻译成机器语言代码的？编译器在程序的优化方面能做哪些工作？软件和硬件是怎么结合工作的？各种复杂的数据结构和算法，包括图论在实现编译系统时如何应用？有限自动机在词法分析中的作用是什么？其程序又如何实现？那么本书可以满足你的好奇心和求知欲。如何实现编译系统？如何实现编译器？如何实现汇编器？如何使用符号表？如何结合操作系统加载器的需要实现链接器？Intel的指令是如何构成的？如何实现不同的编译优化算法？对这些问题，本书结合作者实现的代码实例进行了详尽的阐述，对提高程序员的专业素质有实际的助益，同时本书也可以作为计算机科学相关专业教师的参考书和编译原理实习类课程的教材。

2013年在新疆参加全国操作系统和组成原理教学研讨会时，我带着打印出来的两章书稿给了机械工业出版社的温莉芳老师，与她探讨这本书出版的意义和可行性，她给了我们很大的鼓励和支持，促成了本书的完成。在此，特别感谢温莉芳老师。

本书的责任编辑佘洁老师与作者反复沟通，对本书进行了认真、耐心的编辑，感谢她的辛勤付出。

中国石油大学（华东）的李村合老师在编译器设计的初期给予了我们指导和建议。马力老师在繁忙的工作之余，认真审阅书稿，给出了详细的修改意见。王小云、程坚、梁红卫、葛永文老师对本书提出了他们的意见，并给出了认真的评价。赵国梁同学对书中的代码和文字做了细心的校对。在此，对他们表示衷心的感谢。最后要感谢小范勤劳、坚韧的爸爸妈妈，是他们一直给予他无私的支持和持续的鼓励。

感恩所有给予我们帮助和鼓励的老师、同学和朋友！

张琼声

2016年春于北京

Preface前　　言

本书适合谁读

本书是一本描述编译系统实现的书籍。这里使用“编译系统”一词，主要是为了与市面上描述编译器实现的书籍进行区分。本书描述的编译系统不仅包含编译器的实现，还包括汇编器、链接器的实现，以及机器指令与可执行文件格式的知识。因此，本书使用“编译系统”一词作为编译器、汇编器和链接器的统称。

本书的目的是希望读者能通过阅读本书清晰地认识编译系统的工作流程，并能自己尝试构造一个完整的编译系统。为了使读者更容易理解和学习编译系统的构造方法，本书将描述的重点放在编译系统的关键流程上，并对工业化编译系统的实现做了适当的简化。如果读者对编译系统实现的内幕感兴趣，或者想自己动手实现一个编译系统的话，本书将非常适合你阅读。

阅读本书，你会发现书中的内容与传统的编译原理教材以及描述编译器实现的书籍有所不同。本书除了描述一个编译器的具体实现外，还描述了一般书籍较少涉及的汇编器和链接器的具体实现。而且本书并非“纸上谈兵”，在讲述每个功能模块时，书中都会结合具体实现代码来阐述模块功能的实现。通过本书读者将会学习如何使用有限自动机构造词法分析器，如何将文法分析算法应用到语法分析过程，如何使用数据流分析进行中间代码的优化，如何生成合法的汇编代码，如何产生二进制指令信息，如何在链接器内进行符号解析和重定位，如何生成目标文件和可执行文件等。

本书的宗旨是为意欲了解或亲自实现编译系统的读者提供指导和帮助。尤其是计算机专业的读者，通过自己动手写出一个编译系统，能加强读者对计算机系统从软件层次到硬件层次的理解。同时，深入挖掘技术幕后的秘密也是对专业兴趣的一种良好培养。GCC本身是一套非常完善的工业化编译系统（虽然我们习惯上称它为编译器），然而单凭个人之力无法做到像GCC这样完善，而且很多时候是没有必要做出一个工程化的编译器的。本书试图帮助读者深入理解编译的过程，并能按照书中的指导实现一个能正常工作的编译器。在自己亲自动手实现一个编译系统的过程中，读者获得的不仅仅是软件开发的经历。在开发编译系统的过程中，读者还会学习很多与底层相关的知识，而这些知识在一般的专业教材中很少涉及。

如果读者想了解计算机程序底层工作的奥秘，本书能够解答你内心的疑惑。如果读者想自定义一种高级语言，并希望使该语言的程序在计算机上正常运行，本书能帮助你较快地达到目的。如果读者想从实现一个编译器的过程中，加强对编译系统工作流程的理解，并尝试深入研究GCC源码，本书也能为你提供很多有价值的参考。

基础知识储备

本书尽可能地不要求读者有太多的基础知识准备，但是编译理论属于计算机学科比较深层次的知识领域，难免对读者的知识储备有所要求。本书的编译系统是基于Linux x86平台实现的，因此要求读者对Linux环境的C/C++编程有所了解。另外，理解汇编器的实现内容需要读者对x86的汇编指令编程比较熟悉。本书不会描述过多编译原理教材中涉及的内容，所以要求读者具备编译原理的基础知识。不过读者不必过于担心，本书会按照循序渐进的方式描述编译系统的实现，在具体的章节中会将编译系统实现的每个细节以及所需的知识阐述清楚。

本书内容组织

本书共7章，各章的主要内容分别如下。

第1章代码背后

从程序设计开始，追溯代码背后的细节，引出编译系统的概念。

第2章编译系统设计

按照编译系统的工作流程，介绍本书编译系统的设计结构。

第3章编译器构造

描述如何使用有限自动机识别自定义高级语言的词法记号，如何使用文法分析算法识别程序的语法模块，如何对高级语言上下文相关信息进行语义合法性检查，如何使用语法制导翻译进行代码生成，以及编译器工作时符号信息的管理等。

第4章编译优化

介绍中间代码的设计和生成，如何利用数据流分析实现中间代码优化，如何对变量进行寄存器分配，目标代码生成阶段如何使用窥孔优化器对目标代码进行优化。

第5章二进制表示

描述Intel x86指令的基本格式，并将AT&T;汇编与Intel汇编进行对比。描述ELF文件的基本格式，介绍ELF文件的组织和操作方法。

第6章汇编器构造

描述汇编器词法分析和语法分析的实现，介绍汇编器如何提取目标文件的主要表信息，并描述x86二进制指令的输出方法。

第7章链接器构造

介绍如何为可重定位目标文件的段进行地址空间分配，描述链接器符号解析的流程，以及符号地址的计算方法，并介绍重定位在链接器中的实现。

随书源码

本书实现的编译系统代码已经托管到github，源码可以使用GCC 5.2.0编译通过。代码的github地址是https://github.com/fanzhidongyzby/cit。代码分支x86实现了基于Intel x86体系结构的编译器、汇编器和链接器，编译系统生成的目标文件和可执行文件都是Linux下标准的ELF文件格式。代码分支arm实现了基于ARM体系结构的编译器，目前支持生成ARM 7的汇编代码。

双十一买的，支持一下这样的技术内容，有时间好好学习^_^

好书值得收藏，打基础的书多读几本。路漫漫兮吾乃上下求索编程之道。

不错?…………

慢慢品

还没看，不知道怎么样，貌似很深奥的样子

比想象中薄，不过讲的通俗易懂，好书

不错，很实用。值得购买！

编译系统是每个电脑爱好者的梦想

挺好的