正则引擎设计与实现——基于子集构造法

本文对应的代码实现托管在 Github

light-regex

词法分析

词法分析的任务是把输入序列分割为词素单元.

在自然语言中, 以英语为例, 构成句子的最小单元,可以是单词、短语, 这些最小单元称作 词素(lexeme) . 词素具有属性, 比如动词、名词、副词、形容词等, 这些属性决定了语法层面, 其在句子里可充当的成分.

对于程序语言, 个人的感受是, 对词素并没有一个固定的边界定义, 如果词法分析阶段做的事少一点, 那么语法分析阶段做的事就要多一点, 考虑到语法分析要远比词法分析复杂, 所以后者应当为前者服务, 以尽可能减轻语法分析的复杂度. 因此,我一般先设计文法(也称语法), 在过程中考虑需要有哪些类型的词素.

这里我们先确定两种基本的词素:

1. 匹配字符, 即需要用于匹配的字符, 如单个字符, \ 引导的转义字符 ,\u 引导的 Unicode code point
2. 控制字符, 不匹配, 具有特殊语义的字符 , 如 | ,? ,+ ,* , ( , )

词素的数据类型

直觉上会想到用 char 表示词素, 在很多语言中, char 类型是 16 bit, 采用 UTF-16 编码 (比如 JAVA 和 C#), 对于占用 2 个 code unit 的 unicode 字符需要占用 2 个 char, 所以一个超过 0XFFFF 的 Unicode 字符会被分割为两个词素. 这对于单点匹配没有什么问题,但是,对于范围匹配如 [ - ] ,对应的 Unicode code point 范围是 [\u{1F600}-\u{1F64F}],不可能把边界 1F600 和 1F64F 分别拆成两个 char .

如果用 String 表示,可以满足功能实现,但是对象类型会造成较大的空间浪费.

如果用 int 表示,那么刚好 32 bit,可以直接存 Unicode code point,空间占用合理,也很方便程序统一处理.

关于 EOF

由于我们采用基础类型 int 存储词素, 当读完时返回 null 是不行的. 好在, Unicode code point 的范围是 0x0000 0000 ~ 0x0010 FFFF , 所以可以采用一个超出该范围的特殊值表示 EOF.

词法分析的编码实现

在编码实现上, 一个经验指导是, 使用策略模式独立出不同类型的词素的分词逻辑, 以对象组合的方式组装出词法分析器. 一个词法分析器由多个分词策略组成, 这些分词策略具有不同的优先级, 可采用一个排序树的结构来存放.

语法分析

词法分析是将词素序列转为抽象语法树(Abstract syntax tree)的过程

在自然语言, 比如英语中, 有5种基本句型:

• 主语 + 不及物动词
• 主语 + 及物动词 + 宾语
• 主语 + 及物动词 + 间宾 + 直宾
• 主语 + 及物动词 + 宾语 + 补语
• 主语 + 系动词 + 补语

我们选取其中一种句型作为例子, 我们可以说: "一个英语句子可以由主谓宾构成", 于是我们把这句话写作如下形式:

句子 -> 主语 + 及物动词 + 宾语

接下来, 我们会问, 主语是什么? 答案可写作如下形式:

主语 -> 名词 | 名词性子句 | 动名词 | 不定式

下一个问题, 及物动词是什么? 答案是, 其已经是最小单元, 不可被继续推导, 被称作 终结符(Terminal), 是一个词素.

宾语是什么? 答案是, 可充当主语的都可以充当宾语.

于是最后, 对于主谓宾句式, 我们可设计出如下文法(Grammar):

句子 -> 主语 + 及物动词 + 宾语
主语 -> 名词性成分 
宾语 -> 名词性成分
名词性成分 -> 名词 | 名词性子句 | 动名词 | 不定式

事实上,这个文法不完全, 因为还可以继续追问下去, "名词性子句是什么?", "动名词、不定式是什么?"...

你会发现, 设计英语文法的过程, 就是一个自顶向下推导的过程. 通过这个过程, 确定了所有的 非终结符(Non Terminal) 的组成, 也即确定了产生式(Production).

“非终结符”是指可以继续推导的符号, 比如上例中的 主语、宾语、名词性子句等, 这些可以继续追问它们的构成; 而与之对应, 终结符则是指不可继续推导, 即不可继续追问其构成的符号, 比如一个名词、形容词、副词, 这些已经是最小单元了, 推导到这里就可以终结了, 故称“终结符”.

设计正则文法

在实践中, 设计文法既可以自顶向下, 也可反过来自底向上. 甚至可以不用演绎法, 而用归纳法.

在前面的词法分析中, 我们将词素(后称终结符) 分为了两类:

1. 匹配字符
2. 控制字符

更进一步归纳:

1. 匹配字符
2. 控制字符
   1. 控制前面的字符(也可以是括号里的一个嵌套的表达式)重复多少次,如 *、?
   2. 或,前面的字符(也可以是括号里的一个嵌套的表达式)和后面的之间,二者取其一,即|
   3. 与,正则表达式里默认有“与”的的关系, 我们用符号 & 表达这种隐式关系

继续归纳:

1. 普通匹配字符
2. 一元表达式,*、? 、+、{m,n}
3. 二元表达式, |,&

观察以上3项,一个直觉上的规律是,后面的依次由前面的组成,于是得到如下文法:

primary_expr -> single_literal | '(' expr ')'   //基本词素
unary_expr -> primary_expr | primary_expr '*'  //一元表达式
binary_expr ->
    unary_expr
    |
    unary_expr '｜' binary_expr		//或
    |
    unary_expr binary_expr		// 与
expr -> binary_expr	//正则表达式

正则文法中的优先级

直觉通常可以帮助解决问题的大部分,但是有时还需要有一个纠错过程. 如上文法,没有体现出 And 表达式 与 Or 表达式的优先级,对于输入 ab|c 将生成错误的语法树:

为了让 Or 优先结合,需要将binary_expr拆分,Or 表达式提升为独立的非终结符,放到 And 前面:

primary_expr -> single_literal | range_literal | '(' expr ')' //基本词素
unary_expr -> primary_expr | primary_expr '*'	//一元
or_expr ->	
    unary_expr {Reduce ELSE}
    |
    unary_expr '｜' or_expr	//或
and_expr ->
    or_expr
    |
    or_expr and_expr	//与
expr -> and_expr

语法分析的编码实现

语法分析的实现有两种选择——基于 parser generater 代码生成, 或手写递归下降, 基于 LR 的 Parser 分析能力会更强(如支持左递归文法), 而手写递归下降则更便于控制.

在手写递归下降时, 一个经验指导是, 设计文法时标清晰地标记出每个产生式的 Follow 集. 因为我们编码时每个非终结符对应的分析函数需要明确,何时应当 归约(Reduce) (方法返回), 何时应该 移入(Shift) (方法循环,继续读取下一个词素).

对于 or_expr,当分析出一个 unary_expr 后, 如果 lookahead='|' 则选择移入, 否则归约.

or_expr ->	
    unary_expr {Reduce ELSE}
    |
    unary_expr {Shift if lookahead is '|' } '｜' or_expr	//或

对于 and_expr, 其 Follow 集为 {EOF,')'} ,所以当分析出一个 or_expr 后, 如果 lookahead in EOF,')'则归约, 否则移入.

and_expr ->
    or_expr {Reduce if lookahead in EOF,')'}  
    |
    or_expr and_expr	//与

语义分析

经过语法分析阶段, 对于给定的一个正则表达式, 可以得到其对应的抽象语法树(Abstract Syntax Tree), 而语义分析阶段要做的, 就是对这棵树进行遍历分析, 以达成相应目的.

正则引擎的语义分析, 目的是要得到 AST 对应的 NFA(Non-deterministic finite automata) , 以便在下一步交给子集构造法(Subset Construction Method).

AST TO NFA 的基本过程

NFA 由 状态(NStates) 和 转换(NTrans) 构成, AST 转 NFA 的过程, 其实就是做两件事, 一是确定 NFA 的状态有哪些, 二是确定状态间的转换.

上图是 (a|b)*abb 对应的 AST, 为了便于描述, 叶子节点都打上了标号. 如果人工进行分析(不考虑编码实现), 不难看出, 如果从 NFA 的起点出发, 存在如下状态转换:

换言之, 1,2,3 这三个节点都是 NFA 首个状态, 于是, 得到如下 NFA :

下一步,要考虑的是, 状态 1、2、3, 分别存在哪些转换. 由于是上帝视角(人工分析), 所以很容易得出答案:

状态1

\begin{cases} 1 \xrightarrow{a} 1 \\ 1 \xrightarrow{b} 2 \\ 1 \xrightarrow{a} 3 \end{cases}

$ 状态2

\begin{cases} 2 \xrightarrow{a} 1 \\ 2 \xrightarrow{a} 3 \\ 2 \xrightarrow{b} 2 \end{cases}

状态3

\begin{cases} 3 \xrightarrow{b} 4 \end{cases}

要构建完整的 NFA, 其实只是这个过程的重复. 重复的事情还是交给程序处理为好, 于是下面开始思考编码实现.

First 集与 Follow 集

在前述过程中,其实每一步, 考虑的都是同一个问题: "下一步该怎么走?" ,更具体一点的表述: "当前状态后面可以跟随什么?" 编译原理中,把一个状态可以跟随的符号集合, 称为 Follow 集.

构建 NFA 的过程, 第一步是确定状态, 不难发现, AST 的叶子节点都对应一个 NFA 状态; 第二步是确定状态的转换, 即求出每个状态(叶子节点)的输入什么符号可到达的后继状态, 也即是 Follow 集合.

而计算 Follow 集的前提是需要知道 First 集, 上例中, 在状态3处, 我们之所以知道

3 \xrightarrow{b} 4

, 是因为开启了上帝视角(人工分析), 知道后继状态 4 接受 b. 对于状态 3 而言 b 属于其Follow 集, 而对于状态 4 来说, 是其 First集.

为了描述的简洁性, 下文将用 first(A) 表示节点 A 的 First 集; follow(A) 表示节点A 的 Follow 集; nullable(A) 表示节点 A 是否可空,比如 a*b 中的 a* 就是可空的

First 集合的计算

叶子节点的first集合就是本身, 对于非叶子节点, 其 first 集合计算逻辑如下:

• if nullable(left child) == true
  • first(left child) ∪ first(right child)
• else
  • first(left child)

例外情况:

• 或表达式 | 的 First集合 = first(left child) ∪ first(right child)

Follow 集合的计算

通用规律

• if nullable(first(right sibling node))==true
  • first(right sibling node) ∪ follow(parent node)
• else
  • first(right sibling node)

例外情况:

• * + 表达式, 还要并上 first(left) ((因为其可以重复,所以其 Follow 集包含自身的 First 集)
• | 表达式,左右节点的Follow集均等同父节点

语义分析的编码实现

一个 AST 树, 可能会经历多种处理, 比如 计算 First 集、Follow 集、生成 NFA.

最简单的办法是, 每种处理都对应一个 AST 的处理函数, 这是解释器模式(Interpreter).

这种模式会把数据表示 与 数据处理 耦合在一起, 如果数据的处理只有固定的几种, 那么尚可, 而如果经常变化则不太适合, 试想每当在接口中添加一个处理方法时, 都要去所有的 AST 子类更改, 在 AST 子类很多的时候, 会是一个很麻烦的事. 并且处理方法很多时, 会导致 AST 类过于膨胀, 各种不同类型的处理逻辑都混杂一起.

更好的办法是将 数据表示 与 数据处理 分离, 这便是访客模式(Visitor).

不同类型的访客对语法树的遍历顺序并不一致, FirstSetVisitor 需要以后序遍历, FollowSetVisitor 需要先序遍历. NFAGenerator 则无所谓遍历顺序, 但是在执行顺序上需要最后执行.

如果将遍历与访问分离, 那么就可以在只用 2 次遍历, 完成 3 种 访问.

如果访问的类型更多, 那么种分离将带来更大的优势, 理论上最多只需要 4 次遍历(先序、中序、后序、广度优先) 就可以完成任意种访问.

//1. 后序遍历
traversePostOrder(ast, node -> {
				//计算 First 集
        firstSetVisitor.visit(node)
    }
)
//2. 先序遍历 
traversePreOrder(ast, node -> {
				//计算 Follow 集
        followSetVisitor.visit(node)
				//生成 NFA
				nfaGenerator.visit(node)
    }
)

NFA to DFA

子集构造法

思路: NFA 存在的问题在于,对同一个输入可能存在多个后继状态,其转换具有二义性. 所谓 "二义性" 换一种表述是 "给定条件下存在多种可能转换". 如果化零为整,将多种可能作为一个整体,即把这多个可能的后继状态合为一个"大的状态"来看待,那么情况将会不一样.

具体来说,对于 a*ab (如下图)

在起点处,输入a可能的后继状态是 1、2, 那么就把1、2合为一个状态 A =

\begin{Bmatrix} 1,2 \end{Bmatrix}

大状态 A 里, 状态 1、2 存在转换为

\begin{Bmatrix} 1 \xrightarrow{a} 1 \\ 1 \xrightarrow{a} 2 \\ 2 \xrightarrow{b} 3 \end{Bmatrix}

将其聚合后得到

• 对于

, 由于 {1,2} 已存在就是 A 本身所包含的 NFA 状态, 所以

A \xrightarrow{a} A

• 对于

A \xrightarrow{b} 3

, 生成一个新的状态 B =

\begin{Bmatrix} 3 \end{Bmatrix}

, 得到 DFA 转换

A \xrightarrow{b} B

发热23··

至此,NFA 就变成了 DFA.

从表达的语义来看,DFA 与 NFA 并没有差别,如上例的 NFA 的转换:

start \xrightarrow{a} 1

start \xrightarrow{a} 2

其对应的 DFA 转换:

start \xrightarrow{a} \{1,2\}

事实上, 两者都表达了 "起点处输入a可能到达1或2". 但是在表达形式上, NFA 将这种二义性(或者说多种可能性)表现在转换上了; 而与之不同, DFA 将二义性表达在状态里, 多种可能性被聚合在状态里, 消除了转换的二义性.

如果不是计算机处理,而是人脑,其实潜意识里就已经存在那个 “NFA 转 DFA”的过程, 人脑可以“并发地”同时走多条路径. 这么看,DFA 转 NFA 其实是把人类的潜意识里存在的处理方式“教”给了计算机.

范围输入带来的二义性

工程实践与教科书的区别在于, 教科书总是假设一个理想环境, 而工程并非如此. 前文中讲 NFA 转 DFA 时, 其实忽略一个现实: "转换可以是针对一个范围的输入" .

上图是正则表达式 (b|[b-d]|[c-h]|.)z 对应的 NFA, 你会看到, 起点处的转换, 是存在“交集”的:

换言之,也即是对相同区间的输入存在一种以上的转换,这对于 NFA 没有什么问题(破罐破摔了), DFA 则不可接受.

针对这种情况, 在将 NFA 转换 DFA 时, 需要设计一个算法, 消除 NFA 的存在交集的转换的二义性, 算法过程如下:

上例中, 起点处存在如下 4 个转换:

\begin{Bmatrix} 1.start\xrightarrow{b}1 \\ 2.start\xrightarrow{b-d}2 \\ 3.start\xrightarrow{c-h}3 \\ 4.start\xrightarrow{Any}4 \\ \end{Bmatrix}

我们把每个转换的输入区间看作一个集合, 对转换 1 与转换 2 输入区间作集合运算:

\begin{Bmatrix} 转换1 - 转换2 = \{\} \\ 转换2 - 转换1 = \{c \sim d\} \\ 转换1 ∩ 转换2 = \{b\} \end{Bmatrix}

根据运算结果, 交集为 {b}, 所以

start\xrightarrow{b}\{1,2\}

, 转换2的差集为 {c~d}, 所以

start\xrightarrow{c-d}2

合在一起, 于是得到了如下转换:

\begin{Bmatrix} start\xrightarrow{b}\{1,2\} \\ start\xrightarrow{c-d}2 \end{Bmatrix}

下一步, 将转换 3 与上面两个一一作集合运算, 重复相同的处理逻辑, 得到:

\begin{Bmatrix} start\xrightarrow{b}\{1,2\} \\ start\xrightarrow{c-d}\{2,3\} \\ start\xrightarrow{e-h}3 \\ \end{Bmatrix}

最后, 对转换4 与以上3个转换一一作集合运算, 得到:

至此, 便消除了转换的二义性问题, 得到如下 DFA :