作者：庞建民主编
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
编译与反编译技术实战试读：
前言
“编译技术”是从事软件开发和信息安全相关工作的技术人员必须掌握的基础性技术，也是高等院校计算机科学与技术和软件专业的一门必修专业课，这是理论与实践结合非常强的领域，对提升开发人员的技术水平和大学生科学思维的养成、解决实际问题能力具有重要作用。“反编译技术”则是近几年发展起来的新兴技术，许多计算机软件或信息安全从业者非常关心该技术的发展，但目前这方面的书籍较少，与“编译技术”结合起来讲解的书也很少，从实践角度来剖析的更是少见。本书就是在这种需求以及作者在这两方面的科研实践的驱动下诞生的，目的是为计算机软件和信息安全从业者提供编译与反编译技术方面的知识和实战技巧。本书的编写得到了解放军信息工程大学和机械工业出版社的大力支持，在此表示诚挚的谢意。本书中的一些材料来自本书主编主持的国家自然科学基金（项目编号：61472447）、国家“863”（项目编号：2006AA01Z408）、国家重大专项某子课题等项目的研究成果，在此对这些课题的支持表示衷心的感谢！
本书是机械工业出版社2016年4月出版的《编译与反编译技术》（ISBN 978-7-111-53412-9）一书的姊妹篇，配合学习和使用效果更佳。在本书中，作者着力阐述编译与反编译技术及实战方面的相关知识和实战技巧，力图使用通用的语言讲述抽象的原理、技术和实战技能，但限于作者水平，书中难免有错误与欠妥之处，恳请读者批评指正。作者2017年3月第1章 实践的环境与工具
本书致力于通过实践及案例，从正反向两个角度介绍编译系统的一般构造原理和基本实现技术，本章首先对书中内容涉及的环境与工具进行简单介绍，这些工具都是编译与反编译过程中常用的工具。1.1 实践环境概述
在编译过程中所涉及的环境主要是编译环境及工具链，常用的工具有词法分析生成器、语法分析生成器、编译器、汇编器、链接器等。在反编译过程中主要涉及反汇编器、静态或动态的调试与分析工具。下面对近年来流行的编译与反编译工具逐一进行简单介绍。1.2 词法分析生成器LEX
词法分析是编译过程的第一个阶段，其任务就是将输入的各种符号转化成相应的标识符号，转化后的标识符很容易被后续阶段处理。
LEX是LEXical compiler的缩写，是UNIX环境下非常著名的工具，主要功能是生成一个词法分析器的C源码，描述规则采用正则表达式。描述词法分析器的文件*.l经过LEX编译后生成一个lex.yy.c的文件，然后由C编译器编译生成一个词法分析器。
LEX接收用户输入的正则表达式，识别这些表达式并且将输入流转化为匹配这些表达式的字符串。在这些字符串的分界处，用户提供的程序片段被执行。LEX代码文件将正则表达式和程序片段关联，将每一条输入对应到由LEX生成的程序的表达式，且执行相应的代码片段。
为了完成任务，除了需要提供匹配的表达式以外，用户还需要提供其他代码，甚至是由其他生成器产生的代码。用户提供一般程序设计语言的代码片段完成程序识别表达式后的工作。因此，用户自由编写动作代码时，并不影响其编写高级语言代码来匹配字符串表达式。这就避免迫使用户使用字符串语言来进行输入分析时，也必须使用同样的方法来编写字符处理程序，而这样做有时是不合适的。LEX不是完整的语言，它是一个新语言的生成器，可以插入各种不同的被叫作“宿主语言”的程序设计语言中。就像大多数高级语言可以生成在不同计算机硬件上运行的代码一样，LEX可以生成不同的宿主语言。宿主语言用于LEX生成输出代码，也用于用户插入程序片段，这使得LEX适用于不同的环境和不同的使用者。每一个应用程序可以是硬件、适用于该任务的宿主语言、用户背景和局部接口属性的直接结合。现在，LEX唯一支持的宿主语言是C，过去也支持过其他语言。Fortran LEX自身一般运行于UNIX或Linux系统之上，但是LEX生成的代码可以在任何适当的编译器上使用。
LEX将用户输入的表达式和动作代码转换为宿主语言，生成的函数一般名为yylex。yylex识别字符流中的表达式，并且当每一个表达式被检测出来后，输出相应的动作。
LEX的文件结构简单，分为三个部分：
declarations %% translation rules %% auxiliary procedures
分别是声明段、规则段和辅助部分。
1）声明段包括变量、符号常量和正则表达式的声明。希望出现在目标C源码中的代码，用“%{…%}”括起来。比如：
%{ #include
2）规则段是由正则表达式和相应的动作组成的。如
[0-9]+ printf("Int : %s/n",yytext); [0-9]*/.[0-9]+ printf("Float : %s/n",yytext);“[0-9]+”是描述整数的正则表达式，“[0-9]*/.[0-9]+”是描述浮点的正则表达式，后面的printf即为它们对应的动作。
值得注意的是，LEX依次尝试每一个规则，尽可能地匹配最长的输入流，即规则部分具有优先级的概念。比如下面的规则部分
%% A {printf("run");} AA {printf("like ");} AAAA {printf("I ");} %%
对于内容“AAAAAAA”，LEX程序会输出“I like run”，首先匹配最长的4个“A”，之后在剩下的三个“A”中匹配两个“A”，直到最后的一个“A”。可以看出LEX的确按照最长的规则匹配。
3）辅助部分放一些扫描器的其他模块，可以包含用C语言编写的子程序，而这些子程序可以用在前面的动作中，这样就可以达到简化编程的目的。辅助部分也可以在另一个程序文件中编写，最后再链接到一起。生成C代码后，需用C的编译器编译，链接时需要指定链接库。
本书的第3章将更加详细地介绍LEX及其用法。需要说明的是，对于GNU/Linux用户，与UNIX环境中LEX对应的工具是Flex，其具体用法和LEX相似，这里不再赘述。1.3 语法分析生成器YACC
语法分析的任务是分析句子是否符合语法规范。YACC（Yet Another Compiler Compiler）是一个经典的语法分析生成器。YACC最初是由AT&T公司的Steven C.Johnson为UNIX操作系统开发的，后来一些兼容的程序如Berkeley YACC、GNU Bison、MKS YACC和Abraxas YACC陆续出现，它们都是在此基础上做了少许改进或者增强，但是基本概念是相同的。现在YACC也已普遍移植到Windows及其他平台上。
语法分析生成器是一个指定某个格式中的一种语言的语法作为它的输入，并为该语言产生分析过程以作为它的输出的程序。在历史上，语法分析生成器被称作编译–编译程序，这是由于按照规律可将所有的编译步骤作为包含在语法分析程序中的动作来执行。现在的观点是将语法分析程序仅考虑为编译处理的一个部分，所以这个术语也就有些过时了。YACC迄今为止仍是常用的语法分析生成器之一。
作为YACC对说明文件中的“%token NUMBER”声明的对应，YACC坚持定义所有的记号本身，而不是从别的地方引入一个定义，但是却有可能通过在记号声明中的记号名之后书写一个值来指定将赋给记号的数字值。
YACC的输入是巴科斯范式（BNF）表达的语法规则以及语法归约的处理代码，YACC输出的是基于表驱动的编译器，包含输入的语法归约的处理代码部分。
由于所产生的解析器需要词法分析器的配合，因此YACC经常和词法分析器的产生器（通常就是LEX）联合使用，把两部分产生的C程序一并编译。IEEE POSIX P1003.2标准定义了LEX和YACC的功能和需求。
需要指出的是，本书的第4章还有对YACC及其用法更加详细的介绍。1.4 编译器GCC
GCC（GNU Compiler Collection，GNU编译器套件）是由GNU开发的编程语言编译器。它是以GPL许可证发行的自由软件，也是GNU计划的关键部分。GCC原本作为GNU操作系统的官方编译器，现已被大多数类UNIX操作系统（如Linux、BSD、Mac OS X等）采纳为标准的编译器，GCC同样适用于微软的Windows。
GCC原名为GNU C语言编译器（GNU C Compiler），因为它原本只能处理C语言。随着GCC的快速扩展，其可支持C++，后来又能够支持更多编程语言，如Fortran、Pascal、Objective-C、Java、Ada、Go以及各类处理器架构上的汇编语言等，所以改名为GNU编译器套件。（1）前端接口
前端将高级语言源码经过词法分析、语法分析生成与高级语言无关的低级中间层表示GENERIC，然后经过单一化赋值转化为另一种中间表示层GIMPLE，在中间层GIMPLE组建控制流程图，并在GIMPLE上进行一系列优化。然后将其转换为更加便于优化的RTL中间表示层。有了与前端无关的中间表示，GCC的前端将不同的高级编程语言转换成这种中间表示，这就是GCC处理器支持多种编程语言的根本原因。（2）中间接口
中间接口主要在RTL中间表示上进行各种优化，GCC的优化技巧根据版本不同而有很大不同，但都包含了标准的优化算法，如循环优化、公共子表达式删除、指令重排序等。更多的优化方法也在不断地研究中。（3）后端接口
GCC后端对每条RTL通过模板匹配的方法调用对应的汇编模板生成汇编代码。生成的代码因处理器和结构不同而不同，GCC后端为不同的平台提供了描述指令的汇编模板文件，这样就可以实现对不同平台的支持。这个阶段非常复杂，因为必须要考虑GCC可移植平台的处理器指令集的规格与技术细节，解决指令选择和寄存器分配等问题。（4）GCC常用的参数
在使用GCC编译器的时候，必须给出一系列必要的调用参数和文件名称。GCC编译器的调用参数大约有100多个，这里只介绍其中最基本、最常用的参数。具体细节内容可参考GCC Manual。
GCC最基本的用法是：
gcc [options] [filenames]
其中options就是编译器所需要的参数（也称为编译选项），filenames给出相关的文件名称。
-c：只编译，不链接成为可执行文件，编译器只是由输入的.c等源代码文件生成以.o为后缀的目标文件，通常用于编译不包含主程序的子程序文件。
-o output_filename：确定输出文件的名称为output_filename，同时这个名称不能与源文件同名。如果不给出这个选项，GCC就给出预设的可执行文件a.out。
-g：产生符号调试工具（GNU的gdb）所必要的符号信息，要想对源代码进行调试，必须加入这个选项。
-O：对程序进行优化编译、链接。采用这个选项，整个源代码会在编译、链接过程中进行优化处理，这样产生的可执行文件的执行效率可以提高，但是编译、链接的速度相应地要慢一些。
-O2：比-O更好的优化编译、链接，当然整个编译、链接过程会更慢。
-v：GCC执行时执行的详细过程、GCC及其相关程序的版本号。编译程序时加上该选项可以看到GCC搜索头文件/库文件时使用的搜索路径。1.5 编译器LLVM
LLVM是构架编译器的框架系统，由C++编写而成，用于优化以任意程序语言编写的程序的编译时间、链接时间、运行时间以及空闲时间，对开发者保持开放，并兼容已有脚本。LLVM计划启动于2000年，最初由伊利诺伊大学香槟分校的Chris Lattner主持开展。2006年Chris Lattner加盟Apple公司并致力于LLVM在Apple开发体系中的应用。Apple公司也是LLVM计划的主要资助者。
LLVM的命名最早源自于Low Level Virtual Machine（底层虚拟机）的缩写，由于命名带来的混乱，目前LLVM就是该项目的全称。LLVM核心库提供了与编译器相关的支持，可以作为多种语言编译器的后台来使用，能够进行程序语言的编译期优化、链接优化、在线编译优化、代码生成。LLVM的项目是一个模块化和可重复使用的编译器和工具技术的集合。LLVM提供一个现代化的、基于SSA的编译策略，能够同时支持静态和动态的任意编程语言的编译目标。至今为止，LLVM已被应用到许多商业和开源的项目，并被广泛用于学术研究。
LLVM荣获2012年ACM软件系统奖。
对关注编译技术的开发人员，LLVM提供了很多优点：
1）现代化的设计。LLVM的设计是高度模块化的，使得其代码更为清晰和便于排查问题所在。
2）语言无关的中间代码。一方面，这使得通过LLVM能够将不同的语言相互联结起来，也使得LLVM能够紧密地与IDE交互和集成。另一方面，发布中间代码而非目标代码能够在目标系统上更好地发挥其潜能而又不影响可调试性（比如，在目标系统上针对本机的硬件环境产生目标代码，但又能够直接通过中间代码来进行行级调试）。
3）可作为工具和函数库。使用LLVM提供的工具可以比较容易地实现新的编程语言的优化编译器或虚拟机，或为现有的编程语言引入一些更好的优化/调试特性。1.6 反汇编工具IDA
IDA是IDA PRO的简称，是英文Interactive Disassembler的缩写。它是一个世界顶级的交互式反汇编工具，其使用者覆盖了软件安全专家、军事工业和国家安全信息部门、逆向工程学者、黑客等。它是由HEX-RAYS公司开发的，这是一家多年从事将二进制代码反编译到C的软件安全公司，其旗舰产品就是著名的Hex-Rays.Decompiler（IDA的插件）。
IDA有两种可用版本。标准版支持20多种处理器，高级版支持50多种处理器。IDA不存在任何注册机、注册码或破解版，除了测试版和一个4.9的免费版外，网络上能下载的都是包含用户许可证的正版，因为所有的安装包都是OEM版，所以IDA官网不提供软件下载，并且软件也没有注册的选项（完全可以正常使用，当然这也是一种盗版或侵权的行为，对此IDA公司会采取严厉打击措施）。
IDA的界面比其他反汇编工具界面更加专业，它提供了很多选项并允许用户自己编写插件。它的优点是可以更好地反汇编和进行更深层的分析，而缺点是使用更困难。1.7 反汇编工具OllyICE
OllyICE是一种具有可视化界面的32位汇编分析调试器，是一个动态追踪调试工具，利用IDA与SoftICE结合的思想在Ring3级上进行调试，容易上手，已代替SoftICE成为当今最流行的调试解密工具，同时还支持插件扩展功能，是目前最强大的动态调试工具。1.8 仿真与分析工具QEMU
QEMU是一套由Fabrice Bellard所编写的以GPL许可证分发源码的模拟处理器，在GNU/Linux平台上使用广泛。Bochs、PearPC等与其类似，但不具备其许多特性，比如高速度及跨平台的特性，通过KQEMU这个闭源的加速器，QEMU能模拟至接近真实计算机的速度。
目前，0.9.1及之前版本的QEMU可以使用KQEMU加速器。在QEMU 1.0之后的版本都无法使用KQEMU，但可利用qemu-kvm加速模块，并且加速效果以及稳定性明显好于KQEMU。
QEMU有以下两种主要运作模式：
1）进程级模拟模式。在这种模式下，QEMU能以二进制翻译的方式启动那些为不同处理器编译的Linux可执行程序。典型的程序是Wine及Dosemu。
2）系统级模拟模式。QEMU能模拟整个计算机系统，包括中央处理器及其他周边设备。它使得为跨平台编写的程序进行测试及除错工作变得容易。也能用来在一台主机上虚拟数台不同虚拟计算机。
该软件的优点有：
·默认支持多种架构。可以模拟IA 32、AMD 64、MIPS、SPARC、PowerPC、龙芯等多种架构。
·可扩展，可自定义新的指令集。
·开源，可移植，仿真速度快。
·在支持硬件虚拟化的x86架构上可以使用KVM加速配合内核ksm大页面备份内存，速度稳定，远超过VMware ESX。
·可以在其他操作系统平台上运行Linux程序。
·可以存储及还原运行状态。
·可以支持虚拟网卡等多种外设。
该软件的缺点有：
·对微软视窗及某些主机操作系统的支持不完善（某些模拟的系统仅能运行）。
·对不常用的架构的支持不完善。
·除非使用KQEMU加速器，否则其模拟速度仍不及其他虚拟软件，如VMware。
·比其他模拟软件难安装及使用。1.9 动态分析工具TEMU
TEMU是动态分析工具BitBlaze的一个组件，是一个基于系统仿真器QEMU开发的动态二进制分析工具，以QEMU为基础运行一个完整的系统（包括操作系统和应用程序），并对二进制代码的执行进行跟踪和分析。
TEMU提供以下功能：
1）动态污点分析。TEMU能够对整个系统进行动态污点分析，把一些信息标记为污点（如键盘事件、网络输入、内存读写、函数调用、指令等），并在系统内进行污点传播。这个特性可为符号执行提供插件形式的工具。许多分析都需要对二进制代码进行细粒度的分析，而基于QEMU的全系统模拟器确保了细粒度的分析。
2）获取操作系统视图。操作系统中提取的信息如进程和文件对很多分析都是很重要的。TEMU可以使用这些信息决定当前执行的是哪个进程和模块、调用的API和参数，以及文件的存取位置。全系统的视图使我们能够分析操作系统内核以及多个进程间的交互，而许多其他的二进制分析工具（如Valgrind、DynamoRIO、Pin）只提供了一个局部的视图（如单个进程的信息）。这对于分析恶意代码更为重要，因为许多攻击涉及多个进程，而且诸如rootkits的内核攻击变得越来越普遍。
3）深度行为分析。TEMU能够分析二进制文件和操作环境的交互，如API调用序列、边界内存位置的访问。通过标记输入为污点，TEMU能够进行输入和输出之间的关系分析。并且，全系统仿真器有效地隔离了分析组件和待分析代码。因此，待分析代码更难干扰分析结果。
TEMU由C和C++实现。性能要求高的代码由C实现，而面向分析的代码由C++编写，以便很好地利用C++STL中的抽象数据类型和类型检查。1.10 本章小结
本章简要介绍了阅读本书所需要的实践环境，主要有词法分析生成器LEX、语法分析生成器YACC、编译器GCC和LLVM、反汇编工具IDA和OllyICE、仿真与分析工具QEMU、动态分析工具TEMU等。在第1章简单介绍这些工具，主要是希望读者在开始时就能够在自己的机器上安装这些工具，并能够使用这些工具进行一些简单的实验，某些重要的工具将在后面详细介绍。第2章 编译器实践概述
人与计算机之间的交流也是通过语言进行的，但人类能理解的语言与机器可以理解的语言是不同的，中间需要翻译，因此，相应的编译器诞生了。编译技术所讨论的问题就是如何把符合人类思维方式的意愿（即源程序）翻译成计算机能够理解和执行的形式（即目标程序），而实现从源程序到目标程序转换的程序被称为编译程序或编译器。最早的编译器是20世纪50年代后期的Fortran编译器，该编译器也为后续高级语言和编译器的涌现奠定了基础。与编译技术相反，反编译技术所讨论的问题就是如何把计算机能够理解和执行的形式（目标程序）翻译成符合人类便于理解的形式（源程序或流程图），实现从目标程序到便于人类理解的系列文档的转换程序被称为反编译程序或反编译器。反编译技术起源于20世纪60年代，虽然在时间上只比编译技术晚10年左右，但反编译技术的成熟度却远不如编译技术。半个世纪以来，也涌现了不少实验性的反编译器，如Dcc、Boomerang和IDA的反编译插件Hex_rays等。但这些反编译器都有这样或那样的缺陷，还不能像编译器那样强健。
本章仅对编译器实践方面的知识进行简要阐述，反编译实践方面的概要介绍将在后续章节给出。2.1 编译器、解释器及其工作方式
就目前计算机的硬件发展水平而言，硬件只能识别由0、1字符串组成的机器指令序列，即机器指令程序或目标程序。在计算机发明的早期，计算机只能按照输入的机器指令程序进行简单的计算。但是，机器指令程序不易被人类理解，用它编写程序不仅困难而且还容易出错。于是后来就引入了代替0、1字符串的由助记符号表示的指令，即汇编指令，汇编指令的集合被称为汇编语言，汇编指令序列被称为汇编语言程序。汇编程序实际上与机器语言程序是一一对应的，都要求程序员按照指令工作的方式来思考和解决相关问题，也就是说，两者之间并无本质区别。因此，它们都被称为面向机器的语言或低级语言，以此与更高级的语言相区别，当然，早期并不知道高级别的语言是否能设计和实现。
计算机的发展和普及超乎人们的想象，应用需求的大量增长导致程序员的需求也大幅增长，但是，能够用机器语言或汇编语言编程的人员数量却不多，满足不了这种需求；同时，许多不同领域的科技工作者也想自己动手编写程序来直接解决问题。因此，抽象度更高、功能更强的语言来作为程序设计语言就成为必然，于是就产生了面向各类应用的便于人类理解与运用的程序设计语言，即高级语言。尽管人类可以借助高级语言来编写程序，但计算机硬件真正能够识别和理解的语言还是0、1组成的机器语言，这就需要在高级语言与机器语言之间建立转换系统，使得高级语言能够自动转换为机器语言。也就是说需要若干“翻译”，把各类高级语言翻译成机器语言。程序设计语言通常被分成三个层次：高级语言、汇编语言、机器语言。高级语言可以翻译成机器语言，也可以翻译成汇编语言，这两种翻译都被称为编译。汇编语言到机器语言的翻译称为汇编。编译和汇编属于正向工程，有时还需要将机器语言翻译成汇编语言或高级语言，这通常被称为反汇编或反编译，属于逆向工程范畴。
高级语言的工作方式有两种，一种是编译器工作方式，另一种是解释器工作方式。
在编译器工作方式下，源程序的翻译和翻译后程序的运行处于两个相互独立的阶段。用户输入源程序，编译器对该源程序进行编译，生成目标程序，这个阶段称为编译阶段。目标程序在适当的输入下执行，最终得到运行结果的过程称为运行阶段。
解释器是另一种形式的翻译器。它把翻译和运行结合在一起进行，边翻译源程序，边执行翻译结果，而这种工作方式被称为解释器工作方式。
形象地说，编译器的工作相当于翻译一本原著，原著与源程序对应，译著与目标程序对应，计算机的运行相当于阅读一本译著，这时，原著和翻译人员并不需要在场，译著是主角。解释器的工作相当于在进行现场翻译，外宾和翻译都要在场，翻译一边听外宾讲话，一边翻译给听众，翻译是听众关注的主角。解释器与编译器的最本质区别是：运行目标程序时的控制权在解释器而不是目标程序，也就是说，运行的是解释器，目标程序是解释器的输入。2.2 编译器的结构
目前常用的程序设计语言都已经有很多优秀的编译器，比如C语言有GCC和ICC、C++有G++和I++、Java有JAVAC和GCJ。然而，即使这些常用的程序设计语言，其本身也一直在改变，即不断地完善。因而，实现这些程序设计语言的编译器也需要做出相应的改动。对于程序设计语言自身的改变，有的是为了弥补自身的一些缺陷，如Java语言从设计至今，其体积已经增大了好几倍；有的是为了适应新的软件开发需求，比如为了更容易地开发大型软件等而进行的改善。
除了那些成熟语言的改动会带来编译器软件编程的需要外，新语言的诞生也需要程序员来完成新语言的编译器实现工作。比如，现在不断涌现的各种脚本语言都需要编译器程序员来编写这些语言的编译器或解释器。对于新语言的发明，有的是为了适应特殊领域的编程需要，比如SQL（Structured Query Language）是为关系数据库管理系统专门设计的专用语言；有的是为了更好地利用各种系统资源（尤其是硬件资源），比如OpenCL（Open Computing Language）是为了更好地开发异构平台的计算能力。作为高级语言到目标代码的翻译软件（或者不同语言间的翻译软件）的编译器，对它的编程需求一直都存在。也就是说，总有实现新的编译器或者改动现有编译器的需求存在。
不同的编译器虽然实现方式各异，但编译器的结构却非常相似，通常是按照编译过程的各个阶段来实现相关的程序模块。编译过程中每个阶段工作的逻辑关系如图2-1所示，图中的每个阶段的工作由相关程序模块承担，但其中的符号表管理程序和错误处理程序则贯穿编译过程的各个阶段。这些程序模块构成了编译器的基本结构。图2-1 编译器结构图
通常，编译的阶段又被分成前端和后端两部分。前端是由只依赖于源语言的那些阶段或阶段的一部分组成，往往包含词法分析、语法分析、语义分析和中间代码生成等阶段，当然还包括与这些阶段同时完成的错误处理和独立于目标机器的优化。后端是指编译器中依赖于目标机器的部分，往往只与中间语言有关而独立于源语言。后端包括与目标机器相关的代码优化、代码生成和与这些阶段相伴的错误处理和符号表操作。这种前后端的划分使得编译器的设计更加清晰、合理与高效。
基于同一个前端，重写其后端就可以产生同一种源语言在另一种机器上的编译器，这是为不同类型机器编写编译器的常用做法。反过来，把几种不同的语言编译成同一种中间语言，使得不同的前端都使用同一个后端，进而得到一类机器上的几个编译器，却只取得了有限的成功，其原因在于不同源程序语言的区别较大，使得包容它们的中间语言庞大臃肿，难以得到高效率。但是，在反编译的过程中，设计一种中间语言，将不同体系结构的目标代码先翻译成这种中间语言代码，再由这种中间代码反编译为C代码，则是一种较为有效的途径。2.3 编译器的设计与实现概述
根据不同的用途和侧重点，编译程序可以进一步分类，换句话说，有许多不同种类的编译器变体。譬如：用于帮助程序开发和调试的编译程序称为诊断编译程序，这类编译器可对程序进行详细检查并报告错误；另一类侧重于提高目标代码效率的编译程序称为优化编译程序，这类编译器通常使用多种混合的“变换”来改善程序的性能，但这往往是以编译器的复杂性和编译时间的增加为代价的。通常，将运行编译程序的机器成为宿主机，将运行编译程序所产生的目标代码的机器称为目标机。如果一个编译程序产生不同于其宿主机指令集的机器代码，则称它为交叉编译程序（Cross Compiler）。还有一类编译器，其目标机器可以改变，而不需要重写它的与机器无关的组件，这类编译器称为可再目标编译器（Retargetable Compiler），通常，这类编译器难以生成高效的代码，因为其难以利用特殊情况和目标机器特性。目前，很多编译程序同时提供了调试、优化、交叉编译等多种功能，用户可以通过“编译选项”进行选择。
编译器本身也是一个程序，这个程序是怎么编写的呢？早期人们使用汇编语言编写编译器。虽然用汇编语言编写的编译器代码效率很高，但由于汇编语言编程与高级语言编程相比难度较大，对编译器这种复杂的系统编写起来效率不高，因此，后来人们改用高级语言来编写编译器。随着编译技术的逐步成熟，一些专门的编译器编写工具相继涌现，比较成熟和通用的工具有词法分析器生成器（如LEX）和语法分析器生成器（如YACC）等。还有一些工具，如用于语义分析的语法制导翻译工具、用于目标代码生成的自动的代码生成器、用于优化的数据流工具等。下面简单介绍利用一些工具实现一个新的语言编译器的基本流程。
2.3.1 利用Flex和Bison实现词法和语法分析
在UNIX环境中编写程序，你往往会邂逅神秘的LEX和YACC，而GNU/Linux用户则会邂逅Flex和Bison。
Flex是一个与LEX兼容的词法分析器生成器，可以用它来生成一个新的语言的词法分析器，Flex就是由Vern Paxon实现的一个LEX，使用它既可以节省时间，也可以提高正确性。
Bison是一个与YACC兼容的语法分析器生成器，可以用它来生成一个新的语言的语法分析器，使用它也可以提高正确性并节省开发时间，实际上，Bison是一个可以把符合LALR（1）文法规范的上下文无关文法转换成C语言程序的语法分析器生成器，是一个GNU版本的YACC。
实现一种新语言，需要做的工作主要包括设计文法、进行语法制导的翻译、优化和代码生成，而后续的工作还可以由LLVM的相关工具提供支持。
2.3.2 利用LLVM实现代码优化和代码生成
LLVM是一个包含一系列模块化可重用编译器和工具链技术的项目。LLVM主要的子项目有LLVM Core libraries、Clang、Dragonegg、LLDB等。其中LLVM Core libraries（LLVM核心库）提供了一个不依赖于目标平台的优化器，同时还为许多典型架构的CPU提供了代码生成的支持。这些库是围绕着一个有详细说明的中间代码表示形式（LLVM IR）建立起来的。也就是说，只要能够把待设计的语言翻译成LLVM IR这种中间语言，就可以利用LLVM完成代码优化和代码生成的工作。当然，这要求目标CPU架构必须是LLVM已经支持的，否则就得自己完成代码生成的工作。Clang是一个LLVM自身的C/C++/Objective-C编译器，目标是提供快速的编译。
Dragonegg的功能是把LLVM的优化器、代码生成器和GCC 4.5的分析器结合在一起，这样就使得LLVM能够编译像Ada、Fortran等其他GCC编译器前端支持的语言，且能够拥有一些Clang不支持的C特性（如OpenMP等）。LLDB则是建立在LLVM库和Clang之上的一个非常好的本地调试器。2.4 本章小结
本章首先介绍了编译器和解释器的概念及其工作方式，然后剖析了编译器的结构，对编译器的设计与实现进行了阐述，并对Flex和Bison进行了简要概述，对LLVM及其应用进行了简要介绍，最后给出了基于现有工具的编译器的实现流程。第3章 词法分析器的设计与实现
词法分析是编译过程的第一步，也是编译过程必不可少的步骤。编译过程中执行词法分析的程序称为词法分析器。构造词法分析器有两种方法：一种是用手工方式，即根据识别语言的状态转换图，使用某种高级语言直接编写词法分析器；另一种是利用自动生成工具（如LEX）自动生成词法分析器。本章分别介绍如何手动和自动构造词法分析器。3.1 词法分析器的设计
本节首先介绍词法分析器的功能及其输出的单词符号的表示方式，然后介绍其输入和处理。
3.1.1 词法分析器的功能
词法分析器又叫作扫描器，其功能是从左往右逐个字符地对源程序进行扫描，然后按照源程序的构词规则识别出一个个单词符号，把作为字符串的源程序等价地转化成单词符号串的中间程序。单词符号是程序设计语言中基本的语法单元，通常分为5种：
1）关键字（又称基本字或保留字）：程序设计语言中定义的具有固定意义的英文单词，通常不能用作其他用途，比如C语言中的while、if、for等都是关键字。
2）标识符：用来表示名字的字符串，如变量名、数组名、函数名等。
3）常数：包括各种类型的常数，如整型常数386、实型常数0.618、布尔型常数TRUE等。
4）运算符：又分为算术运算符，如+、-、*、/等；关系运算符，如=、>=、>等；逻辑运算符，如or、not、and等。
5）界符：如“，”“；”“（”“）”“：”等。
在上面所给出的5种单词符号中，关键字、运算符和界符是程序设计语言提前定义好的，因此它们的数量是固定的，通常只有几十个或者上百个。而标识符和常数是程序设计人员根据编程需要按照程序设计语言的规定构造出来的，因此数量即便不是无穷，也是非常大的。
词法分析器输出的单词符号通常用二元式（单词种别，单词符号的属性值）表示。其中：
1）单词种别。单词种别表示单词种类，常用整数编码，这种整数编码又称为种别码。至于一种程序设计语言的单词如何分类、怎样编码，主要取决于技术上的方便。一般来说，基本字可“一字一种”，也可将其全体视为一种；运算符可“一符一种”，也可按运算符的共性分为几种；界符一般采用“一符一种”分法；标识符通常统归为一种；常数可统归为一种，也可按整型、实型、布尔型等分为几种。
2）单词符号的属性值。单词符号的属性值是反映单词特征或者特性的值，是编译中其他阶段所需要的信息。如果一个种别只含有一个单词符号，那么其种别编码就完全代表了自身的值，因此相应的属性值就不需要再单独给出。如果一个种别含有多个单词符号，那么除了给出种别编码之外还应给出单词符号自身的属性值，以便把同一种类的单词区别开来。例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针或者其二进制值作为它自身的值。
3.1.2 输入及其处理
词法分析器的结构如图3-1所示。词法分析器首先将源程序文本输入到一个缓冲区中，该缓冲区称为输入缓冲区，单词符号的识别可以直接在输入缓冲区中进行。但通常情况下为了识别单词的方便，需要对输入的源程序字符串进行预处理。对于许多程序语言来说，空格、制表符、换行符等编辑性字符只有出现在符号常量中时才有意义；注释几乎可以出现在程序中的任何地方。但编辑性字符和注释的存在一般只是为了改善程序的易读性和易理解性，不影响程序本身的语法结构和实际意义，通常在词法分析阶段可以通过预处理将它们删除。因此可以设计一个预处理子程序来完成上述工作，每当词法分析器调用预处理子程序时，其便处理一串固定长度的源程序字符串，并将处理结果放在词法分析器指定的缓冲区中，称为扫描缓冲区。接下来单词符号的识别就可以直接在该扫描缓冲区中进行，而不必考虑其他杂务。图3-1 词法分析器结构图
扫描器对扫描缓冲区进行扫描时通常使用两个指针，即开始指针和搜索指针，其中，开始指针指向当前正在识别的单词的起始位置，搜索指针用于向前搜索以寻找该单词的终点位置，两个指针之间的符号串就是当前已经识别出来的那部分单词。刚开始时，两个指针都指向下一个要识别的单词符号的开始位置，然后，搜索指针向前扫描，直到发现一个单词符号为止，一旦发现一个单词，搜索指针指向该单词的右部，在处理完这个单词以后，两个指针同时指向下一个要识别的单词符号的起始位置。
为了解决程序设计语言中某些单词符号可能存在公共前缀的问题，在进行词法分析时需采用所谓超前搜索技术，也即词法分析器在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别的方式。3.2 词法分析器的手工实现
手工构造词法分析器首先需要将描述单词符号的正规文法或者正规式转化为状态转换图，然后再依据状态转换图进行词法分析器的构造。状态转换图是一个有限方向图，结点代表状态，用圆圈表示；状态之间用箭弧连接，箭弧上的标记（字符）代表射出结点状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态（用双圈表示）。大多数程序语言的单词符号都可以用状态转换图予以识别。具体过程如下：
1）从初始状态出发。
2）读入一个字符。
3）按当前字符转入下一状态。
4）重复步骤2～3直到无法继续转移为止。
在遇到读入的字符是单词的分界符时，若当前状态是终止状态，说明读入的字符组成了一个单词；否则，说明输入字符串不符合词法规则。
这里我们以一个C语言子集作为例子，说明如何基于状态转换图手工编写词法分析器，该语言子集几乎包含了C语言所有的单词符号。主要步骤是，首先给出描述该子集中各种单词符号的词法规则，其次构造其状态转换图，然后根据状态转换图编写词法分析器。
表3-1列出了这个C语言子集的所有单词符号以及它们的种别编码。该语言子集所包含的单词符号有：
1）标识符：以字母、下划线开头的字母、数字和下划线组成的符号串。
2）关键字：标识符的子集，C语言的关键字共有32个（为了测试加入了输入输出函数，共计34个）。
3）无符号十进制整数：由0到9数字组成的字符串。
4）算符和界符：“{”“}”“[”“]”“（”“）”“.”“->”“～”“++”“--”“！”“&”“*”“/”“%”“+”“-”“<<”“>>”“>”“>=”“<”“<=”“==”“！=”“^”“|”“&&”“||”“？”“=”“/=”“*=”“%=”“+=”“-=”“&=”“^=”“|=”“，”“#”“；”“：”，共计44个。表3-1 C语言子集的单词符号及种别编码
下面为产生该C语言子集中所涉及的单词符号的文法的产生式。
1）关键字文法：
keyword→ void | char | int | float | double | short | long | signed | unsigned | struct | union | enum | typedef | sizeof | auto | static | register | extern | const | volatile | return | continue | break | goto | if | else | switch | case | default | for | do | while | scanf | printf
2）标识符文法：
letter→A | … | Z | a | …| z digit→0 | 1 | … | 9 id→letter rid |- rid rid→letter rid |- rid |digit rid | ε
3）无符号整数文法：
digit→0 | 1 | … | 9 digits→digit rdigit rdigit→digit rdigit |ε
4）算符和界符的文法：
op→{ | } | [ | ] | ( | ) | .| -bigger | ~ | +plus | -minus | ! | & | * | / | % | + | - |
依据上述文法可得到如图3-2所示的状态转换图。其中，终态上的星号（*）表示此时还要把超前读出的字符退回，即搜索指针回调一个字符位置。在状态2时，所识别出的标识符应先与表的前34项逐一比较，若匹配，则该标识符是一个保留字，否则就是标识符。如果是标识符，则返回相应的种别编码和标识符本身。在状态4时，将识别的常数种别编码和常数值返回。在状态7、12、16、19、23时，为了识别相应的算符需进行超前搜索。图3-2 对C语言子集进行词法分析的状态转换图
状态转换图非常易于实现，最简单的方法是为每个状态编写一段程序。对于不含回路的分支状态来说，可以用一个switch（）语句或一组if-else语句实现；对于含回路的状态来说，可以让它对应一个while语句。图3-3给出了整个词法分析器的程序设计流程图。图3-3 程序设计流程图
为便于阅读，对下面程序中所涉及的变量和过程进行以下说明：
1）ch字符变量：存放最新读入的源程序字符。
2）strToken字符数组：存放构成单词符号的字符串。
3）void initialization（）子程序：对单词符号设定种别编码。
4）getNextChar（）子程序过程：把下一个字符读入ch中。
5）getbc（）子程序过程：每次调用时，检查ch的字符是否为空白符、回车或者制表符，若是则反复调用getNextChar（），直至ch中读入一非上述符号。
6）concat（）子程序过程：把ch中的字符连接到strToken。
7）isLetter（）、isDigital（）和isUnderline布尔函数：判断ch中字符是否为字母、数字或下划线。
8）reserve_string（）整型函数：对于strToken中的字符串判断它是否为保留字，若它是保留字则给出它的编码，否则返回0。
9）reserve_operator（）整型函数：返回strToken中所识别出的算符和界符编码。
10）retract（）子程序：把搜索指针回调一个字符位置。
11）error（）：出现非法字符：显示出错信息。
对应于图3-2的词法分析器构造如下：
#include
试读结束[说明：试读内容隐藏了图片]