第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所示。词法分析器首先将源程序文本输入到一个缓冲区中，该缓冲区称为输入缓冲区，单词符号的识别可以直接在输入缓冲区中进行。但通常情况下为了识别单词的方便，需要对输入的源程序字符串进行预处理。对于许多程序语言来说，空格、制表符、换行符等编辑性字符只有出现在符号常量中时才有意义；注释几乎可以出现在程序中的任何地方。但编辑性字符和注释的存在一般只是为了改善程序的易读性和易理解性，不影响程序本身的语法结构和实际意义，通常在词法分析阶段可以通过预处理将它们删除。因此可以设计一个预处理子程序来完成上述工作，每当词法分析器调用预处理子程序时，其便处理一串固定长度的源程序字符串，并将处理结果放在词法分析器指定的缓冲区中，称为扫描缓冲区。接下来单词符号的识别就可以直接在该扫描缓冲区中进行，而不必考虑其他杂务。
扫描器对扫描缓冲区进行扫描时通常使用两个指针，即开始指针和搜索指针，其中，开始指针指向当前正在识别的单词的起始位置，搜索指针用于向前搜索以寻找该单词的终点位置，两个指针之间的符号串就是当前已经识别出来的那部分单词。刚开始时，两个指针都指向下一个要识别的单词符号的开始位置，然后，搜索指针向前扫描，直到发现一个单词符号为止，一旦发现一个单词，搜索指针指向该单词的右部，在处理完这个单词以后，两个指针同时指向下一个要识别的单词符号的起始位置。
为了解决程序设计语言中某些单词符号可能存在公共前缀的问题，在进行词法分析时需采用所谓超前搜索技术，也即词法分析器在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别的方式。