Brzozowski 导数

注意：这是一个从 c0stya/brzozowski 分支出来的版本，它提供了原始的Python实现。不过，Rust实现已添加到 aalekhpatel07/brzozowski 中。有关Rust实现的详细信息，请访问 crate 文档。

此代码仅用于教育目的。它并不高效。但它说明了这个想法。

Brzozowski 导数 是一种不太为人所知的处理正则表达式的技术。通常，为了使用正则表达式匹配字符串，我们需要构建一个 有限状态自动机 并模拟它。使用正则表达式导数技术，我们可以直接使用正则表达式，而无需构建和模拟自动机。

它与分析中的经典导数无关。但是，符号性质和链式法则的应用使它感觉类似。更多详细信息，请参阅Scott Owens、John Reppy和Aaron Turon撰写的论文 "Regular-expression derivative re-examined"。

用法

此代码仅实现了三个运算符。它们是连接（$\cdot$）、交替（$\mid$）和Kleene星（$*$）。

用法

> python match.py <regex> <string>

例如。

> python match.py '(c|b)at' 'cat'
(c|b)·a·t
c: a·t
a: t
t: ε
True

> python match.py '(c|b)at' 'car'
(c|b)·a·t
c: a·t
a: t
r: ∅
False

定义和规则

相对于字符串 $u \in \Sigma*$，语言 $L \subset \Sigma*$ 的导数是一个语言 $\partial_u L = \lbrace v \mid u \cdot v \in L \rbrace$。

对于任何字符 a 和 b 以及任何正则表达式 r 和 s，我们有以下规则

$$ \begin{align} \partial_a \varepsilon &= \emptyset & \ \partial_a a &= \epsilon & \ \partial_a b &= \emptyset & \text{ for }(a \neq b) \ \partial_a (r \cdot s) &= \partial_a r \cdot s \mid \nu(r) \cdot \partial_a s & \ \partial_a (r \mid s) &= \partial_a r \mid \partial_a s & \ \partial_a (r*) &= \partial_a r \cdot r* & \end{align} $$

其中函数 $\nu(r)$ 检查由正则表达式定义的语言是否包含空字符串 ($\epsilon$)。我们称这样的正则表达式为 可空的。函数 $\nu$ 的递归定义为

$$ \begin{align} \nu(\varepsilon) &= \emptyset \ \nu(\emptyset) &= \emptyset \ \nu(a) &= \emptyset \ \nu(r \cdot s) &= \nu(r) \cdot \nu(s) \ \nu(r \mid s) &= \nu(r) \mid \nu(s) \ \nu(r*) &= \emptyset \end{align} $$

我们需要针对字符串添加两条规则以完成规则集

$$ \begin{align} \partial_\varepsilon r &= r \ \partial_{ua} &= \partial_{a} \partial_{u} r \end{align} $$

为了找到匹配，我们需要检查正则表达式 $r$ 对字符串 $u$ 的导数是否是 可空的

$$ \nu(\partial_{u} r) = \epsilon $$

示例

让我们检查单词 $cat$ 是否与正则表达式 $(c|b)at$ 匹配。很明显，它匹配，因为正则表达式定义了仅包含两个字符串 $cat$ 和 $bat$ 的语言。无论如何，让我们正式地做这件事。

$$ \partial_{cat}\left[(c \mid b)\cdot a \cdot t\right] = \partial_t\partial_a\partial_c\left[(c \mid b)\cdot a \cdot t\right] $$

让我们分别对每个字符取导数

$$ \begin{align*} \partial_c\left[(c \mid b)\cdot a \cdot t\right] &= \partial_c \left[c \mid b\right]\cdot a \cdot t \mid \nu(c \mid b) \cdot \partial_c [a \cdot t] \text{ by } \cdot \text{-rule} \ &= \partial_c \left[c \mid b\right]\cdot a \cdot t \mid \emptyset \cdot \partial_c [\cdot a \cdot t] \text{ since } \nu(c \mid b) = \nu(c) \mid \nu(b) = \emptyset \mid \emptyset = \emptyset \ &= \partial_c \left[c \mid b\right]\cdot a \cdot t \mid \emptyset \text{ since } r \cdot \emptyset = \emptyset \cdot r = \emptyset \text{ for any }r \ &= \partial_c \left[c \mid b\right]\cdot a \cdot t \text{ since } r \mid \emptyset = \emptyset \mid r = r \text{ for any }r \ &= (\partial_c c \mid \partial_c b) \cdot a \cdot t \text{ by } \mid \text{-rule} \ &= (\epsilon \mid \emptyset) \cdot a \cdot t \ &= \epsilon \cdot a \cdot t \ &= a \cdot t \ \partial_a[a \cdot t] &= \partial_a a \cdot t \mid \nu(a) \cdot \partial_a b \text{ by } \cdot \text{-rule} \ &= \epsilon \cdot t \mid \emptyset \ &= t \ \partial_t[t] &= \epsilon \end{align*} $$

所以 $\partial_{cat}\left[(c \mid b)\cdot a \cdot t\right] = \epsilon$ 是 可空的，单词 $cat$ 与正则表达式 $(c \mid b)\cdot a \cdot t$ 匹配。

匹配算法

实现导数有多种方式。一些实现遵循纯函数风格。这里，我使用传统的命令式风格以避免隐藏逻辑。

match.py 调用以下函数来确定字符串是否与正则表达式匹配

1. augment: 将输入正则表达式扩展为显式的连接运算符 ($\cdot$): $c*at \to c * \cdot a \cdot t$。
2. infix_to_postfix: 将扩展的正则表达式转换为 后缀表达式。
3. postfix_to_tree: 将后缀表达式转换为 二叉树，其中令牌位于叶子节点，运算符位于非终端节点（更新：当前实现使用纯 Python 元组以保持简单）。
4. match: 对输入字符串的每个令牌调用 deriv。然后使用 nullable 评估正则表达式。
   • deriv: 取正则表达式（现在表示为二叉树）相对于输入字符串的令牌的导数。我们修改二叉树 原地。对于某些运算符，我们必须使用平凡的递归函数 clone 来克隆树的一个分支。
   • _sort: 使用 归并排序算法 对树中的选择进行排序。
   • _norm: 简化表达式如 $r | \varepsilon$ 或 $\emptyset \cdot r$。
   • nullable: 检查生成的正则表达式（二叉树）是否是可空的。如果是可空的，那么我们找到了一个匹配。

DFA 构造算法

如果我们想将多个字符串与正则表达式进行匹配，为每个字符串计算梯度太耗时了。我们可以做得更好。让我们预先计算任何可能的输入字符串的导数。

经典的方法是构建非确定有限状态自动机（NFA），然后将其转换为DFA。使用Brzozowski导数，我们可以直接构建DFA。

给定正则表达式 $r$

Q <- r                  queue to keep unexplored states
D <- r                  hash table to store all found states
while Q is not empty
    r <- Q.pop()
    for any c in alphabet A:
        s = take derivative of r wrt c

        if s not in dictionary D, then
            Q.push(s)

逻辑实现在 construct_dfa.py 脚本中。它包括构建graphviz兼容图规范的代码。

> python construct_dfa.py '(c|m)at'

digraph G {
	splines=true; rankdir=LR;
	"(c|m)·a·t";
	"(c|m)·a·t" -> "∅" [ label="a,t" ];
	"(c|m)·a·t" -> "a·t" [ label="c,m" ];
	"∅";
	"∅" -> "∅" [ label="a,c,m,t" ];
	"a·t";
	"a·t" -> "t" [ label="a" ];
	"a·t" -> "∅" [ label="c,m,t" ];
	"t";
	"t" -> "∅" [ label="a,c,m" ];
	"t" -> "ε" [ label="t" ];
	"ε" [peripheries=2];
	"ε" -> "∅" [ label="a,c,m,t" ];
}

使用graphviz命令行库渲染它的方法

> python construct_dfa.py '(c|m)at' | dot -Tpng > dfa.png

为什么需要它

1. 很有趣
2. 使用这种技术，我们可以构建一个非常高效的自动机，接近所谓的最小DFA。尽管有一些考虑，但在某些情况下，这种构建可能非常有用。

待办事项

1. 扩展导数理论部分
2. 添加DFA构建代码
3. 解释正则表达式归一化技术