65.9K
CodeProject 正在变化。 阅读更多。
Home

Pck/FA: C# 中的正则表达式和有限状态机引擎

honey the codewitch
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.33/5 (9投票s)

2019 年 8 月 4 日

公共领域

11分钟阅读

viewsIcon

12486

downloadIcon

188

PCK 的一部分的正则表达式和有限状态引擎

引言

Parser Construction Kit (PCK) 是一个大型项目，包含许多不同的组件。与其一次性探索所有源代码，不如我们分区域进行。这些区域中的每一个都独具价值，但它们都为 PCK 的功能做出了贡献。

此组件是有限自动机引擎 FA。简而言之，它是一个正则表达式和标记库。然而，它还具有一些独特的功能，例如能够将正则表达式表示为抽象语法树，提供一个 DOM，这使得它有可能表示许多不同风格的 DFA 正则表达式。

我们不能使用 .NET 的正则表达式引擎进行高效的词法分析。它并非为此而设计，并存在一些缺点，包括回溯，这对于高效的解析器来说是不可接受的。Pck/FA 包括一个简单的、基于 DFA 的正则表达式引擎，以及一个更通用的有限状态机引擎。您可以将通用 FA 用于诸如计算 LR 解析器中的状态或驱动具有复杂协调路径的工作流引擎等任务。

与我之前的正则表达式引擎不同，这个引擎不生成任何代码。它实际上不需要。它只是渲染一个状态机表的数组，您可以将其传递给像我 此处提供的那样的 CodeDOM 序列化器，然后它将以任何兼容的语言渲染它。

背景

正则表达式是愚蠢的。它们对输入一无所知，它们有一个非常简单的语法，并且您能执行的操作并不多。

正则表达式是短视的。在词法分析过程中，它们几乎是盲目的——在任何时候只知道自己处于什么状态以及下一个字符是什么。

正则表达式是优雅的。它们只做它们需要做的事情，不多也不少。一个字符只被检查一次，语言简洁，并且表达能力与其简单性不符。

我们将利用其愚蠢和短视的部分来保持代码的简单性。愚蠢是好的。愚蠢易于测试。愚蠢易于编码。如果能做到，短视会非常高效。

我不想进行正则表达式教程，所以我让我的引擎变得 POSIX 风格。它还没有支持 POSIX 命名字符类（尽管它能识别它们），也没有支持一些转义字符类（如单词边界）、序数和等价类，但它已经很接近了，在大多数实际情况中几乎可以互换。如果它不能与 POSIX 表达式一起使用，请视为错误。

如果您需要正则表达式教程，请 在此处查看。

正则表达式解析为枚举器的跳转表。基本上，它就像这样

q1:
    if((pc.Current>='0'&& pc.Current<='9')||
        (pc.Current>='A'&& pc.Current<='Z')||
        (pc.Current=='_')||
        (pc.Current>='a'&& pc.Current<='z')) {
        sb.Append((char)pc.Current);
        pc.Advance();
        goto q1;
    }
    return new System.Collections.Generic.KeyValuePair
                    <System.String,string>("id",sb.ToString());

至少如果我们生成代码的话。那是状态 1，在遇到字母、数字或下划线时会转换到自身，否则就会接受。实际上，我们并不真正进行那种代码生成，因为基于数组的表在 .NET 中更快，但它足够简单。

不过，将正则表达式的状态机视为有向图比代码更容易

这是一个用于匹配 C# 风格标识符 [A-Z_a-z][0-9A-Z_a-z]* 的正则表达式的状态图。

[A-Z_a-z][0-9A-Z_a-z]*

我们上面看到了状态 q1 的“生成的代码”。仔细研究代码和图，您应该能看到它们是如何结合在一起的。这是一个非常简单的图。更复杂的图也很简单，只需创建一个更复杂的正则表达式即可。

现在您应该能看到图是如何解析为跳转表的。真正的诀窍是让表达式解析为一个图。这并不简单，但一旦您知道如何做，它比听起来容易。

让我们退一步，因为上面的图并不是全部。我们还没有向您展示的是，我们是从另一个图构建出它的！

[A-Z_a-z][0-9A-Z_a-z]* (NFA)

绿色状态仅代表起始状态。我们现在不关心它。至于图的其余部分，它有更多的状态，以及奇怪的虚线灰色线。让我们来谈谈。

传统上，在沿着黑线移动之前，我们必须等待单个输入，然后消耗该输入并沿着线向箭头方向移动。

对于名为“epsilon 转换”的灰色虚线，我们不必等待任何输入。我们只是移动，这意味着我们可能会同时处于多个状态，因为我们会沿着从当前位置看到的每条虚线灰色路径移动。

如果您聪明且精力充沛，您可能会问的第一个问题是“我们如何才能从上面的代码生成中实现这一点？”——这是一个很棒的问题。

答案是我们不这样做。像这样的图有一个数学属性：其中每一个都有一个等效的、没有虚线的图——通过等效，我的意思是它匹配相同的输入。所以对于您可以想象的每一个这样的图，都存在一个具有相同效果的、没有虚线的对应图。

我们所要做的就是找到它。我们使用一种称为幂集构造的技术来做到这一点。数学有点奇怪，但 fagui 应用程序在一定程度上可以可视化它。应用程序顶部面板上的图是未转换的 FA——我们称之为 NFA。底部面板上的图是没有虚线的等效图，我们称之为 DFA。

fagui

您可以看到底部状态包含顶部所有状态的列表，它们代表的。通常，底部的一个状态（DFA）会代表顶部（NFA）的多个状态。事实上，这就是幂集构造的工作原理。它检查图的所有可能性并创建新的状态来表示这些可能性。幸运的是，ToDfa() 函数处理了繁琐的细节。

您会注意到 Q1 在底部状态列表中的状态 q4 缺失了。当删除重复状态（通过 TrimDuplicates()）时，它被删除了。之所以被删除，是因为它会导致生成的 DFA 中出现重复，但上面没有显示该步骤，而且它并不关键——重复的状态不会破坏这些机器，它们只是冗余的。

现在，我已经告诉您关于这个神奇的图转换，但我还没有讲到我们是如何得到带有虚线的图的——从现在开始，就称之为 NFA。这些是通过 Thompson 的构造算法组合而成的，该算法定义了一些基本的图构造，您可以将它们组合起来创建复合图。Thompson 的算法基本上要求每个构造都有一个“接受”状态。也就是说，一个带有双圆圈的状态，如上所示。

首先，展示一个状态的基本数据结构可能会有所帮助

class CharFA {
  public IDictionary<char,CharFA> Transitions {get;}=new Dictionary<char,CharFA>();
  public ICollection<CharFA> EpsilonTransitions {get;}=new List<CharFA>();
  public bool IsAccepting {get;set;}=false;
  public string AcceptSymbol {get; set;}=null;
}

每个转换都由单个输入字符键控，并导向另一个 CharFA 实例。每个 epsilon 转换（虚线）仅通过集合中目标状态的存在来表示。

如果 IsAccepting 为 true，则状态在图中是双圆圈，并且此时捕获的输入被认为是有效的，即使它无法进一步匹配。AcceptSymbol 对于演示目的并非绝对必需，它只是给我们一个标记接受的标签。现在我们可以忽略它。

Transitions 属性与每个状态的跳转表完全对应。EpsilonTransitions 也“虚拟地”并发跳转，但我们最终希望从图中删除所有这些，因为在代码中渲染它们将是一种特殊的噩梦。

让我们在代码中手动构建一组状态来表示简单的表达式“foo”的图。确保已安装 Graphviz，在 .NET Core 中打开一个新控制台应用并在 VS 中启动——添加对 pck.fa 的引用，然后尝试这样做

using CharFA = Pck.CharFA<string>;
class Program
{
    static void Main(string[] args)
    {
        var foo = new CharFA();
        var foo2 = new CharFA();
        var foo3 = new CharFA();
        var foo4 = new CharFA();
        foo.Transitions.Add('f', foo2);
        foo2.Transitions.Add('o', foo3);
        foo3.Transitions.Add('o', foo4);
        foo4.IsAccepting = true;
        // write a pretty picture!
        foo.RenderToFile(@"..\..\..\foo.jpg");
        return;
    }        
}

这将在项目目录中输出 foo.jpg。

foo

现在，让我们稍微修改代码（和图），使其接受任意数量的尾随“o”s。

...
foo.Transitions.Add('f', foo2);
foo2.Transitions.Add('o', foo3);
foo3.Transitions.Add('o', foo4);
foo4.IsAccepting = true;
foo4.EpsilonTransitions.Add(foo3); // <-- add this line
foo.RenderToFile(@"..\..\..\foo.jpg");
...

现在 foo 看起来像这样

foo+

现在，让我们再次修改代码，使我们的表达式接受一个空 string。

...
 foo.Transitions.Add('f', foo2);
 foo2.Transitions.Add('o', foo3);
 foo3.Transitions.Add('o', foo4);
 foo4.IsAccepting = true;
 foo4.EpsilonTransitions.Add(foo3); // (from before)
 foo.EpsilonTransitions.Add(foo4); // <-- now add this line
 foo.RenderToFile(@"..\..\..\foo.jpg");
...

(foo)?o*

您看到了吗？这就是我们的状态图最终构建的方式。但不要像这样手动操作。使用 static 方法，如 Literal()、Set()、Or()、Repeat()、Concat() 和 Optional()。

或者，您可以使用 RegexExpression DOM，但这有点大材小用，除非您正在解析。

最后一点：让我们将该图转换为其更高效的 DFA 对等项，使用 ToDfa()。

using CharFA = Pck.CharFA<string>;
class Program
{
    static void Main(string[] args)
    {
        var foo = new CharFA();
        var foo2 = new CharFA();
        var foo3 = new CharFA();
        var foo4 = new CharFA();
        foo.Transitions.Add('f', foo2);
        foo2.Transitions.Add('o', foo3);
        foo3.Transitions.Add('o', foo4);
        foo4.IsAccepting = true;
        foo4.EpsilonTransitions.Add(foo3);
        foo.EpsilonTransitions.Add(foo4);
        foo = foo.ToDfa(); // added this line
        foo.RenderToFile(@"..\..\..\foo.jpg");
        return;
    }        
}

(foo)?o*

如果您仔细跟踪每个图的线条，您会发现它们是等效的。

Using the Code

此代码将正则表达式转换为上述形式的有向图。然后它可以将图转换为基于数组的转换表。它可以使用 Graphviz 渲染图，或生成这些数组供外部代码使用。

此库中有两个主要的状态机类：FA<TInput,TAccept>，以及 FA<char,TAccept> 的“特例”，称为 CharFA<TAccept>。

后者是一个完整的正则表达式引擎，并针对字符进行了显著优化，而前者允许您使用除 char 之外的输入类型。

CharFA<TAccept> 类代表图中的单个状态，每个状态都提供了一个丰富的 API 来查询它所属的图（包括 FillClosure()、FillAccepting() 和 FillReferencesTo() 等），将其渲染为多种格式之一（使用 RenderToFile() 和 RenderToStream() 需要 Graphviz），进行转换（ToDfa()、ClonePathTo()、ClonePathToAny()），以各种方式操作或构建图（使用 Literal()、Set()、Concat()、Or()、Optional() 和 Repeat()），并将图转换为状态表（使用 ToArray()）。

FA<TInput,TAccept> 类包含不专门针对字符、正则表达式和范围匹配的 API 子集。

还有一个 Lex() 方法，但它主要用于调试或在运行中检查状态机。词法分析器代码通常因应用程序而异，虽然此方法有效，但它返回的信息不足（如行号和位置）以适用于大多数实际情况。代码生成由使用此库的外部工具处理。

在我之前的 正则表达式提交中，代码生成和运行时词法分析例程包含在主类中。在此分发中，它们位于一个单独的项目中。原因是，我发现实际上每个词法分析器都足够不同，以至于需要其自身的特定词法分析例程，它是标准的一种变体。所以，主 FA 类只是生成 DFA 表作为数组。由消耗数组的任何人决定如何使用它，例如生成代码或扫描文档。我还提供了 pckw 项目中的 fagen，它将从这些数组生成标记器代码。

此代码还为给定的正则表达式提供了抽象语法树或 AST。因此，您可以将正则表达式解析到树中，然后检查构成表达式的各个组件，如或、连接和重复。您有可能使用该树来渲染为不同的正则表达式格式，就像 CodeDOM 为代码所做的那样。事实上，这是 CodeDOM 提供的 AST 的模拟，但用于处理正则表达式。例如，而不是 CodeExpression 和 CodeUnaryExpression，您有 RegexExpression 和 RegexUnaryExpression。您可以使用 RegexExpression 的 Parse() 方法从 string 获取正则表达式 AST，并可以使用 ToFA<TAccept>() 方法从该字符串获取 CharFA<TAccept> 实例。请参阅 fagui 应用程序项目，了解实际如何执行此操作的代码，但只需两行。您还可以修改这些树，然后调用 ToString() 以获得可解析的 regex。

var ast = RegexExpression.Parse(RegexTextBox.Text);
var fa = ast.ToFA("Accept");

最后，还有一个我们尚未完全介绍的广泛 API 领域，那就是 LexDocument API。此 API 暴露了又一个文档对象模型，这次是针对 PCK 规范文件。这些文件非常类似于 flex/lex 规范文件（“*.l”扩展名），可用于创建扫描输入的标记器/词法分析器。

这些文件也可以包含语法规则，但它们被 LexDocument API 忽略——语法规则是为了被解析器生成器而不是词法分析器生成器读取的。文档中的这两种格式可以混合使用，但此 API 只会拾取词法分析器规则和属性。PCK 文件本身几乎总是从另一种格式（通常是 XBNF）机器生成的，但这将是另一篇文章的主题。

格式是基于行的，其中一个词法分析器规则是

MyRuleName= 'myregex'

我们将在未来介绍属性。它们在这里不直接相关，但被各种工具用来更改代码生成或特殊行为等方面。

历史

  • 2019 年 8 月 3 日 - 初始提交
© . All rights reserved.