编译原理(一):词法分析

  • A+
所属分类:安全开发

🍊 编译原理(一):词法分析

这是橘子杀手的第 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 80ip 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 这个记号,肯定对应的是 ifGT 对应的是 >,那么还有另外一些比较特殊的,比如 IDENT,它是标识符,那么我们知道标识符可以有很多种,是一个很大的集合,比如你可以把变量取名叫 x 或者是 xx,所以我们还需要额外的信息去记录它具体是什么,所以这里是 IDENT(x)。与 IDENT 类似的还有 INTSTRING,就不多说了。

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

🌧 词法分析器的实现

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

  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

1
1 1

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,最小化一下,再用转移表实现即可。有了词法分析器之后,下一篇自然就是语法分析器咯,橘友们敬请期待  编译原理(一):词法分析



距离上一篇文章发布差不多有一个月半了
原因是这次尝试写完整个系列一起发
编译原理系列一共有四篇
也就是接下来三天
都!
有!
新的文章!

编译原理(一):词法分析


本文始发于微信公众号(橘子杀手):编译原理(一):词法分析

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: