Rust 实现一个表达式 Parser(4) DFA 实现-六虎

本文将详细完结一个 DFA 进行词法剖析, 在文章中将尽量避开理论, 尽量谈实践

源码 src/lexer/dfa.rs

DFA 介绍

全称 DFA(Deterministic Finite Automaton) 确认有限状况自动机, 与之相对的是 NFA(Non-Deterministic Finite Automaton) 非确认有限状况自动机, 关于 DFA 和 NFA 的区别放到文末打开, 此处只介绍 DFA

DFA 是一种能够依据不同的输入转化到不同状况的特殊的数学模型

以下假定笔者自己便是一个 DFA, 如下

从图能够看出, DFA 看起来很像是一个带权有向图

每个极点都表明我的一种状况, 如 “我起床”, “我学习”, “我吃饭” 等
每条弧上的权重表明我发现了什么, 如 “我发现到饭点了”, “我发现朋友叫我出去玩”, “我发现没玩够” 等
每条弧的方向指示我能够从某种状况到达某种状况, 如 “我能够从起床状况到吃饭状况”, “我能够从吃饭状况到玩状况” 等

以下将上述解释套用到 DFA 中

每个极点表明一种状况
每条弧表明能够从某个状况迁移到另一状况, 详细的, 下一状况称为当时状况的后继状况
每条弧上的权重表明 DFA 接纳到的某种输入
同心圆指示的是中止状况, 如上图中是 “睡觉”
未连通的箭头指出的是开始状况, 如上图中是 “起床”

那么此时假定我这个 DFA 接纳到以下输入序列

["到饭点了", "朋友叫我出去玩", "没玩够", "没玩够", "没玩够", "玩累了"]

易得我承受完一切输入序列终究会停留在 “睡觉” 这一状况, 这一状况也是中止状况, 这意味着这一天完毕了

回到起点, 假定当时有如下输入

["到饭点了", "朋友叫我出去玩", "没玩够" ]

易得我承受完一切输入序列终究会停留在 “玩” 这一状况, 这一状况并不是中止状况, 这意味着这一天还没有完毕

将上面的描述套用到 DFA 中, 则是若承受完一个输入序列, DFA 停留在中止态, 则称该 DFA 承受该输入, 不然则称不承受

那么说了上面这么多, “确认” 和 “有限” 体现在哪里呢

有限: DFA 的状况有限, 能够穷举
确认: 对每一个不同的输入, DFA 总有仅有对应的后继状况, 详细来说便是我不会在接纳到 “到饭点了” 这个输入后, 又能够挑选吃饭, 又能够挑选玩, 我一定会吃饭

DFA 模型

以下直接给出 tiny-expr-parser 的词法剖析阶段运用的 DFA 的模型

简略说明一下

该 DFA 不承受前缀 0, 因而为了简略起见, 将 0 独自作为一种输入承受
上图省略了失利状况, 在详细完结时, 咱们需求得知当时输入是否合法, 因而会增加一个失利状况, 详细来说也便是停留在 zero 状况时, 若是再承受 0 或 1-9 就会进入失利状况, 由于输入不合法, 中止解析进程
DFA 完好运转一次能够得到一个合法输入, 比方一串数字, 一个操作符, 而咱们期望 DFA 在匹配出一个合法输入后继续进行匹配, 直到解析完一切的输入序列, 因而需求在完结的时分做点小手脚

DFA 怎么完结

DFA 看起来像一个特殊的有向带权图, 而咱们的需求其实十分简略, 即依据当时输入以及当时状况快速查找后继状况, 再判别此状况是否是中止态

众所周知, 有向带权图有两种常见的存储结构, 分别是 邻接矩阵 和 十字链表, 这儿咱们应该挑选何种存储结构呢, 以下针对咱们的需求来剖析一下两种存储结构的特色

邻接矩阵

能够在 O(1) 时刻复杂度内求得两极点之间是否连通以及对应权重, 但需求依据权重判别能够到达的下一极点需求遍历极点对应的那一行数据, O(N) 时刻复杂度
全体空间复杂度是 O(极点数量 * 极点数量), 因而若是极点数量大于弧的数量, 会存在大量空间浪费
初始化能够直接硬编码

十字链表

通常能够在 O(1) 的时刻复杂度内求得某极点的出度和入度, 可是依据权重判别能够到达的下一极点需求遍历当时极点的一切出边组成的链表, O(N) 时刻复杂度
尽管存在很多指针域, 但不会存在冗余数据, 空间复杂度 O(极点数量 + 弧的数量)
初始化需求动态创立每个极点的邻接表

能够看到, 貌似没有特别合适的存储结构, 而且最主要的依据权重查找可达的下一极点的需求都需求 O(N) 的时刻复杂度来完结, 可是实际上 DFA 中有个很重要的条件没有运用上, 输入可穷举, 这意味着这个图的权重值是能够穷举的, 那么咱们就能够根据邻接矩阵改变一下存储思路

op	ws	0	1-9
START	1	0	2	3
OPERATOR
ZERO
NUM	3	3

以下解释一下

运用一个矩阵来存储所需, 记为 table
横坐标是一切的输入记为 input
纵坐标是一切的状况, 记为 state
table[state][input] 存储的是当时 state 接纳到 input 时的后继状况
- 如 table[0][1] == 1 表明 START 状况接纳到一个 op 输入, 后继状况为 1 号状况, 也便是索引为 1 的状况 OPERATOR, 说再简略一点便是处在 START 状况接纳到一个 op 输入, 就迁移到 OPERATOR 状况

这样存储有什么好处呢

依据输入查找后继状况只需求 O(1) 时刻复杂度
全体空间复杂度为 O(状况数量 * 条件数量), 而且不可达的情况是应该判别出来并报错的, 也便是说上表比如中的空位都是有用的, 这意味着几乎没有冗余数据
完全能够硬编码初始化

因而运用上述存储结构就能够完美满意咱们的需求, 不过在详细运用的时分还需求再动点小手脚

动点小手脚

由前面的剖析可知, 咱们的状况共有 4 种

START: 开始状况
OPERATOR: 操作符, 中止状况
ZERO: 0, 中止状况
NUM: 数字, 中止状况

输入也有 4 种

op: 任意操作符, "+", "-", "*", "/", "(", ")"
ws: 空格
0: 数字 0
1-9: 数字 1~9

咱们能够快速的依据上面的图建出如下状况表

op	ws	0	1-9
START	1	0	2	3
OPERATOR
ZERO
NUM	3	3

而咱们期望能获知犯错状况, 而且为了便利统一处理, 便将犯错也独自视为一种状况, 建表如下

op	ws	0	1-9
ERROR	0	0	0	0
START	2	1	3	4
OPERATOR
ZERO
NUM	4	4

当犯错时应该立刻中止解析工作并报错, 因而其后继状况咱们不需求关怀, 这儿就随意填个 0 了

此外还有一个问题, 规范的 DFA 一次匹配出一个合法或不合法的输入序列, 而咱们期望这个 DFA 能一直匹配出多个合法序列, 并在犯错时直接中止, 因而再进行如下更改

op	ws	0	1-9
ERROR	0	0	0	0
START	2	1	3	4
OPERATOR	2	1	3	4
ZERO	2	1
NUM	2	1	4	4

当 每个中止状况 接纳到 非当时状况可承受的, 但能够搬运到另一中止状况, 且合法的输入, 就直接让其搬运

比方 OPERATOR 状况下, 若是接纳到数字 0, 就直接让其搬运到 ZERO 状况, 这样咱们就能够直接比照搬运前后状况是否持平来判别是否解析出了一个完好的 Token

这样做仅仅为了简化完结逻辑, 并非有必要

最后将空位填 0 表明犯错, 详细来说便是若当时匹配到一个独自的 0, 后续匹配到任何数字都以为是不合法输入

这样就得到了咱们终究的状况转化表

op	ws	0	1-9
ERROR	0	0	0	0
START	2	1	3	4
OPERATOR	2	1	3	4
ZERO	2	1	0	0
NUM	2	1	4	4

DFA 完结

上面大致理清了完结思路, 下面将正式完结 DFA, 再次放上模型和状况转化表

模型
状况转化表

op ws 0 1-9

ERROR 0 0 0 0

START 2 1 3 4

OPERATOR 2 1 3 4

ZERO 2 1 0 0

NUM 2 1 4 4

状况完结

至此已经十分简略了, 直接硬编码出所需状况, 此外再专门封装一个函数来判别当时状况是否是中止态

这儿运用了闭包来防止引入过多的全局变量

pub const ERROR: usize = 0;
pub const START: usize = 1;
pub const OPERATOR: usize = 2;
pub const ZERO: usize = 3;
pub const NUM: usize = 4;
pub fn get_terminator_judgement() -> impl Fn(usize) -> bool {
    const END_STATE: [usize; 3] = [OPERATOR, ZERO, NUM];
    |state: usize| END_STATE.contains(&state)
}

运用办法如下

#[test]
fn zero_is_terminator() {
    let is_terminator = get_terminator_judgement();
    assert!(is_terminator(ZERO));
}

状况转化函数完结

状况转化表的完结只需求直接硬编码就能够了, 而条件的判别还需求独自封装几个简略的函数, 完结如下

pub fn get_transition() -> impl Fn(char, usize) -> usize {
    /// 状况转化表
    ///
    /// |              | op  | ws  | 0   | 1-9 |
    /// |--------------|-----|-----|-----|-----|
    /// | ERROR        | E   | E   | E   | E   |
    /// | START        | 2   | 1   | 3   | 4   |
    /// | OPERATOR     | 2   | 1   | 3   | 4   |
    /// | ZERO         | 2   | 1   | E   | E   |
    /// | NUM          | 2   | 1   | 4   | 4   |
    ///
    const STATE_TABLE: [(usize, usize, usize, usize); 5] = [
        (0, 0, 0, 0), // ERROR
        (2, 1, 3, 4), // START
        (2, 1, 3, 4), // OPERATOR
        (2, 1, 0, 0), // ZERO
        (2, 1, 4, 4), // NUM
    ];
    let is_op = |c: char| match c {
        '-' | '+' | '*' | '/' | '(' | ')' => true,
        _ => false,
    };
    let is_whitespace = |c: char| match c {
        ' ' => true,
        _ => false,
    };
    let is_zero = |c: char| match c {
        '0' => true,
        _ => false,
    };
    let is_one_to_nine = |c: char| match c {
        '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => true,
        _ => false,
    };
    // 回来一个闭包防止引入过多的全局变量
    move |c: char, state: usize| {
        if is_op(c) {
            // 这儿是公式
            //    后继状况 = table[当时状况][满意条件的输入]
            STATE_TABLE[state].0
        } else if is_whitespace(c) {
            STATE_TABLE[state].1
        } else if is_zero(c) {
            STATE_TABLE[state].2
        } else if is_one_to_nine(c) {
            STATE_TABLE[state].3
        } else {
            ERROR
        }
    }
}

需求留意的是这儿有必要运用 move 关键字来指定 移动一切权 的语义, 由于闭包的生命周期会比这个函数更长, 不获取一切权的话会导致这儿面的暂时变量 drop 掉

该函数回来的闭包函数承受两个参数, 分别是当时输入的字符以及当时的状况, 接着直接运用封装好的函数来进行状况的改变即可, 该函数的运用办法如下

#[test]
fn start_transfer_to_operator_while_received_an_operator() {
    let transition = get_transition();
    assert_eq!(OPERATOR, transition('+', START));
}

至此 DFA 的中心部分已经完结, 剩下部分需求根据词法剖析的逻辑, 因而放到下一篇

DFA & NFA

下面来简略介绍一下 DFA 和 NFA 的区别, 首先回想前文提到的笔者本身作为 DFA, 如下图

这儿直接给出 NFA 版别, 需求留意的是, 下面这个 NFA 和上面这个 DFA 并非等价

不考虑图中含义, NFA 版别和 DFA 版别有以下两点不同

起床 状况时, 我不需求任何条件就能够直接到达 吃饭 状况
吃饭 状况时, 我接纳 “朋友叫我出去玩” 的输入能够到达 玩 状况也能够到达 睡觉 状况

这便是 NFA 和 DFA 的主要不同之处

NFA 中能够存在空输入, 即不需求任何输入也能够迁移状况, 通常记为 $\epsilon$
NFA 中一个状况接纳到某一输入后, 后继状况能够不仅有

以上两点其实能够合并成, NFA 中某一状况接纳到某一输入的后继状况能够不仅有, 这也是 NFA 中 N(Nondeterministic) 非确认 的原因

现在有相关理论证明了 NFA 和 DFA 的等价性, 也存在现成的将 NFA 转化为 DFA 的办法, 实际上转化为 DFA 再完结是 NFA 通常的完结思路, 不过将 NFA 转化为 DFA 通常会导致状况数量的指数等级爆炸, 因而还需求进行化简等操作, 简略来说便是完结 NFA 有点费事

详细的转化办法和化简办法这儿就不打开说了, 由于都是很机械性的工作, 百度一下看看就能懂

Q&A

Q: DFA 还有什么应用?

A: 挺多的, 现在个人感觉自动机是这种匹配问题的杀手等级解决方案, 应用方面一会儿还说不上来很多, 可是感觉匹配相关的问题大部分都能够用自动机解决, 仅仅合不合适的问题, 以下简略罗列一下

DFA/NFA 完结正则表达式(单/多形式匹配)
AC 自动机进行灵敏词匹配(多形式匹配)

Q: 除了用 DFA 还有什么办法能够完结?

A: 上正则! 可是正则本质上也是自动机, 可能是 DFA 或者 NFA

Q: 能够用 NFA 完结么?

A: 实际上一开始我是期望能直接在这一步匹配出正负数并支撑浮点数运算的, 那么很天然的就画出了一个 NFA, 然后通过转化和化简发现很费事很冗余, 我以为没有必要在这儿增加了解的复杂度, 由于中心逻辑应该越精简越好, 因而就直接写出最简略的一个 DFA, 然后砍掉了对浮点数运算的支撑, 可是实际上做起来并不难, 便是费事, 感兴趣的能够自己尝试一下

Rust 实现一个表达式 Parser(4) DFA 实现

DFA 介绍

DFA 模型

DFA 怎么完结

动点小手脚

DFA 完结

状况完结

状况转化函数完结

DFA & NFA

Q&A

作者信息

推广

Rust 实现一个表达式 Parser(4) DFA 实现

DFA 介绍

DFA 模型

DFA 怎么完结

动点小手脚

DFA 完结

状况完结

状况转化函数完结

DFA & NFA

Q&A

相关文章

Jetpack Compose(十一)-重组与自动刷新

让 Windows 终端 🚀 飞一会

Compose：从重组谈谈页面性能优化思路，狠狠优化一笔

IDE远程调试

作者信息

推广