Visual FA 第三部分：驱动一切的底层代码
5.00/5 (2投票s)
在本文中，我们将深入探讨 Visual FA 的内部工作原理。
引言
文章列表
注意：理解第一部分的概念对于本文至关重要。第二部分也有帮助，可以帮助您了解我们正在处理的内容，但第一部分绝对是必不可少的。文章中的一些代码可能已略有过时，因为自编写以来，代码库已更新。
好吧，我答应过我们会走到这一步。我有点不知所措，不知道从哪里开始。这是开始写作的绝佳时机！
到目前为止，我们已经讨论了有限自动机概念和 API 的使用。现在让我们深入研究代码。在本文中，我们将重点关注 FA 类，因为其他所有内容都围绕这个类展开。
转移和其他核心成员
我们将从基础开始——管理核心自动机功能，这意味着处理转移和接受符号等基础知识。
有效的 AcceptSymbol 必须是非负数，因此我们有一个 IsAccepting 属性来检查这一点。尽管它很重要，但实现并不令人兴奋。它也很简单，由一个字段映射组成（一种情况），以及在另一种成员情况下对该字段的 if 检查。很简单。
让我们考虑一下我们的转移。数据的主要部分在那里。我们在 _transitions 成员中内部维护一个列表。这是 FATransition 的声明
struct FATransition
{
public int Min;
public int Max;
public FA To;
public FATransition(FA to, int min = -1, int max =-1)
{
Min = min;
Max = max;
To = to;
}
public bool IsEpsilon { get { return Min == -1 && Max == -1; } }
public override string ToString()
{
if(IsEpsilon)
{
return string.Concat("-> ", To.ToString());
}
if (Min == Max)
{
return string.Concat("[",
char.ConvertFromUtf32(Min),
"]-> ",
To.ToString());
}
return string.Concat("[",
char.ConvertFromUtf32(Min),
"-",
char.ConvertFromUtf32(Max),
"]-> ",
To.ToString());
}
public bool Equals(FATransition rhs)
{
return To == rhs.To &&
Min == rhs.Min &&
Max == rhs.Max;
}
public override int GetHashCode()
{
if(To==null)
{
return Min.GetHashCode() ^
Max.GetHashCode();
}
return Min.GetHashCode() ^
Max.GetHashCode() ^
To.GetHashCode();
}
public override bool Equals(object obj)
{
if (ReferenceEquals(obj, null)) return false;
if (!(obj is FATransition)) return false;
FATransition rhs = (FATransition) obj;
return To == rhs.To && Min == rhs.Min && Max == rhs.Max;
}
}
这很简单。基本上，它要么包含由 Min 和 Max 指示的代码点范围，要么是 epsilon 转移，在这种情况下，这两个字段都为 -1。我们使用范围的原因是，在许多情况下，Unicode 使存储单个代码点不切实际。有许多相关的代码点块最好使用范围来表示。无论如何，FATransition 还包含到 To* 的目标状态的引用。它实现了值相等语义，原因稍后将进行探讨。请注意，我们不为主要成员使用属性。残酷的真相是，我不信任 JIT 编译器将这些直接解析为访问字段，而且它们过于时间关键，无法承担 getter 方法调用的开销。
总之，我们在 FA 的 _transitions 上维护一个在插入时排序的列表。请注意，我没有让 FATransition 实现 IComparable<T> 或 IEquatable<T> 接口，因为我不想鼓励会导致装箱的调用。如果我需要对 struct 的整个列表进行排序，我会使用 Comparison<T>，但在这种情况下，我们甚至都不这样做。如我所说，我们在插入时进行排序。
*精明的开发者可能会意识到，在循环转移的情况下，由于间接的循环引用，它会给垃圾收集器带来不当的负担。实际上，GC 似乎处理得很好，而且我在这里无法使用 WeakReference<FA>，因为它会使 API 变得非常复杂，因为我需要*在某处*持有具体的引用，而这可能意味着要让用户来做。如果我们有某种引用计数的弱引用“指针”，那就太好了。也许有一天我会做一个。
在 FA 上，用户可以使用 Transitions 属性检索转移的只读列表。该属性简单地返回 _transitions.AsReadOnly()。我没有缓存它是因为它很少使用，所以为从未被调用过的内容在每个 FA 实例上占用一点额外的内存似乎不值得。
我们有转移，太好了。现在我们需要一种添加它们的方法。FA 提供了两个成员来执行此操作——AddTransition() 和 AddEpsilon()。我们对每个成员进行一些预处理。首先，我们进行排序插入。其次，我们进行重复删除。最后，我们在 AddTransition() 中进行重叠检查（使用 FARange），然后在两种情况下，我们都会根据需要更新 IsDeterministic 和/或 IsCompact。
我曾考虑过添加一个 FATransitionsList 专用类，该类有一个 Add() 方法，该方法将执行所有这些操作，但它将是额外的间接引用，因此会产生额外的开销和额外的内存，而实际上并没有增加太多东西，除了华而不实的。
总之，这是 AddTransition()
public void AddTransition(FARange range,FA to)
{
if (to == null)
throw new ArgumentNullException(nameof(to));
if(range.Min==-1 && range.Max==-1)
{
AddEpsilon(to);
return;
}
if(range.Min>range.Max)
{
int tmp = range.Min;
range.Min = range.Max;
range.Max = tmp;
}
var insert = -1;
for (int i = 0; i < _transitions.Count; ++i)
{
var fat = _transitions[i];
if (to == fat.To)
{
if(range.Min==fat.Min &&
range.Max==fat.Max)
{
return;
}
}
if (IsDeterministic)
{
if (range.Intersects(
new FARange(fat.Min, fat.Max)))
{
IsDeterministic = false;
}
}
if (range.Max>fat.Max)
{
insert = i;
}
if (!IsDeterministic &&
range.Max < fat.Min)
{
break;
}
}
_transitions.Insert(insert+1,
new FATransition(to, range.Min, range.Max));
}
AddEpsilon() 在您压缩时会进行一些花哨的操作。它会“作弊”，但以数学上可接受的方式。基本上，而不是在添加 epsilon 时添加一个额外的状态，您会将新状态与现有状态合并。这有效地完成了与epsilon闭包相同的效果，但没有开销。此外，在许多情况下，这些压缩创建也是确定性的！这意味着您将享受优化的遍历，而无需创建 DFA 的额外开销，尽管结果不会被最小化。这仅适用于没有冲突转移的状态，但这涵盖了 foo|bar 等场景。总之，它是这样的
public void AddEpsilon(FA to, bool compact = true)
{
if(to==null) throw new ArgumentNullException(nameof(to));
if (compact)
{
for (int i = 0; i < to._transitions.Count; ++i)
{
var fat = to._transitions[i];
if (fat.Min!=-1 || fat.Max!=-1)
{
AddTransition(new FARange(fat.Min, fat.Max), fat.To);
}
else
{
AddEpsilon(fat.To, true);
}
}
if (AcceptSymbol < 0 && to.AcceptSymbol > -1)
{
AcceptSymbol = to.AcceptSymbol;
}
}
else
{
var found =false;
int i;
for (i = 0;i<_transitions.Count;++i)
{
var fat = _transitions[i];
// this is why we don't use List.Contains:
if (fat.Min != -1 || fat.Max != -1) break;
if(fat.To==to)
{
found = true;
break;
}
}
if (!found)
{
_transitions.Insert(i,new FATransition(to));
IsCompact = false;
IsDeterministic = false;
}
}
}
Thompson 构建算法
当然，我们很少直接使用上面这些方法。相反，我们有使用上述方法构建基本构造的方法——Thompson 构建方法，加上一些相关的便利方法，我用它们增强了规范套件。它们包括 Literal()、Set()、Concat()、Or()、Optional()、Repeat() 和 CaseInsensitive()。
Literal 构建的内容如（Literal("ABC")），正如我们在第一篇文章中所涵盖的。
public static FA Literal(IEnumerable<int> codepoints, int accept = 0, bool compact = true)
{
var result = new FA(accept);
var current = result;
foreach (var codepoint in codepoints)
{
// remove the previous accept
current.AcceptSymbol = -1;
// new state is accepting
var fa = new FA(accept);
current.AddTransition(new FARange(codepoint, codepoint), fa);
current = fa;
}
return result;
}
public static FA Literal(string @string, int accept = 0, bool compact = true)
{
return Literal(ToUtf32(@string), accept, compact);
}
请注意，我们的方法通常以 UTF-32 代码点（作为 int）进行处理。有一个 ToUtf32() 方法可以将 string 或 char 数组转换为 UTF-32。上面使用了它。
接下来，我们有 Set()，它构建的内容如下
此实现非常简单，因为我们只是向单个状态添加转移。我曾经在这里对范围进行排序，但现在不必了，因为这由 AddTransition() 处理。
public static FA Set(IEnumerable<FARange> ranges, int accept = 0, bool compact = true)
{
var result = new FA();
var final = new FA(accept);
foreach (var range in ranges)
result.AddTransition(range, final);
return result;
}
这涵盖了我们的一种“原子”功能。其余的则操作其他状态机，基本上是克隆传入的内容，进行相应修改，然后返回。这些函数都不会更改原始表达式。这样效率较低，但在 API 方面要安全得多。未来，我可能会创建不克隆状态的内部函数，这些函数将由 Parse() 等其他方法使用。
总之，接下来我们将介绍连接
public static FA Concat(IEnumerable<FA> exprs, int accept = 0, bool compact = true)
{
FA result = null, left = null, right = null;
// we need to break the expressions into left and right
// pairs to pass to _Concat. There are several corner
// cases to consider, such as having one expression
// or no expressions.
foreach (var val in exprs)
{
if (null == val) continue;
var nval = val.Clone();
if (null == left)
{
if (null == result)
result = nval;
left = nval;
continue;
}
if (null == right)
{
right = nval;
}
nval = right.Clone();
_Concat(left, nval, compact);
right = null;
left = nval;
}
// we need to handle the tail where _Concat didn't.
// find all accept states and set the value to
// the "accept" arg
if (null != right)
{
var acc = right.FillFind(AcceptingFilter);
for (int ic = acc.Count, i = 0; i < ic; ++i)
acc[i].AcceptSymbol = accept;
}
else
{
var acc = result.FillFind(AcceptingFilter);
for (int ic = acc.Count, i = 0; i < ic; ++i)
acc[i].AcceptSymbol = accept;
}
// if no expressions we don't accept anything
return result==null?new FA():result;
}
static void _Concat(FA lhs, FA rhs, bool compact)
{
// take the left hand, clear all the accept states
// and then add an epsilon from each to the start
// of the right hand
var acc = lhs.FillFind(AcceptingFilter);
for (int ic = acc.Count, i = 0; i < ic; ++i)
{
var f = acc[i];
f.AcceptSymbol = -1;
f.AddEpsilon(rhs, compact);
}
}
在这里 _Concat() 执行两个机器之间的实际连接，但 Concat() 接受机器列表并将它们配对，注意那些奇怪的情况，并最终确定接受状态。
现在我们有了 Or()，它在一台机器和另一台机器之间创建一个析取/选择
public static FA Or(IEnumerable<FA> exprs, int accept = 0, bool compact = true)
{
var result = new FA();
var final = new FA(accept);
// for each expr
// 1. add an epsilon from result to the expr
// 2. set all the accept states to non-accepting
// 3. add an epsilon from each to the final state
// unless the state is null in which case
// we just add an empty transition to the final
// state making the whole expression optional so
// (foo|bar|) works as expected
foreach (var fa in exprs)
{
if (null != fa)
{
var nfa = fa.Clone();
result.AddEpsilon(nfa, compact);
var acc = nfa.FillFind(AcceptingFilter);
for (int ic = acc.Count, i = 0; i < ic; ++i)
{
var nffa = acc[i];
nffa.AcceptSymbol = -1;
nffa.AddEpsilon(final, compact);
}
}
else result.AddEpsilon(final, compact);
}
return result;
}
注释和图应该会让上面的内容非常清楚，因为这是一个直接的构造。
继续，我们有 Optional()，它简单地使一个表达式或空字符串被接受
public static FA Optional(FA expr, int accept = 0, bool compact = true)
{
var result = expr.Clone();
if(result.IsAccepting) return result;
// get all the accept states
var acc = result.FillFind(AcceptingFilter);
FA final = null;
if(acc.Count>1)
{
// there's more than one. we have to first
// funnel all of them to one single accept
final = new FA(accept);
for (int ic = acc.Count, i = 0; i < ic; ++i)
{
var fa = acc[i];
fa.AcceptSymbol = -1;
fa.AddEpsilon(final, compact);
}
} else
{
// just change the accept symbol to the final one.
final = acc[0];
final.AcceptSymbol = accept;
}
// bridge the first state to the last one.
result.AddEpsilon(final, compact);
return result;
}
这个应该很简单，但我今天早上发现了一个在有多个接受状态的情况下存在的 bug。我现在在上面单独处理它。我将来可能会以不同的方式处理它，因为有一种不合并接受状态的替代方法，但我犹豫要不要去动一个能正常工作的。
下一个可能是最复杂的。它使用自身以及其他构造方法来完成给定的操作。
我无法在这里绘制所有不同的场景。最简单的场景是基本的循环构造，如下所示
那是 FA.Repeat(FA.Literal("ABC"),1) 或 (ABC)+。类似的构造 FA.Repeat(FA.Literal("ABC")) 或 (ABC)* 会相同，只是 **q0** 会包含另一个方向的 epsilon **q0->q4** 以及 **q4->q0**。
另一种情况是最小出现次数超过一次。考虑 FA.Repeat(FA.Literal("ABC"),3,3) 或 (ABC){3,3}
它只是创建了表达式的 2 个额外副本（总共 3 个）。
现在考虑：FA.Repeat(FA.Literal("ABC"),2,3) 或 (ABC){2,3}
它很长，很难看，而且很深。
public static FA Repeat(FA expr,
int minOccurs = 0,
int maxOccurs = 0,
int accept = 0,
bool compact = true)
{
if (minOccurs < 0) minOccurs = 0;
if (maxOccurs < 0) maxOccurs = 0;
expr = expr.Clone();
if (minOccurs > 0 && maxOccurs > 0 && minOccurs > maxOccurs)
throw new ArgumentOutOfRangeException(nameof(maxOccurs));
FA result;
switch (minOccurs)
{
case 0: // lower bound unbounded. whole expression is optional
switch (maxOccurs)
{
case 0:
result = new FA(accept);
result.AddEpsilon(expr, compact);
foreach (var afa in expr.FillFind(AcceptingFilter))
{
afa.AddEpsilon(result, compact);
}
return result;
case 1:
result = Optional(expr, accept, compact);
return result;
default:
var l = new List<FA>();
expr = Optional(expr, accept, compact);
l.Add(expr);
for (int i = 1; i < maxOccurs; ++i)
{
l.Add(expr.Clone());
}
result = Concat(l, accept, compact);
return result;
}
case 1:
switch (maxOccurs)
{
case 0:
result = Repeat(expr, 0, 0, accept, compact);
result.AcceptSymbol = -1;
return result;
case 1:
return expr;
default:
result = Concat(
new FA[] { expr,
Repeat(expr,
0,
maxOccurs - 1,
accept,
compact) },
accept,
compact);
return result;
}
default:
switch (maxOccurs)
{
case 0:
result = Concat(
new FA[] {
Repeat(expr,
minOccurs,
minOccurs,
accept,
compact),
Repeat(expr,
0,
0,
accept,
compact) },
accept,
compact);
return result;
case 1:
throw new ArgumentOutOfRangeException(nameof(maxOccurs));
default:
if (minOccurs == maxOccurs)
{
var l = new List<FA>();
l.Add(expr);
for (int i = 1; i < minOccurs; ++i)
{
var e = expr.Clone();
l.Add(e);
}
result = Concat(l, accept);
return result;
}
result = Concat(new FA[] {
Repeat(
expr,
minOccurs,
minOccurs,
accept,
compact),
Repeat(
Optional(
expr,
accept,
compact),
maxOccurs - minOccurs,
maxOccurs - minOccurs,
accept,
compact) },
accept,
compact);
return result;
}
}
}
最后，我们有 CaseInsenstive()，它会使机器忽略字符大小写。这并不是真正的 Thompson 算法，但属于一类，所以我包含了它。
public static FA CaseInsensitive(FA expr)
{
const string emsg = "Attempt to make an invalid range case insensitive";
var result = expr.Clone();
var closure = new List<FA>();
result.FillClosure(closure);
for (int ic = closure.Count, i = 0; i < ic; ++i)
{
var fa = closure[i];
var t = new List<FATransition>(fa._transitions);
fa.ClearTransitions();
foreach (var trns in t)
{
var f = char.ConvertFromUtf32(trns.Min);
var l = char.ConvertFromUtf32(trns.Max);
if (char.IsLower(f, 0))
{
if (!char.IsLower(l, 0))
throw new NotSupportedException(emsg);
fa.AddTransition(new FARange(
trns.Min,
trns.Max),
trns.To);
f = f.ToUpperInvariant();
l = l.ToUpperInvariant();
fa.AddTransition(new FARange(
char.ConvertToUtf32(f, 0),
char.ConvertToUtf32(l, 0)),
trns.To);
}
else if (char.IsUpper(f, 0))
{
if (!char.IsUpper(l, 0))
throw new NotSupportedException(emsg);
fa.AddTransition(new FARange(trns.Min, trns.Max), trns.To);
f = f.ToLowerInvariant();
l = l.ToLowerInvariant();
fa.AddTransition(new FARange(
char.ConvertToUtf32(f, 0),
char.ConvertToUtf32(l, 0)),
trns.To);
}
else
{
fa.AddTransition(new FARange(
trns.Min,
trns.Max),
trns.To);
}
}
}
return result;
}
我们在这里所做的只是查找字母，然后为每个字母添加备用的大小写。如果我们遇到一个包含一个字母和一个非字母的范围，我们会报错，但实际上我从未见过这种情况。
查找状态
通常，当您在 Visual FA 中引用状态机时，您会使用 **q0** 作为整个机器的句柄。如果您需要机器中所有状态的列表，您就*取 **q0** 的闭包*。我们为此提供了 FillClosure()
void _Closure(IList<FA> result)
{
if (!_Seen.Add(this))
{
return;
}
result.Add(this);
for (int ic = _transitions.Count, i = 0; i < ic; ++i)
{
var t = _transitions[i];
t.To._Closure(result);
}
}
public IList<FA> FillClosure(IList<FA> result = null)
{
if (null == result)
result = new List<FA>();
_Seen.Clear();
_Closure(result);
return result;
}
本质上，我们递归地检查尚未看到的状态的所有转移，并将其目标添加到结果中。_Seen 是一个线程静态的 HashSet<FA>，它被保留下来，因为它经常被使用，而且我们不想重新创建它。这种方法的一个小缺点是，依赖它的所有函数都不可重入，即使是相互之间也是如此。但是，由于这是一个核心方法，可以被调用很多次，所以减少开销似乎是值得的。
我们之前已经讨论过，但值得重申的是，FillXXXX() API 允许您选择性地回收列表，而 GetXXXX() 风格的 API 只返回列表则不能。这是为了性能。
有一个类似的操作——获取 epsilon 闭包——它查找仅沿着 epsilon 转移可从给定状态或状态到达的所有状态。您可以使用 FillEpsilonClosure() 执行此操作。您可能会觉得不一致，因为与 FillClosure() 不同，这些方法是静态的。原因是与此操作最常用于状态列表而不是单个状态有关。这与 C#（实际上大多数类似语言）的限制有关，即编译器无法区分 fill 方法的结果与必要静态版本中的初始状态参数，因此两个重载都是静态的。总之，它们是这样的
IList<FA> _EpsilonClosure(IList<FA> result, HashSet<FA> seen)
{
if(!seen.Add(this))
{
return result;
}
result.Add(this);
if(IsCompact)
{
return result;
}
for (int i = 0; i < _transitions.Count; ++i)
{
var t = _transitions[i];
if(t.Min==-1 && t.Max==-1)
{
if (t.To.IsCompact)
{
if (seen.Add(t.To))
{
result.Add(t.To);
}
}
else
{
t.To._EpsilonClosure(result, seen);
}
} else {
// no more epsilons. we're done
break;
}
}
return result;
}
public static IList<FA> FillEpsilonClosure(IList<FA> states,
IList<FA> result=null)
{
if (null == result)
result = new List<FA>();
_Seen.Clear();
for(int i = 0;i<states.Count;++i)
{
var fa = states[i];
fa._EpsilonClosure(result,_Seen);
}
return result;
}
public static IList<FA> FillEpsilonClosure(FA state,
IList<FA> result = null)
{
if (null == result)
result = new List<FA>();
_Seen.Clear();
state._EpsilonClosure(result, _Seen);
return result;
}
在操作方式上，这几乎与 FillClosure() 相同，只是它只关心 epsilon 转移，并且有一个与多个状态一起工作的重载。请注意，在查找 epsilon 转移时，如果我们找到一个非 epsilon 转移，我们会提前退出。这是因为 epsilon 转移总是首先在 _transitions 列表中插入，所以如果我们找到一个非 epsilon 转移，我们已经看到所有 epsilon 转移了。
注意：下面的 API 可能会很快修改，以便向 FAFindFilter 委托添加更多信息。
void _Find(FAFindFilter filter,
IList<FA> result)
{
if (!_Seen.Add(this))
{
return;
}
if (filter(this))
{
result.Add(this);
}
for (int i = 0; i < _transitions.Count; ++i)
{
var t = _transitions[i];
t.To._Find(filter, result);
}
}
public IList<FA> FillFind(FAFindFilter filter,
IList<FA> result = null)
{
if (null == result)
result = new List<FA>();
_Seen.Clear();
_Find(filter, result);
return result;
}
您可能会注意到，由于这些方法中使用了 _Seen，我们无法在 FAFindFilter 调用中获取任何类型的闭包。我正在认真考虑为此创建一个单独的线程静态哈希集。总之，它的作用相当直接。它会跟踪所有转移，对于任何未见过的状态，它会调用 FAFindFilter。如果返回 true，则将其添加到 result。
FindFirst() 是一个相关的方法，它只查找第一个匹配项然后停止搜索。
FA _FindFirst(FAFindFilter filter)
{
if (!_Seen.Add(this))
{
return null;
}
if (filter(this))
{
return this;
}
for (int ic = _transitions.Count, i = 0; i < ic; ++i)
{
var t = _transitions[i];
var fa = t.To._FindFirst(filter);
if (null != fa)
{
return fa;
}
}
return null;
}
public FA FindFirst(FAFindFilter filter)
{
_Seen.Clear();
var result = _FindFirst(filter);
return result;
}
它几乎与另一个方法相同，只是它一旦调用 FAFindFilter 返回 true 就会短路。
NFA 到 DFA 的转换
这有点棘手。幂集构造在我实现过几次之后就比较容易了，尽管范围处理是一个复杂的难题，这是我从 Fare 的实现（作者：Nikos Baxevanis - 项目包含许可证信息）中获得的。
private static FA _Determinize(FA fa, IProgress<int> progress)
{
// initialize
int prog = 0;
progress?.Report(prog);
var p = new HashSet<int>();
var closure = new List<FA>();
fa.FillClosure(closure);
// gather our input alphabet
for (int ic = closure.Count, i = 0; i < ic; ++i)
{
var ffa = closure[i];
p.Add(0);
foreach (var t in ffa._transitions)
{
if (t.Min == -1 && t.Max == -1)
{
continue;
}
p.Add(t.Min);
if (t.Max < 0x10ffff)
{
p.Add((t.Max + 1));
}
}
}
var points = new int[p.Count];
p.CopyTo(points, 0);
Array.Sort(points);
++prog;
progress?.Report(prog);
var sets = new Dictionary<_KeySet<FA>, _KeySet<FA>>();
var working = new Queue<_KeySet<FA>>();
var dfaMap = new Dictionary<_KeySet<FA>, FA>();
var initial = new _KeySet<FA>();
var epscl = new List<FA>();
List<FA> ecs = new List<FA>();
List<FA> efcs = null;
_Seen.Clear();
fa._EpsilonClosure(epscl, _Seen);
for(int i = 0; i < epscl.Count;++i)
{
var efa = epscl[i];
initial.Add(efa);
}
sets.Add(initial, initial);
working.Enqueue(initial);
var result = new FA();
result.IsDeterministic = true;
result.FromStates = epscl.ToArray();
foreach (var afa in initial)
{
if (afa.IsAccepting)
{
result.AcceptSymbol = afa.AcceptSymbol;
break;
}
}
++prog;
progress?.Report(prog);
// powerset/subset construction
dfaMap.Add(initial, result);
while (working.Count > 0)
{
// get the next set
var s = working.Dequeue();
// get the next DFA out of the map
// of (NFA states)->(dfa state)
FA dfa = dfaMap[s];
// find the first accepting
// state if any, and assign
// it to the new DFA
foreach (FA q in s)
{
if (q.IsAccepting)
{
dfa.AcceptSymbol = q.AcceptSymbol;
break;
}
}
// for each range in the input alphabet
for (var i = 0; i < points.Length; i++)
{
var pnt = points[i];
var set = new _KeySet<FA>();
foreach (FA c in s)
{
// TODO: Might be able to eliminate the
// epsilon closure here. Needs testing
ecs.Clear();
if (!c.IsCompact)
{
// use the internal _EpsilonClosure
// method to avoid an extra call
// (basically inlining it)
_Seen.Clear();
c._EpsilonClosure(ecs, _Seen);
} else
{
ecs.Add(c);
}
for (int j=0;j<ecs.Count;++j)
{
var efa = ecs[j];
// basically if we intersect somewhere on the input alphabet,
// which we should, then we add the destination state(s) to the set
for (int k = 0; k<efa._transitions.Count;++k)
{
var trns = efa._transitions[k];
if (trns.Min == -1 && trns.Max == -1)
{
continue;
}
// TODO: can probably early out here
// if pnt > trns.Max?
if (trns.Min <= pnt && pnt <= trns.Max)
{
// skip the epsilon closure
// we don't need it
if (trns.To.IsCompact)
{
set.Add(trns.To);
}
else
{
if(efcs==null)
{
efcs = new List<FA>();
}
efcs.Clear();
_Seen.Clear();
trns.To._EpsilonClosure(efcs, _Seen);
for (int m = 0; m < efcs.Count; ++m)
{
set.Add(efcs[m]);
}
}
}
}
}
// less GC stress
_Seen.Clear();
}
// is this a new set or an
// existing one?
if (!sets.ContainsKey(set))
{
sets.Add(set, set);
// add another work item
working.Enqueue(set);
// make a new DFA state
var newfa = new FA();
newfa.IsDeterministic = true;
newfa.IsCompact = true;
dfaMap.Add(set, newfa);
var fas = new List<FA>(set);
// TODO: we should really sort fas
newfa.FromStates = fas.ToArray();
}
FA dst = dfaMap[set];
// find the first and last range to insert
int first = pnt;
int last;
if (i + 1 < points.Length)
{
last = (points[i + 1] - 1);
}
else
{
last = 0x10ffff;
}
// this should already be in sorted order
// otherwise we'd use AddTransition()
dfa._transitions.Add(new FATransition(dst,first, last));
++prog;
progress?.Report(prog);
}
++prog;
progress?.Report(prog);
}
// remove dead transitions (destinations with no accept)
foreach (var ffa in result.FillClosure())
{
var itrns = new List<FATransition>(ffa._transitions);
foreach (var trns in itrns)
{
var acc = trns.To.FindFirst(AcceptingFilter);
if (acc==null)
{
ffa._transitions.Remove(trns);
}
}
++prog;
progress?.Report(prog);
}
++prog;
progress?.Report(prog);
return result;
}
从 TODOs 中可以看出，可能还有一些改进的空间，但我已经对其进行了多次优化。我不太关心这段代码是否易于阅读，因为算法很棘手，即使代码写得更易于访问，仍然会令人困惑。它需要尽可能快，因为它对于大型机器来说已经是一个漫长的过程了。
不幸的是，最小化是我不理解的东西。我甚至无法判断它使用了 3 种左右的算法中的哪一种。同样，这次我 wholesale 地借用了 Fare 的实现。它能工作，所以我不能抱怨，但它确实很难理解！为了理智起见，我不会在这里发布它，因为它非常长，而且如此混乱，以至于可能不会在这里添加太多价值。我不像是能带你一步步看懂。核心在于 _Minimize()。
穿越机器
FillMove()（任何机器）和 Move()（仅限 DFA）根据输入的代码点导航机器。
public static IList<FA> FillMove(IList<FA> states,
int codepoint,
IList<FA> result = null)
{
_Seen.Clear();
if (result == null) result = new List<FA>();
for (int q = 0; q < states.Count;++q)
{
var state = states[q];
for (int i = 0; i < state._transitions.Count; ++i)
{
var fat = state._transitions[i];
// epsilon dsts should already be in states:
if (fat.Min == -1 && fat.Max == -1)
{
continue;
}
if(codepoint<fat.Min)
{
break;
}
if (codepoint <= fat.Max)
{
fat.To._EpsilonClosure(result, _Seen);
}
}
}
_Seen.Clear();
return result;
}
基本上，上面我们所做的就是将一个代码点与转移进行比较。由于转移是排序的，我们得以幸免。在这种情况下，一旦超出范围，我们就可以提前退出，而不必扫描整个转移集。我们跳过 epsilon 转移，因为调用者应该已经跟踪了它们。我们取每个目标状态的 epsilon 闭包。请注意，我们对所有这些都使用了 _Seen。这是因为我们不希望在整个过程中有任何重复。
Move() 执行类似的操作，但它不必使用列表或处理重叠范围到不同目标，因此它性能更高。
public FA Move(int codepoint)
{
if (!IsDeterministic)
{
throw new InvalidOperationException(
"The state machine must be deterministic");
}
for(int i = 0;i<_transitions.Count;++i)
{
var fat = _transitions[i];
if(codepoint<fat.Min)
{
return null;
}
if(codepoint<=fat.Max)
{
return fat.To;
}
}
return null;
}
数组序列化和反序列化
ToArray() 将状态机转换为 int[] 数组。
public int[] ToArray()
{
var working = new List<int>();
var closure = new List<FA>();
FillClosure(closure);
var stateIndices = new int[closure.Count];
// fill in the state information
for (var i = 0; i < stateIndices.Length; ++i)
{
var cfa = closure[i];
stateIndices[i] = working.Count;
// add the accept
working.Add(cfa.IsAccepting ? cfa.AcceptSymbol : -1);
var itrgp = cfa.FillInputTransitionRangesGroupedByState(true);
// add the number of transitions
working.Add(itrgp.Count);
foreach (var itr in itrgp)
{
// We have to fill in the following after the fact
// We don't have enough info here
// for now just drop the state index as a placeholder
working.Add(closure.IndexOf(itr.Key));
// add the number of packed ranges
working.Add(itr.Value.Count);
// add the packed ranges
working.AddRange(FARange.ToPacked(itr.Value));
}
}
var result = working.ToArray();
var state = 0;
// now fill in the state indices
while (state < result.Length)
{
++state;
var tlen = result[state++];
for (var i = 0; i < tlen; ++i)
{
// patch the destination
result[state] = stateIndices[result[state]];
++state;
var prlen = result[state++];
state += prlen * 2;
}
}
return result;
}
我们需要进行两次传递。在第一次遍历机器时，我们将所有基本状态信息填入 working 列表。但是，此时，我们不知道每个状态的最终索引，因此无法填入目标跳转。取而代之的是，我们将 stateIndices 填入每个状态在 working 数组中的绝对索引。在下一次传递中，我们再次遍历机器，以便找到目标状态并将其替换为数组中相应的索引，然后再返回。
要反序列化，我们使用 FromArray()
public static FA FromArray(int[] fa)
{
if (null == fa) throw new ArgumentNullException(nameof(fa));
if (fa.Length == 0)
{
var result = new FA();
result.IsDeterministic = true;
result.IsCompact = true;
return result;
}
// create the states and build a map
// of state indices in the array to
// new FA instances
var si = 0;
var indexToStateMap = new Dictionary<int, FA>();
while (si < fa.Length)
{
var newfa = new FA();
indexToStateMap.Add(si, newfa);
newfa.AcceptSymbol = fa[si++];
// skip to the next state
var tlen = fa[si++];
for (var i = 0; i < tlen; ++i)
{
++si; // tto
var prlen = fa[si++];
si += prlen * 2;
}
}
// walk the array
si = 0;
var sid = 0;
while (si < fa.Length)
{
// get the current state
var newfa = indexToStateMap[si];
newfa.IsCompact = true;
newfa.IsDeterministic = true;
// already set above:
// newfa.AcceptSymbol = fa[si++];
++si;
// transitions length
var tlen = fa[si++];
for (var i = 0; i < tlen; ++i)
{
// destination state index
var tto = fa[si++];
// destination state instance
var to = indexToStateMap[tto];
// range count
var prlen = fa[si++];
for (var j = 0; j < prlen; ++j)
{
var pmin = fa[si++];
var pmax = fa[si++];
if (pmin == -1 && pmax == -1)
{
// epsilon
newfa.AddEpsilon(to, false);
}
else
{
newfa.AddTransition(new FARange(pmin, pmax), to);
}
}
}
++sid;
}
return indexToStateMap[0];
}
实际上，我们在这里所做的就是首先创建所有必需的 FA 实例，设置它们的接受符号，然后从数组中填充转移。
创建词法分析器
ToLexer() 可用于从一系列机器创建词法分析器。它基本上是一个便利方法，尤其是在从一系列表达式创建 DFA 词法分析器时。
public static FA ToLexer(IEnumerable<FA> tokens,
bool makeDfa = true,
bool compact = true,
IProgress<int> progress = null)
{
var toks = new List<FA>(tokens);
if (makeDfa)
{
// first minimize the inner machines
for (int i = 0; i < toks.Count; i++)
{
toks[i] = toks[i].ToMinimizedDfa(progress);
}
}
// create a new root state.
var result = new FA();
for (int i = 0; i < toks.Count; i++)
{
result.AddEpsilon(toks[i], compact);
}
if (makeDfa && !result.IsDeterministic)
{
return result.ToDfa(progress);
}
else
{
return result;
}
}
您不能安全地将 ToMinimizedDfa() 调用到词法分析器的根，这使得从它创建高效的 DFA 变得复杂。此函数首先最小化每个传入的机器，然后再创建词法分析器的根。如果需要并且已指定，它会将根转换为 DFA，基本上消除根中的任何冲突。
解析
解析有点复杂。我们没有太多空间来探索代码，因为代码量非常大。不用担心，它没有那么有趣，我可以在这里描述它。基本上，它通过 StringCursor 扫描输入字符串，StringCursor 包含一个指向从字符串中提取的 UTF-32 代码点的光标并跟踪位置。当它遇到表达式的元素时，它会使用 Thompson 构建方法来构建机器。概念上很简单。最棘手的部分是解析范围，因为范围语法非常复杂。
ToString 魔术
ToString() 本身并不那么有趣，直到您开始传递格式说明符。“e”和“r”可以将状态机转换回正则表达式。应该注意的是，虽然表达式是正确的，但结果有时可能很复杂且有些冗余，尤其是在涉及循环构造时。“r”试图将表达式简化为更易读的内容，但资源消耗更大，我仍在改进它。
这是另一个我们不会在这里详细介绍的长篇内容，除了描述它的整体功能。首先，它构造了机器的边列表。这些边包含从状态和到状态以及指示表达式的字符串。起初，这些字符串只是从一个状态到下一个状态的范围集。在我们遍历它们时，我们通过将目标状态的表达式连接到指向它的任何转移来消除状态，然后在这些转移上将目标状态更改为目标类别的转移的目标状态，从而有效地跳过它并使其孤立。
在此过程中，它会特殊处理循环。如果遇到循环，它会将它们添加到自己的循环表达式列表中，以便稍后转换为字符串。在上一段描述的删除循环中，不会评估任何循环转移。
ToString("r") 有点不同。它使用 RegexExpression 抽象语法树模型在内部表示表达式，以便它可以对表达式调用 Reduce()，后者会尝试简化它。最后，它将其渲染为字符串。实际上，它通过 AST（与 ToString("e") 不同）以不同的方式执行 ToString("e") 所做的所有事情，并增加了额外的步骤。
我非常感谢 David Wolever 创建了他的 状态机到表达式 Go 代码。我尝试了很多年都无法成功实现这一点，而且我找到的描述该算法的资源都不够完整和准确，无法进行编码。最终，我偶然发现了他的作品，学习了一点 Go，现在我理解了这个过程。太棒了！
绘制状态
我在这些文章中的图表是使用 FA 的 RenderToFile() 和 RenderToStream() 生成的。
这些函数会从命令行自动执行 Graphviz 的 dot 可执行文件，该可执行文件负责将 dot 语言的输入转换为指定图像格式的输出。
首先让我们看看 RenderToFile()
public void RenderToFile(string filename, FADotGraphOptions options = null)
{
if (null == options)
options = new FADotGraphOptions();
string args = "-T";
string ext = Path.GetExtension(filename);
if(0==string.Compare(".dot",
ext,
StringComparison.InvariantCultureIgnoreCase)) {
using (var writer = new StreamWriter(filename, false))
{
WriteDotTo(writer, options);
return;
}
} else if (0 == string.Compare(".png",
ext,
StringComparison.InvariantCultureIgnoreCase))
args += "png";
else if (0 == string.Compare(".jpg",
ext,
StringComparison.InvariantCultureIgnoreCase))
args += "jpg";
else if (0 == string.Compare(".bmp",
ext,
StringComparison.InvariantCultureIgnoreCase))
args += "bmp";
else if (0 == string.Compare(".svg",
ext,
StringComparison.InvariantCultureIgnoreCase))
args += "svg";
if (0 < options.Dpi)
args += " -Gdpi=" + options.Dpi.ToString();
args += " -o\"" + filename + "\"";
var psi = new ProcessStartInfo("dot", args)
{
CreateNoWindow = true,
UseShellExecute = false,
RedirectStandardInput = true
};
using (var proc = Process.Start(psi))
{
if (proc == null)
{
throw new NotSupportedException(
"Graphviz \"dot\" application is either not installed or not in the system PATH");
}
WriteDotTo(proc.StandardInput, options);
proc.StandardInput.Close();
proc.WaitForExit();
}
}
我们在这里所做的是从传入的路径中收集文件扩展名，并使用它来确定输出文件格式。然后我们准备命令行参数。最后，我们创建一个新的 ProcessStartInfo 实例，用相关数据填充它，然后再调用 Process 来运行它。运行后，它直接将输入馈送到 dot 的 *stdin*。Dot 负责实际的文件写入。此例程会阻塞，但我可能最终会创建一个异步方法，该方法可以在图像渲染之前返回。
RenderToStream() 类似，只是我们以字符串参数（稍后可能会更改为 enum）的形式接受格式，并且我们从 dot 的 *stdout* 中读取流。
public Stream RenderToStream(string format,
bool copy = false,
FADotGraphOptions options = null)
{
if (null == options)
options = new FADotGraphOptions();
if(0==string.Compare(format,
"dot",
StringComparison.InvariantCultureIgnoreCase))
{
var stm = new MemoryStream();
using(var writer = new StreamWriter(stm)) {
WriteDotTo(writer, options);
stm.Seek(0,SeekOrigin.Begin);
return stm;
}
}
string args = "-T";
args += string.Concat(" ", format);
if (0 < options.Dpi)
args += " -Gdpi=" + options.Dpi.ToString();
var psi = new ProcessStartInfo("dot", args)
{
CreateNoWindow = true,
UseShellExecute = false,
RedirectStandardInput = true,
RedirectStandardOutput = true
};
using (var proc = Process.Start(psi))
{
if(proc==null)
{
throw new NotSupportedException(
"Graphviz \"dot\" application is either not installed or not in the system PATH");
}
WriteDotTo(proc.StandardInput, options);
proc.StandardInput.Close();
if (!copy)
return proc.StandardOutput.BaseStream;
else
{
var stm = new MemoryStream();
proc.StandardOutput.BaseStream.CopyTo(stm);
proc.StandardOutput.BaseStream.Close();
proc.WaitForExit();
return stm;
}
}
}
为 dot 创建输入的过程冗长而混乱。它的尴尬之处在于，它已经在我 FA 引擎的许多迭代中得以幸存，以至于代码已经腐朽，需要重写。问题是，它工作得很好，而且功能强大。用更干净的代码更改它将是大量的努力。无论如何，我不会在这里发布代码，因为它非常长。
下一步？
在下一部分中，我们将介绍 VisualFA.Generator 中的代码生成功能。
历史
- 2024 年 1 月 20 日 - 初始提交