:

    0: 55 push %ebp

    1: 89 e5 mov %esp,%ebp

    3: 83 e4 f0 and 0xfffffff0,%esp

    6: 83 ec 10 sub 0x10,%esp

    9:

    b8 00 00 00 00

    mov

    0x0

    ,%eax

    e: 89 04 24 mov %eax,(%esp)

    11:

    e8 fc ff ff ff

    call

    12

    16: b8 00 00 00 00 mov 0x0,%eax

    1b: c9 leave

    1c: c3 ret

    从数据段二进制信息的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

:

    80482c0: 55 push %ebp

    80482c1: 89 e5 mov %esp,%ebp

    80482c3: 83 e4 f0 and 0xfffffff0,%esp

    80482c6: 83 ec 10 sub 0x10,%esp80482c9: b8 28 e8 0a 08

    mov

    0x80ae828,%eax

    80482ce: 89 04 24 mov %eax,(%esp)80482d1:

    e8 fa 0a 00 00

    call

    8048dd0 <_IO_printf>

    80482d6: b8 00 00 00 00 mov 0x0,%eax

    80482db: c9 leave

    80482dc: c3 ret

    从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,100

    add eax,ebx

    mov [tmp],eax

    mov 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+100

    var2=tmp

    即使优化器没有对这段代码进行处理，编译器的后端也能正确地把

    这段中间代码翻译为目标机制指令。根据指令选择和寄存器分配算法，得到的目标机器指令可能如下：

    mov eax,[var1]

    add eax,100

    mov [var2],eax

    编译器后端在指令选择阶段会选择更“合适”的指令实现中间代码的

    翻译，比如使用“add eax，100”实现tmp=var1+100的翻译。在寄存器分

    配阶段会尽可能地将变量保存在寄存器内，比如tmp一直保存在eax中。

    中间代码的抽象程度一般介于高级语言和目标机器语言之间。良好

    的中间代码形式使得中间代码生成、目标代码生成以及优化器的实现更

    加简单。我们设计的优化器实现了常量传播、冗余消除、复写传播和死

    代码消除等经典的编译优化算法。先通过一个简单的实例说明中间代码

    优化的工作。

    var1=100;

    var2=var1+100;

    将上述高级语言翻译为中间代码的形式如下：

    var1=100

    tmp=var1+100

    var2=tmp常量传播优化使编译器在编译期间可以将表达式的结果提前计算出

    来，因此经过常量传播优化后的中间代码形式如下：

    var1=100

    tmp=200

    var2=200

    死代码消除优化会把无效的表达式从中间代码中删除，假如上述代

    码中只有变量var2在之后会被使用，那么var1和tmp都是无效的计算。因

    此，消除死代码后，最终的中间代码如下：

    var2=200

    再经过后端将之翻译为汇编代码如下：

    mov [var2],200

    由于本书篇幅及作者水平所限，在不能实现所有的编译优化算法的

    情况下，选择若干经典的优化算法来帮助读者理解优化器的基本工作流

    程。

    至此，我们简单介绍了高级语言源文件转化为目标机器的汇编代码

    的基本流程。本书设计的编译器支持多文件的编译，因此编译器会为每

    个源文件单独生成一份汇编文件，然后通过汇编器将它们转换为二进制

    目标文件。汇编过程中涉及目标机器的指令格式和可执行文件的内容，为了便于理解汇编器的工作流程，需要提前准备与操作系统和硬件相关的知识。2.2 x86指令格式

    编译系统的汇编器需要把编译器生成的汇编语言程序转化为x86格

    式的二进制机器指令序列，然后将这些二进制信息存储为ELF格式的目

    标文件。因此需要先了解二进制机器指令的基本结构。

    如图2-10所示，在x86的指令结构中，指令被分为前缀、操作码、ModRM、SIB、偏移量和立即数六个部分。本书设计的编译器生成的

    汇编指令中不包含前缀，这里暂时不介绍它的含义。操作码部分决定了

    指令的含义和功能，ModRM和SIB字节为扩充操作码或者为指令操作

    数提供各种不同的寻址模式。如果指令含有偏移量和立即数信息，就需

    要把它们放在指令后边的对应位置。

    图2-10 x86指令格式

    这里使用一个简单的例子与表2-2说明x86指令结构的含义，例如汇

    编指令：

    add eax,ebx表2-2 二进制指令编码

    查阅Intel的指令手册，当操作数为32位寄存器时，add指令的操作

    码是0x01或者0x03，它们对应的指令格式是add rm32，reg和add reg，rm32。在ModRM字节的定义中，高两位mod字段为0b11时表示指令的

    两个操作数都是寄存器，低三位表示rm操作数寄存器的编号，中间三

    位表示reg操作数寄存器的编号。Intel定义eax寄存器编号为0b000，ebx

    寄存器编号为0b011。如果我们采用操作码0x01，reg应该记录ebx的编

    号0b011，rm32记录eax编号0b000，mod字段为0b11。因此该指令的

    ModRM字节为：

    11 011 000 => 0xd8

    同理，若采用操作码0x03的话，ModRM字节应该是：

    11 000 011 => 0xc3

    指令不再含有其他信息，因此不存在SIB和偏移量、立即数字段。

    这样“add eax，ebx”指令就有两种二进制表示形式：0x01d8与0x03c3。

    通过这个例子可以得出结论：在汇编器语法分析阶段，应该记录生

    成的二进制指令需要的信息。指令的名称决定操作码，指令的寻址方式决定ModRM和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)

    OSABI: 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

    [7] .note.GNU-stack PROGBITS 00000000 00008d 000000 00 0 0 1

    [8] .shstrtab STRTAB 00000000 00008d 000051 00 0 0 1

    [9]

    .symtab

    SYMTAB

    00000000

    000298

    0000a0

    10

    10

    8

    4

    [10].strtab STRTAB 00000000 000338 000015 00 0 0 1

    符号表段是按照表格形式存储符号信息的，我们可以看到主函数和

    printf函数的符号项。Symbol table '.symtab' contains 10 entries:

    Num: Value Size Type Bind Vis Ndx Name

    0: 00000000 0 NOTYPE LOCAL DEFAULT UND

    1: 00000000 0 FILE LOCAL DEFAULT ABS hello.c

    2: 00000000 0 SECTION LOCAL DEFAULT 1

    3: 00000000 0 SECTION LOCAL DEFAULT 3

    4: 00000000 0 SECTION LOCAL DEFAULT 4

    5: 00000000 0 SECTION LOCAL DEFAULT 5

    6: 00000000 0 SECTION LOCAL DEFAULT 7

    7: 00000000 0 SECTION LOCAL DEFAULT 6

    8: 00000000

    29

    FUNC

    GLOBAL

    DEFAULT

    1

    main

    9: 00000000

    0

    NOTYPE

    GLOBAL

    DEFAULT

    UND

    printf

    重定位表也是按照表格形式存储的，很明显，printf作为外部符号

    是需要重定位的。Relocation section '.rel.text' at offset 0x350 contains 2 entries:

    Offset Info Type Sym.Value Sym.Name

    0000000a 00000501 R_386_32 00000000 .rodata00000012

    00000902

    R_386_PC32

    00000000

    printf

    从ELF文件格式的设计中可以看出，可执行文件其实就是按照一定

    标准将二进制数据和代码等信息包装起来，方便操作系统进行管理和使

    用。从文件头可以找到程序头表和段表，从段表可以找到其他所有的

    段。因此，在汇编语言输出目标文件的时候，就需要收集这些段的信

    息，并按照ELF格式组装目标文件。这样做不仅有利于使用操作系统现

    有的工具调试文件信息，也为后期链接器的实现提供了方便。

    另外需要说明的是，对于ELF文件格式的定义，Linux提供了头文件

    描述。在系统目录usrincludeelf.h提供的elf.h头文件中描述了标准ELF

    文件的数据结构的定义，在实现汇编器和链接器的代码中都使用了该头

    文件。2.4 汇编程序的设计

    通过对汇编器已有的了解，可以发现汇编器和编译器的实现非常相

    似。编译器是将高级语言翻译为汇编语言的转换程序，汇编器则是将汇

    编语言翻译为目标机器二进制代码的转换程序。汇编器实际就是汇编语

    言的“编译器”，虽然汇编语言并非高级语言。

    汇编器也包含词法分析、语法分析、语义处理、代码生成四个基本

    流程。但前面讨论过，本书设计的汇编器面向编译器所生成的汇编代

    码，汇编代码的正确性由编译器保证，因此汇编器不需要进行错误检查

    以及语义的正确性检查。本书设计的汇编器结构如图2-12所示。

    相比于编译器，汇编器的工作重点放在目标文件信息的收集和二进

    制指令的生成上。下面分别介绍汇编器的基本模块。图2-12 汇编器结构2.4.1 汇编词法、语法分析

    汇编语言有独立的词法记号，对于汇编词法的分析，只需要构造相

    应的词法有限自动机就可以了。举一个简单的例子：

    mov eax,[ebp-8]

    该指令有8个词法记号，它们分别是：＇mov＇＇eax＇逗号＇[＇＇

    ebp＇＇–＇＇8＇和＇]＇。汇编器的词法分析器将词法记号送到语法分

    析器用于识别汇编语言的语法模块。同样，我们需要构造汇编语言语法

    分析器，在这里可以提前看一下上述汇编指令的抽象语法树，如图2-13

    所示。图2-13 汇编指令抽象语法子树

    图2-13中是简化后的抽象语法树，与编译器类似，语法分析器会在

    非叶子节点处识别语法模块，以产生语义动作。由于汇编器要输出可重

    定位目标文件，因此在语法分析时要收集目标文件的相关信息。比如记

    录代码段和数据段的长度、目标文件符号表的内容、重定位表的内容

    等，这些操作都在语法分析器识别每个语法模块时使用语法制导的方式

    完成。

    另外，汇编器和编译器最大的不同是汇编器需要对源文件进行两遍

    扫描，其根本原因是汇编语言允许符号的后置定义，例如汇编语言常见的跳转指令：

    jmp L

    L:

    很明显，在第一遍分析jmp指令的时候，汇编器并不知道符号L是否

    已经定义。因此，汇编器需要通过第一遍扫描获取符号的信息，在第二

    遍扫描时使用符号的信息。2.4.2 表信息生成

    汇编器的符号表除了记录符号的信息之外，还需要记录段相关的信

    息以及重定位符号的信息，这些信息都是生成可重定位目标文件所必需

    的。

    对于段表的信息，可以在汇编器识别section语法模块时进行处理。

    比如声明代码段的汇编代码及段表信息生成(见图2-14)。

    section .text

    图2-14 段表信息生成

    汇编器的语法分析器只要计算两次section声明之间的地址差，便能

    获得段的长度，从而将段的名称、偏移、大小记录到段表项内。如果规

    定段按照4字节对齐，则需要对段偏移进行扩展，如图2-14所示。

    汇编器的符号表与ELF文件的符号表并非同一个概念。汇编器的符号表来源于汇编语言定义的符号，ELF文件的符号表是汇编器根据需要

    导出的符号信息，如图2-15所示。最明显的一个例子就是使用equ命令

    定义的符号，这个符号对汇编器来说是一个符号，但在ELF文件内，它

    就是一个数字常量，不存在符号信息。

    图2-15 符号表信息生成

    目标文件链接时会重新组织代码段、数据段的位置。这样段内定义

    的所有符号的地址以及引用符号的数据和指令都会产生偏差，这时就重

    新计算符号的地址，修改原来的地址，也就是常说的重定位。重定位一

    般分为两大类：绝对地址重定位和相对地址重定位。在重定位表内，需

    要记录符号重定位相关的所有信息(见图2-16)。图2-16 重定位表信息生成2.4.3 指令生成

    2.2节介绍了x86指令的基本结构。同样，在汇编器语法分析时，需

    要根据指令的语法模块收集这些指令的结构信息。比如操作码、ModRM字段、SIB字段、偏移量、立即数，然后按照指令的结构将上

    述信息写入文件即可。

    首先，指令名和操作码一般是一对多的关系，因此需要根据具体的

    操作数类型或长度来决定操作码的值。按照操作数不同建立一张指令的

    操作码表来执行操作码的查询是一种有效的解决方案。

    其次，有些指令的ModRM字段的reg部分与操作码有关，但不需要

    输出ModRM字段，汇编器需要单独处理这些特殊的指令操作码。另

    外，ModRM字段中包含是否扩展了SIB字段的信息。

    除了正确输出指令的二进制信息外，汇编器在遇到对符号引用的指

    令时还要记录相关重定位信息，比如重定位地址、重定位符号、重定位

    类型等。

    最后，参考之前介绍的ELF文件结构，汇编器将收集到的段信息和

    二进制数据组装到目标文件内。

    至此，根据已描述的汇编器主要工作流程，可以生成标准的ELF可重定位目标文件。那么，如何把这些分散的目标文件合并成我们最终想

    要的可执行文件，便是接下来要介绍的链接器的工作内容。2.5 链接程序的设计

    本书欲设计一个简洁的静态链接器，以满足上述汇编器产生的目标

    文件的链接需求。它的工作内容是把多个可重定位目标文件正确地合并

    为可执行文件，但链接器不是对文件进行简单的物理合并。除了合并同

    类的段外，链接器需要为段分配合适的地址空间，还需要分析目标文件

    符号定义的完整性，同时对符号的地址信息进行解析，最后还有链接器

    最关键的工作——重定位。本书设计的链接器结构如图2-17所示。

    图2-17 链接器结构

    段的地址空间分配除了为加载器提供相应的信息外，还可为段内符

    号地址的计算提供依据。符号解析除了验证符号引用和定义的正确性之

    外，还需要计算出每个符号表内符号的虚拟地址。重定位可以让每个引

    用符号的数据或者代码具有正确的内容，以保证程序的正确性，下面就

    按照这三个方面分别介绍链接器的工作。2.5.1 地址空间分配

    在汇编器生成的目标文件内，是无法确定数据段和代码段的虚拟地

    址的，因此将它们的段地址都设置为0。链接器是这些代码和数据加载

    到内存执行之前的最后一道处理，因此要为它们分配段的基址。

    链接器按照目标文件的输入顺序扫描文件信息，从每个文件的段表

    中提取出各个文件的代码段和数据段的信息。假设可执行文件段加载后

    的起始地址是0x080408000，链接器从该地址开始，就像“摆积木”似的

    将所有文件的同类型段合并，按照代码段、数据段、“.bss”段的顺序依

    次决定每个段的起始地址，此时需要考虑段间对齐产生的偏移以及特殊

    的地址计算方式(参考第5章关于程序头表的描述)。

    图2-18展示了链接器将目标文件a.o和b.o链接为可执行文件ab时，地址空间分配的效果。a.o的数据段大小为0x08字节，代码段大小为0x4a

    字节；b.o的数据段大小为0x04字节，代码段大小为0x21字节。链接后

    的可执行文件ab的数据段大小为0x0c字节，代码段大小为0x6d字节(对

    齐b.o的代码段消耗2字节)。代码段的起始地址为0x08048080，结束地

    址为0x08048080+0x6d=0x080480ed。数据段起始地址为0x080490f0，结

    束地址为0x080490f0+0x0c=0x080490fc。图2-18 地址空间分配2.5.2 符号解析

    如果说地址空间分配是为段指定地址的话，那么符号解析就是为段

    内的符号指定地址。对于一个汇编文件来说，它内部使用的符号分为两

    类：一类来自自身定义的符号，称为内部符号。内部符号在其段内的偏

    移是确定的，当段的起始地址指定完毕后，内部符号的地址按照如下方

    式计算：

    符号地址=符号所在段基址+符号所在段内偏移

    另一类来自其他文件定义的符号，本地文件只是使用该符号，这类

    符号称为外部符号。外部符号地址在本地文件内是无法确定的，但是外

    部符号总定义在其他文件中。外部符号相对于定义它的文件就是内部符

    号了，同样使用前面的方式计算出它的地址，而使用该符号的本地文件

    需要的也是这个地址。

    在重定位目标文件内，符号表记录了符号的所有信息。对于本地定

    义的符号，符号表项记录符号的段内偏移地址。对于外部引用的符号，符号表项标识该符号为“未定义的”。当链接器扫描到定义该外部符号的

    目标文件时，就需要将该外部符号的地址修改为正确的符号地址。最终

    的结果使得所有目标文件内的符号信息，无论是本地定义的还是外部定

    义的都是完整的、正确的。链接器在扫描重定位目标文件的符号表时会动态地维护两个符号集

    合。一个记录所有文件定义的全局符号集合Export，该集合内的所有符

    号允许被其他文件引用。还有一个记录所有文件使用的未定义符号的集

    合Import，该集合内所有符号都来源于其他目标文件。文件扫描完毕

    后，链接器需要验证Import集合是否是Export的子集。如果不是，就表

    明存在未定义的符号。未定义的符号信息是未知的，链接器无法进行后

    续的操作，因而会报错。如果验证成功，则表明所有文件引用的外部符

    号都已定义，链接器才会将已定义的符号信息拷贝到未定义符号的符号

    表项。

    符号解析完毕后，所有目标文件符号表内的所有符号都获得了完

    整、正确的符号地址信息。比如图2-18内的符号var、ext和fun在符号解

    析后的符号地址分别为0x080490f4、0x080490f8和0x080480cc。2.5.3 重定位

    重定位从本质上来说就是地址修正。由于目标文件在链接之前不能

    获取自己所使用符号的虚拟地址信息，因此导致依赖于这些符号的数据

    定义或者指令信息缺失。汇编器在生成目标文件的时候就记录下所有需

    要重定位的信息。链接器获取这些重定位信息，并按照重定位信息的含

    义修改已经生成的代码，使得最终的代码正确、完整。

    之所以称重定位是链接器最关键的操作，主要是因为地址空间分配

    和符号解析都是为重定位做准备的。程序在运行时，段的信息、符号的

    信息都显得“微不足道”，因为CPU只关心文件内的代码和数据。即便如

    此，也不能忽略地址空间分配和符号解析的重要性。既然重定位是对已

    有二进制信息的修改，因此作为链接器需要清楚几件事情：

    1)在哪里修改二进制信息？

    2)用什么信息进行修改？

    3)按照怎样的方式修改？

    这三个问题反映在重定位中对应的三个参数：重定位地址、重定位

    符号和重定位类型。重定位地址在重定位表中没有直接记录，因为在重定位目标文件

    内，段地址还没确定下来，它只记录了重定位位置所在段内的偏移，在

    地址空间分配结束后，我们使用如下公式计算出重定位地址：

    重定位地址=重定位位置所在段基址+重定位位置的段内偏移

    重定位符号记录着被指令或者数据使用的符号信息，比如call指令

    的标号、mov指令使用的变量符号等。在符号解析结束后，重定位符号

    的地址就已经确定了。

    重定位类型决定修改二进制信息的方式，即绝对地址重定位和相对

    地址重定位。

    在确定了重定位符号地址和重定位地址后，根据重定位的类型，链

    接器便可以正确修改重定位地址处的符号地址信息。

    至此，链接器的主要工作流程描述完毕。作为编译系统的最后一个

    功能模块，链接器与操作系统的关系是最密切的，比如它需要考虑页面

    地址对齐、指令系统结构以及加载器工作的特点等。2.6 本章小结

    本章介绍了编译系统的设计，并按照编译、汇编和链接的顺序阐述

    了它们的内部实现。同时，也介绍了x86指令和ELF文件结构等与操作

    系统及硬件相关的知识。

    通过以上的描述，可以了解高级语言如何被一步步转化为汇编语

    言，以及词法分析、语法分析、语义分析、符号表和代码生成作为编译

    器的主要模块，其内部是如何实现的。汇编器在把汇编语言程序转化为

    二进制机器代码时，做了怎样的工作；汇编器的词法和语法分析与编译

    器有何不同；汇编器如何生成二进制指令和目标文件的信息。链接器在

    处理目标文件时是如何进行地址分配、符号解析以及重定位的，它生成

    的可执行文件和目标文件有何不同等。

    通过对这些问题的简要描述，我们对编译系统的工作流程有了全局

    的认识。至于具体的实现细节会在以后的章节中以一个自己动手实现的

    编译系统为例详细进行介绍，下面就让我们开始实现一个真正的编译系

    统吧!第3章 编译器构造

    千举万变，其道一也。

    ——《荀子》

    从本章开始，将详细阐述如何构造一个自定义语言的编译器。在实

    现编译器之前，必须弄清编译器要处理什么样的语言。本书设计的自定

    义语言是C语言的子集。C语言本身容易理解，为多数人熟知，了解C语

    言编译器的实现过程对加深理解C语言的本质大有裨益。此外，选用C

    语言的子集可以有效降低编译器实现的复杂度，将我们的精力重点放在

    编译器实现的流程，而非繁杂、重复的编码工作上。

    参考图2-1描述的编译器的结构，接下来详细阐述编译器每个功能

    模块的实现。3.1 词法分析

    词法分析是编译器处理流程中的第一步，它顺序扫描源文件内的字

    符，通过与词法记号的有限自动机进行匹配，产生各式各样的词法记

    号。图3-1描述了词法分析器的结构，将从源文件内按序扫描字符的功

    能独立出来，称之为扫描器，而与有限自动机进行匹配产生词法记号的

    功能称为解析器。

    图3-1 词法分析器结构

    根据词法分析器的结构，需要解决以下四个问题：

    1)扫描器如何实现源文件字符的扫描，它与普通的读文件有什么

    区别？

    2)词法记号是如何定义的？3)为什么有限自动机可以识别词法记号？

    4)解析器是如何利用有限自动机将一串字符转化为词法记号的？

    带着这四个问题，我们一起探索词法分析器的实现。3.1.1 扫描器

    扫描器读取源文件，按序返回文件内的字符，直到文件结束。简单

    地说，扫描器按序读取源文件内的每一个字节的数据。如图3-2所示，字符a前面的空格＇\x20＇和分号后面的换行符＇\n＇都会被读取。

    图3-2 扫描器功能

    使用C语言的库函数fscanf或者fread可以轻松实现扫描器的功能，代

    码如下：

    1 char Scanner::scan

    (FILEfile){

    2 char ch; 保存读取的字符

    3 if(fscanf

    (file,%c,ch)==EOF){ fscanf读取文件内字符到

    ch

    4 ch=-1; 文件结束时

    ch记录为-1

    5 }

    6 return ch; 返回字符

    这样做可以实现扫描器的基本功能，但是并不高效。因为词法分析

    器每次调用scan函数获取源文件内的下一个字符时，都会产生一次对磁

    盘的读操作，而磁盘的IO操作是比较耗时的。更高效的方式是使用一

    块缓冲区保存后续的多个字符，每次调用scan时首先从缓冲区内按序获

    取字符，只有缓冲区为空时才会读取磁盘重新加载缓冲区。这有点类似

    于Linux文件系统的预读机制。

    使用缓冲区进行文件扫描的算法流程如图3-3所示。图3-3 扫描器算法

    扫描器使用80字节长度的缓冲区，每次从缓冲内读取字符，如果缓

    冲区为空，则从源文件内加载新的80字节数据到缓冲区，直到文件读取

    完毕。算法的实现代码如下：

    1 define BUFLEN 80 缓冲区大小

    2 int lineLen=0; 缓冲区内的数据长度

    3 int readPos=-1; 读取位置4 char line[BUFLEN]; 缓冲区

    5 int lineNum=1; 行号

    6 int colNum=0; 列号

    7 char lastch=ch; 上一个字符

    8 char scan

    (FILEfile){

    9 if(!file) 没有文件

    10 return -1;

    11 if(readPos==lineLen-1){ 缓冲区读取完毕

    12 lineLen=fread

    (line,1,BUFLEN,file); 重新加载缓冲区数据

    13 if(lineLen==0){ 没有数据了

    14 lineLen=1; 数据长度为

    1

    15 line[0]=-1; 文件结束标记

    16 }

    17 readPos=-1; 恢复读取位置

    18 }

    19 readPos++; 移动读取点

    20 char ch=line[readPos]; 获取新的字符

    21 if(lastch=='\n'){ 新行22 lineNum++; 行号累加

    23 colNum=0; 列号清空

    24 }

    25 if(ch==-1){ 文件结束，自动关闭

    26 fclose(file);

    27 file=NULL;

    28 }

    29 else if(ch!='\n') 不是换行

    30 colNum++; 列号递增

    31 lastch=ch; 记录上一个字符

    32 return ch; 返回字符

    33 }

    第9行判断文件指针是否为空，如果为空，则直接返回文件结束符–

    1。

    第11行判断读取位置readPos是否到达缓冲区内数据的末尾，如果

    是，则使用fread库函数重新加载缓冲区，读入BUFLEN字节数据。

    第13行判断fread的返回值，如果lineLen等于0，则说明文件结束。

    此时将lineLen设置为1，并在缓冲区内保存一个特殊字符–1，表示文件

    结束。第17行将readPos重置为–1，从文件中将数据加载到缓冲区后，从缓

    冲区的开始处读字符。

    第19~20行累加读取位置readPos，并将缓冲区内readPos位置的字符

    保存到ch中。

    第21~24行判断，若上一个字符是换行符，则将行号加1，列号清

    0。

    第25~28行判断，若当前字符是文件结束符，则将文件关闭，文件

    指针置为NULL。之后，如果再次调用scan，根据第9行的判断，扫描器

    将仍返回特殊字符–1。

    第29~30行判断，若当前字符不是换行符则将列号加1。

    第31行将扫描过的字符保存到lastch，这样扫描下一个字符时，lastch总是保存了上次扫描到的字符。

    第32行返回当前扫描到的字符。

    通过对扫描器算法scan的不断调用，可以将源文件转化为线性的字

    符序列，为解析器提供输入。不过在展开对解析器的讨论前，需要明确

    词法记号的定义。3.1.2 词法记号

    词法记号是高级语言代码的基本单位，可以认为高级语言代码是词

    法记号按照一定规则的组合。词法记号通常可以分为标识符、关键字、常量、界符四大类，高级语言的定义对词法记号的定义有直接影响。不

    同语言对标识符的定义不同，如Visual Basic不区分标识符的大小写，C

    语言区分标识符的大小写。不同语言的关键字表也不尽相同，如在C语

    言内不存在C++的virtual关键字。不同语言的界符定义不同，PASCAL

    的赋值运算符为“∶=”，而C语言的赋值运算符为“=”等。

    本书编译系统处理的自定义语言的词法记号如下：

    1)类型系统。支持int、char、void基本类型和一维指针、一维数组

    类型。涉及的词法记号有关键字int、char、void，指针运算符为＇＇，取址运算符为＇＇，数组索引运算符为＇[＇和＇]＇。

    2)常量。字符常量、字符串常量、二八十进制整数。涉及的词法

    记号有数字常量num、字符常量ch、字符串常量str。与常量对应的变量

    使用标识符表示，因此标识符id也是词法记号。

    3)表达式。支持加、减、乘、除、取模、取负、自加、自减算术

    运算，大于、大于等于、小于、小于等于、等于、不等于关系运算和“与”、“或”、“非”逻辑运算。涉及的词法记号有＇+＇，＇–＇，＇

    ＇，＇＇，＇%＇，＇–＇，＇++＇，＇–＇，＇>＇，＇>=＇，＇<

    ＇，＇<=＇，＇==＇，＇!=＇，＇＇，＇||＇，＇!＇。注意这里

    的乘法运算符和指针运算符是同一个字符，在词法分析器内它们被视为

    同一个词法记号。同理，减法运算符和取负运算符也是如此。

    4)语句。支持赋值语句，do-while、while、for循环语句，if-else、switch-case条件分支语句，函数调用、return、break、continue语句。涉

    及的词法记号有赋值运算符＇=＇，关键字do、while、for、if、else、switch、case、default、return、break、continue。另外，复合语句或函数

    体需要使用花括号包含起来；基本语句都是以分号结束；case和default

    关键字后使用冒号分隔，因此词法记号还包含＇{＇、＇}＇、分号以及

    冒号。

    5)声明与定义。支持extern变量声明、函数声明，变量、函数定

    义。涉及的词法记号有extern关键字，＇(＇和＇)＇，注意小括号也

    可能出现在表达式中。另外，变量定义列表和函数的参数列表都使用逗

    号分隔，因此逗号是词法记号。

    6)其他。支持默认类型转换、单行和多行注释等。默认类型的转

    换属于代码生成部分的内容，注释不是有效的词法记号。不过除了以上

    提到的词法记号之外，还需要引入两个特殊的词法记号。err表示词法分

    析出错时返回的词法记号，词法分析器或语法分析器都自动忽略这个词法记号。此外，使用词法记号end表示文件结束。

    于是，自定义语言涉及的所有词法记号如表3-1所示。

    表3-1 词法记号

    我们使用一个枚举类型记录所有的词法记号标签，为后面的代码提

    供符号定义。

    1

    2 词法记号标签3

    4 enum Tag

    {

    5 ERR, 错误，异常

    6 END, 文件结束标记

    7 ID, 标识符

    8 KW_INT,KW_CHAR,KW_VOID, 数据类型

    9 KW_EXTERN, extern

    10 NUM,CH,STR, 常量

    11 NOT,LEA, 单目运算! -

    12 ADD,SUB,MUL,DIV,MOD, 算术运算符

    13 INC,DEC, 自加自减

    14 GT,GE,LT,LE,EQU,NEQU, 比较运算符

    15 AND,OR, 逻辑运算

    16 LPAREN,RPAREN,

    17 LBRACK,RBRACK, []

    18 LBRACE,RBRACE, {}

    19 COMMA,COLON,SEMICON, 逗号

    ,冒号

    ,分号

    20 ASSIGN, 赋值21 KW_IF,KW_ELSE, if-else

    22 KW_SWITCH,KW_CASE,KW_DEFAULT, swicth-case-deault

    23 KW_WHILE,KW_DO,KW_FOR, 循环

    24 KW_BREAK,KW_CONTINUE,KW_RETURN break,continue,return

    25 };

    注意Tag枚举类型内保存的词法记号标签都是大写，以避免与C语

    言关键字冲突。关键字标签都是以KW_开始，界符标签被分配了合适的

    名字。

    词法记号标签只是区分了不同的词法记号，而对一些特殊的词法记

    号，如标识符、常量等除了需要保存词法记号标签信息外，还要保存标

    识符名称、常量值等信息，以用来构造符号表。我们采用面向对象的思

    想来设计与词法记号相关的类。

    如图3-4所示，基类Token表示一般的词法记号，它只包含一个公有

    字段tag，用于记录词法记号的标签。Token有四个派生类Id、Num、Char、Str，分别对应标识符、数字常量、字符常量、字符串常量。其中

    Id的公有字段name记录了标识符的名称，Num的公有字段val记录了数

    字常量的值，Char的公有字段ch记录了字符常量的值，Str的公有字段str

    记录了字符串常量的值。图3-4 词法记号类图

    与Id关联的是Keywords类，它的公有字段keywords是教列表类型，记录了自定义语言定义的所有关键字。Keywords的实例化类型为

    hash_map，它记录了关键字名称与关键字词

    法记号标签的映射关系。如此设计的原因是关键字在词法分析器内可以

    看作一类特殊的标识符，词法分析器在创建标识符词法记号对象之前只

    需要使用getTag方法查询Keywords内保存的关键字表，便可以确定是创

    建Id对象还是普通的关键字词法记号Token对象。

    按照上述类的设计，我们实现了词法记号相关的类，代码如下：

    1

    2 词法记号类

    3

    4 class Token5 {

    6 public:

    7 Tag tag; 内部标签

    8 Token (Tag t);

    9 virtual string toString;

    10 virtual ~Token ;

    11 };

    12

    13 标识符记号类

    14

    15 class Id

    :public Token

    16 {

    17 public:

    18 string name;

    19 Id (string n);

    20 virtual string toString;

    21 };

    22

    23 数字记号类

    24

    25 class Num

    :public Token

    26 {

    27 public:

    28 int val;

    29 Num (int v);

    30 virtual string toString;

    31 };

    32

    33 字符记号类

    34

    35 class Char

    :public Token

    36 {

    37 public:

    38 char ch;

    39 Char (char c);

    40 virtual string toString;

    41 };

    42

    43 字符串记号类

    44 45 class Str

    :public Token

    46 {

    47 public:

    48 string str;

    49 Str (string s);

    50 virtual string toString;

    51 };

    52

    53

    54 关键字表类

    55

    56 class Keywords

    57 {

    58 hash函数

    59 struct string_hash{

    60 size_t operator(const string str) const{

    61 return __stl_hash_string(str.c_str);

    62 }

    63 };

    64 hash_map keywords;

    65 public:

    66 Keywords; 关键字表初始化

    67 Tag getTag(string name); 测试是否是关键字

    68 };

    确定了词法记号后，接下来便是将扫描器输出的字符序列转化为词

    法记号的序列，这一步由解析器完成。如图3-1所示，解析器读入字

    符，使用有限自动机对输入字符进行匹配，最终输出词法记号。因此在

    描述解析器实现之前，还需要了解如何构造词法记号的有限自动机。3.1.3 有限自动机

    在编译原理的教材中，对有限自动机的描述十分详细，因此我们假

    定读者了解这方面的知识。有限自动机识别的语言称为正则语言，有限

    自动机分为确定的有限自动机(DFA)和非确定的有限自动机(NFA)

    两种。DFA和NFA都可以描述正则语言，DFA规定只能有一个开始符

    号，且转移标记不能为空，其代码实现较为方便。由于每个NFA都可以

    转化为一个DFA，本书的词法分析器统一使用DFA描述前面定义的所有

    词法记号。

    1.标识符

    在第2章中曾描述过标识符的有限自动机，作为词法分析过程的例

    子。对于任意DFA总有一个唯一的开始状态0，它的输入是一串字符序

    列，根据字符选择不同的转移进入下一个状态，当遇到结束状态时接收

    已输入的字符串。如图3-5所示，标识符从开始状态起，当读入下划线

    或字母时进入状态id，状态id是结束状态，其本身也可以接收任意多个

    下划线、字母和数字，当读入其他不能识别的字符时便停止自动机的识

    别过程。这正好符合C语言对标识符的定义：以下划线或字母开始的任

    意下划线、字母和数字组合的字符串。图3-5 标识符有限自动机

    2.关键字

    关键字是一类特殊的词法记号，本质上与标识符没有任何区别，只

    是词法分析器将之作为系统保留的标识符，不允许用户重新定义。我们

    在分析标识符结束后可以查询关键字表，来确定当前识别的标识符是普

    通的标识符还是关键字。表3-2描述了自定义语言中所有的关键字。

    表3-2 关键字表3.常量

    常量词法记号有三种：num、ch和str，它们分别对应数字常量、字

    符常量和字符串常量。以下分别描述这三种常量的自动机结构。

    对于数字常量，本书仅考虑整数常量，支持十进制、二进制、八进

    制和十六进制整数。整数的定义可以简单地认为是数字0~9的任意组

    合。对不同进制的整数的定义如下。

    1)十进制整数：以数字1~9开始，0~9中任意个数字组合的字符

    串。

    2)八进制整数：以数字0开始，0~7中任意个数字组合的字符串。这也是为什么十进制整数不能以0开始，因为会与八进制整数的定义冲

    突。

    3)二进制整数：以字符串“0b”开始，0~1中任意个数字组合的字符

    串。

    4)十六进制整数：以字符串“0x”开始的，0~9及字母a~f、A~F中一

    个或多个数字、字母组合的字符串。

    整数的有限自动机如图3-6所示，其中结束状态d-num、o-num、b-

    num和h-num分别表示十进制、八进制、二进制、十六进制整数的自动

    机结束状态。结束状态err表示自动机识别过程中出现词法错误时到达的

    状态，一旦进入err状态便停止自动机，报告对应的词法错误。整数有限

    自动机从状态0开始，当读入字符1~9时，进入d-num状态进行十进制整

    数的识别。当读入字符0时转移到o-num状态，然后继续读入字符，如果

    是0~7则识别八进制整数，如果读入字符b则进行二进制整数的识别，如

    果读入字符x则进行十六进制整数的识别。图3-6 整数有限自动机

    字符常量是用左右单引号包含的一个字符，并且支持特殊字符的转

    义。比如＇a＇和＇\n＇都是合法的字符。

    图3-7描述了字符有限自动机的结构，其中状态ch为识别字符的结

    束状态，err为错误状态。字符有限自动机从状态0开始，读入一个单引

    号字符进入状态1。再次读入一个普通字符进入状态3，或者读入字符＇

    \＇和另一个字符进行转义字符的识别，如果读入的字符是换行符、文

    件结束符或单引号则报错。我们定义的字符转义字符包括＇\n＇、＇

    \\＇、＇\t＇、＇\0＇和＇\'＇，换行符和文件结束符是不能转义的，未

    定义的转义字符作为普通字符对待，转义字符的处理在状态2处完成。

    状态3表示识别了一个正常的字符，然后再读入一个单引号完成字符词法记号的识别，除此之外则报告词法错误。

    图3-7 字符有限自动机

    字符串有限自动机如图3-8所示，其中状态str为识别字符串的结束

    状态，err为错误状态。字符串有限自动机从状态0开始，读入一个双引

    号字符进入状态1。状态1可以接收任意多个普通字符，如果此时读入字

    符＇\＇和另一个字符，则进入状态2进行转义字符的识别，如果读入的

    字符是换行符、文件结束符则报错。我们定义的字符串转义字符包括＇

    \n＇、＇\\＇、＇\t＇、＇\0＇、＇\换行＇和＇\＇，其中＇\换行＇是对

    换行符转义，表示字符串内换行，文件结束符是不能转义的，未定义的

    转义字符作为普通字符对待，转义字符的处理在状态2处完成后回到状

    态1继续处理。处于状态1时，只要读入一个双引号便完成了字符串词法

    记号的识别。图3-8 字符串有限自动机

    4.界符

    词法记号中的界符数量较多，但是形式无外乎两种：单字节界符和

    双字节界符。比如“%”是单字节界符，“>=”是双字节界符。界符的有限

    自动机结构比较简单。

    单字节界符有限自动机如图3-9a所示，取模运算符有限自动机读入

    一个字符＇%＇后进入结束状态，完成词法记号mod的识别。双字节界

    符有限自动机如图3-9b所示，大于大于等于运算符有限自动机读入字符

    ＇>＇进入结束状态gt，此时产生词法记号gt。但是按照“贪心”的原则，此时自动机如果读入字符＇=＇，则进入结束状态ge，产生词法记号

    ge。其他类型的界符的有限自动机结构类似，这里就不必一一列举了。图3-9 界符有限自动机

    我们设计的词法记号中单字节界符包括＇+＇、＇-＇、＇＇、＇

    ＇、＇%＇、＇＇、＇>＇、＇<＇、＇=＇、＇!＇、＇，＇、＇：

    ＇、＇；＇、＇(＇、＇)＇、＇[＇、＇]＇、＇{＇、＇}＇和文件结

    束符–1，双字节界符包括＇++＇、＇--＇、＇>=＇、＇<=＇、＇==＇、＇!=＇、＇＇和＇||＇。需要注意的是，界符＇＇除了作为除法运

    算符外，还可以作为单行多行注释的开始。界符＇||＇在读入第一个字

    符＇|＇时并不能被自动机接收，因为我们没有定义词法记号＇|＇。

    5.无效词法记号

    除了以上的词法记号外，还有两类自动机没有涉及，因为它们并不

    产生真正的词法记号，我们称为无效词法记号。一类是空白字符(空

    格、制表符、换行符)，另一类是注释。参考C语言的特点，所有有效

    词法记号之间可以出现任意多个空白字符和注释。图3-10 空白字符有限自动机

    如图3-10，空白字符的有限自动机非常简单，它只有一个状态，即

    开始状态亦是结束状态，并接收任意多个空格、＇\t＇和＇\n＇。前面

    描述的有限自动机识别结束后都会产生一个词法记号，那么空白字符的

    有限自动机识别结束后应该如何处理呢？有两种方式可以选择，一种是

    不产生任何词法记号，识别结束后继续识别其他词法记号。另一种方式

    是产生词法记号err，因为词法记号err会被词法分析器或语法分析器自

    动忽略。前面的有限自动机在识别出错时都会产生词法记号err，因此不

    会影响后续词法记号的识别。

    如图3-11所示，注释有限自动机从开始状态0读入字符＇＇后进入

    结束状态div，此时可以识别除法运算词法记号div。但是按照“贪心”规

    则，如果此时读入字符＇＇或＇＇则进入单行多行注释的识别过程。

    单行注释内容在状态1处处理，此时读入任意一行内容，直到遇到换行

    符或文件结束符后进入结束状态s-com，识别单行注释。多行注释内容

    在状态2处处理，此时可以读入任意长度的内容，当读入文件结束符时产生词法错误，当读入字符＇＇时进入状态3。状态3处如果读入字符

    ＇＇进入结束状态m-com，识别多行注释，如果仍读入字符＇＇则继

    续保持在状态3，否则返回状态2。状态3可以接收任意多个字符＇＇是

    为了避免出现“……”字符串不能被识别为注释的情况。这里需要注

    意的是，多行注释不能出现嵌套的情况，嵌套多行注释不能被有限自动

    机识别，因为超出了正则文法的描述能力，属于上下文无关文法。

    图3-11 注释有限自动机

    无论是单行注释还是多行注释，识别结束后都会返回词法记号err。

    这与空白字符有限自动机的处理有所区别，因为注释的有限自动机包含

    了除法运算符词法记号的识别，为了保持代码的一致性，该自动机不得

    不返回一个词法记号。3.1.4 解析器

    解析器的输入是扫描器产生的线性字符序列，而输出是词法记号序

    列。解析器的构造依赖于词法记号有限自动机的实现，词法记号的有限

    自动机构造完毕后，便可以编码实现解析器(真正意义上的词法分析

    器)，完成词法记号的解析。

    根据有限自动机实现词法分析器一般有两种方式：基于表驱动的方

    式和硬编码方式。基于表驱动方式的词法分析需要为词法记号建立状态

    转移表，而硬编码方式的词法分析则使用程序控制结构直接实现词法分

    析。

    1.基于表驱动的词法分析

    表3-3是有限自动机的状态转移表，这里主要描述了标识符有限自

    动机的状态转移，其他词法记号有限自动机的状态和转移被简化处理。

    表格的第一列表示自动机的当前状态，表格的第一行表示自动机读入的

    当前字符，即状态转移弧上的字符，单元格内表示自动机将要进入的下

    一个状态，这个关系正好与自动机的基本结构对应。

    表3-3 状态转移表自动机从状态0开始，如果读入的字符是＇_＇或＇a-z＇中的任意

    一个小写字母，或＇A-Z＇中的任意一个大写字母，查询状态转移表得

    到下一个状态为id。转移到状态id，继续读入的字符如果是＇_＇或小写

    字母、大写字母或＇0-9＇中的数字，则仍进入状态id，否则转移到

    accept状态。accept是一个特殊的状态，它表示除了当前读入字符之外

    的所有已读入字符构成自动机识别的字符串。此时词法分析器根据进入

    accept状态的那个状态(状态id)决定词法记号的处理结果，即产生标

    识符的词法记号。

    需要注意的是，在进入accept状态时读入的字符并不是自动机已经

    接受的字符。因此，在后续的词法记号自动机识别的过程中，需要重新

    读入当前字符，以避免当前读入字符被跳过。为此，每次查询状态转移

    表之前并不读入新的字符，而是假定字符已经读入。那么自动机开始运

    行时，需要将当前字符初始化为空格(或者＇\n＇，＇\t＇)，这样自

    动机启动后会首先进入空白字符有限自动机的处理，识别这个空白字

    符。

    基于表驱动的词法分析的伪代码描述如下：

    1 cur_char=' '; 初始字符为空格2 Token Lexer::tokenize

    { 词法记号解析

    3 cur_state=0; 初始状态为

    0

    4 while(1){ 启动有限自动机

    5 next_state=table[cur_state,cur_char]; 查表获取下一个状态

    6 if(next_state==accept){ 接受状态

    7 return process

    (cur_state); 处理接受状态

    8 }

    9 else if(next_state==error){ 错误状态

    10 return lex_error

    (cur_state,cur_char); 词法错误处理

    11 }

    12 else{ 正常状态转移

    13 handle_state

    (cur_state,cur_char); 处理当前状态

    14 cur_state=next_state; 进入下一个状态

    15 cur_char=scan

    (file); 扫描获取下一个字符16 }

    17 }

    18 }

    第1行将当前读入字符初始化为空格，这样第一次调用tokenize时会

    执行空白字符自动机识别的过程。

    第3行将当前状态初始化为开始状态0，开始词法记号的解析过程。

    第5行查询状态转移表table，行索引为cur_state，列索引为

    cur_char。

    第6~8行处理accept状态，返回词法记号。

    第9~11行处理err状态，进行词法错误处理。

    第12~16行处理正常的状态转移，首先处理当前状态和已经接受的

    字符，比如计算数字常量的值、处理转义字符等。然后设定cur_state为

    查询得到的下一个状态，调用扫描器读入下一个字符，回到第6行继续

    词法记号解析。

    使用状态转移表进行词法分析的实现就是查询状态转移表、状态比

    较和状态处理的过程，实现简单。词法分析器的自动生成工具一般都采

    用这种方法。词法分析器自动生成工具根据用户提供的词法记号定义配

    置文件，建立词法记号有限自动机NFA，然后将NFA确定化为DFA，再

    将DFA最小化，生成状态转移表，最后按照上述过程进行词法分析。然而，主流的编译器并未采用表驱动的词法分析方式，而是采用硬编码的

    方式，可能考虑了以下因素：

    1)保存状态转移表需要大量的存储空间，构建状态转移表对词法

    记号的定义有很强的依赖，一旦更改了词法记号的定义，状态转移表变

    化很大，不利于代码维护。

    2)基于表驱动的词法分析过程形式虽然简单，但是灵活性较差，不利于对特定状态的自定义处理。所有词法记号有限自动机的状态转移

    在代码层面形式基本相同，导致代码的可读性较差，调试不够方便。

    3)基于表驱动的词法分析在每次读入一个字符后都会发生状态转

    移，大量的查表、状态比较和状态处理降低了词法分析器的性能。

    因此，本书采用硬编码的方式构建词法分析器。

    2.硬编码方式的词法分析

    与基于表驱动方式的词法分析不同的是，硬编码方式的词法分析不

    需要显式地确立有限自动机的状态，它使用程序的控制结构直接对词法

    记号进行解析，即根据词法记号本身的含义，使用代码解析词法记号的

    内容。

    我们仍以标识符为例，再次分析标识符的定义：以下划线、字母开始的任意多个下划线、字母和数字组合的字符串。首先对一个标识符从

    概念上进行拆分，一个合法的标识符包含两部分：标识符的第一部分是

    一个字符，它可能是下划线或字母。标识符的第二部分可以是任意长度

    的字符串，但是字符串内的每个字符必须是下划线、字母或数字。根据

    这样的拆分，很容易发现解析标识符的控制结构。首先是一个判断语

    句，判定读入的字符是不是下划线或字母，以确定开始识别标识符。然

    后是一个循环语句，期望读入更多的下划线、字母或数字。其伪代码描

    述如下：

    if(ch==下划线

    or字母){

    ch=scan(file);

    while(ch==下划线

    or字母

    or数字){

    ch=scan(file);

    }

    }

    这样的硬编码方式与表驱动方式识别出的字符串完全等价，而且不

    需要考虑有限自动机的状态转移，也完全消除了查表、判断状态等操

    作。其实，硬编码中的程序控制语句已经蕴含了有限自动机状态的转移

    信息。我们对有限自动机做如下处理：将有限自动机的状态转化为一个标

    号，将每条状态转移弧转化为一条跳转到目标状态的goto语句，且在每

    条goto语句前读入新的字符，弧上的字符标签转化为判断条件。对于标

    识符的有限自动机，我们可以得到如下代码：

    0:

    if(ch==下划线

    or字母){

    ch=scan(file);

    goto 1;

    }

    goto end;

    1:

    if(ch==下划线

    or字母

    or数字){

    ch=scan(file);

    goto 1;

    }

    goto end;

    end:

    然后将这段代码转化为控制流图，如图3-12所示。图3-12 DFA与控制流图

    我们发现，根据DFA转化得到的代码控制流图与前面硬编码的程序

    控制结构完全一致，这种将DFA直接转化为编码的方式一般称为直接编

    码方式。虽然使用这种方式也可以完成词法分析器的构造，但是这种方

    式仍需要考虑自动机状态的转换，并且包含大量的goto语句，代码明显

    不如硬编码方式简洁。因此，使用硬编码方式的词法分析是较好的选

    择。接下来逐一描述词法记号的硬编码实现。

    (1)标识符在前面的章节中已经描述了标识符词法记号的硬编码实现。然而，在实际的词法分析过程中，硬编码的程序控制结构只是提供了识别词法

    记号的框架。对于标识符来说，在词法分析过程中，还需要记录标识符

    的名称，创建标识符词法记号对象，这需要在硬编码控制结构中插入相

    关代码来完成。识别标识符词法记号的代码如下：

    1 if(ch>='a'ch<='z'||ch>='A'ch<='Z'||ch=='_'){

    2 string name=;

    3 do{

    4 name.push_back(ch);

    5 scan;

    6 }while(ch>='a'ch<='z'||ch>='A'ch<='Z'

    7 ||ch=='_'||ch>='0'ch<='9'); 匹配结束

    8 Tag tag=keywords.getTag(name);

    9 if(tag==ID)

    10 t=new Id(name);

    11 else

    12 t=new Token(tag);

    13 }

    标识符词法分析过程中，使用name记录接收的字符。这里仍假定当

    前字符已经提前读入，存储在ch内。需要注意的是，前面描述的标识符识别的程序控制结构是if+while形式，而这里是if+do-while形式。因为无

    论while语句条件是否成立，都会执行第4~5行语句，因此这里可以修改

    为do-while循环。这也从侧面说明了硬编码实现的词法分析器的编码灵

    活性。

    代码的第1~7行完成了标识符词法记号的识别，并将标识符的名字

    记录在变量name中。第8行通过查询关键字表来确定当前识别的字符串

    是普通的标识符还是系统保留的关键字。

    (2)关键字

    我们一直把关键字当作一类特殊的标识符对待，甚至前面识别标识

    符的代码中都包含了关键字词法记号的生成。在词法分析器的实现中，使用了散列表保存关键字信息，相关代码如下：

    1

    2 关键字列表初始化

    3

    4 Keywords::Keywords

    5 {

    6 keywords[int]=KW_INT;

    7 keywords[char]=KW_CHAR;

    8 keywords[void]=KW_VOID;

    9 keywords[extern]=KW_EXTERN;

    10 keywords[if]=KW_IF;

    11 keywords[else]=KW_ELSE;

    12 keywords[switch]=KW_SWITCH;

    13 keywords[case]=KW_CASE;

    14 keywords[default]=KW_DEFAULT;

    15 keywords[while]=KW_WHILE;

    16 keywords[do]=KW_DO;

    17 keywords[for]=KW_FOR;

    18 keywords[break]=KW_BREAK;

    19 keywords[continue]=KW_CONTINUE;

    20 keywords[return]=KW_RETURN;

    21 }

    22 23 测试是否是关键字

    24

    25 Tag Keywords::getTag

    (string name)

    26 {

    27 return keywords.find(name)!=keywords.end

    28 ?keywords[name]:ID;

    29 }

    在Keywords类的构造函数中，我们初始化了关键字的散列表

    keywords。当词法分析器需要确定一个字符串是否是关键字时，只需要

    调用Keywords类的getTag方法即可。第27~28行是一个条件表达式，它

    在关键字表内查询name是否存在，如果存在则返回散列表记录的关键字

    标号，否则返回标识符标号ID。只要在该函数的调用处判断函数getTag

    返回的词法标签是否是ID，便能确定当前识别的字符串是标识符还是关

    键字。

    (3)常量

    我们仍按照数字常量、字符常量、字符串常量的顺序介绍常量词法

    记号的识别。与标识符类似，仍然是对词法记号在概念上进行拆分，以

    确定识别词法记号的程序控制结构。

    数字常量支持四种进制：十进制、八进制、二进制和十六进制，只

    要以数字0~9开始的字符串都会产生数字词法记号。十进制整数要求以

    1~9开始，是任意多个0~9数字的组合。这与标识符类似，是一个if+do-while控制结构。八进制整数要求以“0”开始，二进制整数要求以“0b”开

    始，十六进制整数要求以“0x”开始。它们拥有公共的前缀0，因此还需

    要读入一个字符来确定具体的数字进制。如果读入字符＇b＇，则确定

    是二进制整数，后边紧跟以0~1开始的任意0~1组合的字符串，也是一个

    if+do-while控制结构。如果读入字符＇x＇，则确定是十六进制整数，后边紧跟以0~9、A~Z或a~z开始的，任意0~9、A~Z或a~z组合的字符

    串，也是if+do-while控制结构。如果读入的是0~7中的字符，则确定是

    八进制整数，后边紧跟任意多个0~7数字的组合，是一个do-while控制结

    构。如果读入的是其他字符，则表示仅有一个数字0被接受。实现代码

    如下：

    1 if(ch>='0'ch<='9'){

    2 int val=0;

    3 if(ch!='0'){

    4 do{

    5 val=val10+ch-'0';

    6 scan;

    7 }while(ch>='0'ch<='9');

    8 }

    9 else{

    10 scan;

    11 if(ch=='x'){

    12 scan;

    13 if(ch>='0'ch<='9'||ch>='A'ch<='F'

    14 ||ch>='a'ch<='f'){

    15 do{

    16 val=val16+ch;

    17 if(ch>='0'ch<='9')val-='0';

    18 else if(ch>='A'ch<='F')val+=10-'A';

    19 else if(ch>='a'ch<='f')val+=10-'a';

    20 scan;

    21 }while(ch>='0'ch<='9'||ch>='A'ch<='F'

    22 ||ch>='a'ch<='f');

    23 }

    24 else{

    25 LEXERROR(NUM_HEX_TYPE); 0x26 t=new Token(ERR);

    27 }

    28 }

    29 else if(ch=='b'){

    30 scan;

    31 if(ch>='0'ch<='1'){

    32 do{

    33 val=val2+ch-'0';

    34 scan;

    35 }while(ch>='0'ch<='1');

    36 }

    37 else{

    38 LEXERROR(NUM_BIN_TYPE); 0b

    39 t=new Token(ERR);

    40 }

    41 }

    42 else if(ch>='0'ch<='7'){ 八进制

    43 do{

    44 val=val8+ch-'0';

    45 scan;

    46 }while(ch>='0'ch<='7');

    47 }

    48 }

    49 if(!t)t=new Num(val); 最终数字

    50 }

    第2行使用变量val保存数字的值，初始化为0。

    第3~8行是十进制整数的识别过程，第9~48行是其他进制数的识别

    过程。

    第11~28行是十六进制整数的识别过程，第24~27行处理十六进制整

    数定义时，“0x”之后无有效字符的词法错误。LEXERROR宏用于输出词

    法错误信息，后面会对该宏进行介绍，并产生词法记号err。第29~41行是二进制整数的识别过程，第37~40行处理二进制整数定

    义时，“0b”之后无有效字符的词法错误。LEXERROR宏用于输出词法错

    误信息，产生词法记号err。

    第42~47行是八进制整数的识别过程，此处不会产生词法错误。这

    是因为在进行非十进制整数识别时，已经读入字符＇0＇，无论新读入

    的字符是否是0~7数字，0本身就是一个合法的八进制整数。

    第50行根据数字识别过程中计算得到的val的值创建数字词法记

    号。

    对于字符常量，要求它是由两个单引号包含起来的唯一字符或一个

    转义字符。词法分析器读入一个单引号后开始对字符常量进行识别。如

    果读入字符＇\＇则继续读入一个字符，并处理字符的转义。如果读入

    另一个单引号，则说明两个单引号之间没有有效字符，视为词法错误。

    如果读入了换行符或文件结束符，将导致词法错误。这个过程是一个典

    型的if控制结构。如果被转义的字符是换行符或文件结束符，则字符词

    法记号识别失败。否则进行正常的转义字符处理。这也是一个if控制结

    构，实现代码如下：

    1 if(ch=='\''){

    2 char c;

    3 scan;

    4 if(ch=='\\'){ 转义

    5 scan;

    6 if(ch=='n')c='\n';7 else if(ch=='\\')c='\\';

    8 else if(ch=='t')c='\t';

    9 else if(ch=='0')c='\0';

    10 else if(ch=='\'')c='\'';

    11 else if(ch==-1||ch=='\n'){ 文件结束

    换行

    12 LEXERROR(CHAR_NO_R_QUTION);

    13 t=new Token(ERR);

    14 }

    15 else c=ch; 没有转义

    16 }

    17 else if(ch=='\n'||ch==-1){ 换行

    文件结束

    18 LEXERROR(CHAR_NO_R_QUTION);

    19 t=new Token(ERR);

    20 }

    21 else if(ch=='\''){ 没有数据

    22 LEXERROR(CHAR_NO_DATA);

    23 t=new Token(ERR);

    24 scan; 读掉引号

    25 }

    26 else c=ch; 正常字符

    27 if(!t){

    28 if(scan('\'')){ 匹配右侧引号

    ,读掉引号

    29 t=new Char(c);

    30 }

    31 else{

    32 LEXERROR(CHAR_NO_R_QUTION);

    33 t=new Token(ERR);

    34 }

    35 }

    36 }

    第2行使用变量c记录识别的字符。第4~16行识别转义字符，第11~14行处理不能转义的字符，报告词

    法错误。

    第17~20行处理字符词法记号内出现换行符或文件结束符时的词法

    错误。

    第21~25行处理两个单引号之间无有效字符的情况。注意这里识别

    右单引号后需要主动读入下一个字符，不再将这个右单引号作为下一个

    词法记号的开始。

    第27~35行识别字符词法记号的右单引号，第29行产生字符词法记

    号，第31~34行处理右单引号丢失的词法错误。

    字符串常量与字符常量的识别相似，要求它是由两个双引号包含起

    来的字符和转义字符的任意组合，包括空串。词法分析器读入一个双引

    号后开始，并期望读入另一个双引号完成字符串常量的识别，这是一个

    while控制结构。如果读入字符＇\＇则继续读入一个字符，处理字符的

    转义。如果读入了换行符或文件结束符，将导致词法错误。这个过程是

    一个if控制结构。如果被转义的字符是文件结束符，则字符串词法记号

    识别失败。否则进行正常的转义字符处理。这也是一个if控制结构，实

    现代码如下：

    1 if(ch==''){

    2 string str=;

    3 while(!scan('')){

    4 if(ch=='\\'){ 转义5 scan;

    6 if(ch=='n')str.push_back('\n');

    7 else if(ch=='\\')str.push_back('\\');

    8 else if(ch=='t')str.push_back('\t');

    9 else if(ch=='')str.push_back('');

    10 else if(ch=='0')str.push_back('\0');

    11 else if(ch=='\n'); 字符串换行

    12 else if(ch==-1){

    13 LEXERROR(STR_NO_R_QUTION);

    14 t=new Token(ERR);

    15 break;

    16 }

    17 else str.push_back(ch);

    18 }

    19 else if(ch=='\n'||ch==-1){ 文件结束

    20 LEXERROR(STR_NO_R_QUTION);

    21 t=new Token(ERR);

    22 break;

    23 }

    24 else

    25 ......