跳至主要內容

词法分析（Lexical Analysis）

西风逍遥游大约 7 分钟

词法分析（Lexical Analysis）

词法分析是编译器工作的第一步，负责读取字符串，转换为一个个的 Token，供语法分析使用。

那么什么是Token呢？Token是编译器识别出来的一个个的词法单元，就像句子里面的单词一样，比如：

int a = 1;

这个C语句，一种直观的切分方法是：

这样做的好处是，我们尽量将有用的信息提取出来，并且划分成词，分成大类，这样语法分析的时候，就可以自然地使用这些词，而不用去想每次读一个字符，下个字符是什么。 归类的好处是明显的，比如1这个token，无论数字是多少，在语法分析器眼里，这个地方就是一个数字而已，不用去关心细节的内容。

词法分析的过程

词法分析的过程，从宏观上来讲，是一个将文件读取成字符串，然后再输出成token序列的过程。这个过程可以有两种实现方式，一种是完整读入，然后输出完整的token序列。另外一种是按需获取，类似一个迭代器，每次调用，都返回下一个token，直到文件结束。一般我们为了节约内存，提升性能，往往会采取第二种按需读取的方式。这对于较大文件的处理是非常有必要的。

按需读取，则引入了一些较为复杂的问题，比如文件按需加载，这时就需要将文件分块，需要考虑到文件的边界问题，比如一个token可能跨越两个文件块，这时就需要将两个文件块合并成一个token，这就需要在文件块的边界做一些特殊处理。对于这种模式的词法分析，有时还会因为难以获取上下文，而导致无法轻松打印异常信息。这两个问题我们可以留到单独一节来讨论。

词法的表示

词法一般是使用正则表达式进行表示的，比如标识符的正则表达式为：[a-zA-Z_][a-zA-Z0-9_]*

如果您之前没有了解过正则表达式，那么推荐您先阅读 正则表达式 一章。

常见的Token划分方法

一个典型的编程语言词法，往往包含几个大类：

  1. 标识符（identifier）

大多数编程语言都运行用户定义各种符号，如变量名，函数名，类型名等等，这种一般被称为标识符（indentifier）。这些符号让用户随便取名，方便开发时使用。 典型的C语言标识符可以用正则表达式表示为：[a-zA-Z_][a-zA-Z0-9_]*，也就是以字母或下划线开头，后面跟着字母、数字或下划线组成的字符串。

  1. 关键字（keyword）

保留字是编程语言中，被语言本身保留的一些标识符，这些标识符有特殊的含义，不能被用户定义，比如C语言中的，if，while等等。大多数语言的关键字是固定的，这方便了词法分析器的设计，但有一些特殊情况，也可以允许用户自定义关键字，这种时候一般就需要先把所有关键字当做标识符来处理，词法分析器在识别到标识符的时候，再去查表，判断是否是关键字。

  1. 数字

一般编程语言都会有许多种不同形式的数字，进行数学运算和表达式运算往往是编程语言的重要功能，所以数字的识别是词法分析器的重要部分。

  1. 字符串

字符串处理在很多程序中也相当常见，单引号或双引号括起来的一串字符，就是字符串，比如"hello world"，'a'，"123"等等。这里要尤其注意字符串的表达能力，为了表示字符串中的引号，特殊符号等，转义往往是字符串需要原生支持的功能。

  1. 注释

准确的来说，注释一般不算做token，我们在把注释识别之后往往直接丢弃，对于语法分析器来说，注释是没有意义的，但是注释的识别是词法分析器的重要部分，因为注释的存在，会影响到后面的token的识别。

  1. 空白符

空白符是词法分析中另外一种需要丢弃的符号，但其往往用来分隔其他的token，比如分割两个标识符。

  1. 运算符

一元运算符表示对某个表达式的操作，比如*, !，~，++，--等等。各种数学运算和逻辑运算都需要二元运算符，比如+，-，*，/，&&，||等等。有些符号既是一元运算符，也是二元的，那么我们在词法分析的时候，一般不做区分，把其统称运算符，等到语法分析层面时再根据上下文来进行判断。

词法分析的实现

手工编写的词法分析器

尽管目前有很多自动的词法分析生成工具，但很多情况下手工编写的词法分析器依旧很有用，因为可以更加灵活的处理一些特殊情况，尤其是提供更好的异常处理，以及能把一些typo的错误识别出来。 手工编写词法分析器的方式并不困难，主要就是用代码来编写该如何识别词法。

比如，如果我们想切分出字符串来，那么可以写一个函数：

enum TokenID {
    Unknown,
    StringT,
    ...
}

struct Token {
    TokenID ID;
    string data;
};

Token scanString(const char*& input) {
    string data;
    assert(*input == '"');
    ++input;
    while (*input != '"')
        if (*input != '\\') {
            ++input; 
            data += *input;
        } else {
            input+=2;
            data += escape(*(input-1));
        }
    ++input;
    return {StringT, data};
}

整个词法分析器可能是在一个大的switch里面:

Token getNextToken(const char*& input) {
    
}

自动生成词法分析器

自动生成词法分析器的工具有很多，比如flex，lex，antlr等等。这些工具都是根据一定的规则，自动生成词法分析器的代码，这样就可以省去手工编写的过程。

如果你想了解flex可使用方法，那么可以参考 极速教程-flex

自动生成词法分析器是一个相对复杂的过程，核心思路是，使用一系列有优先级的正则表达式来描述每个词法，然后词法分析器会根据这个列表进行匹配，选择最长，最高优先级的匹配结果。而每个正则式匹配后，都可以触发对应的动作，从而可以用来生成一个对应的token。

词法分析器在实现上，一般是使用确定有限自动机来完成功能的，这样可以保证分析器的性能。如果您之前没有了解过自动机，可以参考 自动机理论 一章。

整个流程可以简单描述为四步：

  1. 正则表达式的识别
  2. 构造自动机
  3. 优化自动机
  4. 生成代码

对于正则表达式的识别，我们可以用手工编写的方式，也可以使用其他自动生成的工具，比如flex。首先将正则表达式转换为可以识别的语法树，然后再进行处理。

对于自动机的构造，这里有两条不同的技术路线，一种是先构造NFA，再将NFA转换为DFA。另外一种方式是更为紧凑的直接构造DFA的方法。两种思路上其实是一致的，只是实现方式上看是否保留有中间临时数据(NFA)。

默认页脚
Copyright © 2024 西风逍遥游