作者：范志东,张琼声
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
自己动手构造编译系统：编译、汇编与链接试读：
前言
本书适合谁读
本书是一本描述编译系统实现的书籍。这里使用“编译系统”一词，主要是为了与市面上描述编译器实现的书籍进行区分。本书描述的编译系统不仅包含编译器的实现，还包括汇编器、链接器的实现，以及机器指令与可执行文件格式的知识。因此，本书使用“编译系统”一词作为编译器、汇编器和链接器的统称。
本书的目的是希望读者能通过阅读本书清晰地认识编译系统的工作流程，并能自己尝试构造一个完整的编译系统。为了使读者更容易理解和学习编译系统的构造方法，本书将描述的重点放在编译系统的关键流程上，并对工业化编译系统的实现做了适当的简化。如果读者对编译系统实现的内幕感兴趣，或者想自己动手实现一个编译系统的话，本书将非常适合你阅读。
阅读本书，你会发现书中的内容与传统的编译原理教材以及描述编译器实现的书籍有所不同。本书除了描述一个编译器的具体实现外，还描述了一般书籍较少涉及的汇编器和链接器的具体实现。而且本书并非“纸上谈兵”，在讲述每个功能模块时，书中都会结合具体实现代码来阐述模块功能的实现。通过本书读者将会学习如何使用有限自动机构造词法分析器，如何将文法分析算法应用到语法分析过程，如何使用数据流分析进行中间代码的优化，如何生成合法的汇编代码，如何产生二进制指令信息，如何在链接器内进行符号解析和重定位，如何生成目标文件和可执行文件等。
本书的宗旨是为意欲了解或亲自实现编译系统的读者提供指导和帮助。尤其是计算机专业的读者，通过自己动手写出一个编译系统，能加强读者对计算机系统从软件层次到硬件层次的理解。同时，深入挖掘技术幕后的秘密也是对专业兴趣的一种良好培养。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的汇编代码。第1章代码背后
知其然，并知其所以然。——《朱子语类》1.1 从编程聊起
说起编程，如果有人问我们敲进计算机的第一段代码是什么，相信很多人会说出同一个答案——“Hello World！”。编程语言的教材一般都会把这段代码作为书中的第一个例子呈现给读者。当我们按照课本或者老师的要求把它输入到开发环境，然后单击“编译”和“运行”按钮，映入眼帘的那行字符串定会令人欣喜不已！然而激动过后，一股强烈的好奇心可能会驱使我们去弄清一个新的概念——编译是什么？
遗憾的是，一般教授编程语言的老师不会介绍太多关于它的内容，最多会告诉我们：代码只有经过编译，才能在计算机中正确执行。随着知识和经验的不断积累，我们逐渐了解到当初单击“编译”按钮的时候，计算机在幕后做了一系列的工作。它先对源代码进行编译，生成二进制目标文件，然后对目标文件进行链接，最后生成一个可执行文件。即便如此，我们对编译的流程也只有一个模糊的认识。
直到学习了编译原理，才发现编译器原来就是语言翻译程序，它把高级语言程序翻译成低级汇编语言程序。而汇编语言程序是不能被计算机直接识别的，必须靠汇编器把它翻译为计算机硬件可识别的机器语言程序。而根据之前对目标文件和链接器的了解，我们可能猜测到机器语言应该是按照二进制的形式存储在目标文件内部的。可是目标文件到底包含什么，链接后的可执行文件里又有什么？问题貌似越来越多。
图1-1展示了编译的大致工作流程，相信拥有一定编程经验的人，对该图所表达的含义并不陌生。为了让源代码能正常地运行在计算机上，计算机对代码进行了“繁复”的处理。可是，编译器既然是语言翻译程序，为什么不把源代码直接翻译成机器语言，却还要经过汇编和链接的过程呢？图1-1 编译的流程
似乎我们解决了一些疑惑后，总是会有更多的疑惑接踵而来。但也正是这些层出不穷的疑惑，促使我们不断地探究简单问题背后的复杂机制。当挖掘出这些表象下覆盖的问题本质时，可能比首次敲出“Hello World！”程序时还要喜悦。在后面的章节中，将会逐步探讨编译背后的本质，将谜团一一揭开，最终读者自己可动手构造出本书所实现的编译系统——编译器、汇编器与链接器，真正做到“知其然，并知其所以然”。1.2 历史渊源
历史上很多新鲜事物的出现都不是偶然的，计算机学科的技术和知识如此，编译系统也不例外，它的产生来源于编程工作的需求。编程本质上是人与计算机交流，人们使用计算机解决问题，必须把问题转化为计算机所能理解的方式。当问题规模逐渐增大时，编程的劳动量自然会变得繁重。编译系统的出现在一定程度上降低了编程的难度和复杂度。
在计算机刚刚诞生的年代，人们只能通过二进制机器指令指挥计算机工作，计算机程序是依靠人工拨动计算机控制面板上的开关被输入到计算机内部的。后来人们想到使用穿孔卡片来代替原始的开关输入，用卡片上穿孔的有无表示计算机世界的“0”和“1”，让计算机自动读取穿孔卡片实现程序的录入，这里录入的指令就是常说的二进制代码。然而这种编程工作在现在看起来简直就是一个“噩梦”，因为一旦穿孔卡片的制作出现错误，所有的工作都要重新来过。
人们很快就发现了使用二进制代码控制计算机的不足，因为人工输入二进制指令的错误率实在太高了。为了解决这个问题，人们用一系列简单明了的助记符代替计算机的二进制指令，即我们熟知的汇编语言。可是计算机只能识别二进制指令，因此需要一个已有的程序自动完成汇编语言到二进制指令的翻译工作，于是汇编器就产生了。程序员只需要写出汇编代码，然后交给汇编器进行翻译，生成二进制代码。因此，汇编器将程序员从烦琐的二进制代码中解脱出来。
使用汇编器提高了编程的效率，使得人们有能力处理更复杂的计算问题。随着计算问题复杂度的提高，编程中出现了大量的重复代码。人们不愿意进行重复的劳动，于是就想办法将公共的代码提取出来，汇编成独立的模块存储在目标文件中，甚至将同一类的目标文件打包成库。由于原本写在同一个文件内的代码被分割到多个文件中，那么最终还需要将这些分离的文件拼装起来形成完整的可执行代码。但是事情并没有那么简单，由于文件的模块化分割，文件间的符号可能会相互引用。人们需要处理这些引用关系，重新计算符号的引用地址，这就是链接器的基本功能。链接器使得计算机能自动把不同的文件模块准确无误地拼接起来，使得代码的复用成为可能。
图1-2描述的链接方式称为静态链接，但这种方式也有不足之处。静态链接器把公用库内的目标文件合并到可执行文件内部，使得可执行文件的体积变得庞大。这样做会导致可执行文件版本难以更新，也导致了多个程序加载后相同的公用库代码占用了多份内存空间。为了解决上述的问题，现代编译系统都引入了动态链接方式（见图1-3）。动态链接器不会把公用库内的目标文件合并到可执行文件内，而仅仅记录动态链接库的路径信息。它允许程序运行前才加载所需的动态链接库，如果该动态链接库已加载到内存，则不需要重复加载。另外，动态链接器也允许将动态链接库的加载延迟到程序执行库函数调用的那一刻。这样做，不仅节约了磁盘和内存空间，还方便了可执行文件版本的更新。如果应用程序模块设计合理的话，程序更新时只需要更新模块对应的动态链接库即可。当然，动态链接的方式也有缺点。运行时链接的方式会增加程序执行的时间开销。另外，动态链接库的版本错误可能会导致程序无法执行。由于静态链接和动态链接的基本原理类似，且动态链接器的实现相对复杂，因此本书编译系统所实现的链接器采用静态链接的方式。图1-2 静态链接图1-3 动态链接
汇编器和链接器的出现大大提高了编程效率，降低了编程和维护的难度。但是人们对汇编语言的能力并不满足，有人设想要是能像写数学公式那样对计算机编程就太方便了，于是就出现了如今形形色色的高级编程语言。这样就面临与当初汇编器产生时同样的问题——如何将高级语言翻译为汇编语言，这正是编译器所做的工作。编译器比汇编器复杂得多。汇编语言的语法比较单一，它与机器语言有基本的对应关系。而高级语言形式比较自由，计算机识别高级语言的含义比较困难，而且它的语句翻译为汇编语言序列时有多种选择，如何选择更好的序列作为翻译结果也是比较困难的，不过最终这些问题都得以解决。高级语言编译器的出现，实现了人们使用简洁易懂的编程语言与计算机交流的目的。1.3 GCC的工作流程
在着手构造编译系统之前，需要先介绍编译系统应该做的事情，而最具参考价值的资料就是主流编译器的实现。GNU的GCC编译器是工业化编译器的代表，因此我们先了解GCC都在做什么。
我们写一个最简单的“HelloWorld”程序，代码存储在源文件hello.c中，源文件内容如下：#include
如果将hello.c编译并静态链接为可执行文件，使用如下gcc命令直接编译即可：$gcc hello.c –o hello -static
hello即编译后的可执行文件。
如果查看GCC背后的工作流程，可以使用--verbose选项。$gcc hello.c –o hello –static --verbose
输出的信息如下：$cc1 -quiet hello.c -o hello.s$as -o hello.o hello.s$collect2 -static -o hello \ crt1.o crti.o crtbeginT.o hello.o \ --start-group libgcc.a libgcc_eh.a libc.a --end-group \ crtend.o crtn.o
为了保持输出信息的简洁，这里对输出信息进行了整理。可以看出，GCC编译背后使用了cc1、as、collect2三个命令。其中cc1是GCC的编译器，它将源文件hello.c编译为hello.s。as是汇编器命令，它将hello.s汇编为hello.o目标文件。collect2是链接器命令，它是对命令ld的封装。静态链接时，GCC将C语言运行时库（CRT）内的5个重要的目标文件crt1.o、crti.o、crtbeginT.o、crtend.o、crtn.o以及3个静态库libgcc.a、libgcc_eh.a、libc.a链接到可执行文件hello。此外，cc1在对源文件编译之前，还有预编译的过程。
因此，我们从预编译、编译、汇编和链接四个阶段查看GCC的工作细节。1.3.1 预编译
GCC对源文件的第一阶段的处理是预编译，主要是处理宏定义和文件包含等信息。命令格式如下：$gcc –E hello.c –o hello.i
预编译器将hello.c处理后输出到文件hello.i，hello.i文件内容如下：# 1 "hello.c"# 1 "
比如文件包含语句#include
我们可以将预编译的工作简单地理解为源码的文本替换，即将宏定义的内容替换到宏的引用位置。当然，这样理解有一定的片面性，因为要考虑宏定义中使用其他宏的情况。事实上预编译器的实现机制和编译器有着很大的相似性，因此本书描述的编译系统将重点放在源代码的编译上，不再独立实现预编译器。然而，我们需要清楚的事实是：一个完善的编译器是需要预编译器的。1.3.2 编译
接下来GCC对hello.i进行编译，命令如下：$gcc –S hello.i –o hello.s
编译后产生的汇编文件hello.s内容如下： .file "hello.c" .section .rodata.LC0: .string "Hello World!" .text.globl main .type main, @functionmain: pushl %ebp movl %esp, %ebp andl $-16, %esp subl $16, %esp movl $.LC0, %eax movl %eax, (%esp) call printf movl $0, %eax leave ret .size main, .-main .ident "GCC: (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5" .section .note.GNU-stack,"",@progbits
GCC生成的汇编代码的语法是AT&T格式，与Intel格式的汇编有所不同（若要生成Intel格式的汇编代码，使用编译选项“-masm=intel”即可）。比如立即数用“$”前缀，寄存器用“%”前缀，内存寻址使用小括号等。区别最大的是，AT&T汇编指令的源操作数在前，目标操作数在后，这与Intel汇编语法正好相反。本书会在后续章节中详细描述这两种汇编语法格式的区别。
不过我们仍能从中发现高级语言代码中传递过来的信息，比如字符串“Hello World！”、主函数名称main、函数调用call printf等。1.3.3 汇编
接着，GCC使用汇编器对hello.s进行汇编，命令如下：$gcc –c hello.s –o hello.o
生成的目标文件hello.o，Linux下称之为可重定位目标文件。目标文件无法使用文本编辑器直接查看，但是我们可以使用GCC自带的工具objdump命令分析它的内容，命令格式如下：$objdump –sd hello.o
输出目标文件的主要段的内容与反汇编代码如下：hello.o: file format elf32-i386Contents of section .text: 0000 5589e583 e4f083ec 10b80000 00008904 U............... 0010 24e8fcff ffffb800 000000c9 c3 $............Contents of section .rodata:0000 48656c6c 6f20576f 726c6421 00 Hello World!.Contents of section .comment: 0000 00474343 3a202855 62756e74 752f4c69 .GCC: (Ubuntu/Li 0010 6e61726f 20342e34 2e342d31 34756275 naro 4.4.4-14ubu 0020 6e747535 2920342e 342e3500 ntu5) 4.4.5.Disassembly of section .text:00000000
从数据段二进制信息的ASCII形式的显示中，我们看到了汇编语言内定义的字符串数据“Hello World！”。代码段的信息和汇编文件代码信息基本吻合，但是我们发现了很多不同之处。比如汇编文件内的指令“movl$.LC0，%eax”中的符号.LC0的地址（字符串“Hello World！”的地址）被换成了0。指令“call printf”内符号printf的相对地址被换成了0xfffffffc，即call指令操作数部分的起始地址。
这些区别本质来源于汇编语言符号的引用问题。由于汇编器在处理当前文件的过程中无法获悉符号的虚拟地址，因此临时将这些符号地址设置为默认值0，真正的符号地址只有在链接的时候才能确定。1.3.4 链接
使用GCC命令进行目标文件链接很简单：gcc hello.o –o hello
GCC默认使用动态链接，如果要进行静态链接，需加上-static选项：gcc hello.o –o hello –static
这样生成的可执行文件hello便能正常执行了。
我们使用objdump命令查看一下静态链接后的可执行文件内的信息。由于可执行文件中包含了大量的C语言库文件，因此这里不便将文件的所有信息展示出来，仅显示最终main函数的可执行代码。080482c0
从main函数的可执行代码中，我们发现汇编过程中描述的无法确定的符号地址信息在这里都被修正为实际的符号地址。如“Hello World！”字符串的地址为0x080ae828，printf函数的地址为0x08048dd0。这里符号_IO_printf与printf完全等价，call指令内部相对地址为0x000afa，正好是printf地址相对于call指令下条指令起始地址0x080482d6的偏移。1.4 设计自己的编译系统
根据以上描述，我们意欲构造一个能将高级语言转化为可执行文件的编译系统。高级语言语法由我们自己定义，它可以是C语言语法，也可以是它的一个子集，但是无论如何，该高级语言由我们根据编程需要自行设计。另外，我们要求生成的可执行文件能正常执行，无论它是Linux系统的ELF可执行文件，还是Windows系统的PE文件，而本书选择生成Linux系统的ELF可执行文件。正如本章开始所描述的，我们要做的就是：自己动手完成当初单击“编译”按钮时计算机在背后做的事情。
然而在真正开工之前，我们需要承认一个事实——我们是无法实现一个像GCC那样完善的工业化编译器的。因此必须降低编译系统实现的复杂度，确保实际的工作在可控的范围内。本书对编译系统的实现做了如下修改和限制：
1）预编译的处理。如前所述，预编译作为编译前期的工作，其主要的内容在于宏命令的展开和文本替换。本质上，预编译器也需要识别源代码语义，它与编译器实现的内容十分相似。通过后面章节对编译器实现原理的介绍，我们也能学会如何构造一个简单的预编译器。因此，在高级语言的文法设计中，本书未提供与预编译处理相关的语法，而是直接对源代码进行编译，这样使得我们的精力更关注于编译器的实现细节上。
2）一遍编译的方式。编译器的设计中可以对编译器的每个模块独立设计，比如词法分析器、语法分析器、中间代码优化器等。这样做可能需要对源代码进行多遍的扫描，虽然编译效率相对较低，但是获得的源码语义信息更完善。我们设计的编译系统目标非常直接——保证编译系统输出正确的可执行文件即可，因此采用一遍编译的方式会更高效。
3）高级语言语法。为了方便大多数读者对文法分析的理解，我们参考C语言的语法格式设计自己的高级语言。不完全实现C语言的所有语法，不仅可以减少重复的工作量，还能将精力重点放在编译算法的实现上，而不是复杂的语言语法上。因此在C语言的基础上，我们删除了浮点类型和struct类型，并将数组和指针的维数简化到一维。
4）编译优化算法。编译器内引入了编译优化相关的内容，考虑到编译优化算法的多样性，我们挑选了若干经典的编译优化算法作为优化器的实现。通过对数据流问题优化算法的实现，可以帮助理解优化器的工作原理，对以后深入学习编译优化算法具有引导意义。
5）汇编语言的处理。本书的编译器产生的汇编指令属于Intel x86处理器指令集的子集，虽然这间接降低了汇编器实现的复杂度，但是不会影响汇编器关键流程的实现。另外，编译器在产生汇编代码之前已经分析了源程序的正确性，生成的汇编代码都是合法的汇编指令，因此在汇编器的实现过程中不需要考虑汇编语言的词法、语法和语义错误的情况。
6）静态链接方式。本书的编译系统实现的链接器采用静态链接的方式。这是因为动态链接器的实现相对复杂，而且其与静态链接器处理的核心问题基本相同。读者在理解了静态链接器的构造的基础上，通过进一步的学习也可以实现一个动态链接器。
7）ELF文件信息。除了ELF文件必需的段和数据，我们把代码全部存放在“.text”段，数据存储在“.data”段。按照这样的文件结构组织方式，不仅能保证二进制代码正常执行，也有助于我们更好地理解ELF文件的结构和组织。
综上所述，我们所做的限制并没有删除编译系统关键的流程。按照这样的设计，是可以允许一个人独立完成一个较为完善的编译系统的。1.5 本章小结
本章从编程最基本的话题聊起，描述了初学者接触程序时可能遇到的疑惑，并从编程实践经验中探索代码背后的处理机制。然后，使用最简单的“Hello World！”程序展现主流编译器GCC对代码的处理流程。最后，我们在工业化编译系统的基础上做了一定的限制，提出了本书编译系统需要实现的功能。在接下来的章节中，会对本书中编译系统的设计和实现细节详细阐述。第2章编译系统设计
麻雀虽小，五脏俱全。——《围城》
一个完善的工业化编译系统是非常复杂的，为了清晰地描述它的结构，理解编译系统的基本流程，不得不对它进行“大刀阔斧”地删减。这为自己动手实现一个简单但基本功能完整的编译系统提供了可能。虽然本书设计的是简化后的编译系统，但保留了编译系统的关键流程。正所谓“麻雀虽小，五脏俱全”，本章从全局的角度描述了编译系统的基本结构，并按照编译、汇编和链接的流程来介绍其设计。2.1 编译程序的设计
编译器是编译系统的核心，主要负责解析源程序的语义，生成目标机器代码。一般情况下，编译流程包含词法分析、语法分析、语义分析和代码生成四个阶段。符号表管理和错误处理贯穿于整个编译流程。如果编译器支持代码优化，那么还需要优化器模块。
图2-1展示了本书设计的优化编译器的结构，下面分别对上述模块的实现方案做简单介绍。图2-1 编译器结构2.1.1 词法分析
编译器工作之前，需要将用高级语言书写的源程序作为输入。为了便于理解，我们使用C语言的一个子集定义高级语言，本书后续章节的例子都会使用C语言的一些基本语法作为示例。现在假定我们拥有一段使用C语言书写的源程序，词法分析器通过对源文件的扫描获得高级语言定义的词法记号。所谓词法记号（也称为终结符），反映在高级语言语法中就是对应的标识符、关键字、常量，以及运算符、逗号、分号等界符。见图2-2。图2-2 词法分析功能
例如语句：var2=var1+100;
该语句包含了6个词法记号，它们分别是：“var2”“=”“var1”“+”“100”和分号。
对词法分析器的要求是能正常识别出这些不同形式的词法记号。词法分析器的输入是源代码文本文件内一长串的文本内容，那么如何从文本串中分析出每个词法记号呢？为了解决这个问题，需要引入有限自动机的概念。
有限自动机能解析并识别词法记号，比如识别标识符的有限自动机、识别常量的有限自动机等。有限自动机从开始状态启动，读入一个字符作为输入，并根据该字符选择进入下一个状态。继续读入新的字符，直到遇到结束状态为止，读入的所有字符序列便是有限自动机识别的词法记号。
图2-3描述了识别标识符的有限自动机。C语言标识符的定义是：一个不以数字开始的由下划线、数字、字母组成的非空字符串。图中的自动机从0号状态开始，读入一个下划线或者字母进入状态1，状态1可以接受任意数量的下划线、字母和数字，同时状态1也是结束状态，一旦它读入了其他异常字符便停止自动机的识别，这样就可以识别任意一个合法的标识符。如果在非结束状态读入了异常的字符，意味着发生了词法错误，自动机停止（当然，上述标识符的有限自动机不会出现错误的情况）。图2-3 标识符有限自动机
我们以赋值语句“var2=var1+100；”中的变量var2为例来说明有限自动机识别词法记号的工作过程。
识别var2的自动机状态序列和读入字符的对应关系如表2-1所示，结束状态之前识别的字符序列即为合法的标识符。表2-1 自动机状态序列
使用有限自动机，可以识别出自定义语言包含的所有词法记号。把这些词法记号记录下来，作为下一步语法分析的输入。如果使用一遍编译方式，就不用记录这些词法记号，而是直接将识别的词法记号送入语法分析器进行处理。2.1.2 语法分析
词法分析器的输入是文本字符串，语法分析器的输入则是词法分析器识别的词法记号序列。语法分析器的输出不再是一串线性符号序列，而是一种树形的数据结构，通常称之为抽象语法树。见图2-4。图2-4 语法分析功能
继续前面赋值语句的例子，我们可以先看看它可能对应的抽象语法树，如图2-5所示。图2-5 抽象语法树示例
从图2-5中可以看出，所有的词法记号都出现在树的叶子节点上，我们称这样的叶子节点为终结符。而所有的非叶子节点，都是对一串词法记号的抽象概括，我们称之为非终结符，可以将非终结符看作一个单独的语法模块（抽象语法子树）。其实，整个源程序是一棵完整的抽象语法树，它由一系列语法模块按照树结构组织起来。语法分析器就是要获得源程序的抽象语法树表示，这样才能让编译器具体识别每个语法模块的含义，分析出程序的整体含义。
在介绍语法分析器的工作之前，需要先获得高级语言语法的形式化表示，即文法。文法定义了源程序代码的书写规则，同时也是语法分析器构造抽象语法树的规则。如果要定义赋值语句的文法，一般可以表达成如下产生式的形式：
<赋值语句>=>标识符等号<表达式>分号
被“<>”括起来的内容表示非终结符，终结符直接书写即可，上式可以读作“赋值语句推导出标识符、等号、表达式和分号”。显然，表达式也有相关的文法定义。根据定义好的高级语言特性，可以设计出相应的高级语言的文法，使用文法可以准确地表达高级语言的语法规则。
有了高级语言的文法表示，就可以构造语法分析器来生成抽象语法树。在编译原理教材中，描述了很多的文法分析算法，有自顶向下的LL（1）分析，也有自底向上的算符优先分析、LR分析等。其中最常使用的是LL（1）和LR分析。相比而言，LR分析器能力更强，但是分析器设计比较复杂，不适合手工构造。我们设计的高级语言文法，只要稍加约束便能使LL（1）分析器正常工作，因此本书采用LL（1）分析器来完成语法分析的工作。递归下降子程序作为LL（1）算法的一种便捷的实现方式，非常适合手工实现语法分析器。
递归下降子程序的基本原则是：将产生式左侧的非终结符转化为函数定义，将产生式右侧的非终结符转化为函数调用，将终结符转化为词法记号匹配。例如前面提到的赋值语句对应的子程序的伪代码大致是这样的。void 赋值语句(){ match(标识符); match(等号); 表达式(); match(分号);}
每次对子程序的调用，就是按照前序的方式对该抽象语法子树的一次构造。例如在构造赋值语句子树时，会先构造“赋值语句”根节点，然后依次匹配标识符、等号子节点。当遇到下一个非终结符时，会进入对应的“表达式”子程序内继续按照前序方式构造子树的子树。最后匹配当前子程序的最后一个子节点，完成“赋值语句”子树的构造。整个语法分析就是按照这样的方式构造“程序”树的一个过程，一旦在终结符匹配过程中出现读入的词法记号与预期的词法记号不吻合的情况，便会产生语法错误。
在实际语法分析器实现中，并不一定要显式地构造出抽象语法树。递归下降子程序实现的语法分析器，使得抽象语法树的语法模块都蕴含在每次子程序的执行中，即每次子程序的正确执行都表示识别了对应的语法模块。因此，可以在语法分析子程序中直接进行后续的工作，如语义分析及代码生成。2.1.3 符号表管理
符号表是记录符号信息的数据结构，它使用按名存取的方式记录与符号相关的所有编译信息。编译器工作时，少不了符号信息的记录和更新。在本书定义的高级语言中，符号存在两种形式：变量和函数。前者是数据的符号化形式，后者是代码的符号化形式。语义分析需要根据符号检测变量使用的合法性，代码生成需要根据符号产生正确的地址，因此，符号信息的准确和完整是进行语义分析和代码生成的前提。见图2-6。图2-6 符号表管理功能
对于变量符号，需要在符号表中记录变量的名称、类型、区分变量的声明和定义的形式，如果变量是局部变量，还需要记录变量在运行时栈帧中的相对位置。例如以下变量声明语句：extern int var;
该语句声明了一个外部的全局变量，记录变量符号的数据结构除了保存变量的名称“var”之外，还需要记录变量的类型“int”，以及变量是外部变量的声明形式“extern”。
对于函数符号，需要在符号表中记录函数的名称、返回类型、参数列表，以及函数内定义的所有局部变量等。例如下面的函数定义代码：int sum(int a,int b){ int c; c=a+b; return c;}
符号表应该记录函数的返回类型“int”、函数名“sum”、参数列表“int，int”。函数的局部变量除了显式定义的变量“c”之外，还暗含参数变量“a”和“b”。
由于局部变量的存在，符号表必须考虑代码作用域的变化。函数内的局部变量在函数之外是不可见的，因此在代码分析的过程中，符号表需要根据作用域的变化动态维护变量的可见性。2.1.4 语义分析
编译原理教材中，将语言的文法分为4种：0型、1型、2型、3型，并且这几类文法对语言的描述能力依次减弱。其中，3型文法也称为正规文法，词法分析器中有限自动机能处理的语言文法正是3型文法。2型文法也称为上下文无关文法，也是目前计算机程序语言所采用的文法。顾名思义，程序语言的文法是上下文无关的，即程序代码语句之间在文法层次上是没有关联的。例如在分析赋值语句时，LL（1）分析器无法解决“被赋值的对象是已经声明的标识符吗？”这样的问题，因为语法分析只关心程序语言语法形式的正确性，而不考虑语法模块上下文之间联系的合法性。
然而实际的情况是，程序语言的语句虽然形式上是上下文无关的，但含义上却是上下文相关的。例如：不允许使用一个未声明的变量，不允许函数实参列表和形参列表不一致，不允许对无法默认转换的类型进行赋值和运算，不允许continue语句出现在循环语句之外等，这些要求是语法分析器不能完成的。
根据本书设计的程序语言文法，编译器的语义分析模块（见图2-7）处理如下类似问题：图2-7 语义分析功能
1）变量及函数使用前是否定义？
2）break语句是否出现在循环或switch-case语句内部？
3）continue语句是否出现在循环内部？
4）return语句返回值的类型是否与函数返回值类型兼容？
5）函数调用时，实参列表和形参列表是否兼容？
6）表达式计算及赋值时，类型是否兼容？
语义分析是编译器处理流程中对源代码正确性的最后一次检查，只要源代码语义上没有问题，编译器就可以正常引导目标代码的生成。2.1.5 代码生成
代码生成是编译器的最后一个处理阶段，它根据识别的语法模块翻译出目标机器的指令，比如汇编语言，这一步称为使用基于语法制导的方式进行代码生成。见图2-8。图2-8 代码生成功能
为了便于理解，本书采用常见的Intel格式汇编语言程序作为编译器的输出。继续引用赋值语句“var2=var1+100；”作为例子，若将之翻译为汇编代码，其内容可能是：mov eax,[var1]mov ebx,100add eax,ebxmov [tmp],eaxmov eax,[tmp]mov [var2],eax
参考图2-5中的两个非叶子节点，它们分别对应了表达式语法模块和赋值语句语法模块。上面汇编代码的前4行表示将var1与100的和存储在临时变量tmp中，是对表达式翻译的结果。最后两行表示将临时变量tmp复制到var2变量中，是对赋值语句的翻译结果。根据自定义语言的语法，需要对如下语法模块进行翻译：
1）表达式的翻译。
2）复合语句的翻译。
3）函数定义与调用的翻译。
4）数据段信息的翻译。2.1.6 编译优化
现代编译器一般都包含优化器，优化器可以提高生成代码的质量，但会使代码生成过程变得复杂。一般主流的工业化编译器会按照如图2-9所示结构进行设计。
现代编译器设计被分为前端、优化器和后端三大部分，前端包含词法分析、语法分析和语义分析。后端的指令选择、指令调度和寄存器分配实际完成代码生成的工作，而优化器则是对中间代码进行优化操作。实现优化器，必须设计编译器的中间代码表示。中间代码的设计没有固定的标准，一般由编译器设计者自己决定。图2-9 现代编译器结构
由于中间代码的存在，使得语法制导翻译的结果不再是目标机器的代码，而是中间代码。按照我们自己设计的中间代码形式，上述例子生成的中间代码可能是如下形式：tmp=var1+100var2=tmp
即使优化器没有对这段代码进行处理，编译器的后端也能正确地把这段中间代码翻译为目标机制指令。根据指令选择和寄存器分配算法，得到的目标机器指令可能如下：mov eax,[var1]add eax,100mov [var2],eax
编译器后端在指令选择阶段会选择更“合适”的指令实现中间代码的翻译，比如使用“add eax，100”实现tmp=var1+100的翻译。在寄存器分配阶段会尽可能地将变量保存在寄存器内，比如tmp一直保存在eax中。
中间代码的抽象程度一般介于高级语言和目标机器语言之间。良好的中间代码形式使得中间代码生成、目标代码生成以及优化器的实现更加简单。我们设计的优化器实现了常量传播、冗余消除、复写传播和死代码消除等经典的编译优化算法。先通过一个简单的实例说明中间代码优化的工作。var1=100;var2=var1+100;
将上述高级语言翻译为中间代码的形式如下：var1=100tmp=var1+100var2=tmp
常量传播优化使编译器在编译期间可以将表达式的结果提前计算出来，因此经过常量传播优化后的中间代码形式如下：var1=100tmp=200var2=200
死代码消除优化会把无效的表达式从中间代码中删除，假如上述代码中只有变量var2在之后会被使用，那么var1和tmp都是无效的计算。因此，消除死代码后，最终的中间代码如下：var2=200
再经过后端将之翻译为汇编代码如下：mov [var2],200
由于本书篇幅及作者水平所限，在不能实现所有的编译优化算法的情况下，选择若干经典的优化算法来帮助读者理解优化器的基本工作流程。
至此，我们简单介绍了高级语言源文件转化为目标机器的汇编代码的基本流程。本书设计的编译器支持多文件的编译，因此编译器会为每个源文件单独生成一份汇编文件，然后通过汇编器将它们转换为二进制目标文件。汇编过程中涉及目标机器的指令格式和可执行文件的内容，为了便于理解汇编器的工作流程，需要提前准备与操作系统和硬件相关的知识。2.2 x86指令格式
编译系统的汇编器需要把编译器生成的汇编语言程序转化为x86格式的二进制机器指令序列，然后将这些二进制信息存储为ELF格式的目标文件。因此需要先了解二进制机器指令的基本结构。
如图2-10所示，在x86的指令结构中，指令被分为前缀、操作码、ModR/M、SIB、偏移量和立即数六个部分。本书设计的编译器生成的汇编指令中不包含前缀，这里暂时不介绍它的含义。操作码部分决定了指令的含义和功能，ModR/M和SIB字节为扩充操作码或者为指令操作数提供各种不同的寻址模式。如果指令含有偏移量和立即数信息，就需要把它们放在指令后边的对应位置。图2-10 x86指令格式
这里使用一个简单的例子与表2-2说明x86指令结构的含义，例如汇编指令：add eax,ebx表2-2 二进制指令编码
查阅Intel的指令手册，当操作数为32位寄存器时，add指令的操作码是0x01或者0x03，它们对应的指令格式是add r/m32，reg和add reg，r/m32。在ModR/M字节的定义中，高两位mod字段为0b11时表示指令的两个操作数都是寄存器，低三位表示r/m操作数寄存器的编号，中间三位表示reg操作数寄存器的编号。Intel定义eax寄存器编号为0b000，ebx寄存器编号为0b011。如果我们采用操作码0x01，reg应该记录ebx的编号0b011，r/m32记录eax编号0b000，mod字段为0b11。因此该指令的ModR/M字节为：11 011 000 => 0xd8
同理，若采用操作码0x03的话，ModR/M字节应该是：11 000 011 => 0xc3
指令不再含有其他信息，因此不存在SIB和偏移量、立即数字段。这样“add eax，ebx”指令就有两种二进制表示形式：0x01d8与0x03c3。
通过这个例子可以得出结论：在汇编器语法分析阶段，应该记录生成的二进制指令需要的信息。指令的名称决定操作码，指令的寻址方式决定ModR/M和SIB字段，指令中的常量决定偏移量和立即数部分。
由于本书设计的编译器所生成的汇编指令的种类有限，因此降低了汇编器对指令信息分析的复杂度，但是还有大量的其他类型的指令需要具体分析，这些内容会在以后章节中阐述。2.3 ELF文件格式
ELF文件格式描述了Linux下可执行文件、可重定位目标文件、共享目标文件、核心转储文件的存储格式。本书设计的编译系统只关心可执行文件和可重定位目标文件的格式，如果要设计动态链接器的话，则还需要了解共享目标文件的内容。
ELF文件信息的一般存储形式如图2-11所示。图2-11 ELF文件
在Linux下，可以使用readelf命令查看ELF文件的信息。如果要查看1.3.3节生成的hello.o的信息，可以使用如下命令查看ELF的所有关键信息：readelf –a hello.o
在ELF文件中，最开始的52个字节记录ELF文件头部的信息，通过它可以确定ELF文件内程序头表和段表的位置及大小。以下列出了hello.o文件头信息。ELF Header: Magic: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 Class: ELF32 Data: 2's complement, little endian Version: 1 (current) OS/ABI: UNIX - System V ABI Version: 0 Type: REL (Relocatable file) Machine: Intel 80386 Version: 0x1 Entry point address: 0x0 Start of program headers: 0 (bytes into file) Start of section headers: 224 (bytes into file) Flags: 0x0 Size of this header: 52 (bytes) Size of program headers: 0 (bytes) Number of program headers: 0 Size of section headers: 40 (bytes) Number of section headers: 11 Section header string table index: 8
紧接着文件头便是程序头表，它记录程序运行时操作系统如何将文件加载到内存，因此只有可执行文件包含程序头表。使用readelf查看1.3.4节静态链接生成的hello文件，可以看到它的程序头表，类型为LOAD的表项表示需要加载的段。以下列出它的程序头表信息。Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align LOAD 0x000000 0x08048000 0x08048000 0x84fd2 0x84fd2 R E 0x1000 LOAD 0x085f8c 0x080cdf8c 0x080cdf8c 0x007d4 0x02388 RW 0x1000 NOTE 0x0000f4 0x080480f4 0x080480f4 0x00044 0x00044 R 0x4 TLS 0x085f8c 0x080cdf8c 0x080cdf8c 0x00010 0x00028 R 0x4 GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x4 GNU_RELRO 0x085f8c 0x080cdf8c 0x080cdf8c 0x00074 0x00074 R 0x1
ELF文件最关键的结构是段表，这里的段表示文件内的信息块，与汇编语言内的段并非同一个概念。段表记录了ELF文件内所有段的位置和大小等信息。在所有的段中，有保存代码二进制信息的代码段、存储数据的数据段、保存段表名称的段表字符串表段和存储程序字符串常量的字符串表段。符号表段记录汇编代码中定义的符号信息，重定位表段记录可重定位目标文件中需要重定位的符号信息。hello.o的段表如下：Section Headers: [Nr] Name Type Addr Off Size ES Flg Lk Inf Al [0] NULL 00000000 000000 000000 00 0 0 0 [1] .text PROGBITS 00000000 000034 00001d 00 AX 0 0 4 [2] .rel.text REL 00000000 000350 000010 08 9 1 4 [3] .data PROGBITS 00000000 000054 000000 00 WA 0 0 4 [4] .bss NOBITS 00000000 000054 000000 00 WA 0 0 4 [5] .rodata PROGBITS 00000000 000054 00000d 00 A 0 0 1 [6] .comment PROGBITS 00000000 000061 00002c 01 MS 0 0 1
试读结束[说明：试读内容隐藏了图片]