如何在 C# 中构建正则表达式引擎
5.00/5 (22投票s)
在 C# 中构建一个功能丰富、非回溯的正则表达式引擎和代码生成器
更新
请参阅我的 Unicode 支持产品 此处
必备组件
项目解决方案采用 Visual Studio 2017 格式。它被编译为一个标准库和一个 Core 可执行文件。
此外，为了获得渲染支持，您需要安装 GraphViz，此代码使用它将状态图渲染成图像。您所需要做的就是运行 GraphViz 的安装程序，它应该在您的路径中。您不需要 GraphViz 来使用大多数正则表达式功能。您只需要它来制作漂亮的图片，例如本文中的图像。
由于我们使用的是 .NET Standard 和 .NET Core，我们还引用了 Code DOM NuGet 包。这对于代码生成功能是必需的。
引言
这是一篇雄心勃勃的文章。目标是引导您构建一个功能齐全的正则表达式引擎和代码生成器。该代码包含一个完整且即用型正则表达式引擎，并附有大量注释和分解，以帮助您理解源代码。
首先，您可能想知道我们为什么要首先开发一个。除了学习正则表达式内部工作原理的乐趣之外，.NET 框架的正则表达式类中还存在一个空白，而该项目很好地填补了这一空白。这将在下一节中解释。
我之前为 C# 编写了一个正则表达式引擎并在此处发布，但我没有解释代码的机制。我只是简单地介绍了几个基本原理。在这里，我的目标是深入研究一个更新的、高度分区的库，它应该足以揭开这个“野兽”的神秘面纱，让您可以开发自己的引擎或对其进行扩展。
我没有吝惜优化，尽管源代码增加了复杂性。我希望您能获得一个可以“开箱即用”的东西。话虽如此，向您提供最终库是一个次要目标。主要目标是教您如何自己构建一个。
概念化这个混乱的局面
本文假定您对常见正则表达式符号有大致的了解。您不必是专家，但了解 ?、*、+、|、[] 和 () 的作用非常有帮助。如果您只知道其中一部分，那也没关系，只要您理解正则表达式背后的基本思想及其用途即可。
您可能不知道的是它们操作背后的理论，我们将在本文中介绍。
本质上，正则表达式是一个基于有限状态机的有向图。也就是说，它是一个节点网络，通过有向路径连接到其他节点。这比描述更容易可视化
此正则表达式图匹配“foo”或“bar”。其正则表达式将是 foo|bar。
它的工作原理如下：我们总是从 q0 开始。从那里，我们有一系列指向外部的黑色箭头。每个箭头都标有一个字符。然后，我们检查要匹配字符串的第一个字符。如果是“f”，我们继续到 q1。如果是“b”，我们继续到 q4。每当我们沿着黑色箭头移动时，输入字符串的光标位置就会增加一。在 q1 或 q4 上，我们将检查**下一个**输入字符，依此类推。这会一直持续到我们无法再匹配任何字符。如果此时，我们处于一个带有双圈的状态（一个“接受状态”），我们已经匹配。如果此时我们处于某个单圈状态，那么我们没有匹配。
我们可以基于解析正则表达式创建这些图，然后使用代码“运行”这些图，以便它们可以匹配输入字符串。
说到匹配，使用正则表达式引擎有两种显著不同的方式。第一种，也许也是最常见的一种，是扫描一大段文本以查找特定模式。例如，如果您在 Visual Studio 中启用正则表达式匹配，这就是您在“搜索和替换”对话框中所做的事情。Microsoft 的正则表达式引擎已经很好地涵盖了这一点，并且在这些情况下通常最好使用它。对于长字符串，它可能比我们的库表现更好，因为它实现了诸如Boyer-Moore搜索等功能，而我们的库没有。通常，在这种匹配方式下，依靠 Microsoft 的引擎是一个好主意。
使用正则表达式引擎的另一种方法称为**词法分析**。这基本上是通过输入流移动，并尝试将光标下的字符串与特定模式匹配，然后报告匹配的模式，然后前进。基本上，它使用复合正则表达式（与“或”组合）并将文本与特定表达式之一匹配——并告诉您是哪个表达式匹配。这对于解析器使用的词法分析器/标记器非常有用。Microsoft 的正则表达式引擎不适合此任务，并且尝试将其用于此任务会带来许多缺点，包括额外的代码复杂性和相当大的性能损失。这种功能上的差距足以证明，如果正在编写解析器或出于其他原因进行标记化，则需要自定义正则表达式引擎。
与 Microsoft 的正则表达式引擎不同，此引擎不回溯。也就是说，它永远不会多次检查一个字符。这会带来更好的性能，但非回溯表达式不如回溯表达式那样具有表达性/强大。使用此引擎无法实现原子零宽度断言等功能，但这种权衡是值得的，尤其是在用于标记化时。
回到图，正如所暗示的，这些图中的每一个都代表一个有限状态机。状态机有一个根，总是由 **q0** 表示。如果我们要截取图的任何子集，例如，从 **q4** 开始，并忽略任何未被 **q4** 直接或间接指向的内容，那么这也是一个状态机。基本上，一个有限状态机是一组相互连接的状态机！
要从当前节点找到整个状态机，您需要获取一个状态的**闭包**。闭包是从某个状态（包括其自身）直接或间接可达的所有状态的集合。**q0** 的闭包总是整个图。在本例中，**q4** 的闭包是 { **q4**，**q5**，**q3** }。请注意，我们从不沿着箭头向后移动。图是有向的。获取闭包是任何有限状态机代码的核心操作。
让我们看一个稍微复杂一点的例子：(foo|bar)+。基本上，我们只是给机器添加了一个循环，这样它就可以匹配“foobarfoo”或“foofoobar”或“barbarfoofoobar”等。
这张图看起来完全不同！但是，如果您遵循它，它将变得有意义。另请注意，我们从双圈接受状态引出了箭头。这意味着我们一旦到达接受状态就不会停止，直到我们无法继续为止——无论是由于我们无法找到下一个字符匹配，还是因为我们用尽了输入。我们只关心在尽可能多地匹配**之后**它是接受的。这称为**贪婪匹配**。您可以通过更复杂的表达式模拟**惰性匹配**，但在非回溯正则表达式中没有内置的功能。
构建这些图有点技巧。上面的图称为**DFA**，但使用**NFA**以编程方式构建图要容易得多。为了实现NFA，我们在图中添加了一种额外类型的线——虚线，我们称之为**epsilon 转换**。与输入转换不同，epsilon 转换不消耗任何输入或前进输入光标。一旦您处于某个状态，您**也**处于通过虚线连接到它的每个状态。是的，我们现在可以同时处于多个状态。
立刻引人注目的是灰色虚线的增加，以及图表变得多么直观。请记住，我曾说过您会自动进入通过 epsilon 转换连接的状态，这意味着您一进入 **q0**，您**也**处于 **q1**、**q2** 和 **q8**。可以说，**q0** 的**epsilon 闭包**是 { **q0**、**q1**、**q2**、**q8** }。这是因为从每个相关状态引出的虚线箭头。
与之前的图相比，上述图的计算机导航成本要高得多。原因是这些 epsilon 转换引入了同时处于多个状态的能力。据说它是**非确定性的**。
前一个图是**确定性的**。它一次只能处于一个状态，这使得计算机更容易快速导航。
这些非确定性图的一个有趣特性是存在 1 个等效的确定性图。也就是说，存在一个没有虚线/epsilon 转换的等效图。换句话说，对于任何 NFA，都存在 1 个等效的 DFA。我们将在后面利用这个特性。
既然我们知道我们可以创建这些 NFA（带有 epsilon 转换），然后将它们转换为 DFA（不带 epsilon 转换），我们将使用 NFA 图进行所有状态机构建，只有在完成后才将它们转换为 DFA。
我们将使用 Thompson 构造算法的一个变体来构建我们的图。这通过定义几个基本子图，然后将这些子图组合成更大的图来实现
首先，我们有一个**文字**——正则表达式 `ABC`
接下来，我们有一个**字符集**——正则表达式 `[ABC]`
![[A-C]/[ABC]](https://cloudfront.codeproject.com/articles/5251476/set.jpg)
接下来，我们有**连接**——正则表达式 `ABC(DEF)`：（这通常是隐式的）
现在，我们有**或**——正则表达式 `ABC|DEF`
接下来我们有**可选**——正则表达式 `(ABC)?`
最后，我们有**重复**——正则表达式 `(ABC)+`
所有其他模式都可以由这些构成。我们将它们像乐高积木一样拼凑起来以构建图形。唯一的问题是，当我们把它们粘在一起时，我们必须将以前的接受状态变为非接受状态，然后为最终机器创建一个新的接受状态。重复此过程，嵌套以组合图形。
请注意那些只有一条虚线出线的灰色状态。这些是**中性**状态。它们实际上不会改变机器接受的内容，但在汤普森构造期间引入。这很好，因为它是图转换为 DFA 后将消除的副产品。
同时，**最终**状态仅仅是没有出站转换的状态。通常，这些状态也是接受状态。
这些有限状态机是我们正则表达式引擎的核心。
我们将把词法分析作为首要目标，所以我将尝试解释它。上面，我们使用了“**接受**”作为我们的符号——它出现在双圈状态的状态标签（qX）下方。我们可以使用其他符号，并且每个图可以有许多不同的符号。通常，这样的机器被称为词法分析器。从技术上讲，它们是 DFA 数学的一种“hack”，但它们是所有基于 FSM 的词法分析器普遍使用的“hack”。它只是意味着你不能将它表示为文本正则表达式——它只能在代码中创建。这是一个匹配一系列数字、一系列字母（一个“单词”）或一串空格的词法分析器，它会报告是哪一种
![[0-9]+|[A-Za-z]+|\w+](https://cloudfront.codeproject.com/articles/5251476/lexer.jpg)
对此没有真正的文本正则表达式表示。它是其他正则表达式的组合。每个都有自己关联的**接受符号**。此外，我们不是像传统查找第一个匹配那样，一次性对长字符串运行这台机器，而是每次“移动”输入时都必须运行这台机器。基本上，每次运行机器时，它都会前进输入光标，所以我们只需一遍又一遍地运行机器来移动。每次迭代都会报告一个符号或一个错误。
因此，在这里，将其运行在输入字符串“foo123 bar”上将报告
Word: foo
Digits: 123
Whitespace:
Word: bar
这就是为什么解析器通常依赖它们。它基本上将输入流分解成一系列词元或**标记**。运行这种机器的代码通常被称为**标记器**或**词法分析器**。它是我们正则表达式引擎的一个特长，因为这是它在 .NET 下最有用的应用。
幂集构造再次是我们将 NFA 转换为 DFA 的方式。我们喜欢这样，因为 DFA 效率更高，我们稍后会看到。我们基本上需要做的是找出我们可以处于的所有可能的状态组合。每组可能的状态大致会解析为一个 DFA 状态。例外情况是，当两个状态在相同的输入下转换到不同的目标状态时，这是不可能的。此时，我们最终会引爆可能性，因为我们需要克隆路径 N-1 次，其中 N 是冲突的数量。这既不容易解释也不容易编码。希望一个图表会有所帮助
该图表指示 DFA 状态由哪些源状态组成。您将看到每个状态都包含其他几个状态。然而，有时在正确——或者更确切地说，不正确的情况下，几个状态会产生更多的状态。我认为我无法非常清楚地向您解释该算法，但代码应该有所帮助。
您可能已经注意到的一点是，转换箭头有时上方有范围。它**实际上**正在做的是将许多箭头合并为一个，然后为该箭头分配一个范围。
这通常是外观上的，尽管代码是范围感知的，有时会将其用于优化，主要是在代码生成或 DFA 状态表遍历期间。
说到 DFA 状态表，DFA 的一个优点是相对容易将其简化为状态表，从而实现更高效的遍历。从 DFA 生成代码也更容易，但这些在 NFA 中都不容易做到。
DFA 状态表如下所示
| 状态 | 接受 | 输入 | 目标 |
| q0 | 不适用 | [0-9] | q1 |
| q0 | 不适用 | [A-Za-z] | q2 |
| q0 | 不适用 | \s | q3 |
| q1 | 数字 | [0-9] | q1 |
| q2 | 单词 | [A-Za-z] | q2 |
| q3 | 空白 | \s | q3 |
在我们自己的类中，我们使用嵌套数组来使其稍微更高效，但概念是相同的。
这是**q2**，作为生成的代码
q2:
if ((((context.Current >= 'A')
&& (context.Current <= 'Z'))
|| ((context.Current >= 'a')
&& (context.Current <= 'z'))))
{
// capture the current character under the cursor
context.CaptureCurrent();
// advance the input position by one
context.Advance();
// goto the next state (ourself)
goto q2;
}
return 1; // "Word" symbol id
无论哪种方式，使用表格或使用生成的代码，您都可以完成相同的事情。
总之，希望这使得概念足够清晰，我们可以开始编写代码了。
编写这个混乱的程序
我已将 `CharFA
让我们从**CharFA.cs**中状态机中单个状态的基本数据结构开始。
/// <summary>
/// Represents a single state in a character based finite state machine.
/// </summary>
/// <typeparam name="TAccept">The type of the accepting symbols</typeparam>
public partial class CharFA<TAccept>
{
// we use a specialized dictionary class both for performance and
// to preserve the order of the input transitions
/// <summary>
/// Indicates the input transitions.
/// These are the states that will be transitioned to on the specified input key.
/// </summary>
public IDictionary<char, CharFA<TAccept>> InputTransitions { get; }
= new _InputTransitionDictionary();
/// <summary>
/// Indicates the epsilon transitions.
/// These are the states that are transitioned to without consuming input.
/// </summary>
public IList<CharFA<TAccept>> EpsilonTransitions { get; }
= new List<CharFA<TAccept>>();
/// <summary>
/// Indicates whether or not this is an accepting state.
/// When an accepting state is landed on, this indicates a potential match.
/// </summary>
public bool IsAccepting { get; set; } = false;
/// <summary>
/// The symbol to associate with this accepting state.
/// Upon accepting a match, the specified symbol is returned which can identify it.
/// </summary>
public TAccept AcceptSymbol { get; set; } = default(TAccept);
/// <summary>
/// Indicates a user-defined value to associate with this state
/// </summary>
public object Tag { get; set; } = null;
/// <summary>
/// Constructs a new instance with the specified accepting value and accept symbol.
/// </summary>
/// <param name="isAccepting">Indicates whether or not the state is accepting</param>
/// <param name="acceptSymbol">Indicates the associated symbol to be used
/// when accepting.</param>
public CharFA(bool isAccepting,TAccept acceptSymbol=default(TAccept))
{
IsAccepting = isAccepting;
AcceptSymbol = acceptSymbol;
}
/// <summary>
/// Constructs a new non-accepting state
/// </summary>
public CharFA()
{
}
}
一旦你剥离了注释，这里还没有太多内容。它主要只是一些数据字段和几个构造函数
首先，我们有 `InputTransitions`。这是一个 `IDictionary
接下来，我们有 `EpsilonTransitions`。这是一个 `IList
`IsAccepting` 表示该状态是否是接受状态。图中双圈表示接受状态。
`AcceptSymbol` 表示与此状态关联的接受符号。这用于标记化。每个符号基本上是它所代表模式的 ID。上面，它们是“Word”、“Digits”和“Whitespace”。
最后，我们有 `Tag`。此属性用于与状态关联的任意用户定义值。这通常用于调试，但不一定是。它对机器没有影响。
除此之外，我们只是有一个方便的构造函数和默认构造函数。
现在，我们需要一种方法来做最基本的事情，甚至找到状态机的边界。我们需要我们的闭包函数！我们可以在**CharFA.Computation.cs**中看到这些和其他计算方法。
从现在开始，我将仅突出显示必要的有趣代码部分，否则文章将非常长。
public IList<CharFA<TAccept>> FillClosure(IList<CharFA<TAccept>> result = null)
{
if (null == result)
result = new List<CharFA<TAccept>>();
else if (result.Contains(this))
return result;
result.Add(this);
// use a cast to get the optimized internal input mapping by FA state
foreach (var trns in InputTransitions as IDictionary<CharFA<TAccept>,ICollection<char>>)
trns.Key.FillClosure(result);
foreach (var fa in EpsilonTransitions)
fa.FillClosure(result);
return result;
}
基本上，我们在这里做的是递归调用我们以前从未见过的任何状态上的 `FillClosure()`，并在进行过程中添加它们。在递归之前检查我们是否已经有状态很重要，否则机器中的循环会导致此函数中的堆栈溢出！
`FillEpsilonClosure()` 的工作方式基本相同，但只遍历 epsilon 转换。
继续，我们有 `FillMove()`
public static IList<CharFA<TAccept>> FillMove(IEnumerable<CharFA<TAccept>> states,
char input, IList<CharFA<TAccept>> result = null)
{
if (null == result) result = new List<CharFA<TAccept>>();
foreach (var fa in FillEpsilonClosure(states))
{
// examine each of the states reachable from this state on no input
CharFA<TAccept> ofa;
// see if this state has this input in its transitions
if (fa.InputTransitions.TryGetValue(input, out ofa))
foreach (var efa in ofa.FillEpsilonClosure())
if (!result.Contains(efa)) // if it does, add it if it's not already there
result.Add(efa);
}
return result;
}
还记得我说过你可以同时处于多个状态吗？嗯，这个函数接收我们当前所处的状态集合，并按照指定的输入字符移动，产生移动后所得到的状态集合，如果适用，它会沿着所有必要的虚线灰色线和实心黑线移动。基本上，它的工作原理是在执行 epsilon 闭包后，依次查询每个输入转换字典以获取输入字符。然后它对这些结果状态执行 epsilon 闭包以完成操作。这是运行正则表达式的核心，因为它代表了正则表达式字符匹配的单次迭代。这适用于 NFA 和 DFA，但有一种更有效的方法可以沿着 DFA 移动，因为它们只能处于一个状态。考虑 `MoveDfa()`
public CharFA<TAccept> MoveDfa(char input)
{
CharFA<TAccept> fa;
if (InputTransitions.TryGetValue(input, out fa))
return fa;
return null;
}
这里不涉及循环或集合。只有一个字典查找。这效率更高，但稍后，我们将使其效率更高。请注意，您可以在 NFA 上尝试此操作，但它无法正常工作。不幸的是，虽然可以检查机器是否是 DFA，但没有足够高效的方法来执行此方法。请务必仅将其与 DFA 一起使用。
`FillInputTransitionRangesGroupedByState()` 读起来很拗口，但它很有描述性。每个状态都会返回一个集合，其中包含指向该状态的输入。这些输入以字符范围的形式返回。这主要用于显示和代码生成。这些范围用于显示输入转换上方的范围，并且代码生成器使用它们来创建条件语句。
我想引导您注意我们在**CharFA.InputTransitionDictionary.cs**中优化的输入转换字典
// a specialized input transition container dictionary.
// this isn't required for a working regex engine but
// can make some common operations significantly faster.
partial class CharFA<TAccept>
{
/// <summary>
/// This is a specialized transition container
/// that can return its transitions in 3 different ways:
/// 1. a dictionary where each transition state is keyed
/// by an individual input character (default)
/// 2. a dictionary where each collection of inputs is keyed
/// by the transition state (used mostly by optimizations)
/// 3. an indexable list of pairs where the key is the transition state
/// and the value is the collection of inputs
/// use casts to get at the appropriate interface for your operation.
/// </summary>
private class _InputTransitionDictionary :
IDictionary<char, CharFA<TAccept>>, // #1
IDictionary<CharFA<TAccept>, ICollection<char>>, // #2
IList<KeyValuePair<CharFA<TAccept>, ICollection<char>>> // #3
{
IDictionary<CharFA<TAccept>, ICollection<char>> _inner =
new ListDictionary<CharFA<TAccept>, ICollection<char>>();
...
在内部，此类将转换存储为 `IDictionary
继续，让我们来看看**CharFA.SetComparer.cs**中一个庞大的相等比较器类
partial class CharFA<TAccept>
{
// this class provides a series of comparers for various CharFA operations
// these are primarily used during duplicate checking and in the powerset
// construction
private sealed class _SetComparer :
IEqualityComparer<IList<CharFA<TAccept>>>,
IEqualityComparer<ICollection<CharFA<TAccept>>>,
IEqualityComparer<IDictionary<char, CharFA<TAccept>>>
{
...
有关相等比较器工作原理的更多信息，请参阅我关于 C# 中的值相等语义的文章。您可以看到此类实现了其中三个，每个处理不同类型的容器。我们在幂集构造期间以及需要通过状态集合对字典或哈希表进行键控或需要比较输入转换（由重复状态检测代码使用）的其他区域中使用这些。
我们如果没有能力首先构建状态机，就做不了多少事情。幸运的是，我们在**CharFA.ThompsonConstruction.cs**中有一堆方法可以做到这一点
每个方法都接受一个输入字符串或一个或多个表达式，可能还有其他参数，最后是一个可选的接受符号。此文件提供了以下构造
- `Literal()`：根据输入字符串构建文字。
- `Set()`：根据输入字符串或字符范围集合构建字符集。
- `Or()`：在两个或多个表达式之间创建交替。基本上，这将创建一个匹配指定表达式中任何一个的状态机。
- `Concat()`：创建两个或多个表达式的系列连接。
- `Optional()`：创建一个使传入表达式可选的状态机。
- `Repeat()`：根据可选指定的最小和最大次数重复表达式。
- `CaseInsensitive()`：使指定表达式不区分大小写。
这些方法通过接受传入的 FSM/表达式或字符串，并根据它创建一个新的 FSM 来工作。通常，这些方法连接不同状态之间的线条以完成操作。
考虑 `Set()`
public static CharFA<TAccept> Set(IEnumerable<char> set, TAccept accept = default(TAccept))
{
var result = new CharFA<TAccept>();
var final = new CharFA<TAccept>(true, accept);
foreach (var ch in set)
result.InputTransitions[ch]= final;
return result;
}
它所做的是创建两个新状态，然后对于集合中的每个字符，它创建一个从第一个状态到最终状态的转换，然后返回第一个状态。这会创建如前所示的字符集图。其中一些可能会变得相当复杂。`Repeat()` 就是一个例子，因为它有太多的特殊情况。
这一切都很好，但如果我们需要查看图表并检查我们刚刚构建的内容怎么办？当然，我们可以通过调试器深入研究字典，但这太麻烦了！相反，为什么不直接将状态机渲染成 jpeg 或 png 呢？进入**CharFA.GraphViz.cs**
这自然需要 GraphViz，所以请确保它已安装。这基本上涵盖了使用 GraphViz **dot** 工具从状态机图渲染图像的整个繁琐过程。Dot 非常强大，但也杂乱，有点像 Perl。生成这些点规范的代码反映了这一点。它的工作原理是接受状态机并将点规范写入流，然后将其管道输送到 dot 工具，然后管道输送回图像。这需要 GraphViz 在您的路径中，但只要它已安装，它应该已经存在。您可以通过 `CharFA
var lit = CharFA<string>.Literal("ABC");
lit.RenderToFile("5251476/literal.jpg");
这段代码处理所有糟糕的细节。您可以通过文件扩展名指定输出格式。例如，要渲染 PNG 文件，您可以使用“*.png”而不是“*.jpg”。我使用此功能渲染了本文中的所有图表。
最后，如果我们不能实际使用正则表达式进行词法分析/标记化或搜索文本，那么这一切都将毫无用处。这就是**CharFA.Lexer.cs**和**CharFA.Matcher.cs**的用途
partial class CharFA<TAccept>
{
/// <summary>
/// Creates a lexer out of the specified FSM "expressions"
/// </summary>
/// <param name="exprs">The expressions to compose the lexer with</param>
/// <returns>An FSM representing the lexer.</returns>
public static CharFA<TAccept> ToLexer(params CharFA<TAccept>[] exprs)
{
var result = new CharFA<TAccept>();
for (var i = 0; i < exprs.Length; i++)
result.EpsilonTransitions.Add(exprs[i]);
return result;
}
/// <summary>
/// Lexes the next input from the parse context.
/// </summary>
/// <param name="context">The <see cref="ParseContext"/> to use.</param>
/// <param name="errorSymbol">The symbol to report in the case of an error</param>
/// <returns>The next symbol matched - <paramref name="context"/>
/// contains the capture and line information</returns>
public TAccept Lex(ParseContext context,TAccept errorSymbol = default(TAccept))
{
TAccept acc;
// get the initial states
var states = FillEpsilonClosure();
// prepare the parse context
context.EnsureStarted();
while (true)
{
// if no more input
if (-1 == context.Current)
{
// if we accept, return that
if (TryGetAnyAcceptSymbol(states, out acc))
return acc;
// otherwise return error
return errorSymbol;
}
// move by current character
var newStates = FillMove(states, (char)context.Current);
// we couldn't match anything
if (0 == newStates.Count)
{
// if we accept, return that
if (TryGetAnyAcceptSymbol(states, out acc))
return acc;
// otherwise error
// store the current character
context.CaptureCurrent();
// advance the input
context.Advance();
return errorSymbol;
}
// store the current character
context.CaptureCurrent();
// advance the input
context.Advance();
// iterate to our next states
states = newStates;
}
}
/// <summary>
/// Lexes the next input from the parse context.
/// </summary>
/// <param name="context">The <see cref="ParseContext"/> to use.</param>
/// <param name="errorSymbol">The symbol to report in the case of an error</param>
/// <returns>The next symbol matched - <paramref name="context"/>
/// contains the capture and line information</returns>
/// <remarks>This method will not work properly on an NFA but will not error
/// in that case, so take care to only use this with a DFA</remarks>
public TAccept LexDfa(ParseContext context, TAccept errorSymbol = default(TAccept))
{
// track our current state
var state = this;
// prepare the parse context
context.EnsureStarted();
while (true)
{
// if no more input
if (-1 == context.Current)
{
// if we accept, return that
if(state.IsAccepting)
return state.AcceptSymbol;
// otherwise return error
return errorSymbol;
}
// move by current character
var newState = state.MoveDfa((char)context.Current);
// we couldn't match anything
if (null == newState)
{
// if we accept, return that
if (state.IsAccepting)
return state.AcceptSymbol;
// otherwise error
// store the current character
context.CaptureCurrent();
// advance the input
context.Advance();
return errorSymbol;
}
// store the current character
context.CaptureCurrent();
// advance the input
context.Advance();
// iterate to our next states
state = newState;
}
}
public static int LexDfa(CharDfaEntry[] dfaTable,
ParseContext context, int errorSymbol = -1)
{
// track our current state
var state = 0;
// prepare the parse context
context.EnsureStarted();
while (true)
{
// if no more input
if (-1 == context.Current)
{
var sid = dfaTable[state].AcceptSymbolId;
// if we accept, return that
if (-1 != sid)
return sid;
// otherwise return error
return errorSymbol;
}
// move by current character
var newState = MoveDfa(dfaTable, state, (char)context.Current);
// we couldn't match anything
if (-1 == newState)
{
// if we accept, return that
if (-1 != dfaTable[state].AcceptSymbolId)
return dfaTable[state].AcceptSymbolId;
// otherwise error
// store the current character
context.CaptureCurrent();
// advance the input
context.Advance();
return errorSymbol;
}
// store the current character
context.CaptureCurrent();
// advance the input
context.Advance();
// iterate to our next states
state = newState;
}
}
}
您可以看到我们引入了一个新类，名为 `ParseContext`。此类在词法分析或匹配期间处理光标位置跟踪和捕获。它也可以用于实现手动编写的解析器，这是它的设计初衷。有关更多信息，请参阅我关于它的 Code Project 文章。`ParseContext` 可以针对 `IEnumerable
匹配功能非常相似，因此我们不会在这里介绍实现。
这里的三种方法都使用不同的机制做相同的事情。它们按照性能顺序从差到好排列。性能更好的方法需要前期准备——转换为 DFA 或 DFA 状态表，但它们性能更好。它们使用起来相当简单。每种方法的操作方式几乎相同，但词法分析 DFA 表略微复杂，因为符号被映射到 `int`，并且您使用符号表来解析它们。
// create a parse context over our test string
var pc = ParseContext.Create(test);
// while not end of input
while (-1 != pc.Current)
{
// clear the capture so that we don't keep appending the token data
pc.ClearCapture();
// lex the next token, using #ERROR as our error symbol
var acc = lexer.Lex(pc, "#ERROR");
// write the result
Console.WriteLine("{0}: {1}",acc, pc.GetCapture());
}
使用匹配来搜索字符串看起来像这样
CharFAMatch match;
var pc = ParseContext.Create(test);
while (null!=(match=word.Match(pc)))
Console.WriteLine("Found match at {0}: {1}", match.Position, match.Value);
我们只需不断调用 `Match()` 或 `MatchDfa()`，直到它返回 `null`。
如何解析实际的文本正则表达式？如果我们想从像 `(ABC|DEF)+` 这样的表达式创建一个 `CharFA
`RegexExpression.Parse()` 是我们从文本表示中获取正则表达式 DOM 的方式。它使用 递归下降解析来构建 DOM。
以下 DOM 表达式可用
- `RegexExpression`：所有其他表达式的抽象基类。
- `RegexUnaryExpression`：具有一个目标表达式的表达式的抽象基类。
- `RegexBinaryExpression`：具有左右目标表达式的表达式的抽象基类。
- `RegexCharsetExpression`：表示 `[]` 表达式。支持许多 POSIX 字符类。
- `RegexConcatExpression`：表示正则表达式连接，例如 `ABC`。
- `RegexLiteralExpression`：表示单个字面字符，例如 `A`。
- `RegexOptionalExpression`：表示 `?` 修饰符。
- `RegexOrExpression`：表示 `|` 交替。
- `RegexRepeatExpression`：表示 `*`、`+` 和 `{,}` 修饰符。
以下是 DOM 的一个简短示例
var test = "(ABC|DEF)*";
var dom = RegexExpression.Parse(test);
Console.WriteLine(dom.ToString());
var rep = dom as RegexRepeatExpression;
rep.MinOccurs = 1;
Console.WriteLine(dom.ToString());
var fa = dom.ToFA("Accept");
输出为
(ABC|DEF)*
(ABC|DEF)+
并创建了一个状态机图
现在，为了将上述内容转换为 DFA，我们需要执行幂集构造。
相关代码位于**CharFA.PowersetConstruction.cs**中
partial class CharFA<TAccept>
{
/// <summary>
/// Transforms an NFA to a DFA
/// </summary>
/// <param name="progress">The optional progress object used to report
/// the progress of the operation</param>
/// <returns>A new finite state machine equivalent to this state machine
/// but with no epsilon transitions</returns>
public CharFA<TAccept> ToDfa(IProgress<CharFAProgress> progress = null)
{
// The DFA states are keyed by the set of NFA states they represent.
var dfaMap = new Dictionary<List<CharFA<TAccept>>,
CharFA<TAccept>>(_SetComparer.Default);
var unmarked = new HashSet<CharFA<TAccept>>();
// compute the epsilon closure of the initial state in the NFA
var states = new List<CharFA<TAccept>>();
FillEpsilonClosure(states);
// create a new state to represent the current set of states. If one
// of those states is accepting, set this whole state to be accepting.
CharFA<TAccept> dfa = new CharFA<TAccept>();
var al = new List<TAccept>();
// find the accepting symbols for the current states
foreach (var fa in states)
if (fa.IsAccepting)
if (!al.Contains(fa.AcceptSymbol))
al.Add(fa.AcceptSymbol);
// here we assign the appropriate accepting symbol
int ac = al.Count;
if (1 == ac)
dfa.AcceptSymbol = al[0];
else if (1 < ac)
dfa.AcceptSymbol = al[0]; // could throw, just choose the first one
dfa.IsAccepting = 0 < ac;
CharFA<TAccept> result = dfa; // store the initial state for later,
// so we can return it.
// add it to the dfa map
dfaMap.Add(states, dfa);
dfa.Tag = new List<CharFA<TAccept>>(states);
// add it to the unmarked states, signalling that we still have work to do.
unmarked.Add(dfa);
bool done = false;
var j = 0;
while (!done)
{
// report our progress
if (null != progress)
progress.Report(new CharFAProgress(CharFAStatus.DfaTransform, j));
done = true;
// a new hashset used to hold our current key states
var mapKeys = new HashSet<List<CharFA<TAccept>>>(dfaMap.Keys, _SetComparer.Default);
foreach (var mapKey in mapKeys)
{
dfa = dfaMap[mapKey];
if (unmarked.Contains(dfa))
{
// when we get here, mapKey represents the epsilon closure of our
// current dfa state, which is indicated by kvp.Value
// build the transition list for the new state by combining the transitions
// from each of the old states
// retrieve every possible input for these states
var inputs = new HashSet<char>();
foreach (var state in mapKey)
{
var dtrns = state.InputTransitions as
IDictionary<CharFA<TAccept>, ICollection<char>>;
foreach (var trns in dtrns)
foreach (var inp in trns.Value)
inputs.Add(inp);
}
// for each input, create a new transition
foreach (var input in inputs)
{
var acc = new List<TAccept>();
var ns = new List<CharFA<TAccept>>();
foreach (var state in mapKey)
{
CharFA<TAccept> dst = null;
if (state.InputTransitions.TryGetValue(input, out dst))
{
foreach (var d in dst.FillEpsilonClosure())
{
// add the accepting symbols
if (d.IsAccepting)
if (!acc.Contains(d.AcceptSymbol))
acc.Add(d.AcceptSymbol);
if (!ns.Contains(d))
ns.Add(d);
}
}
}
CharFA<TAccept> ndfa;
if (!dfaMap.TryGetValue(ns, out ndfa))
{
ac = acc.Count;
ndfa = new CharFA<TAccept>(0 < ac);
// assign the appropriate accepting symbol
if (1 == ac)
ndfa.AcceptSymbol = acc[0];
else if (1 < ac)
ndfa.AcceptSymbol = acc[0]; // could throw, instead just set it
// to the first state's accept
dfaMap.Add(ns, ndfa);
// work on this new state
unmarked.Add(ndfa);
ndfa.Tag = new List<CharFA<TAccept>>(ns);
done = false;
}
dfa.InputTransitions.Add(input, ndfa);
}
// we're done with this state
unmarked.Remove(dfa);
}
}
++j;
}
return result;
}
}
哦，那真丑。可悲的事实是，我很久以前在我的正则表达式引擎的一个早期版本中花了很长时间才让它工作。它随着时间的推移而发展。我只是模模糊糊地理解其中涉及的数学，所以我没有尝试从头开始重写它，尽管它可能需要这样做。好消息是，它有效。使用 `ToDfa()` 很简单，但进度参数需要一些解释。它遵循 Microsoft 用于长时间运行任务的 `IProgress
我们有一个相关的机制可以在**CharFA.DfaStateTable.cs**中生成 DFA 状态表。它包含 `ToDfaStateTable()`，该方法接受一个可选（但推荐）符号表，该符号表只是一个 `TAccept` 数组。它将它们映射到 ID，使得 ID 是 `TAccept` 符号在数组中的索引。由于基于表的 DFA 只使用整数，因此此表用于将它们映射回符号。创建的表可以传递给静态 `XXXXDfa()` 方法。
我们的引擎现在功能完备，除了代码生成，所以这是我们接下来要介绍的。让我们访问**CharFA.CodeGeneration.cs**
此代码支持两种主要的代码生成样式：它可以简单地将 DFA 表和符号表序列化为代码（表驱动），也可以实际使用 goto 生成可编译的状态机代码。通常，建议使用表驱动方法，因为除非状态机很大，否则它们的速度大致相同，在这种情况下，表驱动形式会超越编译形式。编译形式主要出于好奇和说明目的。请记住，无论哪种方式，发布版本都会快得多。
表驱动数组的序列化通过 `GenerateSymbolTableInitializer()` 和 `GenerateDfaStateTableInitializer()` 执行。每个方法都返回一个 Code DOM 表达式，可用于初始化字段或变量。
通常，您会使用 Code DOM 构建一个类，然后对于每个生成的正则表达式或词法分析器，您将在该类上序列化一个或两个只读静态成员字段：如果使用词法分析器，则为符号表，在任何情况下都为 DFA 状态表。然后，您可以在运行时使用这些字段，就像使用普通的运行时 DFA 状态表一样，根据需要将它们传递给 `LexDfa()` 或 `MatchDfa()`。使用词法分析器时，您将使用符号表来解析接受符号，如下所示
pc = ParseContext.Create(test);
while (-1 != pc.Current)
{
pc.ClearCapture();
var acc = CharFA<string>.LexDfa(GeneratedLexDfaTable, pc, 3);
// when we write this, we map our symbol id back to the
// symbol using our symbol table.
Console.WriteLine("{0}: {1}", GeneratedLexSymbols[acc], pc.GetCapture());
}
这是最简单的代码生成选项，最适合通用用途。
另一种生成代码的方式是通过 `GenerateMatchMethod()` 和 `GenerateLexMethod()` 方法，它们使用 goto 生成可编译的代码。这些方法不需要 DFA 表，但您需要将符号表与词法分析方法一起使用，因此请使用上述方法生成符号表。在使用它们之前，您必须适当地命名方法并设置访问修饰符。
通常，如前所述，您将使用 Code DOM 构建一个类，然后对于每个生成的正则表达式或词法分析器，您将使用上述方法在该类上创建一个静态方法（以及词法分析器关联的符号表字段）。通常，您将生成词法分析和匹配方法，以及每个表达式一个符号表字段。为了获得完整的正则表达式功能，总共有三个成员。如果您不需要词法分析，可以省略它，或者与匹配类似。明确地说，如果您只需要匹配，那么每个表达式将只有一个静态方法。如果您只需要词法分析，那么每个表达式将有一个静态方法和一个静态只读字段。如果您需要词法分析和匹配，那么每个表达式将有两个方法和一个字段，总共有三个成员。
请谨慎使用此功能，因为编译方法可能会很快变得庞大。源中的数组也会变得很大，但大部分是空白。另请记住，由于静态字段初始化程序，表驱动版本在启动时会有轻微开销，因此如果您有大量此类内容，您的应用程序在启动时可能会稍微停顿。无论您如何操作，这仍然比在运行时构建状态机快得多。
让我们通过重新审视我们的 DFA 词法分析器图（这次没有额外的杂乱）来探讨编译版本
请记住这张图。现在让我们看看它的默认生成代码
internal static int Lex(RE.ParseContext context)
{
context.EnsureStarted();
// q0
if (((context.Current >= '0')
&& (context.Current <= '9')))
{
context.CaptureCurrent();
context.Advance();
goto q1;
}
if ((((context.Current >= 'A')
&& (context.Current <= 'Z'))
|| ((context.Current >= 'a')
&& (context.Current <= 'z'))))
{
context.CaptureCurrent();
context.Advance();
goto q2;
}
if (((((context.Current == '\t')
|| ((context.Current >= '\n')
&& (context.Current <= ' ')))
|| (context.Current == '\r'))
|| (context.Current == ' ')))
{
context.CaptureCurrent();
context.Advance();
goto q3;
}
goto error;
q1:
if (((context.Current >= '0')
&& (context.Current <= '9')))
{
context.CaptureCurrent();
context.Advance();
goto q1;
}
return 0;
q2:
if ((((context.Current >= 'A')
&& (context.Current <= 'Z'))
|| ((context.Current >= 'a')
&& (context.Current <= 'z'))))
{
context.CaptureCurrent();
context.Advance();
goto q2;
}
return 1;
q3:
if (((((context.Current == '\t')
|| ((context.Current >= '\n')
&& (context.Current <= ' ')))
|| (context.Current == '\r'))
|| (context.Current == ' ')))
{
context.CaptureCurrent();
context.Advance();
goto q3;
}
return 2;
error:
context.CaptureCurrent();
context.Advance();
return 3;
}
如果您将之前的图表与上面的代码进行比较，您会发现它们是如何对应的：每个状态都由图中的一个标签表示——除了第一个状态，它由一个注释表示，因为它从未被跳转到。同时，每个转换范围都由 `if` 语句中的相关条件表示。每个可能的目的状态都有一个 `if`。`CaptureCurrent()` 只是存储光标处的字符，而 `Advance()` 只是将光标向前移动一个字符。每个返回的接受符号 ID 都是硬编码的。错误条件知道返回 `3` 是因为我们将其传递给了生成方法。除此之外，代码非常简单。
通常，您会希望在使用它之前更改方法的名称，可能还会更改访问修饰符。以上只是默认值。
表生成方法没有那么有趣，因为它们只是生成数组初始化表达式。我们不会在这里介绍生成的代码，但附带的演示项目会介绍。这两个表生成方法使用 `_Serialize()`，它递归地创建 Code DOM 表达式以实例化实例或数组中的值。为了使 `CharDfaEntry` 和 `CharDfaTransitionEntry` 序列化，我们使用 Microsoft 的组件模型类型描述符框架，并在**CharDfaEntry.cs**中有两个自定义类型转换器，它们告诉我们的代码如何序列化各自的类型。它使用 `InstanceDescriptor`，这有点神秘，但请参阅这篇文章了解其工作原理的详细信息。
通常，您会使用 Code DOM 创建一个类，然后将您生成的方法或字段添加到其中
下面展示了生成编译和表驱动词法分析代码的过程
// create the symbol table (include the error symbol at index/id 3)
var symbolTable = new string[] { "Digits", "Word", "Whitespace", "#ERROR" };
// create the DFA table we'll use to generate code
var dfaTable = lexer.ToDfaStateTable(symbolTable);
// create our new class - in production we'd change the name
// to something more appropriate
var compClass = new CodeTypeDeclaration("RegexGenerated");
compClass.TypeAttributes = System.Reflection.TypeAttributes.Class;
compClass.Attributes = MemberAttributes.Final | MemberAttributes.Static;
// add the symbol table field - in production we'll change the name
var symtblField = new CodeMemberField(typeof(string[]), "LexSymbols");
symtblField.Attributes = MemberAttributes.Static | MemberAttributes.Public;
// generate the symbol table init code
symtblField.InitExpression = CharFA<string>.GenerateSymbolTableInitializer(symbolTable);
compClass.Members.Add(symtblField);
// Generate and add the compiled lex method code
compClass.Members.Add(CharFA<string>.GenerateLexMethod(dfaTable, 3));
// in production we'd change the name of the returned method
// above
// add the DFA table field - in production we'd change the name
var dfatblField = new CodeMemberField(typeof(CharDfaEntry[]), "LexDfaTable");
dfatblField.Attributes = MemberAttributes.Static | MemberAttributes.Public;
// generate the DFA state table init code
dfatblField.InitExpression = CharFA<string>.GenerateDfaStateTableInitializer(dfaTable);
compClass.Members.Add(dfatblField);
// create the C# provider and generate the code
// we'll usually want to put this in a namespace
// but we haven't here
var prov = CodeDomProvider.CreateProvider("cs");
prov.GenerateCodeFromType(compClass, Console.Out, new CodeGeneratorOptions());
您需要在每个表达式的这个类上重复此操作。我建议为每个表达式使用一个部分类，因为源代码已经很长。该机制类似，但生成匹配方法稍微容易一些，因为它们不需要符号表字段。
使用编译的 `Lex()` 方法与使用 `LexDfa()` 的 DFA 状态表版本完全相同，只是更简单。您不必传递 DFA 状态表或错误符号，因为这些已经“内置”到方法中并是常量。您仍然必须使用符号表将符号 ID 映射回其符号。这是出于解析器性能方面的原因，解析器倾向于在内部将符号作为 `int` ID 处理。
使用 `GenerateMatchMethod()` 生成编译匹配方法基本相同，只是不需要错误符号 ID。使用编译匹配方法与使用静态 `MatchDfa()` 方法相同，只是您不传递 DFA 状态表。有关如何进行匹配的代码，请参阅上面的代码。您也无需生成符号表。
我们现在功能齐全。其余代码文件要么是支持文件，要么是锦上添花。这应该为您构建自己的正则表达式引擎或修改此引擎提供坚实的基础。希望您喜欢这段旅程。
历史
- 2019 年 11 月 20 日 – 初次提交