Aione's blog

一起快乐摸鱼吧🐳

  1. 1. NFA
  2. 2. DFA
  3. 3. NFA to DFA
  4. 4. 如何应用 DFA 来识别 token ?
  5. 5. 例子

看 DFA, NFA 有点头大,记一下,理一下流程。

NFA

NFA 可被 $(Q,\Sigma, T, q0, F)$ 定义,其中

  • $Q$ 为状态的有限集合
  • $\Sigma$ 为输入字符集
  • $T$ 为转移函数, 可以表示为 $Q\times \Sigma \to P(Q)$ ,因为每个状态有输入和输出,输入为$\Sigma$,输出就是下一个状态,在 NFA 中,下一个状态不唯一,所以下个状态表示为 $P(Q)$ ,也就是说 $Q$ 的幂集合
  • $q_0$ 为起始状态
    在带有 $\varepsilon$移动 的状态下,NFA 可被扩展为 $NFA-\varepsilon$ 或者说 $NFA-\lambda$ ,那么此时的 $T$ 可以表示为 $Q\times (\Sigma \cup \{\varepsilon\}) \to P(Q)$

    $\varepsilon$ 移动, 即使说一个状态在没有输入的状况下转化为其他状态,也就是说,当前状态不确定,薛定谔的状态

DFA

DFA 和 NFA 可以互相转化,与 NFA 不同,DFA 在一个输入下只有唯一的一种后继状态,DFA 可以表示为 $Q\times\Sigma\to Q$ 由于 DFA 的性质,还可以写成 $Q\times\Sigma^{*}\to Q$

NFA to DFA

即由 $Q\times\Sigma\to P(Q)\Rightarrow Q\times\Sigma\to Q$,很显然的一个想法是令$Q\in P(Q)$,也就是说,把 NFA 中由一个输入产生的多个后继状态在不改变 NFA 的情况下组合成一个。

这种转换的方法叫幂集构造,由上述公式的变化,易知:

如果我们有一个$n$个状态的 NFA,当把它变为 DFA 的时候,我们最多会有 $2^n$ 个状态。

如何应用 DFA 来识别 token ?

首先我们要把语言划分成不同到成分,即不同到 class,然后如何识别呢?对于每个 class 我们可以定义相应到 DFA ,这可以用语言自带的库实现,比如字符串对比,正则表达式。然后我们只要把不同部分的 DFA 组合到一起形成一个大的 DFA 就可以了。

例子

在对 sql 进行词法分析对过程中,有个例子就是,当输入为[a-zA-Z]的时候,下一个状态是不确定的,有可能为 Identifier 也可能为 Keyword,即如下 NFA

NFA.gv.png

通过魔法,可以转化为如下 DFA

DFA.gv.png

实际上,在转换为 DFA 之后,switch 写一下 lexer 就写完了。

最近正好在写 sql 的 lexer,看到了几个例子,这里记一下。在 SQL 里,如何快速识别出关键字(KEYWORD)是分析速度最大的影响因素。我看到有两种实现。

  1. 用 hash 表实现,$O(1)$
  2. 用 字典🌲 实现, $O(1)$
  3. 顺序查找,$O(N)$

字典树是跑的最快的,因为 hash 表在最差的情况下可能到 $O(N)$ ,当然这也要看 hash 表到实现,但是字典树到最差情况就是 $O(max(len(keyword)))$ ,只要$max(len(keyword))<num_keywords$ 那么字典树就绝对更快。 ping-cap 的 sql parser 就是这么写的。


ref:

  1. DFA wiki
  2. NFA wiki
  3. pingcap sqlparser

Author : Aione
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
Link to this article : https://aione.me/2020/03/14/NFA-DFA/

This article was last updated on days ago, and the information described in the article may have changed.