编辑推荐
编译原理领域的鸿篇巨著和里程碑作品!60余万行源代码和1140余幅运行时结构图从底层揭示程序编译原理和GCC工作机制!中文版尚未出版,英文版即输出美国。
本书的出版具有里程碑意义:
它*一次让编译原理不再像是一门高深晦涩的“数学课”,而是一个可以调试、可以接触、可以真切感受的理论体系。本书用1140余幅信息量巨大的运行时结构图和视频动画取代了同类书中复杂枯燥的数学公式,更加立体和直观,生动地将编译后的执行程序在内存中的运行时结构图展现了出来;
它*一次将GCC源代码、编译原理、运行时结构、编译系统原理(包含汇编与链接)的内在关系、逻辑与原理梳理清楚了,并将它们结合成一个整体。真正能够让读者透彻掌握编译器如何运行和如何设计,以及为什么要这么设计;
它是*一本系统解读著名商用编译器GCC核心源代码的著作,GCC源代码一共有600万行,为了便于讲解和阅读,本书进行了取舍和裁剪,讲解了与编译本质相关的核心的60万行代码。
内容简介
本书是编译原理领域的鸿篇巨著,中文版尚未出版,英文版权已经输出到美国,将在世界范围内产生重要影响。从以下多个角度讲,本书都具有重要的里程碑意义:
它让编译原理不再像是一门高深晦涩的“数学课”,而是一个可以调试、可以接触、可以真切感受的理论体系。本书用1140余幅信息量巨大的运行时结构图和视频动画取代了同类书中复杂枯燥的数学公式,更加立体和直观,生动地将编译后的执行程序在内存中的运行时结构图展现了出来;
它将GCC源代码、编译原理、运行时结构、编译系统原理(包含汇编与链接)的内在关系、逻辑与原理梳理清楚了,并将它们结合成一个整体。真正能够让读者透彻掌握编译器如何运行和如何设计,以及为什么要这么设计;
它是系统解读著名商用编译器GCC核心源代码的著作,GCC源代码一共有600万行,为了便于讲解和阅读,本书进行了取舍和裁剪,讲解了与编译本质相关的*核心的60万行代码。
全书一共8章,具体内容和逻辑如下:
第1章以一个C程序(先简单,后复杂)的运行时结构为依托,对程序编译的整体过程做了宏观讲述,让读者对编译有整体认识,这样更容易理解后面的内容。
第2~6章通过实际的程序案例、结合GCC的源代码,根据程序编译的顺序和流程,依次讲解了词法分析、语法分析、中间结构和目标代码的生成,遵循了由易到难的原则,先是通过简单程序讲解清楚原理,然后再通过复杂程序强化理解。
第7章讲解了与编译器紧密关联的汇编器和链接器,能让读者对可执行程序的*终生成有一个完整的了解。
第8章讲解了预处理,就编译器的执行顺序而言,预处理器的执行比较靠前,之所以放在*后讲,是因为它比较独立,在读者已经了解整个编译过程中之后再讲解,读者会更容易理解。
作者简介
新设计团队,新设计团队由中国科学院大学的教师杨力祥发起,成立于世纪之交,团队成员全部都是杨力祥老师的得意弟子,现在他们是很多企业核心和支柱。新设计团队不断发展、优胜劣汰、适者生存、自然形成。团队在计算机领域中始终只对*基础的、有体系的事情感兴趣,喜欢从根节点解决问题,目前已经在编译器和操作系统等领域取得了突破性的成果,具体如下:
1.图示化的编译器
成功研发出基于图形、图像(而非基于字符、语句)的图示化集成开发环境,直接由图形编译为可执行程序,中间不再转成一般的计算机语言。已经能够成功的编译扫雷等界面应用程序,也可以成功编译linux0.11这样的简单操作系统,编译结果可以正确boot运行。
2.安全操作系统
研发出全新的安全操作系统。使用现有CPU,内核依据新的原理设计而成,不需要安装任何防火墙和杀毒软件,就可以抵御一切已知、未知的网络入侵。此操作系统支持ftp的基础功能,兼容Linux。此操作系统曾经于2014年4月1日至2014年9月30日在互联网上悬赏1万美金进行入侵攻击测试,至今未有人攻破。
3.基于安全CPU的安全操作系统
根据新的操作系统原理,团队还设计了包含全新安全指令的CPU,以及由安全CPU支持的安全操作系统。目前安全CPU的指令设计已经完成,开发了安全CPU仿真平台及基于其上的全新安全操作系统。操作系统可以全面支持Linux(技术上也可以做到全面支持Windows或其他操作系统)。一旦CPU硬件设计制造完成,就可以直接运行安全操作系统,实现真正的安全(EAL7)。
新设计团队还将他们对编译器和操作系统的研究理论成果集结成出版物,除本书外,还出版了《Linux内核设计的艺术》(2011年,机械工业出版社)一书,版权输出到美国、韩国和中国台湾,实现了国内计算机著作向美国输出的零的突破。英文版被美国的MIT、Stanford、Cornell、UMD等100多所大学图书馆及Library of Congress(美国国会图书馆)收藏。
目录
作者简介
前 言
第1章 运行时结构及编译过程概述 1
1.1 一个简单C程序的运行时结构 1
1.2 更为复杂C程序的运行时结构 16
1.3 编译过程概述 25
1.3.1 词法分析 25
1.3.2 语法分析 26
1.3.3 从语法树到中间代码再到目标代码 26
第2章 词法分析 28
2.1 词法分析概要说明 28
2.2 词法分析过程 31
2.3 状态转换图 36
2.3.1 状态转换图总体介绍 36
2.3.2 依托状态转换图展现词法分析过程 42
2.4 GCC实现词法分析的源代码 55
2.4.1 词法分析源代码总览 55
2.4.2 结合GCC源代码讲解词法分析过程 55
2.4.3 标识符、数字、字符和字符串的详细分析过程 65
第3章 语法分析 74
3.1 语法分析综述 74
3.2 语法分析思路 74
3.3 产生式 78
3.3.1 什么是产生式 78
3.3.2 产生式的具体示例 80
3.4 匹配产生式,消除左递归 89
3.4.1 用标准产生式做匹配,出现左递归 89
3.4.2 消除左递归 93
3.4.3 产生式的工作效率 97
3.5 提取左公因子,消除回溯 100
3.5.1 对“直接声明符”的产生式提取左公因子 100
3.5.2 用提取过左公因子的产生式再去匹配 102
3.5.3 对其他产生式都提取左公因子 103
3.5.4 函数声明和定义两部分产生式的合并 105
3.6 语法分析结果:语法树 107
3.7 GCC关于语法分析的源代码解析 112
3.7.1 GCC语法分析函数调用图 112
3.7.2 全部语句的语法分析 115
第4章 语法树到目标代码 217
4.1 总述语法树到中间代码的转化过程 217
4.2 目标代码到运行时结构的映射 224
4.3 语法树转高端gimple 232
4.3.1 语法树到高端gimple的总体步骤及运行时 236
4.3.2 高端gimple的实际数据结构 241
4.3.3 语法树转高端gimple的GCC源代码解析 246
4.4 高端gimple到低端gimple 286
4.4.1 高端gimple转低端gimple概述 286
4.4.2 高端gimple转化低端gimple的GCC代码解析 293
4.5 低端gimple到cfg 297
4.5.1 低端gimple到cfg的转化概述 297
4.5.2 低端gimple转cfg的实际过程 300
4.6 cfg转ssa 301
4.7 生成RTL 305
4.7.1 为何要有RTL 305
4.7.2 转化RTL阶段的主要步骤 306
4.7.3 确定初始RTL中的运行时信息 320
4.8 RTL生成目标代码(汇编) 332
4.8.1 汇编文件介绍 332
4.8.2 创建汇编文件 334
4.8.3 输出汇编文件总入口 334
4.8.4 全局变量写入汇编文件 335
4.8.5 函数写入汇编文件 340
第5章 语句拓展案例的编译过程 353
5.1 总述各个语句拓展案例的编译过程 353
5.2 if语句的语法分析 376
5.2.1 多个变量的声明语句语法分析 376
5.2.2 if语句的语法分析过程 381
5.2.3 if...else if语句的语法分析过程 387
5.3 带标号语句的语法分析 395
5.4 switch...case、goto、break语句的语法分析过程 399
5.4.1 switch...case 语句 399
5.4.2 goto语句 407
5.4.3 分析break语句 409
5.5 do...while、while、for语句的语法分析过程 420
5.5.1 do...while语句的语法分析 424
5.5.2 while语句的语法分析过程 433
5.5.3 for语句的语法分析过程 444
5.6 各种语句嵌套组合的语法分析过程 472
5.6.1 两条变量声明语句分析的结果 477
5.6.2 分析while循环语句 477
5.6.3 进入if进行分析 480
5.6.4 进入else进行分析 485
5.7 所有案例语法树转中间结构的过程 516
5.7.1 案例1的语法树转高端gimple的总体介绍 516
5.7.2 案例1的语法树转高端gimple的代码分析 528
5.7.3 案例1的高端gimple转低端gimple 552
5.7.4 案例1的低端gimple到cfg 552
5.7.5 转化RTL阶段的主要步骤 562
5.7.6 案例2的语法树转高端gimple 587
5.7.7 案例3的语法树转高端gimple 596
第6章 数据拓展案例的编译过程 612
6.1 数据拓展案例的编译过程总述 612
6.1.1 基础类型数据总述 612
6.1.2 用户自定义类型数据总述 617
6.1.3 指针类型数据总述 626
6.1.4 作用域和生存期总述 640
6.1.5 表达式总述 645
6.2 基础类型数据的语法分析过程 652
6.2.1 非浮点型数据的语法分析 653
6.2.2 浮点型数据的语法分析 662
6.3 复合类型数据的语法分析过程 670
6.3.1 数组的语法分析 670
6.3.2 枚举类型数据的语法分析 675
6.3.3 struct类型数据的语法分析 678
6.3.4 union类型数据的语法分析 683
6.3.5 自定义数据声明和使用的语法分析 684
6.4 指针类型数据的语法分析过程 693
6.4.1 对swap_point函数中指针的语法分析 693
6.4.2 对指针使用的语法分析 696
6.5 关于作用域和生存期的语法分析过程 705
6.5.1 C语言作用域和生存期概述 705
6.5.2 全局变量data语法分析中作用域相关处理过程 706
6.5.3 fun函数定义的语法分析中作用域相关处理 709
6.5.4 main函数定义中局部变量声明data作用域处理过程 716
6.5.5 main函数内部语句块中变量nCount作用域处理过程 719
6.5.6 main函数中引用变量data时选择相应声明节点的过程分析 719
6.5.7 main函数中引用变量nCount时选择相应声明节点的过程分析 720
6.5.8 main函数中退出内部语句块时更新变量作用域过程分析 721
6.5.9 fun函数中静态变量temp生存期信息的语法分析 726
6.6 表达式的语法分析过程 728
6.6.1 if条件中的表达式语法分析 728
6.6.2 if条件下面“语句”部分的表达式语法分析 740
6.7 所有案例语法树转中间结构(RTL)的过程 754
6.7.1 基础类型数据语法树转高端gimple的过程 754
6.7.2 用户自定义数据语法树转高端gimple的过程 794
6.7.3 指针类型数据语法树转高端gimple的过程 838
6.7.4 作用域和生存期案例语法树转高端gimple的过程 878
6.7.5 复杂表达式案例的语法树转高端gimple的过程 887
第7章 汇编与链接 934
7.1 汇编器 934
7.1.1 详细介绍汇编指令到机器指令的转化 934
7.1.2 .o文件格式总体情况介绍 953
7.1.3 代码段、数据段以及其他各个表项间的关系 962
7.1.4 从汇编文件到目标文件的实现 967
7.1.5 汇编器处理的源代码分析 973
7.2 链接器 985
7.2.1 .o文件链接总体介绍 985
7.2.2 多个.o文件链接时通过符号表建立关系 989
7.2.3 链接时统一计算地址并回填 997
7.2.4 链接器源代码介绍 999
7.2.5 库函数的链接 1002
7.2.6 动态链接 1002
第8章 预处理 1012
8.1 文件包含 1012
8.2 宏定义 1017
8.3 条件编译 1019
8.4 带参数的宏定义 1022
附录 RTX定义 1031
作者的话 1039
前言/序言
掌握程序在内存中的运行时结构对提高程序设计水平的重要性再怎么强调都不过分,将程序员编写的源代码转化为可执行程序是由编译器完成的,编译器对运行时结构的形成起着非常重要的作用。如果你想提高自己的编程水平,了解编译器怎么将你编写的源代码转换为可执行程序的,那么本书就是为你而写的!如果你对编译原理很感兴趣,也很愿意阅读编译器的源代码,却苦于代码量庞大,不知从何下手,那么你必将从本书中得到巨大的收获。
对程序员来说,提高编程水平最关键的因素之一就是了解程序的运行时结构,只有了解了自己编写的源代码运行的时候在内存中是什么样的(运行时结构),才能真正写出高质量的代码。编译器是将源代码转化为最终运行时结构的工具,如何实现运行时结构正是本书最重要的一条主线。编译器是一个非常经典的程序,其中包含的很多技术已广泛应用于其他软件(如文字处理软件、数据库、Web开发程序等)。读懂编译器的源代码,对计算机软件的很多方面来说都会有借鉴作用。
一般介绍编译原理的书籍通常都是空泛地讲一些抽象的概念,甚至夹杂不少晦涩的数学公式,脱离了具体的编译器,基本上没有编译器的源代码,初学者很难理解。
而本书则是以一个真实、具体、商用GCC编译器的源代码为蓝本,以几个案例程序的实际编译为线索,详细讲解编译案例程序的源代码的具体过程。
本书先对读者最难理解的复杂过程、关系和数据结构以动画视频的方式进行直观、形象的讲解。看过这些视频,读者就会对编译原理有一个概略、直观、整体的理解,从而很容易掌握更深的内容。纸质内容再将编译原理与GCC编译器的源代码有机联系起来,用了大量直观的图示、源代码、文字做详细讲解。
本书没有用一个数学公式,力争用最简单易懂的语言把深奥的理论讲明白。读者在看完本书后会真正了解一个编译器是如何运行的,以及为什么要这么设计,更重要的是知道编译完的程序执行时在内存中的运行时结构是什么样的。
我们还为读者提供了一个缩减版的GCC源代码。原版的GCC源代码大约有600万行,是一个适用于多种计算机语言的编译器,体量过于庞大,几乎无法在短时间内阅读、理解,甚至很难记忆。我们只保留了C语言的相关部分,并去掉了错误分析、处理和优化的相关部分,大约只有130万行,其中约50万行是为了与具体指令集相关,由机器生成的代码,仅涉及后端;在剩下的80万行代码中,与编译本质相关的核心代码大约有60万行。此外,我们还提供了与之相对应的汇编器和链接器的源代码,这些代码虽然不是编译器的一部分,但却是生成完整的可执行程序必不可少的。我们还提供了一整套的开发调试环境,既有适用于Linux的,也有适用于Windows的。读者可以在一个比较小的范围内随着本书的讲解跟踪调试,这样效率更高。读者在阅读的时候始终都能与真实的编译过程、真实的编译器源代码紧密相连。本书的编译原理不再像一门“数学课”,而是一个可以调试、可以接触、可以真切感受的理论体系。
读者只要了解C语言的语法规则,会使用C语言编写一些简单的程序,就能看懂本书。
《代码的诞生:程序员的奇幻之旅》 想象一下,你指尖敲击键盘,一行行代码如同咒语般落下,最终化为屏幕上栩栩如生的应用程序、游戏,抑或是驱动着我们生活的精密系统。然而,你是否曾好奇,这些跃然纸上的字符,是如何被计算机理解并执行的?它们又经历了怎样的蜕变,才得以从抽象的逻辑转化为奔腾的计算力?《代码的诞生:程序员的奇幻之旅》正是为你揭开这层神秘面纱的指南,它将带领你踏上一段深入理解程序生命周期的奇妙旅程,让你从根本上洞察软件如何被创造、转化和运行。 本书并非枯燥的技术手册,而是一场精心设计的探索之旅。我们将以生动形象的比喻和引人入胜的叙事,逐一剖析程序从诞生到运行的每一个关键环节。你将不再是那个仅仅编写代码的“代码匠”,而是能够理解代码背后原理的“代码炼金术士”,你的编程视野将因此而开阔,解决问题的能力也将得到质的飞跃。 第一章:初识源代码——程序员的画板 一切的起点,是我们手中那张充满无限可能的“画板”——源代码。在这里,我们用人类能够理解的语言(如C、Python、Java等),描绘出我们想要实现的功能和逻辑。这一章,我们将深入探讨各种编程语言的特性,它们如何用不同的语法和结构来表达思想,以及为什么选择某种语言往往取决于项目的需求和程序员的偏好。我们将学习如何清晰、高效地编写代码,如何遵循编码规范,如同画家精心挑选颜料和构图,为接下来的“魔法”打下坚实的基础。你将了解到,一个好的程序员,首先是一个优秀的“代码艺术家”,懂得如何用最简洁、最富有表现力的方式来表达自己的想法。 第二章:语言的翻译官——文本的奇妙旅程 人类的语言,计算机却无法直接理解。源代码,无论多么精妙,都只是文本字符串的集合。要让计算机“读懂”我们的意图,就需要一个称职的“翻译官”。本章,我们将聚焦于源代码到机器指令的转化过程。 词法分析 (Lexical Analysis): 想象一下,一位细心的图书管理员,将一本书中的句子拆分成一个个独立的单词,并为每个单词打上标签。词法分析器就像这位图书管理员,它会逐字逐句地扫描源代码,将连续的字符流分割成有意义的“单词”——即“词法单元”(Tokens),例如关键字(`if`、`while`)、标识符(变量名、函数名)、运算符(`+`、`-`)、字面量(数字、字符串)等等。我们会详细介绍这个过程是如何进行的,以及如何处理各种复杂的语法情况。 语法分析 (Syntax Analysis): 拆分完单词,接下来需要理解句子的结构。语法分析器则扮演着“句法学家”的角色,它会根据编程语言的语法规则,将词法单元组织起来,形成一个具有层级结构的“语法树”(Abstract Syntax Tree, AST)。这棵树清晰地展示了代码的逻辑结构,就像一棵剖析精美的基因图谱,让我们能直观地看到程序的骨架。我们将深入讲解如何构建这棵树,以及它在后续步骤中的重要作用。 语义分析 (Semantic Analysis): 仅仅拥有正确的语法结构是不够的,我们还需要确保程序的“意思”是合乎逻辑的。语义分析器则是一位严谨的“逻辑侦探”,它会检查语法树,验证变量是否已经声明、类型是否匹配、函数调用是否正确等一系列符合编程语言语义的规则。我们会探讨类型检查、作用域规则等关键概念,确保我们编写的程序不仅语法正确,而且在逻辑上也能够“说得通”。 第三章:代码的精雕细琢——优化与转换 将源代码转化为计算机能理解的机器码,并非一步到位。为了让程序运行得更快、更有效率,还需要经过一系列精雕细琢的“优化”过程。本章,我们将揭示这些让代码“脱胎换骨”的魔法。 中间代码生成 (Intermediate Code Generation): 在生成最终的机器码之前,许多编译器会先将程序转化为一种“中间表示”(Intermediate Representation, IR)。这种中间代码是一种比源代码更接近机器指令,但又比机器指令更通用的形式。它极大地简化了优化过程,使得针对不同目标架构的机器码生成变得更加模块化。我们会介绍几种常见的中间代码形式,以及它们如何为后续的优化奠定基础。 代码优化 (Code Optimization): 这一环节是提升程序性能的关键。我们将深入探讨各种经典的优化技术,比如: 常量折叠 (Constant Folding): 将编译时就可以确定的常量表达式直接计算出结果,例如将 `2 + 3` 直接替换为 `5`。 死代码消除 (Dead Code Elimination): 移除那些永远不会被执行的代码,如同理发师修剪掉多余的头发,让程序更“精干”。 循环优化 (Loop Optimization): 针对程序中最常被执行的部分——循环,进行各种优化,例如循环展开、循环不变外提等,如同流水线工人优化操作流程,提升效率。 寄存器分配 (Register Allocation): 巧妙地利用计算机的“快速通道”——寄存器,将频繁使用的数据存储其中,减少对速度较慢的主内存的访问。 机器无关优化与机器相关优化: 我们还将区分在不同目标机器上都可以进行优化的“机器无关优化”,以及需要针对特定处理器架构进行的“机器相关优化”,从而实现跨平台的性能提升。 第四章:与硬件的对话——机器码的诞生 经过重重优化,代码终于要与最底层的硬件进行“对话”。本章,我们将深入探究如何将优化后的中间代码转化为目标机器能够直接执行的机器码。 指令选择 (Instruction Selection): 计算机拥有丰富多样的指令集,就像拥有各种各样的工具。指令选择器会根据中间代码的表示,选择最合适、最高效的机器指令来执行相应的操作。我们将了解不同指令集的特点,以及如何进行高效的指令选择。 指令调度 (Instruction Scheduling): 现代处理器拥有强大的并行处理能力,可以同时执行多条指令。指令调度器则负责重新排列指令的顺序,使其能够最大限度地发挥处理器的并行性,减少“等待”时间。如同交响乐指挥家,协调各个乐器演奏的节奏,使整体乐章流畅而富有力量。 目标代码生成 (Target Code Generation): 这是最后一步,将所有选择和调度好的指令,翻译成特定计算机架构下的二进制机器码。这一过程需要对目标机器的寄存器、内存模型、指令集等有深入的理解。我们将揭示如何生成可执行文件,以及这些二进制代码是如何被加载到内存并最终被 CPU 执行的。 第五章:程序的执行——从二进制到生机勃勃 生成机器码只是程序生命周期的一部分,如何让这些冰冷的二进制指令“活”过来,成为我们看到的动态程序,同样充满智慧。 链接 (Linking): 许多程序并非孤立存在,它们会调用其他模块、库中的函数。链接器就像一位“信息整合师”,它会将程序编译生成的目标代码,与所需的库文件中的代码连接起来,形成一个完整的可执行文件。我们将探讨静态链接和动态链接的区别,以及它们如何影响程序的部署和运行。 加载 (Loading): 当我们双击一个程序时,操作系统会将可执行文件加载到内存中,为程序的运行做好准备。加载器则负责分配内存空间、解析重定位信息、将代码和数据拷贝到内存等一系列操作。 运行时的魔法: 程序一旦加载到内存,CPU 便开始逐条执行机器指令。本章,我们还将触及一些与程序运行紧密相关的概念,例如内存管理、栈和堆的使用、函数调用机制等,让你对程序在内存中的“一举一动”了然于胸。 第六章:程序员的工具箱——构建高效的开发流程 理解编译原理,不仅仅是为了满足好奇心,更是为了提升我们作为程序员的生产力。本章,我们将探讨如何利用我们所学到的知识,来优化我们的开发流程。 选择合适的编译器和选项: 不同的编译器在性能、兼容性等方面各有优势。我们将学习如何选择适合项目需求的编译器,以及如何利用编译器的各种选项来优化编译速度和生成代码的性能。 调试的艺术: 当程序出现 bug 时,理解编译原理能够帮助我们更准确地定位问题。我们还将介绍一些高级的调试技巧,例如利用汇编代码分析,深入理解程序运行的底层细节。 跨平台开发的挑战与机遇: 了解不同目标架构的机器码生成过程,将有助于我们更好地进行跨平台开发,确保程序在不同操作系统和硬件上都能高效运行。 《代码的诞生:程序员的奇幻之旅》,将带你踏上一段前所未有的编程探索之旅。你将不再满足于“知其然”,更会追求“知其所以然”。通过这本书,你将深刻理解代码背后的运行机制,解锁更高级的编程思维,成为一名真正意义上的“代码魔法师”,用你的智慧和创造力,打造出更多令人惊叹的数字世界。准备好了吗?让我们一起,揭开代码的神秘面纱,见证它如何从无形到有形,从抽象到生动,最终绽放出璀璨的光芒!