🍊 编译原理（一）：词法分析

这是橘子杀手的第 27 篇文章
题图摄于：北京 · 北海公园

☁️ 系列开篇

为什么是编译原理？大家可能觉得有点奇怪，作为一个安全从业者，为什么会去看编译原理这种没有直接相关的知识 

这段时间我频繁遇到一类需求，即某个系统的自定义语句，如何转换为另一种固定的语句。以数据库的查询语句为例，MongoDB 的搜索，它的查是：{"ip": "1.1.1.1", "port": "80"} 和 {"$and": [{ip": "1.1.1.1"}, {"port": "80"}]}，都可以从数据库查询出来 ip 是 1.1.1.1 且端口是 80 的记录；又比如 {"$or": [{ip": "1.1.1.1"}, {"port": "80"}]}，可以从数据库查询出来 ip 是 1.1.1.1 或端口是 80 的记录。这样的语句呢，虽然看起来很直接，但是写起来还是稍显麻烦了一点，如果我们直接在前端的输入框照搬这个格式，用起来就比较麻烦，不如 ip is 1.1.1.1 and port is 80、ip is 1.1.1.1 or port is 80 这样来的简单，我相信大家在很多地方都见过这样的转换。我现在的处理方式是递归，一层一层解开用户传入的查询语句，然后解析成 MongoDB 的语句，虽然的确可以使用，但是需要考虑各种嵌套的情况、优先级的问题（比如(ip is 1.1.1.1 and port is 443) or (ip is 2.2.2.2 and port is 80)），所以有时候出现了 bug，查起来也比较麻烦。

其实大学的时候我是学过编译原理的（虽然现在都还给老师了...），当时觉得挺有意思的，最后的大作业是编译一个老师给定的简单语言（我记得是一个绘图的语言），用 Python 实现了它的编译器，并且可以成功执行。我觉得我遇到的这个需求，比我之前做的那个大作业要简单一些，也更加常见，如果你是编译原理老师，可以考虑把它作为大作业，或者大作业前的一次 “小大作业”。

编译原理的课程并不难，既然有缘再次遇到类似的问题，可以寻求编译原理的帮助，不如趁此机会重新复习一遍。大学很多课程里学到的知识，一开始确实会觉得没什么用，没事，先学了再说，等遇到相关问题的时候，你会发现自己可以想起能够使用什么手段解决，虽然比较笼统，但是大致有个方向，这还是很不错的。所以如果你还是在校学生，一定要好好学习哦  

这个系列是比较入门的，所以只专注于知识本身，会略掉一些的背景知识，也可能会有一些错误，希望各位大佬各位海涵。至于课程，我推荐网易公开课的这个：

https://mooc.study.163.com/course/1000002001

2 倍速看一遍也挺快的，各位如果有时间还是建议看一下。好了其他的就不说了，开始吧。

☁️ 编译器的阶段划分

作为系列的第一篇，先简单介绍一下整体的知识点。按照惯例，最后一篇会有一个思维导图做总结。

这是一个简单编译器的阶段划分：

先看红色的路线，源程序作为编译器的输入，编译器负责把源程序翻译成目标程序输出。如果我们再进一步看的详细一些，在黄色线路里，编译器中做了什么事情呢？首先包含了一个前端和一个后端，源程序作为前端的输入，生成一个“中间表示”，后端接收中间表示，产出目标程序；更细节的，前端具体做了什么事情呢？蓝色路线，首先，源程序输入给词法分析器，生成 “记号”，也就是通常说的，词法分析器分析一个字符流，切分，生成记号流，输入给语法分析器，语法分析器生成抽象语法树，传给语义分析器，最后生成中间表示。

如果看不懂，别着急，这些流程都会讲到  

☁️ 词法分析器

那么第一篇自然就要从词法分析器开始。

上面提到，词法分析器接受字符流，产出记号流。举个例子：

if (x > 5)
    y = '1';
else
    y = '0';

那么在词法分析器看来，这就是一个字符流：if (x > 5)n y = '1';nelsen y = '0';。那么词法分析器是怎么处理字符流的呢，它会将记号流切分为多个小块，然后识别里面的关键字、标识符、数字等等，将它们分类。经过分类之后，这个字符流，在词法分析器看起来是这样的：

IF LPAREN IDENT(x) GT INT(5) RPAREN
    IDENT(y) ASSIGN STRING('1') SEMICOLON
ELSE
    IDENT(y) ASSIGN STRING('0') SEMICOLON

那么这就是记号流了，上面全大写的，就被称为一个 记号。具体来解释一下，对于记号流里面的记号，有些是比较明显的，例如我们知道 IF 这个记号，肯定对应的是 if，GT 对应的是 >，那么还有另外一些比较特殊的，比如 IDENT，它是标识符，那么我们知道标识符可以有很多种，是一个很大的集合，比如你可以把变量取名叫 x 或者是 xx，所以我们还需要额外的信息去记录它具体是什么，所以这里是 IDENT(x)。与 IDENT 类似的还有 INT、STRING，就不多说了。

那么，词法分析器的任务就很清晰了，那么接下来，就是详细的知识点了。

🌧 词法分析器的实现

词法分析器有两大类实现方案：

1. 手动构造
• 复杂，容易出错（毕竟一种语言的规则通常都比较多）
• 比较可控，是主流的方案（GCC、LLVM 等采用此办法）
2. 自动构造
• 构造速度快，工作量少（可以搞个 demo）
• 细节难以控制

这里先介绍手动构造的方法。

❄️ 手动构造

状态转移图是一个非常重要的概念。假设我们在分析一个语言，它有以下运算符：<、>、<=、>=、<>(不等于)，那么可以画出状态转移图示例如下：

圆圈里的数字代表了这个节点是第几个状态，比如蓝色的就是状态 0。那么我们来看状态 1，例如词法分析器读入的第一个字符是 <，那么我们没法判断它到底是 <，还是 <= 或者是 <>，所以还需要继续往后看，那么其中比较特殊的是 4，上面有个 *，代表的是回滚一个字符，因为走到 4 的时候，不管从输入字符流中拿的是什么，都是 <，所以这时应该回滚，避免消耗了字符，却没有用到  

那么同样，我们也可以画出 C 语言标识符的状态转移图：

那么问题来了，对于 C 语言来说，if 是一个关键字，不应该当做标识符使用，所以在识别标识符的时候，应该去掉规定的关键字。

有两种办法，第一种是，if 开头的情况单独拎出来，然后完成状态转移图，例如：当然，这里的状态 4 其实也不是真正的终点，毕竟类似 ifxy 的字符也是有可能出现的，所以这种方法还是稍微麻烦了一些。

第二种，由于我们知道，关键字是标识符的一部分，所以可以先不考虑关键字，统一按照标识符来进行识别，等识别完成之后，查表判断一下这个标识符是不是关键字，O(1) 即可完成，非常简便 

❄️ 自动构造

自动构造的流程非常简单：

声明式规范 => 某工具 => 词法分析器

接下来逐个介绍每个环节内部的一些细节：

声明式规范

这里的 声明式规范，就是我们熟知的正则表达式。这里给出更加规范的定义：

对于给定的字符集：Σ = {c1, c2, ..., cn}，有
1. ε（空字符串）是正则表达式
2. 对于任意 c ∈ Σ，c 是正则表达式
3. 如果 M、N 是正则表达式，那么以下都是正则表达式
   - 选择：M | N == {M, N}
   - 连接：MN == {mn | m ∈ M, n ∈ N}
   - 闭包：M* == {ε, M, MM, MMM, ...}

这里举几个例子，例如我们想表达 C 语言里的关键字 if，正则表达式应该是什么样的呢？非常简单，就是 if。那么标识符应该怎么表示呢？标识符应该是以字母或者下划线开头，后面跟 0 个或者多个字母/数字/下划线，所以显然是：

(a|b|c|...|z|A|B|...|Z|_)(a|b|c|...|z|A|B|...|Z|_|0|1|...|9)*

为了篇幅，我省去中间的字符，用省略号代替。那么我们会发现一个非常明显的问题：太长了。所以为了简化正则表达式，就有了正则表达式的语法糖：

1. [c1-cn] == c1|c2|...|cn
2. c+ == 一个或者多个 c
3. c? == 一个或者零个 c
4. "c*" == 就是 c* 本身，不是闭包，类似转义
5. c{i, j} == i 个到 j 个 c 的连接
6. 点 (.) == 除了 'n' 之外的任意字符

这就是我们常用的正则表达式   

某工具

“某工具”，常见的有 lex、flex、jlex 等。对比与手动构造，我们不需要再去自己实现状态转移图，只需要说明我们想要的东西，然后输入给这个工具，这个工具就会生成一个我们想要的词法分析器。所以，如果我们选用自动构造，那么词法分析器的工作就变成了如何去声明式规范。

自动机

那么“某工具”的输出是什么呢？这就引出了 有限状态自动机。

有限状态自动机（FA）非常简单：

输入的字符串 => FA => yes/no

即，FA 会告诉你，它能不能接受或者说识别你输入的字符串，可以回答 yes，否则回答 no。更加规范的描述是：

M = (Σ, S, q0, F, δ)

- Σ: 字母表
- S: 状态集
- q0: 初始状态 
- F: 终结状态集
- δ: 转移函数

确定状态的有限状态自动机（DFA）

有点抽象吧？举个例子：

对于这个图来说：

- Σ: {a, b}
- S: {0, 1, 2}
- q0: {0}
- F: {2}
- δ: {
  (q0, a) -> q1,
  (q0, b) -> q0,
  (q1, a) -> q2,
  (q1, b) -> q1,
  (q2, a) -> q2,
  (q2, b) -> q2,
}

接受的定义是，输入串消耗完毕之后，最后的状态一定要是终结状态，假如输入的字符串 S = abab，那显然是可以被接受的。

我们再详细地看它的转移函数，每个状态，遇到特定的一个输入，都只有一个路线可以走，那么这种 FA 就叫做 DFA。

非确定状态的有限状态自动机（NFA）

再来看一个更有意思的例子：

状态 0，假如给一个输入是 a，那么它既可以到达状态 0，也可以到达状态 1；对于状态 1 来说，如果遇到 b 那么也有 2 条路可以走。所以，这个自动机是非确定性的，即 NFA。

来看上面 DFA 与 NFA 的对比，主要的区别就在于判断 “接受” 的难度不同。由于 NFA，走的路线多种多样，我们就需要不断尝试，如果在某一条路线上不能被接受，NFA 不能直接回答 “no”，而是需要回滚路线，重新尝试，直到所有可能路线都无法接受，才能回答 “no”。例如，假设输入 S = a，那么如果选择走 a 回到状态 0，此时输入完毕，而状态是 0，不是终结状态 1，所以呢，应该回答 no；但是如果选择走 a 到达状态 1，则可以接受。在这里，我们应该选择后者，因为不管怎么走，只要能走到终结状态，就应该被接受。

那么显然，我们更喜欢 DFA，因为实现起来更加简单，并且 NFA 是可以转换为 DFA 的 ，具体的我们后面再说。

回到最开始的那个流程：

声明式规范 => 某工具 => 词法分析器

经过我们上面的介绍，就可以具体化为：

正则表达式（re） => NFA => DFA => 词法分析器代码

那么这些转换是怎么实现的呢？

re => NFA

常用的是 Thomson 算法。基本方式是递归：

1. 对于基本的 re，直接构造
2. 对于复合的 re，递归构造

回想一下，上面提到的正则表达式，有这几种可能（e 均为正则表达式）：

1. ε，即空字符串
2. c，即单个字符
3. e1e2，连接
4. e1|e2，选择
5. e1*，闭包

对于前两种，是基本的 re，可以直接构造：

对于 3，就要复合构造了。首先，直接拼接 2 个基本构造，中间使用 ε 连接即可，即第一行所示：

那么显然，对于后面那个基本构造，原先的初始状态 0 不再是初始状态；对于前面那个基本构造，终结状态 1 不再是终结状态，所以调整之后就变成了第二行的形式。那么你可能会想，为什么不简化为第三行的形式呢？直接去掉 ε，多简洁？其实第二行与第三行，本质上是完全一样的，但是第二行用代码实现起来比较容易，形式统一，所以不化简更好，因为我们后面的流程中，会专门对状态转移图进行化简，所以现在不要去做节点的合并。在画这种图的时候，还注意一下，使得一个状态发生转移的情况，只能有一种，如果必须要加一种新的情况，则要改成加一个新的节点，然后用 ε 连接这两个节点。

比如 e1|e2 画成这样，其实也可以：

但是就有 2 种情况可以使得状态 0 发生转移，所以我们可以新加一个节点，e1|e2 就是这样：

对于 e1*，就是这样：

有了这 5 种基本构造之后，我们就可以构造更加复杂的正则表达式了，比如 a(b|c)*：

可以看到，Thomson 算法理解起来比较容易，代码实现就是递归，比较方便，所以 re 转换成 NFA 确实是不难的。

NFA => DFA

之前也提到过，NFA 不好直接用于构造词法分析器，因为会有大量的回溯。NFA 转换成 DFA 的算法为 子集构造算法。

以 a(b|c)* 为例子：

我们用 n 来代表状态。首先，把定义一个集合 q0，只包含初始节点。然后，对于这个集合里面的 n0，我们考虑它在接受什么字符的时候，可以转移到哪些状态。那么只要有一个输入 a，它就可以走到 n1。但是从 n1 后面到 n2，其实是不需要消耗字符的，所以 n0 如果可以走到 n1，那么它必然也可以走到 n2，因为它不需要读取输入，根据这个思路，那么 n0 消耗一个 a 之后，可以走到的节点有 {n1, n2, n3, n4, n6, n9}：

{n0}, 记为 q0
n0 + a: {n1, n2, n3, n4, n6, n9}, 记为 q1

接着同理，我们考虑 q1 里面所有状态，接收到所有可能的输入后（注意不能是 ε），可以走到的节点：

{n0}, 记为 q0
n0 + a: {n1, n2, n3, n4, n6, n9}, 记为 q1
q1 + b: {n5, n8, n9, n3, n4, n6}, 记为 q2
q2 + b: {n5, n8, n9, n3, n4, n6}, 记为 q3

那么，大家可以发现，q2、q3 实际上是一样的，那么这条分支就可以停止了。接下来应该求解 q1 + c 了，具体的过程就不多写了。需要注意的是，由于 q1 中含有原终结状态 9，所以，状态集 q1 就是一个终结状态。

在上面的过程中，我们求解都有 2 个步骤：

1. 状态集消耗一个字符，能够走到的状态集。所以很明显，这里要消耗，所以不能是 ε，并且只能消耗一个。
2. 得到步骤 1 中的状态集之后，还需要考虑，这里面的所有节点，通过 ε 能走到的所有状态。注意，这里的每个状态，只要可以通过 ε 走，就必须一直走下去，我们把这个步骤称为求解 ε-闭包。这一步得到状态集的就是最后的结果。

上面我们提到了，这个算法在得出状态集之后，如果发现这个状态集之前遇到过，那么就不继续深入了。现在的问题是，这个算法一定会运行结束吗？会不会死循环呢？其实是不会的，因为其实最多只会生成 2^n 个状态集，n 是状态转移图里的状态数量，所以这个算法在生成所有状态集之后，就停止了，并且这是最糟糕的情况，实际情况中，不太可能有所有状态的组合。例如我们上面那个例子，状态转移图里的状态数量一共是 10 个，理论上会生成 2^10 = 1024 个不同的 q，肯定没有这么多。

经过求解呢，我们就可以得到这么一个状态转移图：

DFA => 词法分析器代码

在上一步我们通过 NFA 的转换，得到了一个 DFA：

在变成最后的词法分析器代码之前，首先需要进行最小化。

DFA 的最小化

仔细看的话，实际上有些状态是可以进行合并的。q2 可以通过 b 到 q2，也可以通过 c 到 q3；q3 可以通过 c 到 q3，也可以通过 b 到 q2。所以 q2 和 q3 其实是可以合并的。合并完 q2、q3 得到 q4 之后我们会发现，q1 和 q4 同样可以合并，整个过程如下：

最终我们的 DFA 状态就是最简洁的形式，直观地看起来，可以轻松地与 a(b|c)* 的含义对上。

那么，这个应该怎么用代码实现呢 

最有名的就是 Hopcroft 算法 了，它的基本思想就是，合并状态。来举个例子，f(ee|ie)：

1. 首先把整个状态，按照接受状态和非接受状态进行划分，分别得到 N、A，即：
2. 那么首先，q3、q5 都无法接受字符继续往下，所以 A 是不可分割的
3. 由于 q2、q4 都可以接受 e 这个字符，转移至 A，所以 q2、q4 就是一个等价状态，可以合并：
4. 对于 N1 来说，由于 q1 接收的是 e 转移到 N2，而 q0 就不行，所以要继续拆分：
5. 最后得到：

大家可能会在想，具体实现起来，怎么知道 N1 会被 e 或者 i 分割呢？最粗暴的就是直接遍历所有可能的字符，看 N1 是否会被某个字符分割，例如 C 的标识符，只能是 ASCII 码，也就 256 种可能性。

最小化之后，就剩下最后一步了，将前面得到的最小化的 DFA 实际上是一个数据结构。

DFA 转为词法分析器代码

DFA，它实际上是一个有向图。具体用代码实现起来，有几种方式：

1. 转移表（类似邻接矩阵）
2. 跳转表
3. ...

没有通用的标准，大家按照实际情况选择。下面依旧是以 a(b|c)* 为例：

首先来看 转移表。

a、b、c 代表可能使得状态发送转移的字符；0、1 代表状态，对于表中不存在的字符，统一返回 error 即可。

那么对应的代码就可以是这样：

def next_token(string):
    token = []
    loc = [0]

    while string:
        char = string.pop()
        new_loc = table[loc[-1]].get(char, None)
        if new_loc is None:
            string.append(char)
            break
        else:
            token.append(char)
            loc.append(new_loc)

    while len(loc) > 1:
        new_loc = loc.pop()
        if new_loc in end_status:
            # 产出 token 之后，是终结状态
            break
        else:
            string.append(token.pop())

    return "".join(token)


table = {
  0: {
    'a': 1,
  },
  1: {
    'b': 1,
    'c': 1,
  }
}

# 终结状态集
end_status = [1]

string = list(input("S = "))[::-1]

while string:
    token = next_token(string)
    if not token:
        print(f'invalid string: {"".join(string[::-1])}')
        break
    else:
        print(f'got token: {token}')

接下来，来看 跳转表 的实现：

'''
python 没有 goto 语句，可以借助第三方库完成
pip install goto-statement
'''

from goto import with_goto

@with_goto
def next_token(string):
    token = []
    goto .q0

    label .q0
    char = string.pop()
    if char in ['a']:
        token.append(char)
        goto .q1
    else:
        string.append(char)

    label .q1
    if string:
      char = string.pop()
      if char in ['b', 'c']:
          token.append(char)
          goto .q1
      else:
          string.append(char)
  
    return "".join(token)


string = list(input("S = "))[::-1]

while string:
    token = next_token(string)
    if not token:
        print(f'invalid string: {"".join(string[::-1])}')
        break
    else:
        print(f'got token: {token}')

可以看到，跳转表不需要预先存储 table，利用一个 goto 块代表一个节点，所以更加省内存，如果是一个大型的项目，可能 table 就很大了。但是也要看到，这种实现方式不是很通用，不但 goto 语句并不是所有编程语言都有，而且往往不同的状态转移图需要写不同的 goto 块，我这上面写的跳转表代码还没考虑到回滚的问题，大家有时间可以尝试实现一下这种状态转移图：

需要注意的是，实现要遵循 最长匹配原则，如果输入的是 ififii，那么识别出的 token 应该是合法的 ifif 和非法的 ii。如果你使用转移表来完成，则只需要修改 table 就好了；如果要用跳转表，要修改的东西就多咯，所以我还是建议大家使用转移表  

☁️ 总结

词法分析到这就结束啦，只要写好正则，然后画出状态转移图，把这个 NFA 转为 DFA，最小化一下，再用转移表实现即可。有了词法分析器之后，下一篇自然就是语法分析器咯，橘友们敬请期待