看 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
通过魔法，可以转化为如下 DFA
实际上，在转换为 DFA 之后，switch 写一下 lexer 就写完了。
最近正好在写 sql 的 lexer，看到了几个例子，这里记一下。在 SQL 里，如何快速识别出关键字(KEYWORD)是分析速度最大的影响因素。我看到有两种实现。
- 用 hash 表实现，$O(1)$
- 用 字典🌲 实现， $O(1)$
- 顺序查找，$O(N)$
字典树是跑的最快的，因为 hash 表在最差的情况下可能到 $O(N)$ ，当然这也要看 hash 表到实现，但是字典树到最差情况就是 $O(max(len(keyword)))$ ，只要$max(len(keyword))<num_keywords$ 那么字典树就绝对更快。 ping-cap 的 sql parser 就是这么写的。
ref: