将有限状态机转换为正则表达式的改进算法
4.99/5 (13投票s)
本文描述了一种用于将 FA 转换为正则表达式的状态去除算法的改进。
引言
许可
本文提供的代码采用 MIT 许可，但我概述的概念属于公共领域。您可以随意使用这些概念而无需署名（尽管我们非常感激），但如果您使用代码或从中派生代码，则适用 MIT 许可。
软件先决条件
为了渲染状态图，需要 GraphViz。您可以 在此处 下载。
这是怎么回事？
归根结底，这与正则表达式有关，而正则表达式是使用状态机实现的。将正则表达式转换为状态机的最常用算法——Thompson's construction 后跟 subset construction——非常有名。还有三种不太为人所知但可行的算法，用于将其中一个状态机转换回正则表达式。本文是对其中一种算法的探索和改进。
为什么要这样做？
您可能希望将基于有限自动机的状态机转换回正则表达式有几个原因：
- 调试：将机器或机器的子集视为更易于人类阅读的正则表达式字符串，比查看状态对象图要容易得多。
- 显示：尤其是在处理机器的子集时，例如在构建词法分析器代码或渲染状态图时，能够生成这些子集作为正则表达式，可以使这些机器子集具有可读性。
- "反编译"：偶尔，您可能会遇到状态机的二进制文件表示，例如 Gold Parser 生成的那些。使用此算法，您可以将这些预制状态机转换回用于创建它们的正则表达式的近似值。（它可能不是完全相同的表达式，但它将匹配相同的文本。）
- 将 DFA 转换回 NFA：这种情况的用途很窄，因为所有 DFA 本身也是 NFA（尽管反之不然）。但是，这可能有助于比较图形或显示图形。这可能是目前最好的 DFA 到 NFA 的转换算法，因为它是一种整体方法——它将 DFA 结构转换回最初创建它们的 Thompson 结构，然后这些结构会反映在 NFA 中。其他算法则不然。
- 好奇心：即使没有我的改进，FA 状态移除算法也很有趣，理解它能帮助您更熟悉正则表达式和模式匹配的工作原理。
背景
我们在这里不关注匹配代码。这完全是关于将正则表达式与状态机相互转换。话虽如此，该引擎已经足够完整，可以轻松扩展以进行匹配。
我们将把状态机中的状态表示为一个类。该类有一个整数接受符号 ID 和一个指向更多该类实例的转换列表。列表中的每个转换都包含一个最小代码点、一个最大代码点和一个目标状态。最小和最大代码点一起表示一个匹配代码点范围，以使 Unicode 匹配更现实。
我们将改进 状态移除方法，将状态机转换为正则表达式。
这种技术的通用形式的思想是，状态机中的每个转换都由正则表达式的一部分标记，而不是代码点范围。您逐个移除状态，并在移除它们的同时，增强通往它们的现有表达式，直到您最终得到一个从根状态到最终状态的单一转换，该转换包含代表整个机器的表达式。有关详情，请参阅链接。
在通用算法中，表达式由一个字符串表示，该字符串根据需要进行连接。
我们将引入一个抽象语法树。抽象语法树（在本例中）是一个表达式树。它具有 RegexLiteralExpression、RegexSetExpression、RegexRepeatExpression 和 RegexConcatExpression 等类。我们不是构建字符串，而是使用这些类来构建我们的表达式。
这样做可以让我们在表达式构建完成后对其进行更高级别的分析，从而可能找到简化它的机会。这一点很重要，因为虽然状态移除算法通常能为基本表达式产生合理的结果，但随着表达式变得越来越复杂，它们很容易变得难以阅读。部分原因是状态移除方法不会使用 + 等更高级别的运算符，而是选择将 z+ 渲染为 zz*，例如。另一个问题是过度使用括号。我们可以通过分析我们的语法树来修复这些问题。
理解代码
基础知识
FA 类代表状态机中的一个状态。我们通过创建这些类的实例并通过 AddTransition() 将它们链接在一起来构建状态机。
RegexExpression 类是抽象语法树中表达式元素的基类。所有其他表达式类都继承自它。其余的 RegexXXXXExpression 类是派生自 RegexExpression 的具体类。
我们将重点关注 RegexExpression 及其派生类，因为那是代码的核心所在。与我通常的正则表达式产品不同，解析和 Thompson 构造逻辑位于抽象语法树类中，而不是 FA 类中。
您可以自由使用抽象语法树的对象模型来构建正则表达式，但调用 RegexExpression.Parse() 将正则表达式转换为树可能更方便。
解析后，您可以通过各种成员对其进行修改，使用 ToString() 获取其字符串表示形式，或使用 ToFA() 将其转换为状态机。
从状态机转换
话虽如此，我们在这里真正感兴趣的方法是 FromFA()。此方法接受一个状态机并返回一个代表它的抽象语法树。基本思想是，我们将从一个看起来像原始状态机的机器开始，然后从中移除状态，用代表它们 的子表达式替换它们，直到只剩下第一个和最后一个状态，它们之间只有一个转换。这个单一的转换包含了整个正则表达式。
我们需要一个特殊的 FA 变体。这基本上是一个精简版的 FA 类，但转换存储的是 RegexExpression 对象而不是代码点范围。
private class _EFATransition {
public RegexExpression Expression;
public _EFA To;
public _EFATransition(RegexExpression expression = null, _EFA to = null) {
Expression = expression;
To = to;
}
}
private sealed class _EFA {
public bool IsAccepting;
public int Accept;
public List<_EFATransition> Transitions { get; } = new List<_EFATransition>();
public IList<_EFA> FillClosure(IList<_EFA> result = null) {
if (result == null) result = new List<_EFA>();
if (result.Contains(this))
return result;
result.Add(this);
foreach (var t in Transitions) {
t.To.FillClosure(result);
}
return result;
}
public static IList<KeyValuePair<_EFA, int>>
GetIncomingTransitionIndices(IEnumerable<_EFA> closure,
_EFA efa,
bool includeLoops = true) {
var result = new List<KeyValuePair<_EFA, int>>();
foreach (var cfa in closure) {
var i = 0;
foreach (var t in cfa.Transitions) {
if (includeLoops || t.To != cfa) {
if (t.To == efa) {
var kvp = new KeyValuePair<_EFA, int>(cfa, i);
if (!result.Contains(kvp)) {
result.Add(kvp);
}
}
}
++i;
}
}
return result;
}
public IDictionary<_EFA, RegexExpression>
FillInputTransitionsGroupedByState(IDictionary<_EFA, RegexExpression> result = null) {
if (result == null) {
result = new Dictionary<_EFA, RegexExpression>();
}
for (var i = 0; i < Transitions.Count; ++i) {
var t = Transitions[i];
RegexExpression exp;
if (!result.TryGetValue(t.To, out exp)) {
var or = new RegexOrExpression(t.Expression);
result.Add(t.To, or);
} else {
var or = exp as RegexOrExpression;
var oor = t.Expression as RegexOrExpression;
if(oor!=null) {
or.Expressions.AddRange(oor.Expressions);
} else
or.Expressions.Add(t.Expression);
}
}
return result;
}
}
我们有一个标准 FA 类上不存在的函数。GetIncomingTransitionIndices() 为我们提供了机器中指向该状态的所有状态/转换组合。与 FA 类中同名函数的函数类似，FillInputTransitionsGroupedByState() 为我们提供了目标状态/表达式对，其中每个状态都是其相应表达式指向的目标状态。这基本上是一种获取状态出边转换的简洁方法。
在 FromFA() 中，我们做的第一件事是从传入的基于 FA 的机器重建一个 _EFA 机器。
var closure = fa.FillClosure();
// reserve an extra for the new final state
IList<_EFA> efas = new List<_EFA>(closure.Count + 1);
var i = 0;
while (i <= closure.Count) {
efas.Add(null);
++i;
}
i = 0;
foreach (var cfa in closure) {
efas[i] = new _EFA();
++i;
}
var final = new _EFA();
final.IsAccepting = true;
final.Accept = 0;
efas[i] = final;
for (i = 0; i < closure.Count; ++i) {
var e = efas[i];
var c = closure[i];
if (c.AcceptSymbolId!=-1) {
e.Transitions.Add(new _EFATransition(null,final));
}
for(var j = 0;j<c.Transitions.Count;++j) {
var ct = c.Transitions[j];
if(ct.Min==-1 && ct.Max==-1) {
e.Transitions.Add(new _EFATransition(null, efas[closure.IndexOf(ct.To)]));
}
}
var rngGrps = c.FillInputTransitionRangesGroupedByState();
foreach (var rngGrp in rngGrps) {
var tto = efas[closure.IndexOf(rngGrp.Key)];
if (rngGrp.Value.Count==1) {
var r = rngGrp.Value[0];
if(r.Key==r.Value) {
var lit = new RegexLiteralExpression(r.Key);
e.Transitions.Add(new _EFATransition(lit, tto));
continue;
}
}
var sexpr = new RegexSetExpression(rngGrp.Value);
e.Transitions.Add(new _EFATransition(sexpr, tto));
}
}
这个 _EFA 机器现在与 FA 机器相同，除了所有之前的接受状态现在都是非接受状态，并以 null 表达式（epsilon）转换为接受的 final 状态。每个代码点范围都已转换为基本的等效表达式。考虑下面的 _EFA 机器，由 (foo|ba[rz])+[A-Z_a-z][A-Z_a-z0-9]* 产生。
q0:
-> q1
-> q22
q1:
f -> q2
q2:
o -> q3
q3:
o -> q4
q4:
-> q5
q5:
-> q6
q6:
-> q7
-> q17
q7:
-> q8
-> q13
q8:
f -> q9
q9:
o -> q10
q10:
o -> q11
q11:
-> q12
q12:
-> q6
q13:
b -> q14
q14:
a -> q15
q15:
[rz] -> q16
q16:
-> q12
q17:
[A-Z_a-z] -> q18
q18:
-> q19
q19:
-> q26
-> q20
q20:
[0-9A-Z_a-z] -> q21
q21:
-> q19
q22:
b -> q23
q23:
a -> q24
q24:
[rz] -> q25
q25:
-> q5
*q26:
现在我们需要开始将它们组合起来。我们将不断修改机器，直到不再有可以进行的修改为止。一旦完成，我们将再进行一次遍历，以确保不再有可以进行的修改，但基本思想是，我们修改机器直到无法再修改为止。
这个过程有几个阶段。在第一阶段，我们解决简单情况，即只有一个指向某个状态和从某个状态出来的转换。我们将这些简单状态转换的连续串联起来。
while (!innerDone) {
innerDone = true;
i = 0;
foreach (var e in efas) {
if (e.Transitions.Count == 1) {
var its = _EFA.GetIncomingTransitionIndices(efas, e);
if (its.Count == 1 && its[0].Key.Transitions.Count == 1) {
// is a loop?
if (e.Transitions[0].To == its[0].Key) {
var rep = new RegexRepeatExpression();
rep.Expression = e.Transitions[0].Expression;
rep.MinOccurs = rep.MaxOccurs = 0;
e.Transitions[0].Expression = rep;
} else {
var exp = its[0].Key.Transitions[0].Expression;
var cat = exp as RegexConcatExpression;
if (cat == null) {
cat = new RegexConcatExpression();
cat.Expressions.Add(exp);
exp = cat;
its[0].Key.Transitions[0].Expression = cat;
}
cat.Expressions.Add(e.Transitions[0].Expression);
its[0].Key.Transitions[0] = new _EFATransition(exp, e.Transitions[0].To);
}
innerDone = false;
efas = efas[0].FillClosure();
break;
} else {
foreach (var it in its) {
// is it a loop?
if (efas.IndexOf(it.Key) >= efas.IndexOf(e)) {
// yes
} else {
// no
var t = it.Key.Transitions[it.Value];
it.Key.Transitions[it.Value] =
new _EFATransition(t.Expression, e.Transitions[0].To);
var exp = t.Expression;
var cat = exp as RegexConcatExpression;
if (cat == null) {
cat = new RegexConcatExpression();
cat.Expressions.Add(exp);
exp = cat;
it.Key.Transitions[it.Value].Expression = exp;
}
cat.Expressions.Add(e.Transitions[0].Expression);
innerDone = false;
efas = efas[0].FillClosure();
break;
}
}
}
}
++i;
}
if (innerDone) {
efas = efas[0].FillClosure();
} else
done = false;
}
...
这看起来很复杂，但它的大部分工作只是检查状态是否有唯一的传入和传出转换，然后将它们拆开并构建新的转换，这些转换是将几个连续的转换串联起来的。它做的另一件事是解决简单的自循环。完成此阶段后，我们将得到这个 _EFA 机器。
q0:
foo -> q1
ba[rz] -> q1
q1:
-> q2
[A-Z_a-z] -> q3
q2:
foo -> q1
ba[rz] -> q1
q3:
-> q4
[0-9A-Z_a-z] -> q3
*q4:
现在它开始变得更易于管理了！状态少了很多，并且其中出现了正则表达式的雏形。
接下来，我们将组合多个转换，例如 q0 中的转换。
innerDone = false;
while (!innerDone) {
innerDone = true;
foreach (var e in efas) {
var rgs = e.FillInputTransitionsGroupedByState();
if (rgs.Count != e.Transitions.Count) {
e.Transitions.Clear();
foreach (var rg in rgs) {
e.Transitions.Add(new _EFATransition(rg.Value, rg.Key));
}
innerDone = false;
efas = efas[0].FillClosure();
break;
}
}
}
if (innerDone) {
efas = efas[0].FillClosure();
} else
done = false;
这将产生这个结果：
q0:
foo|ba[rz] -> q1
q1:
-> q2
[A-Z_a-z] -> q3
q2:
foo|ba[rz] -> q1
q3:
-> q4
[0-9A-Z_a-z] -> q3
*q4:
现在我们进展顺利了！剩下的工作不多了。接下来，我们修复 q3 中的循环。
while (!innerDone) {
innerDone = true;
foreach (var e in efas) {
for (var ii = 0; ii < e.Transitions.Count; ++ii) {
var t = e.Transitions[ii];
if (t.To == e) {
// this is a loop
var rep = new RegexRepeatExpression();
rep.Expression = t.Expression;
rep.MinOccurs = rep.MaxOccurs = 0;
// prepend it to all the other transitions
for (var iii = 0; iii < e.Transitions.Count; ++iii) {
if (ii != iii) {
var tt = e.Transitions[iii];
if (tt.To != e) {
var cat = tt.Expression as RegexConcatExpression;
if (cat == null) {
cat = new RegexConcatExpression();
cat.Expressions.Add(rep);
cat.Expressions.Add(tt.Expression);
e.Transitions[iii].Expression = cat;
} else {
cat.Expressions.Insert(0, rep);
}
}
}
}
e.Transitions.RemoveAt(ii);
--ii;
innerDone = false;
efas = efas[0].FillClosure();
break;
}
}
}
}
if (innerDone) {
efas = efas[0].FillClosure();
} else
done = false;
这就留下了这个结果：
q0:
foo|ba[rz] -> q1
q1:
-> q2
[A-Z_a-z] -> q3
q2:
foo|ba[rz] -> q1
q3:
(?:[0-9A-Z_a-z])* -> q4
*q4:
这些是所有主要步骤，所以现在我们所要做的就是重复我们刚才所做的一切，直到最后只剩下一个转换。
q0:
(?:foo|ba[rz])(?:(?:foo|ba[rz]))*[A-Z_a-z](?:[0-9A-Z_a-z])* -> q1
*q1:
等等。我们还没做完。我们已经通过状态移除方法完成了基本的 FA 到正则表达式的算法，但我们还没有真正改进它。
但是，我们已经为这个表达式构建了一个抽象语法树，所以我们的目标是检查这棵树，并在可能的情况下进行简化。
简化我们的表达式
Reduce() 在可能的情况下将返回一个简化的表达式。在这一操作中，我们改进了通用算法。其思想是检查树，看是否有任何冗余或可以简化的内容。一个例子是 (foo|) 被转换为 (foo)?。另一个可能是将 aa* 转换为 a+。再一个可能是将 (a|b|c|d|e|f|z|) 转换为 [a-fz]?。
实现的关键是 TryReduce() 方法，它被 Reduce() 反复调用，直到返回 false，每次都可能返回一个简化的表达式。每种类型的表达式都有其自己的简化代码。
这是 RegexConcatExpression 的简化代码。它基本上会简化嵌套的表达式，将嵌套的连接表达式展平为一个，移除只有一个表达式的连接，并解析 zz* 之类的表达式为 z+。
private bool _AddReduced(RegexExpression e) {
if (e == null) return true;
var r = false;
while (e!=null && e.TryReduce(out e)) r = true;
if (e == null) return true;
var c = e as RegexConcatExpression;
if(null!=c) {
for(var i = 0;i<c.Expressions.Count;++i) {
var ce = c.Expressions[i];
if(ce!=null) {
_AddReduced(ce);
}
}
return true;
}
Expressions.Add(e);
return r;
}
public override bool TryReduce(out RegexExpression reduced) {
var result = false;
var cat = new RegexConcatExpression();
for(var i = 0;i<Expressions.Count;++i) {
var e = Expressions[i];
if(e==null) {
result = true;
continue;
}
if(cat._AddReduced(e)) {
result = true;
}
}
switch(cat.Expressions.Count) {
case 0:
reduced = null;
return true;
case 1:
reduced = cat.Expressions[0].Reduce();
return true;
default:
// fixup things like zz* so it's z+
for(var i = 1;i<cat.Expressions.Count;++i) {
var e = cat.Expressions[i].Reduce();
var rep = e as RegexRepeatExpression;
if (rep != null) {
var ee = rep.Expression;
var cc = ee as RegexConcatExpression;
if (cc != null) {
var k = 0;
for (var j = i - cc.Expressions.Count; j < i; ++j) {
if (!cc.Expressions[k].Equals(cat.Expressions[j])) {
reduced = result ? cat : this;
return result;
}
++k;
}
cat.Expressions[i] = new RegexRepeatExpression(cc,
rep.MinOccurs + 1,
rep.MaxOccurs > 0 ? rep.MaxOccurs + 1 : 0).Reduce();
cat.Expressions.RemoveRange(i - cc.Expressions.Count,
cc.Expressions.Count);
result = true;
} else {
if (cat.Expressions[i - 1].Equals(ee)) {
cat.Expressions[i] = new RegexRepeatExpression(ee,
rep.MinOccurs + 1,
rep.MaxOccurs > 0 ? rep.MaxOccurs + 1 : 0).Reduce();
cat.Expressions.RemoveAt(i - 1);
result = true;
}
}
}
}
reduced = result?cat:this;
return result;
}
}
我们不会探讨所有的简化代码，因为每种例程的概念都是相同的——寻找简化表达式的方法。RegexRepeatExpression 有自己的简化代码，但它与此想法相同。
下一步
状态移除算法实现和简化实现都有改进的空间。特别是状态移除算法往往会产生 (foobar|bazbar|fubar) 而不是 (foo|baz|fu)bar 这样的表达式，这是不太理想的。简化算法不会将 barbarbar 简化为 (bar){3}，尽管它应该这样做。字符集简化不会解析为字符类，并且字符类减法尚未实现。
尽管如此，即使存在这些限制，我认为这项技术比现有的教科书式状态移除算法有了实质性的改进。
历史
- 2022 年 1 月 6 日 - 首次提交