正则表达式引擎实现日志

Reference

编译原理(龙书)

https://www.zhihu.com/question/27434493(实现思路)

http://www.cnblogs.com/cyjb/p/LexerIntroduce.html(基于C#的词法分析器)

https://www.cnblogs.com/plodsoft/p/5853945.html

https://github.com/chenzl25/crowbar

https://www.cnblogs.com/wrencai/p/4508585.html(介绍POSIX正则表达式标准及其拓展)

https://blog.csdn.net/ljy1988123/article/details/54666825(正则表达式的工程实践问题)

https://blog.csdn.net/cuiods/article/details/52673154(词法分析的大致框架和思路)

Intro

文本输入(可选)

编码处理

https://blog.csdn.net/guxiaonuan/article/details/78678043

https://zh.wikipedia.org/wiki/UTF-8

https://blog.whezh.com/encoded/

输入的文本载体一般为txt, txt是纯文本格式, 也没有本身没有确切的文本格式说明. 因此我们需要通过不同txt格式的特征, 猜测它们的种类, 确定了编码种类, 再进行字符编码转换. 最终将它们全都转换为UTF-32(UCS-4)的定长字符, 对应C++的char32_t, 方便处理.

字符编码

我打算仅支持读取Unicode编码, 所以我先介绍Unicode的概念以及它的几种编码方式. 然后再介绍几种其他常见的编码.

Unicode(UCS)

简单地说, Unicode(“Universal Multiple-Octet Coded Character Set”)是一项业界标准, 为每种语言的每个字符设定了统一且唯一的二进制编码. Unicode只是一个抽象的标准, 只做映射, 不涉及到编码的存储策略.

Unicode的实现方式不同于编码方式。一个字符的Unicode编码是确定的。但是在实际传输过程中,由于不同系统平台的设计不一定一致,以及出于节省空间的目的,对Unicode编码的实现方式有所不同。Unicode的实现方式称为Unicode转换格式(Unicode Transformation Format,简称为UTF)

Unicode 将全世界所有的字符定义在一个集合里。这么多的字符不是一次性定义的,而是分区定义。每个区可以存放 65536 个(2^16)字符,称为一个平面(plane)。目前,一共有 17 个(2^5)平面,也就是说,整个 Unicode 字符集的大小现在是 2^21

最前面的 65536 个字符位,称为基本平面(简称 BMP ),它的码点范围是从 0 到 2^16-1,写成 16 进制就是从 U+0000 到 U+FFFF。所有最常见的字符都放在这个平面,这是 Unicode 最先定义和公布的一个平面。剩下的字符都放在辅助平面(简称 SMP ),码点范围从 U+010000 到 U+10FFFF。

UTF-32(UCS-4)

UTF-32就是Unicode的一种定长编码方式, 利用四个字节来编码所有的Unicode字符.

虽然有32位比特, 但规定前导比特数必须为零, 故只能表示$2^{21}$个Unicode码位.

这样做好处是处理时不需要进行编码转换, 提升了效率, 但浪费了空间.

虽然为每一个码位提供固定长度的位元组看似方便, 但UTF-32存在一个字符位置有多于一种可能的码点(结合字符)或一个码点用于多个字符位置(CJK表意字符).

UTF-16(UCS-2)

UTF-16是一种变长编码方式, 一个Unicode字符需要1个或2个16位长的码元来表示.

对于 Unicode 编号范围在 0 ~ FFFF 之间的字符,UTF-16 使用两个字节存储,并且直接存储 Unicode 编号,不用进行编码转换,这跟 UTF-32 非常类似。

对于 Unicode 编号范围在 10000~10FFFF 之间的字符,UTF-16 使用四个字节存储,具体来说就是:将字符编号的所有比特位分成两部分,较高的一些比特位用一个值介于 D800~DBFF 之间的双字节存储,较低的一些比特位(剩下的比特位)用一个值介于 DC00~DFFF 之间的双字节存储。

H, L为ch16, c为ch32

1
2
3
4
> H = Math.floor((c-0x10000) / 0x400)+0xD800
>
> L = (c - 0x10000) % 0x400 + 0xDC00
>
Unicode 十六进制码点范围UTF-8 二进制
0000 0000 - 0000 007F0xxxxxxx
0000 0080 - 0000 07FF110xxxxx 10xxxxxx
0000 0800 - 0000 FFFF1110xxxx 10xxxxxx 10xxxxxx
0001 0000 - 0010 FFFF11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Unicode 编号范围 (十六进制)具体的 Unicode 编号 (二进制)UTF-16 编码编码后的 字节数
0000 0000 ~ 0000 FFFFxxxxxxxx xxxxxxxxxxxxxxxx xxxxxxxx2
0001 0000—-0010 FFFFyyyy yyyy yyxx xxxx xxxx110110yy yyyyyyyy 110111xx xxxxxxxx4

绝大多数汉字都只占2个字节. 但有例外, 如𠮷.

UTF-16

UTF-16 编码介于 UTF-32 与 UTF-8 之间,同时结合了定长和变长两种编码方法的特点。它的编码规则很简单:基本平面的字符占用 2 个字节,辅助平面的字符占用 4 个字节。也就是说,UTF-16 的编码长度要么是 2 个字节(U+0000 到 U+FFFF),要么是 4 个字节(U+010000 到 U+10FFFF)。那么问题来了,当我们遇到两个字节时,到底是把这两个字节当作一个字符还是与后面的两个字节一起当作一个字符呢?

这里有一个很巧妙的地方,在基本平面内,从 U+D800U+DFFF 是一个空段,即这些码点不对应任何字符。因此,这个空段可以用来映射辅助平面的字符。

辅助平面的字符位共有 2^20 个,因此表示这些字符至少需要 20 个二进制位。UTF-16 将这 20 个二进制位分成两半,前 10 位映射在 U+D800 到 U+DBFF,称为高位(H),后 10 位映射在 U+DC00 到 U+DFFF,称为低位(L)。这意味着,一个辅助平面的字符,被拆成两个基本平面的字符表示。

因此,当我们遇到两个字节,发现它的码点在 U+D800 到 U+DBFF 之间,就可以断定,紧跟在后面的两个字节的码点,应该在 U+DC00 到 U+DFFF 之间,这四个字节必须放在一起解读。

由于计算机存储的大端模式和小端模式, UTF-16在储存时不一定是低位对应内存低位的, 所以我们需要区分UTF-16 BE(大端模式)和UTF-16 LE(小端模式).

在UCS 编码中有一个叫做 “Zero Width No-Break Space”,中文译名作“零宽无间断间隔”的字符,它的编码是 FEFF。而 FFFE 在 UCS 中是不存在的字符,所以不应该出现在实际传输中。UCS 规范建议我们在传输字节流前,先传输字符 “Zero Width No-Break Space”。这样如果接收者收到 FEFF,就表明这个字节流是 Big-Endian 的;如果收到FFFE,就表明这个字节流是 Little- Endian 的。因此字符 “Zero Width No-Break Space” (“零宽无间断间隔”)又被称作 BOM (即Byte Order Mark)。

所幸, UTF-16储存的文件头都会有BOM(Byte Order Mark)用于区分这两种模式.

编码模式对应BOM
UTF-16 BEFE FF
UTF-16 LEFF FE

UTF-16的BOM占两个字节.

UTF-8

1545376734130

UTF-8 的编码规则很简单:如果只有一个字节,那么最高的比特位为 0;如果有多个字节,那么第一个字节从最高位开始,连续有几个比特位的值为 1,就使用几个字节编码,剩下的字节均以 10 开头。UTF-8有个优点是兼容ASCII, 当只使用一个字节时恰好对应ASCII码.

UTF-8被设计为可使用一到六个字节为每个字符编码, 编码范围甚至超出了Unicode定义的区域, 2003年11月UTF-8被RFC 3629重新规范, 只能使用Unicode定义的区域, 最多四个字节.

具体的表现形式为:

Number of bytesBits for code pointFirst code pointLast code pointByte 1Byte 2Byte 3Byte 4
17U+0000U+007F0xxxxxxx
211U+0080U+07FF110xxxxx10xxxxxx
316U+0800U+FFFF1110xxxx10xxxxxx10xxxxxx
421U+10000U+10FFFF11110xxx10xxxxxx10xxxxxx10xxxxxx

xxx 就用来存储 Unicode 中的字符编号。

对于常用的字符,它的 Unicode 编号范围是 0 ~ FFFF,用 1~3 个字节足以存储,只有及其罕见,或者只有少数地区使用的字符才需要 4~6个字节存储。

UTF-8 BOM

UTF-8以字节为编码单元因此不需要 BOM 来表明字节顺序,但可以用 BOM 来表明编码方式。字符 “Zero Width No-Break Space” 的 UTF-8 编码是 EF BB BF。所以如果接收者收到以 EF BB BF 开头的字节流,就知道这是 UTF-8编码了。

字符编码识别

借鉴状态转移的思想, 实现一个编码识别类, 而且可选是否进行编码检查.

代码未重构, 先不放

字符编码转换

由之前的介绍很容易实现编码转换, 而且借助状态转移可以拓展出实时检测编码错误和缓冲的功能.

同上

输入缓冲区

一个词素被一个模式匹配上之前, 词法分析器需要超前扫描若干字符. 为了减少回退字符到输入流的开销, 我们使用RingBuffer结构, 将每个小Buffer用双向链表连成环, 以便减少空间的使用, 减少空间分配申请.

相关变量

  • current_buffer current_index: 指向正在访问的数据缓冲区
  • first_buffer first_index: 指向最早的数据缓冲区
  • last_buffer last_index: 指向最新的数据缓冲区

正则表达式

正则表达式是一种描述词素的重要表示方法。虽然正则表达式并不能表达出所有可能的模式(例如“由等数量的 a 和 b 组成的字符串”),但是它可以非常高效的描述处理词法单元时要用到的模式类型。

正则表达式的定义

正则表达式可以由较小的正则表达式按照规则递归地构建。每个正则表达式 $r$ 表示一个语言 $L(r)$,而语言可以认为是一个字符串的集合。正则表达式有以下两个基本要素:

  1. $\epsilon$ 是一个正则表达式, $L( \epsilon ) = { \epsilon }$,即该语言只包含空串(长度为 0 的字符串)。
  2. 如果 $a$ 是一个字符,那么 $\bf{ a }$ 是一个正则表达式,并且 $L( \bf{a} ) = \{ a \}$,即该语言只包含一个长度为 1 的字符串 a。

由小的正则表达式构造较大的正则表达式的步骤有以下四个部分。假定 $r$ 和 $s$ 都是正则表达式,分别表示语言 $L(r)$ 和 $L(s)$,那么:

  1. $(r)|(s)$ 是一个正则表达式,表示语言 $L(r) \cup L(s)$,即属于 $L(r)$ 的字符串和属于 $L(s)$ 的字符串的集合( $L(r) \cup L(s) = \left\{ {s|s \in L(r)\ or\ s \in L(s)} \right\}$ )。
  2. $(r)(s)$ 是一个正则表达式,表示语言 $L(r)L(s)$,即从 $L(r)$ 中任取一个字符串,再从 $L(s)$ 中任取一个字符串,然后将它们连接后得到的所有字符串的集合( $L(r)L(s) = \left\{ {st|s \in L(r)\ and\ t \in L(s)} \right\}$ )。
  3. $(r)$ 是一个正则表达式,表示语言 $L(r)$,即将 $L(r)$ 连接 $0$ 次或多次后得到的语言。
  4. $(r)$ 是一个正则表达式,表示语言 $L(r)$。

正则表达式的标准

正则表达式的文法分为3种标准:BRE、ERE 和 ARE。其中 BER 和 ERE 属于 POSIX 标准,ARE 则是由各家定义的扩展。

正则表达式的表示

lexer使用的正则表达式描述

正则表达式描述
x单个字符 x。
.除了换行以外的任意单个字符。
[xyz]一个字符类,表示 ‘x’,’y’,’z’ 中的任意一个字符。
[a-z]一个字符类,表示 ‘a’ 到 ‘z’ 之间的任意一个字符(包含 ‘a’ 和 ‘z’)。
a-z一个字符类,表示除了 [a-z] 之外的任意一个字符。
[a-z-[b-f]]一个字符类,表示 [a-z] 范围减去 [b-f] 范围的字符,等价于 [ag-z]。
r*将任意正则表达式 r 重复 0 次或多次。
r+将 r 重复 1 次或多次。
r?将 r 重复 0 次或 1 次,即“可选”的 r。
r{m,n}将 r 重复 m 次至 n 次(包含 m 和 n)。
r{m,}将 r 重复 m 次或多次(大于等于 m 次)。
r{m}将 r 重复恰好 m 次。
(r)表示 r 本身。
rsr 与 s 的连接。
r\sr 与 s 的并。
r/s仅当 r 后面跟着 s 时,才匹配 r。这里 ‘/‘ 表示向前看,s 并不会被匹配。

Unit

简单来说, 正则表达式可以描述为一系列的字符类和运算符. 所以我定义了一个Unit枚举, 可以表示字符类Char和运算符Operator. 该类有获取unit优先级的方法, 用于实现中缀表达式转后缀表达式.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#[derive(PartialEq, Clone)]
pub enum Unit {
Char(Char),
Operator(Operator),
}

impl Unit {
pub fn get_pivot(&self) -> u32 {
match self {
Unit::Operator(op) => match op {
Operator::LeftParenthese() => 1,
Operator::RightParenthese() => 2,
Operator::Alternation() => 3,
Operator::Concatenation() => 4,
Operator::Repeat(_rp) => 5,
},
Unit::Char(_ch) => 0,
}
}
}

字符类

1
2
3
4
5
6
7
8
9
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub enum Char {
Single(char),
Set(Vec<char>),
Range(char, char),
Ranges(Vec<(char, char)>),
Not(char, char),
But(char, char, char, char),
}
enum意义
Single表示单个字符, a
Set表示字符集, 比如[abc]
Range表示字符范围, 比如[a-z]
Ranges表示字符范围集, 比如[:alpha:], [a-z,A-Z], 可用于转移合并
Not表示字符不属于一个范围, 比如[^a-z]
But表示属于一个范围且不属于另一个范围, 比如[a-z-[b-e]]

为了支持字符类的功能, 需要有以下方法

1
2
3
pub fn is_match(&self, ch: char) -> bool;
pub fn from_str(raw_str: &str) -> Option<Char>;
pub fn to_string(&self) -> String; // 转化为.dot风格的字符串

运算符类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#[derive(PartialEq, Clone)]
pub enum Repeat {
Exact(usize), // a{m}
FromZero(), // a+
From(usize), // a{m,}
FromTo(usize, usize), // a{m,n}
Maybe(), // a?
}

#[derive(PartialEq, Clone)]
pub enum Operator {
LeftParenthese(), // (
RightParenthese(), // )
Alternation(), // |
Concatenation(), // a.b
Repeat(Repeat), // a* a+ a? a{m,n}
}

为了支持多种重复运算符, 将{m,n}视为一个运算符, 并创建一个Repeat枚举. 为了支持之后的中缀表达式转后缀表达式, 为左右括号单独设置了运算符.

正则表达式的解析

1
2
3
pub struct Expression {
pub units: Vec<Unit>,
}

正则表达式的解析分两步

  • 从字符串转换为中缀表达式Vec<Unit>, 这一步只需要简单的format!就可以做到
  • 从中缀表达式转换为后缀表达式, 这一步需要获取Unit的优先级, 并且利用两个栈来获取后缀表达式, 这一步是难点. 这一步是为了之后使用Thomson方法做准备.

字符串转中缀表达式

-

中缀表达式转后缀表达式

简单来说步骤如下

  • 初始化时, 创建一个数组和一个栈, 分别为输出数组和运算符栈
  • 从中缀表达式数组中取出unit, 直到结束
    • 如果为Char, 直接输出到输出数组
    • 如果为Operator
      • 如果是), 则不断将运算符栈中的运算符弹到输出数组, 弹出(
      • 如果栈为空或当前运算符优先级大于等于栈顶运算符, 则直接将当前运算符压入运算符栈
      • 如果当前运算符优先级小于栈顶运算符, 则不断将栈顶运算符弹出到输出数组, 直到栈为空或当前运算符优先级大于等于栈顶运算符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
pub fn inffix_to_suffix(regex: Vec<Unit>) -> Vec<Unit> {
let mut ans: Vec<Unit> = Vec::new();
let mut stack: Vec<Unit> = Vec::new();

let mut back_reference_stack: Vec<Vec<Vec<Unit>>> = Vec::new();
// let mut back_reference_point: usize = 0;

for u in regex.iter() {
let pivot: u32 = u.get_pivot();
match pivot {
0 => ans.push(u.clone()),
_ => {
if stack.is_empty() {
stack.push(u.clone());
} else if *u == Unit::Operator(Operator::LeftParenthese()) {
stack.push(u.clone());
} else if *u == Unit::Operator(Operator::RightParenthese()) {
loop {
ans.push(if let Some(unit) = stack.pop() {
match unit {
Unit::Operator(Operator::LeftParenthese()) => break,
_ => unit,
}
} else { break; });
}

back_reference_stack.pop();
} else {
loop {
let stk_pivot: u32 = {
if let Some(unit) = stack.last() {
unit
}
else {break;}
}.get_pivot();

if stk_pivot <= pivot {break;}
ans.push(stack.pop().unwrap());
}
stack.push(u.clone());
}
},
}
}

loop {
if let Some(unit) = stack.pop() {
ans.push(unit);
} else { break; }
}

ans
}

不确定有限状态自动机(NFA)

https://blog.csdn.net/cuiods/article/details/52673154

NFA就是自动机的状态对字母表中的每个符号可以有也可以没有转移,对一个符号甚至可以有多个转移。有$\epsilon$转移的NFA称为$\epsilon-NFA$.

正则表达式转NFA

从正则表达式到非确定的有限状态机对于人来说非常好理解,但是对于机器来说确比较复杂。从RE到DFA有两种方法:自顶向下逐步分解法和自下而上组合方法(Thompson方法)。

自顶向下逐步分解法:Top-down stepwise refinement according to the structure of RE

这种方法符合人的思维习惯,首先我们从最简单的情况开始考虑。

base

(a|b)* a (a|b) (a|b)为例,这个正则表达式符合上面的αβ特征,因此第一步可以变成:

base1

而对于(a|b)*,又符合上面的a*特征,因此(a|b)*可以继续分解为

base2

可以看到a|b还可以继续分解,类似这样的分解过程到所有边的标记只剩下ε或字母表的单一字符为止
然而,对于计算机来说,字符是一个一个读入的,计算机不能从整体把握情况逐步向下分解,因此我们还需要适合计算机的方法。

自下而上组合法:Bottom-up combination(Thomson方法)

这种比前一种方法稍微复杂一点,但其实想法也很简单,我试着换一种表述来解释这个方法。 在遇到单个的字符时,我们直接构造转换图,比如遇到a时,我们就构造这样的转换图:

a

这样,我们就形成了一个单元U,这个U就是上面已经生成的转换图。
在遇到操作符时,我们所有的处理都是针对单元的,在下面的图示中,我们用虚线圆圈表示一个单元。

op

在处理完操作符后形成的仍是一个单元,处理完后的整体变成单元U’参与下一次处理。这里类似于一种递归的过程。
但是,像a|b这样的式子,在处理‘|’这个操作符时,我们显然需要两个单元,但计算机在读到‘|’操作符时,我们在为a构造了转换图,计算机还不知道b的存在,也就不能做上面这样的处理,所以这种方法需要以下条件:

  • 正则表达式(RE)需要处理为后缀表达式
  • 正则表达式(RE)中需要写明操作符‘.’,如ab需要写为a.b

满足以上条件后,计算机可以用这种方法自动生成NFA。

实现

我的实现中采用了Thomson方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
pub fn from_expression(expression: &Vec<Unit>) -> Nfa {
let units = expression;
let mut nfas: Vec<Nfa> = Vec::new();
for unit in units {
match unit {
Unit::Char(ch) => {
let head = FaState {
index: 0,
trans: [Tran::Char(ch.clone(), 1)].iter().cloned().collect(),
kind: FaStateType::Normal,
};
let tail = FaState {
index: 1,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

nfas.push(
Nfa {
states: vec![head, tail],
head: 0,
tail: 1,
}
)
},
Unit::Operator(Operator::Concatenation()) => {
let nfa_2 = nfas.pop().expect("Failed to get nfa");
let nfa_1 = nfas.pop().expect("Failed to get nfa");

nfas.push(Nfa::from_concatenation(nfa_1, nfa_2));
},
Unit::Operator(Operator::Alternation()) => {
let nfa_2 = nfas.pop().expect("Failed to get nfa");
let nfa_1 = nfas.pop().expect("Failed to get nfa");

nfas.push(Nfa::from_alternation(nfa_1, nfa_2));
},
Unit::Operator(Operator::Repeat(repeat)) => {
match repeat {
Repeat::Exact(times) => {
let nfa = nfas.pop().expect("Failed to get nfa");
nfas.push(Nfa::from_repeat_exact(nfa, *times));
},
Repeat::FromZero() => {
let nfa = nfas.pop().expect("Failed to get nfa");
nfas.push(Nfa::from_repeat_fromzero(nfa));
},
Repeat::From(from) => {
let nfa = nfas.pop().expect("Failed to get nfa");
nfas.push(Nfa::from_repeat_from(nfa, *from));
},
Repeat::FromTo(from, to) => {
let nfa = nfas.pop().expect("Failed to get nfa");
nfas.push(Nfa::from_repeat_fromto(nfa, *from, *to));
},
Repeat::Maybe() => {
let nfa = nfas.pop().expect("Failed to get nfa");
nfas.push(Nfa::from_repeat_maybe(nfa));
}
}
},
_ => {
panic!("unexpected char");
},
}
}

nfas.pop().expect("Generate Nfa Error.")
}

基本规则

epsilon转移和字符转移

对于正则表达式 ϵ,构造如图的 NFA

对于包含单个字符 a 的正则表达式 a,构造如图的 NFA。

img

归纳规则

s|t

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
fn from_alternation(mut nfa_1: Nfa, mut nfa_2: Nfa) -> Nfa {
let len_1 = nfa_1.states.len();
let len_2 = nfa_2.states.len();

let head = FaState {
index: 0,
trans: [
Tran::Epsilon(1),
Tran::Epsilon(1 + len_1),
].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let tail = FaState {
index: len_1 + len_2 + 1,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

nfa_1.add_offset(1);
nfa_2.add_offset(len_1 + 1);

nfa_1.states[nfa_1.tail - 1].add_epsilon_tran(tail.index);
nfa_2.states[nfa_2.tail - 1 - len_1].add_epsilon_tran(tail.index);

Nfa {
head: 0,
tail: tail.index,
states: {
let mut states: Vec<FaState> = Vec::new();

states.push(head);
states.append(&mut nfa_1.states);
states.append(&mut nfa_2.states);
states.push(tail);

states
}
}
}

st

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fn from_concatenation(mut nfa_1: Nfa, mut nfa_2: Nfa) -> Nfa {
nfa_2.add_offset(nfa_1.states.len());

let old_tail = nfa_1.tail;
let old_head = nfa_2.head;
let tail = nfa_2.tail;

nfa_1.states.append(&mut nfa_2.states);
nfa_1.states[old_tail].add_epsilon_tran(old_head);

nfa_1.tail = tail;

nfa_1
}

s*

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
fn from_repeat_fromzero(mut nfa_1: Nfa) -> Nfa {
let len_1 = nfa_1.states.len();

let head = FaState {
index: 0,
trans: [
Tran::Epsilon(1),
Tran::Epsilon(1 + len_1),
].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let tail = FaState {
index: len_1 + 1,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

nfa_1.add_offset(1);

nfa_1.states[nfa_1.tail - 1].add_epsilon_tran(tail.index);
nfa_1.states[nfa_1.tail - 1].add_epsilon_tran(1);

Nfa {
head: 0,
tail: tail.index,
states: {
let mut states: Vec<FaState> = Vec::new();

states.push(head);
states.append(&mut nfa_1.states);
states.push(tail);

states
}
}
}

s?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
fn from_repeat_maybe(mut nfa_1: Nfa) -> Nfa {
let len_1 = nfa_1.states.len();

let head = FaState {
index: 0,
trans: [
Tran::Epsilon(1),
Tran::Epsilon(1 + len_1),
].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let tail = FaState {
index: len_1 + 1,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

nfa_1.add_offset(1);

nfa_1.states[nfa_1.tail - 1].add_epsilon_tran(tail.index);

Nfa {
head: 0,
tail: tail.index,
states: {
let mut states: Vec<FaState> = Vec::new();

states.push(head);
states.append(&mut nfa_1.states);
states.push(tail);

states
}
}
}

s{m}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
fn from_repeat_exact(nfa_1: Nfa, times: usize) -> Nfa {
let len_1 = nfa_1.states.len();

let head = FaState {
index: 0,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let tail = FaState {
index: len_1 * times + 1,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let mut new_states: Vec<FaState> = Vec::new();

new_states.push(head);

for time in 0..times {
let mut nfa_tmp = nfa_1.clone();
nfa_tmp.add_offset(time * len_1 + 1);

new_states.last_mut().unwrap().add_epsilon_tran(time * len_1 + 1);
new_states.append(&mut nfa_tmp.states);
}

new_states.last_mut().unwrap().add_epsilon_tran(times * len_1 + 1);
new_states.push(tail);

Nfa {
head: 0,
tail: 1 + len_1 * times,
states: new_states,
}
}

s{m,n}

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
fn from_repeat_fromto(nfa_1: Nfa, m: usize, n: usize) -> Nfa {
let len_1 = nfa_1.states.len();

let head = FaState {
index: 0,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let tail = FaState {
index: len_1 * n + 1,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let mut new_states: Vec<FaState> = Vec::new();

new_states.push(head);

for time in 0..n {
let mut nfa_tmp = nfa_1.clone();
nfa_tmp.add_offset(time * len_1 + 1);

new_states.last_mut().unwrap().add_epsilon_tran(time * len_1 + 1);
new_states.append(&mut nfa_tmp.states);
}

new_states.last_mut().unwrap().add_epsilon_tran(n * len_1 + 1);
new_states.push(tail);

for i in m-1..n-1 {
let index = (i + 1) * len_1;
new_states[index].add_epsilon_tran(n * len_1 + 1);
}

Nfa {
head: 0,
tail: 1 + len_1 * m,
states: new_states,
}
}

s{m,}

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
fn from_repeat_from(nfa_1: Nfa, times: usize) -> Nfa {
let len_1 = nfa_1.states.len();

let head = FaState {
index: 0,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let tail = FaState {
index: len_1 * times + 1,
trans: [].iter().cloned().collect(),
kind: FaStateType::Normal,
};

let mut new_states: Vec<FaState> = Vec::new();

new_states.push(head);

for time in 0..times {
let mut nfa_tmp = nfa_1.clone();
nfa_tmp.add_offset(time * len_1 + 1);

new_states.last_mut().unwrap().add_epsilon_tran(time * len_1 + 1);
new_states.append(&mut nfa_tmp.states);
}

new_states.last_mut().unwrap().add_epsilon_tran(times * len_1 + 1);
new_states.last_mut().unwrap().add_epsilon_tran((times - 1) * len_1 + 1);
new_states.push(tail);

Nfa {
head: 0,
tail: 1 + len_1 * times,
states: new_states,
}
}

确定有限状态自动机

对于一个已经形成的NFA,我们需要定义新的状态来形成DFA。首先要解释两种方法和他们对应的使用情形。

导致”不确定”的根源

NFA之所以为NFA而不是DFA,主要是因为以下两个原因,解决以下的两种情形,就能将NFA转为DFA。

边上的$\epsilon$闭包

dfa

遇到这种情况,后面的三个状态完全可以合并,如果将后面的三个状态合为一个,那这个转换图里就没有ε边,也就满足了DFA的条件。

对应的解决方法是找出ε闭包,也就是先找出该状态的ε边推出的所有状态,再找那些状态的ε边推出的状态,是一个迭代的过程,直到找出一个状态的ε闭包。如果是从状态x开始的,我们将通过该过程找到的所有状态集称为以x状态为核的ε闭包,记为ε-closure({x}),或ε-c({x})。从定义可以知道,核相同,推出的ε闭包一定相同。

不确定的后续状态

dfa

遇到这种情况,如果能将状态2和状态3合并到一起,就不会出现“面对相同的输入状态可能跳转到多种状态的情形了”,合并状态2和状态3这样类似的状态的方法叫做子集构造法,若从状态Ii开始,以a边推出的所有状态集合为B,我们记为Ii–a–>B,比如上图可以记为1-a->{2,3}

NFA->DFA: 子集构造法

原理

将 NFA 转换为 DFA,采用的是子集构造(subset construction)算法。该算法的过程与 NFA 匹配过程比较相似。在 NFA 的匹配过程中,使用的都是 NFA 的一个状态集合,那么子集构造法就是用 DFA 的一个状态来对应 NFA 的一个状态集合,即 DFA 读入输入字符串 *a1a2⋯an之后到达的状态,就对应于 NFA 读入同样的字符串

a1a2⋯an之后到达的状态的集合。

子集构造算法需要用到的操作有:

  • ϵ-closure(s): 能够从 NFA 的状态 s 开始,获得只通过 ϵ 转移能够到达的 NFA 状态集合
  • ϵ-closure(T): 能够从 T 中某个 NFA 状态 s开始,只通过 ϵ 转移能够到达的 NFA 状态集合,即 $\cup_{s \in T} \epsilon \text{-} closure(s)$
  • move(T,a): 能够从 T 中某个状态 s 出发,通过标号为 a 的转移到达的 NFA 状态集合

子集构造法

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:一个 NFA N
输出:与 NFA 等价的 DFA D
一开始,ϵ-closure(s0) 是 D 中的唯一状态,且未被标记
while (在 D 中存在未被标记的状态 T) {
为 T 加上标记
foreach (每个字符类 a) {
U=ϵ-closure(move(T,a))
if (U 不在 D 中) {
将 U 加入 D 中,且未被标记
}
T[a]=U
}
}

计算 ϵ-closure(T)

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:NFA 的状态集合 T
输出:ϵ-closure(T)
将 T 的所有状态压入堆栈
ϵ-closure(T)=T
while (堆栈非空) {
弹出栈顶元素 t
foreach (u : t 可以通过 ϵ 转移到达 u) {
if (u∉ϵ-closure(T)) {
ϵ-closure(T)=ϵ-closure(T)∪{u}
将 u 压入堆栈
}
}
}

move(T,a)

1
2
3
4
5
6
7
8
输入:NFA 的状态集合 T
输出:move(T,a)
move(T,a)=∅
foreach (u∈T) {
if (u 存在字符类 a 上的转移,目标为 t) {
move(T,a)=move(T,a)∪{t}
}
}

示例

img

img

img

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
fn get_epsilon_closure(t: Option<Vec<bool>>, states: &Vec<FaState>) -> Option<Vec<bool>> {
match t {
None => None,
Some(t) => {
let mut e_t = t.clone();
let mut stack: Vec<usize> = Vec::new();
for (i, b) in t.iter().enumerate() {
match b {
true => stack.push(i),
false => {},
}
}
loop {
if let Some(t) = stack.pop() {
for tran in &states[t].trans {
match tran {
Tran::Char(_ch, _u) => {},
Tran::Epsilon(u) => {
if e_t[*u] == false {
e_t[*u] = true;
stack.push(*u);
}
}
}
}
} else {break;}
}
Some(e_t)
}
}
}
fn get_move(t: Vec<bool>, a: &Char, states: &Vec<FaState>) -> Option<Vec<bool>> {
let mut m_t = None;

for (i, &b) in t.iter().enumerate() {
if b == true {
for tran in &states[i].trans {
if let Tran::Char(ch, to) = tran {
if *ch == *a {
if let None = m_t {
let mut tmp: Vec<bool> = Vec::new();
for _i in 0..states.len() {
tmp.push(false);
}
m_t = Some(tmp);
}

m_t = match m_t {
None => panic!(""),
Some(mut m_t) => {
m_t[*to] = true;
Some(m_t)
}
}
}
}
}
}
}

m_t
}

impl dfa {
pub fn from_nfa(nfa_states: &Vec<FaState>, chars: HashSet<Char>) -> Dfa {
let mut dfa = Dfa {
head: 0,
tail: vec![],
states: [].iter().cloned().collect(),
};
dfa.states.push(FaState {
index: dfa.states.len(),
trans: [].iter().cloned().collect(),
kind: FaStateType::Head,
});

let mut bool_states: Vec<bool> = Vec::new();
for _i in 0..nfa_states.len() { bool_states.push(false); }
bool_states[0] = true;
bool_states = match get_epsilon_closure(Some(bool_states), &nfa_states) {
None => panic!(""),
Some(bool_states) => bool_states,
};

let mut raw_states: Vec<Vec<bool>> = Vec::new();
raw_states.push(bool_states.clone());

let mut map: HashMap<Vec<bool>, usize> = HashMap::new();
map.insert(bool_states.clone(), 0);

let mut done: HashSet<usize> = HashSet::new();


let mut queue: VecDeque<usize> = VecDeque::new();
queue.push_back(0);

loop {

if let Some(t) = queue.pop_front() {
done.insert(t);

for ch in chars.iter() {
let bool_states = raw_states[t].clone();

if let Some(u) = get_epsilon_closure(get_move(bool_states, ch, &nfa_states), &nfa_states) {
let u_id = if let Some(u_id) = map.get(&u) {
*u_id
} else {
let u_id = dfa.states.len();

dfa.states.push(FaState {
index: u_id,
trans: [].iter().cloned().collect(),
kind: {
if u[nfa_states.len() - 1] {
dfa.tail.push(u_id);
FaStateType::Tail
} else {
FaStateType::Normal
}
},
});

raw_states.push(u.clone());

map.insert(u.clone(), u_id);

u_id
};

dfa.states[t].add_char_tran(ch.clone(), u_id);

if let None = done.get(&u_id) {
queue.push_back(u_id);
}
}
}
} else {break;}
}

dfa
}
}

DFA 的化简

DFA 最小化

上面虽然构造出了一个可用的 DFA,但它可能并不是最优的,例如下面的两个等价的 DFA,识别的都是正则表达式 (a|b)*baa,但具有不同的状态数。

img

显然,状态数越少的 DFA,匹配时的效率越高,所以需要使用一些算法,来将 DFA 的状态数最小化,即 DFA 的化简。

化简 DFA 的思想是寻找等价状态——它们都(不)是接受状态,而且对于任意的输入,总是转移到等价的状态。找到所有等价的状态后,就可以将它们合并为一个状态,实现 DFA 状态数的最小化。

寻找等价状态一般有两种方法:分割法和合并法。

  • 分割法是先将所有接受状态和所有非接受状态看作两个等价状态集合,然后从里面分割出不等价的状态子集,直到剩下的所有等价状态集合都不可再分。
  • 合并法是先将所有状态看作不等价的,然后从里面找到两个(或多个)等价的状态,并合并为一个状态。

两种方法都可以实现 DFA 的化简,但是合并法比较复杂,因此这里我使用分割法来对 DFA 进行化简。

DFA 最小化的算法如下:

输入:一个 DFA D
输出:与 D 等价的最简 DFA D’
构造 D 的初始划分 $\Pi$,初始划分包含两个组:接受状态组和非接受状态组
while (true) {
foreach (组 $G \in \Pi$) {
将 G 划分为更小的组,使得两个状态 s 和 t 在同一组中当且仅当对于所有输入符号,s 和 t 的转移都到达 $\Pi$ 中的同一组
}
将新划分的组保存到 $\Pi _{new}$ 中
if ($\Pi_{new} \ne \Pi$) {
$\Pi = \Pi_{new}$
} else {
$\Pi _{final} = \Pi$
break;
}
}
在 $\Pi _{final}$ 中的每个组中都选取一个状态作为该组的代表,这些代表就构成了 D’ 的状态。
$D’$ 的开始状态是包含了 $D$ 的开始状态的组的代表。
$D’$ 的接受状态是包含了 $D$ 的接受状态的组的代表。
令 $s$ 是 $\Pi_{final}$ 中某个组 $G$ 中的状态(不是代表),那么将 $D’$ 中到 $s$ 的转移,都更改为到 $G$ 的代表的转移。

因为接受状态和非接受状态在最开始就被划分开了,所以不会存在某个组即包含接受状态,又包含非接受状态。

在实际的实现中,需要注意的是由于一个 DFA 状态可能对应多个不同的终结符,因此在划分初始状态时,对应的终结符不同的终结状态也要被划分到不同的组中。

字符类合并

在 DFA 最小化之后,还要将字符类也最小化,因为 DFA 的最小化过程会合并等价状态,这时可能会使得某些字符类变得等价,如图 5 所示。

img

等价字符类的寻找比等价状态更简单些,先将化简后的 DFA 用表格的形式写出来,以图 5 中的 DFA 为例:

DFA 状态a 上的转移b 上的转移c 上的转移
ABB\emptyset
BBBC
C\emptyset\emptyset\emptyset

表格中的第一列是 DFA 的状态,后面的三列分别代表不同字符类上的转移。表格的第二行到第四行分别对应着 A、B、C 三个状态的转移。那么,如果在这个表格中某两列完全相同,那么对应的字符类就是等价的。

文章目录
  1. 1. Reference
  2. 2. Intro
  3. 3. 文本输入(可选)
    1. 3.1. 编码处理
      1. 3.1.1. 字符编码
        1. 3.1.1.1. Unicode(UCS)
        2. 3.1.1.2. UTF-32(UCS-4)
        3. 3.1.1.3. UTF-16(UCS-2)
        4. 3.1.1.4. UTF-8
      2. 3.1.2. 字符编码识别
      3. 3.1.3. 字符编码转换
    2. 3.2. 输入缓冲区
  4. 4. 正则表达式
    1. 4.1. 正则表达式的定义
    2. 4.2. 正则表达式的标准
    3. 4.3. 正则表达式的表示
    4. 4.4. 正则表达式的解析
      1. 4.4.1. 字符串转中缀表达式
      2. 4.4.2. 中缀表达式转后缀表达式
  5. 5. 不确定有限状态自动机(NFA)
    1. 5.1. 正则表达式转NFA
      1. 5.1.1. 自顶向下逐步分解法:Top-down stepwise refinement according to the structure of RE
      2. 5.1.2. 自下而上组合法:Bottom-up combination(Thomson方法)
    2. 5.2. 实现
    3. 5.3. 基本规则
      1. 5.3.1. epsilon转移和字符转移
    4. 5.4. 归纳规则
      1. 5.4.1. s|t
      2. 5.4.2. st
      3. 5.4.3. s*
      4. 5.4.4. s?
      5. 5.4.5. s{m}
      6. 5.4.6. s{m,n}
      7. 5.4.7. s{m,}
  6. 6. 确定有限状态自动机
    1. 6.1. 导致”不确定”的根源
      1. 6.1.1. 边上的$\epsilon$闭包
      2. 6.1.2. 不确定的后续状态
    2. 6.2. NFA->DFA: 子集构造法
      1. 6.2.1. 原理
      2. 6.2.2. 示例
      3. 6.2.3. 实现
    3. 6.3. DFA 的化简
      1. 6.3.1. DFA 最小化
      2. 6.3.2. 字符类合并
|