Visual FA 第二部分：使用 Visual FA 分析自动机和处理文本
5.00/5 (2投票s)
继续 Visual FA 系列，现在我们探索 API 基础
引言
既然您已阅读第一部分，您应该准备好更详细地研究 Visual FA API。
本文旨在带您了解 Visual FA 广泛 API 的运作原理，从基本匹配到生成和编译您自己的匹配器代码。
更新：截至 2024 年 1 月 18 日的错误修复。请重新下载，因为当存在多个接受状态时，`FA.Optional()` 中存在一个错误。
文章列表
必备组件
- 您需要一份最新的 Visual Studio
- 您需要安装 Graphviz 并将其添加到 PATH 中。
- 您需要接受以下事实：此项目的根文件夹中包含几个必要的执行文件（deslang.exe 和 csbrick.exe），它们用于构建。您可以在 CodeProject 中搜索它们，这里有关于它们的文章，GitHub 上也有它们的代码——请参阅此解决方案中的 README.md 获取链接。它们无害且必要。如果没有在构建过程中进行一些巧妙的操作，此解决方案无法完成一半的巧妙工作。
注意：此解决方案虽然完全可用，但仍在进行大量开发，并将定期在 GitHub 上更新。下载时请记住这一点。
快速入门
让我们从计算文本文件中的单词开始。
// Reference VisualFA
using System;
using System.IO;
using VisualFA;
/* create a state machine to match a word */
FA word = FA.Parse("[A-Za-z]+");
// let's ensure fastest possible matching
// by converting the state machine to the
// most efficient form
word = word.ToMinimizedDfa();
using(StreamReader reader = new StreamReader("myfile.txt")) {
int count = 0;
// Run() returns an FARunner that can be used
// with foreach to get all the text in the document
foreach(FAMatch match in word.Run(reader)) {
// a runner returns all text.
// if you only want matching portions
// check IsSuccess
if(match.IsSuccess) {
++count;
}
}
Console.WriteLine("Found {0} words in document.",count);
}
现在，稍微复杂一点，让我们计算我们自己的源文件中的块注释。这需要使用“块结束”功能，该功能可以通过惰性匹配模拟来匹配多字符结束条件。我们在上一篇文章中已经讨论过它，但让我们在这里实际操作一下
// Reference VisualFA
using System;
using System.IO;
using VisualFA;
/* create a state machine to match a comment block */
// "/*" accept of 0
FA commentBlock = FA.Parse(@"\/\*",0).ToMinimizedDfa();
// "*/"
FA commentBlockEnd = FA.Parse(@"\*\/").ToMinimizedDfa();
using(StreamReader reader = new StreamReader(@"..\..\..\Program.cs")) {
int count = 0;
// here we feed Run() our block end array as well
// it contains just one item - our comment block end
// note that the index of the block end must be the
// same as the accept symbol the block end is associated
// with
foreach(FAMatch match in
commentBlock.Run(reader,new FA[] {commentBlockEnd})) {
if(match.IsSuccess) {
++count;
}
}
Console.WriteLine("Found {0} comment blocks in source code.",count);
}
词法分析或文本标记化
除了性能方面的一些优势外，如果您只做诸如计数单词和块注释之类的事情，那么使用 Visual FA 而非 Microsoft 的引擎并没有太多理由。Visual FA 真正与众不同之处在于其“词法分析”能力。如前所述，Visual FA 返回所有文本。在词法分析时，这是您想要的，因为词法分析器通常旨在识别它们正在词法分析的文档中的所有构造。如果它们没有，则通常存在某种语法错误。
基本上，当您进行词法分析时，您会忽略 `FAMatch` 的 `IsSuccess` 属性。相反，您的主要信息是 `SymbolId` 字段，其中包含匹配文本的接受符号，如果出错则为 `-1`。
词法分析设置起来有点复杂，因为与普通正则表达式不同，没有正则表达式语法来描述词法分析器。因此，您不能简单地调用 `Parse()` 并返回一个词法分析器。相反，词法分析器是（通常是）`Parse()`d 表达式的集合，其中每个表达式都有自己的接受符号。
using VisualFA;
FA commentBlock = FA.Parse(@"\/\*", 0);
FA commentBlockEnd = FA.Parse(@"\*\/");
FA commentLine = FA.Parse(@"\/\/[^\n]*", 1);
FA wspace = FA.Parse("[ \\t\\r\\n]+", 2);
FA ident = FA.Parse("[A-Za-z_][A-Za-z0-9_]*", 3);
FA intNum = FA.Parse("0|\\-?[1-9][0-9]*", 4);
FA realNum = FA.Parse("0|\\-?[1-9][0-9]*(\\.[0-9]+([Ee]\\-?[1-9][0-9]*)?)?", 5);
FA op = FA.Parse(@"[\-\+\*\/\=]",6);
FA[] tokens = new FA[] {
commentBlock,
commentLine,
wspace,
ident,
intNum,
realNum,
op
};
// our tokens will be minimized by ToLexer
// we must minimize our block ends ourselves.
FA[] blockEnds = new FA[] {
commentBlockEnd.ToMinimizedDfa()
};
// ToLexer will minimize its tokens and create
// a DFA lexer by default
FA lexer = FA.ToLexer(tokens);
// NOTE: never call ToMinimizedDfa() on a lexer machine
// as it will lose its distinct accept states
// ToDfa() is okay, and ToMinimizedDfa() is
// usually okay on states other than the root.
// ToLexer() will create a valid optimized lexer so
// there is no need.
string tolex = "/* example lex */" + Environment.NewLine +
"var a = 2 + 2" + Environment.NewLine +
"print a";
foreach(FAMatch token in lexer.Run(tolex,blockEnds)) {
Console.WriteLine("{0}:{1} at position {2}",token.SymbolId,token.Value,token.Position);
}
更高级的用例
LexGen 工具
老实说，考虑到您可以为运行器生成代码，通常很少有理由不这样做，尤其是在词法分析用例方面。设置起来的运行时开销更小，无需编写样板代码来构建词法分析器，并且可能不依赖 VisualFA。有什么不喜欢的呢？
事实上，这个用例如此重要，以至于我为这个解决方案提供了两个项目，以方便做到这一点：`LexGen` 和 `LexGen.DNF`。
每个项目都代表相同的命令行可执行文件，只是后者针对 .NET Framework，因此不支持 Core 或 Standard 中使用的 .NET spans，而 Visual FA 可以在其生成的代码中使用这些 spans 以获得更好的性能。DNF 可执行文件的一个优点是它是自包含的，而不是需要一个 EXE、一个 DLL 和一个 .json 文件随身携带。当您必须针对 .NET Framework 遗留代码时，它也很好用。
这是使用屏幕
Usage: LexGen <inputfile> [/output <outputfile>] [/class <codeclass>] [/nospans]
[/namespace <codenamespace>] [/language <codelanguage>] [/tables]
[/textreader] [/ignorecase] [/noshared] [/runtime] [/ifstale]
[/nfagraph <nfafile>] [/dfagraph <dfafile>] [/vertical] [/dpi <dpi>]
LexGen generates a lexer/scanner/tokenizer in the target .NET language
<inputfile> The input lexer specification
<outputfile> The output source file - defaults to STDOUT
<codeclass> The name of the main class to generate - default derived from <outputfile>
<nospans> Do not use the Span feature of .NET
<codenamespace> The namespace to generate the code under - defaults to none
<codelanguage> The .NET language to generate the code in - default derived from <outputfile>
<tables> Generate lexers based on DFA tables - defaults to compiled
<textreader> Generate lexers that stream off of TextReaders instead of strings
<ignorecase> Create a case insensitive lexer - defaults to case sensitive
<noshared> Do not generate the shared code as part of the output - defaults to generating the shared code
<runtime> Reference the Visual FA runtime - defaults to generating the shared code
<ifstale> Only generate if the input is newer than the output
<staticprogress> Do not use dynamic console features for progress indicators
<nfafile> Write the NFA lexer graph to the specified image file.*
<dfafile> Write the DFA lexer graph to the specified image file.*
<vertical> Produce the graph(s) in vertical layout.*
<dpi> The DPI of any outputted graphs - defaults to 300.*
* Requires GraphViz to be installed and in the PATH
<inputfile> 为 Rolex 词法分析器规范格式
它是一种基于行的格式，每行类似于以下内容
ident<id=1,ignoreCase>= '[A-Z_][0-9A-Z_]*'
或更一般地说
identifier [ "<" attributes ">" ] "=" ( "'" regexp "'" | "\"" literal "\"" )
每个属性都是一个标识符，后跟可选的 `=` 和 JSON 风格的字符串、布尔值、整数或其他值。如果未指定值，则为 `true`，这意味着上面的 `ignoreCase` 设置为 `true`。请注意字面表达式如何用双引号括起来，正则表达式如何用单引号括起来。
有一些可用的属性，如下所示
id- 表示与此符号关联的非负整数 IDignoreCase- 表示表达式应被解释为不区分大小写blockEnd- 表示指定符号的多字符结束条件。当遇到时，词法分析器将继续读取，直到找到并消耗 `blockEnd` 值。这对于具有多个字符结束条件的表达式非常有用，例如 C 语言块注释、HTML/SGML 注释和 XML CDATA 节。这可以是一个正则表达式（单引号）或一个字面量（双引号）。
规则在匹配方面可能有些模糊。如果模糊，则规范中的第一条规则是匹配的规则，从而产生一组按 ID（最低优先）和按“文档顺序”优先的规则。
正则表达式语言支持基本的非回溯构造和常见的字符类，以及 `[:IsLetter:]`/`[:IsLetterOrDigit:]`/`[:IsWhiteSpace:]`/等，它们映射到其 .NET 对应项。请务必转义单引号，因为它们在词法分析器规范中用于分隔表达式。
如果指定了 `/output
如果指定了 `/class
/nospans 强制生成的匹配器在匹配器代码内部使用 `System.String` 而不是 `System.ReadOnlySpan
如果指定了 `/namespace
如果指定了 `/language
/tables 表示应生成基于表的运行器。编译的匹配器通常运行速度稍快，尽管有时根据机器的不同情况会相反，但基于表的匹配器生成的二进制文件大小要小得多，尤其是在同一个项目中包含多个词法分析器时（通过多次使用 `LexGen` 并带有 `/noshared`），因为实际的匹配器代码可以在它们之间共享。
/textreader 指定生成的运行器应该基于 `TextReader` 而不是 `string` 进行操作。对于以文件而不是字符串为主要业务的词法分析器来说，这通常更有意义。然而，由于 `TextReader` 的工作方式，基于 `TextReader` 运行本身效率略低于基于 `string` 运行。换句话说，如果您不指定此选项，您的词法分析器必须基于内存中的字符串进行操作，但会比替代方案更快。如果您指定此选项，您会损失一点性能，但获得从文件流式传输的能力。
/ignorecase 会改变默认行为。如果您指定此项，则除非通过 `ignoreCase=false` 属性另行指定，否则词法分析器规范文件中的所有规则都将不区分大小写。通常情况正好相反。
/noshared 和 /runtime 应结合考虑。
这里有几种可能性
- 未指定任何选项，在这种情况下，将生成共享代码，并且不需要依赖 Visual FA。事实上，它不能依赖 Visual FA，因为如果引用该项目将出现命名冲突。
- 仅指定了
/runtime。在这种情况下，不会生成共享代码，所有生成的代码都依赖于 Visual FA 运行时在您的项目中被引用。 - 同时指定
/runtime和/noshared，结果与第 2 条相同。 - 只指定了
/noshared，在这种情况下，将不生成对 Visual FA 的依赖，但也不会生成共享代码。除非之前的 LexGen 运行未指定/noshared或/runtime，否则这将产生无效输出。基本上，原因如下：如果您想在项目中创建多个词法分析器，并且不想依赖 Visual FA 运行时，您可以使用不带/noshared或/runtime的 LexGen 运行一次。之后，在与第一个相同的<codenamespace>下生成所有后续词法分析器，并指定/noshared，这将使它们使用第一次运行中生成的共享代码。
/ifstale 告诉工具跳过生成，除非输入文件比指定的 `/output
/staticprogress 是另一个在使用 LexGen 作为构建工具时很有用的选项。默认情况下，进度指示通过动态进度条输出到控制台。这与 Visual Studio 构建输出窗口中的模拟控制台不兼容。如果您使用 `/staticprogress`，则进度条将被替换为点。这只是美观上的改变，但可以防止一个烦人的问题。
其余选项都与生成词法分析器图有关，这些选项要求安装 Graphviz 并将其添加到 PATH 中。
/nfagraph <nfafile> 将词法分析器的 NFA 形式图渲染到指定输出文件 - 通常是 jpg、png、svg 或类似格式。
/dfagraph <dfafile> 将词法分析器的 DFA 形式图渲染到指定输出文件 - 通常是 jpg、png、svg 或类似格式。
/vertical 将图从上到下渲染，而不是从左到右。
/dpi <dpi> 以 300DPI 以外的 DPI 渲染图形。
使用示例
Example.rl - 我们的输入词法分析器规范，采用 Rolex 格式
ident='[A-Z_a-z][0-9A-Z_a-z]*'
num='[0-9]+((\.[0-9]+[Ee]\-?[1-9][0-9]*)?|\.[0-9]+)'
space='[\r\n\t\v\f ]'
op='[\-\+\\\*%=]'
lineComment= '\/\/[^\n]*'
blockComment<blockEnd="*/">= "/*"
通过以下命令行操作
LexGen Example.rl /output ExampleRunner.cs /namespace Example /runtime /textreader /nfagraph Example_nfa.jpg /dfagraph Example_dfa.jpg /vertical
产生三个文件
ExampleRunner.cs - 一个依赖 Visual FA 运行时实现的 FATextReaderRunner，它词法分析由规范描述的输入。其完全限定名为 Example.ExampleRunner。
Example_nfa.jpg - 一张非常大的 JPG 图像，其中包含完全展开的 NFA 状态机。
Example_dfa.jpg - 一张较小但仍然很大的 JPG 图像，其中包含 DFA 状态机。它在缩小到网站尺寸时勉强足够小，可以分辨。
由于我们在命令行中声明了 /runtime，生成的代码依赖于运行时库，但即使我们没有声明，使用代码的方式也相同，除了对 Visual FA 的依赖。
一旦您创建了一个 C# 项目并引用了 Visual FA 运行时，您就可以将 ExampleRunner.cs 包含到您的项目中并使用您创建的词法分析功能
using VisualFA;
using Example;
...
ExampleRunner runner = new ExampleRunner();
using(TextReader reader = new StreamReader(myfile)) {
runner.Set(reader);
foreach(FAMatch match in runner) {
Console.WriteLine("{0}:{1} at {2}", match.SymbolId, match.Value, match.Position);
}
}
使用 API
FA 类
Visual FA API 的主要焦点是 `VisualFA.FA` 类。每个实例代表状态机中的一个状态。您通常将状态机的根 (q0) 保存在一个变量中并以此为基础进行操作。通过 `FA`，您可以解析或手动构建状态机、绘制它们或实例化运行器来执行匹配。如果您引用 `VisualFA.Compiler` 或 `VisualFA.Generator`，每个都会向 `FA` 添加用于编译状态机或为其生成代码的方法。我们稍后将介绍这些，但需要注意的是，`LexGen` 大部分繁重工作都由 `VisualFA.Generator` 完成。
IsDeterministic 指示某个特定状态是否是确定性的。请注意，它并没有说明整个机器。IsDfa() 可以告诉您整个机器是否是确定性的。请注意，如果机器中的任何状态是非确定性的，则整个机器必须被视为非确定性/NFA。（实际上，我的一些运行器代码针对这种情况进行了优化，但大部分情况下，这个说法仍然成立）。该值仅在没有 epsilon 转换且没有重叠转换到不同状态时才为真。
对于 DFA 状态 (IsDeterministic=true)，IsCompact 始终为 true，但对于 NFA 状态 (IsDeterministic=false)，IsCompact 仅在不存在 epsilon 转换时才为 true。
bool fiddleWithThis = true;
FA q0 = FA.Parse("foo|bar",0,fiddleWithThis);
Console.Write("q0 is ");
if(q0.IsDeterministic) {
Console.WriteLine("deterministic (DFA)");
} else if(q0.IsCompact) {
Console.WriteLine("compact non-deterministic (cNFA)");
} else {
Console.WriteLine("expanded non-deterministic (eNFA)");
}
您可以使用 `ToDfa()` 通过幂集构造/子集构造将任何机器转换为 DFA。它接受一个可选的 `IProgress
虽然您可以使用 `IsDfa()` 来确定 `ToDfa()` 是否必要，但通常情况下我不推荐这样做。`IsDfa()` 会检查机器中的每个状态的 `IsDeterministic`，直到遇到一个不确定的状态。在最坏的情况下——即它是 DFA 的情况——它必须检查每个状态。`IsDeterministic` 是一个非常快的调用，但检查每个状态意味着遍历闭包，尽管已优化，但并非免费。`IsDfa()` 有一个接受闭包的重载，如果您已经拥有闭包，可以大大减少开销。更重要的是，`ToDfa()` 总是返回机器的副本，即使它已经是 DFA。如果您只在某些情况下返回副本，那么如果用户随后修改他们收到的内容，这可能很危险，因为这意味着“有时”他们将修改他们不真正拥有的原始源机器，这是我不建议先检查的主要原因。我们在示例中这样做是因为它是一个示例，而不是一般情况。
// create an expanded NFA
FA q0 = FA.Parse("foo|bar", 0, false);
if(q0.IsDfa())
{
Console.WriteLine("Machine is a DFA");
} else
{
Console.Write("Machine is an NFA. Converting");
q0 = q0.ToDfa(
new Progress<int>(
(i) => {
if (0 == (i % 10))
{
Console.Write(".");
}
})
);
Console.WriteLine();
if (q0.IsDfa())
{
Console.WriteLine("Machine is a DFA");
} else
{
// this will never run
Console.WriteLine("ToDfa() failed (should never happen!)");
}
}
要获取当前机器中的所有状态——即从当前状态直接或间接可达的所有状态，这被称为“获取一个状态的闭包”——您可以使用 `FillClosure()`。
FA q0 = FA.Parse("foo|bar");
List<FA> existingList = new List<FA>();
q0.FillClosure(existingList);
// or
IList<FA> closure = q0.FillClosure();
请注意，调用此方法有两种方式。第一种方式用数据填充现有的列表实例，第二种方式返回一个包含数据的新列表。除此之外，行为是相同的。Visual FA 是一个非常依赖集合的库。它对列表和集合进行了大量操作，通常在紧密的循环中。在这些情况下，它喜欢预先创建列表实例并回收它们，而 `FillClosure()` 的第一次使用允许您使用回收的列表实例。额外的性能值得其使用上的一点初始困惑。一旦您理解了它的原因，它就非常容易使用。每当您看到 `FillXXXXX()` 方法时，您都可以期待出于类似原因的类似行为——最后一个参数是一个可选列表，它将用结果填充该列表。如果您不提供一个，它会创建一个。无论哪种方式，它都会返回它。
一个类似的操作，即“epsilon 闭包”，可以应用于一组状态。回顾一下，一个状态的 epsilon 闭包是它自身加上所有通过 epsilon 转换直接或间接可达的状态
FA q0 = FA.Parse("true|false|unspecified");
IList<FA> epsilonClosure = FA.FillEpsilonClosure(new FA[] { q0 });
请注意，我们必须将一个单元素数组作为第一个参数传入。`FillEpsilonClosure()` 主要设计用于处理整个状态组。也就是说，它旨在获取一组状态的 epsilon 闭包，而不仅仅是单个状态，因为除了一个特例之外，它都是这样使用的。另一个特例是当你第一次遍历 NFA 时，第一个操作是获取 q0 的 epsilon 闭包。如果我尝试创建一个在单个状态上操作的实例方法 `FillEpsilonClosure()`，C# 会报错，因为“填充”语义需要一个最终的可选列表参数。这会使其与静态方法冲突，因此我选择不提供它。这里真的没有任何好的选择。从功能角度来看，我最喜欢的选择是简单地将项目添加到你传入的初始列表中，因为这满足了这种特定操作——结果列表将始终包含传入列表中的项目，但这会导致 epsilon 闭包的填充方法与其他操作的填充方法在工作方式上出现严重混淆的不一致性。
还有 `FindFirst()` 和 `FillFind()`，它们都接受 `FAFindFilter`。这两种方法允许您轻松地在整个机器中搜索符合您给定条件的状态。还有几个预定义的过滤器：`AcceptingFilter`、`FinalFilter`、`NeutralFilter` 和 `TrapFilter`。
特别是 `FindFirst()` 可能比手动获取闭包然后循环遍历更有效，因为手动方法总是需要检查机器中的每个状态。
using VisualFA;
// play with this value
bool fiddleWithThis = false;
FA q0 = FA.Parse("foo|bar", 0, fiddleWithThis);
// mark each state in the machine with an id
// so we can refer to it later
q0.SetIds();
// count the closure
Console.Write("This machine has {0} states, ",
q0.FillClosure().Count);
// count the non-compact states
Console.WriteLine("of which {0} are not compact.",
q0.FillFind((fa) => !fa.IsCompact).Count);
// find the first deterministic state
FA firstDfa = q0.FindFirst((fa) => fa.IsDeterministic);
if (null != firstDfa)
{
Console.WriteLine(
"This machine has at least one deterministic state: q"+
firstDfa.Id.ToString());
}
`FillMove()`/`Move()` 是沿给定代码点在机器中前进位置的方法。第一种方法可以处理确定性状态和非确定性状态。第二种方法仅适用于确定性状态，但操作速度稍快。
在任何一种情况下，您在机器中的当前位置都由 DFA 的一个状态或 NFA 的一组状态表示。您将当前状态（或多个状态）和要尝试的代码点传递给移动方法，您将获得代表新当前位置的状态（或多个状态）（如果有）。如果您没有获得一个或多个状态，则该代码点没有可用的有效移动。
这就引出了 `GetFirstAcceptSymbol()`，它接受一组状态并返回在该组中找到的第一个接受符号，如果没有则返回 -1。我们用它来检查当前位置是否是接受状态，一旦我们用尽所有移动，我们就会这样做。
让我们使用移动来遍历一些状态机。我们首先为 DFA 做，因为它更简单，然后为 NFA 做。在每种情况下，我们都在抽象基类 `FATextReaderRunner` 上实现 `NextMatch()`，以避免在此处重复保持文本光标等的样板代码。
// here this._fa is the target machine we will be parsing.
// parse this or otherwise build it and use it here.
FA dfaState = this._fa, dfaNext = null, dfaInitial = this._fa;
// start out with an empty capture buffer
this.capture.Clear();
// first move:
if (this.current == -2)
{
this.Advance();
}
// store the current position
long cursor_pos = this.position;
int line = this.line;
int column = this.column;
while(true) {
// try to transition from dfaState on
// the current codepoint under the
// cursor
dfaNext = dfaState.Move(this.current);
if (dfaNext != null)
{
// found a transition
// capture the current
// char, advance the input
// position:
this.Advance();
// move to the next state
dfaState = dfaNext;
} else {
// no matching transition
// is the current state accepting?
if(dfaState.IsAccepting) {
// normally you'd process
// a block end here if one
// was specified. Omitted
return FAMatch.Create(
dfaState.AcceptSymbol,
this.capture.ToString(),
cursor_pos,
line,
column);
}
// not accepting - error
// keep capturing input until we find a valid move or there's
// no more input
while (this.current != -1 &&
dfaInitial.Move(this.current) == null)
{
this.Advance();
}
if (capture.Length == 0)
{
// end of input
return FAMatch.Create(-2, null, 0, 0, 0);
}
// error
return FAMatch.Create(-1,
capture.ToString(),
cursor_pos,
line,
column);
}
}
这将使用从正则表达式创建的 DFA 状态机匹配文本。这实际上并不可怕。您无需自己编写此代码，因为 `FATextReaderStateRunner` 已经实现了 DFA 和 NFA 机器的匹配。您甚至不需要直接使用 `FATextReaderStateRunner`，因为它在您使用 `FA.Run()` 时会提供给您。上述内容仅用于说明目的。以下内容更多相同，但适用于 NFA 机器
// here this._fa is the target machine we will be parsing.
// parse this or otherwise build it and use it here.
IList<FA> initial = FA.FillEpsilonClosure(new FA[] { this._fa });
IList<FA> next = null;
IList<FA> states = new List<FA>(initial);
// start out with an empty capture buffer
this.capture.Clear();
// first move:
if (this.current == -2)
{
this.Advance();
}
// store the current position
long cursor_pos = this.position;
int line = this.line;
int column = this.column;
while(true) {
// try to transition from states on
// the current codepoint under the
// cursor
next = FA.FillMove(states, this.current);
if (next.Count > 0)
{
// found at least one transition
// capture the current
// char, advance the input
// position:
this.Advance();
// move to the next states
states = FA.FillEpsilonClosure(next);
} else {
// no matching transition
// is any current state accepting?
int acc = FA.GetFirstAcceptSymbol(states);
if(acc>-1) {
// normally you'd process
// a block end here if one
// was specified. Omitted
return FAMatch.Create(
acc,
this.capture.ToString(),
cursor_pos,
line,
column);
}
// not accepting - error
// keep capturing input until we find a
// valid move or there's no more input
while (this.current != -1 &&
FA.FillMove(initial, this.current).Count == 0)
{
this.Advance();
}
if (capture.Length == 0)
{
// end of input
return FAMatch.Create(-2, null, 0, 0, 0);
}
// error
return FAMatch.Create(-1,
capture.ToString(),
cursor_pos,
line,
column);
}
}
您可以看到，它基本上是相同的，只是我们同时处理多个状态，而不是单个状态。
同样，您不需要自己实现匹配代码。有一整套 `FARunner` 派生类将为您执行匹配。说到这里
FARunner 及其派生类
`FARunner` 类是负责匹配文本的类的基类。它可枚举，这意味着它可以与 `foreach()` 一起使用，以提供一系列输入上的 `FAMatch` 实例，并且还提供 `Reset()` 和 `NextMatch()` 来遍历匹配项。`Reset()` 并不总是受支持。流式传输源无法重置。`FARunner` 不规定输入源类型。这是派生类的责任。
进一步派生的类提供一个 `Set()` 方法，该方法将其输入源作为参数。该方法的具体细节取决于派生类，但该方法的行为始终是将匹配重置到新输入源的开始位置，无论该输入源是什么。
FAStringRunner 是一个抽象运行器类，旨在用于字符串源。它提供了一个 `Set(string input)` 方法。从此派生的运行器在字符串上进行匹配。
FATextReaderRunner 是一个抽象运行器类，旨在用于 `TextReader` 源。它提供了一个 `Set(TextReader input)` 方法。从此派生的运行器在流式文本源（通常来自文件）上进行匹配。
生成的和编译的运行器类都派生自上述两者之一。
其余提供的运行器都是具体类，但您不需要自己实例化它们。相反，您可以使用 `FA.Run()` 方法来获取它们的实例。
运行时匹配器依赖于 `FAStringStateRunner` 和 `FATextReaderStateRunner` 来完成繁重的工作。它们的代码基本上类似于我们之前探索过的在状态机中移动的代码，只是进行了一些优化，并且更具动态性，因为它可以在需要时动态切换 DFA 和 NFA 状态导航。
还有另一种匹配方式我们尚未探讨，但很快就会探讨，那就是使用 `int[]` 数组进行匹配。任何状态机都可以序列化和反序列化为 `int[]` 数组。`FAStringDfaTableRunner` 和 `FATextReaderDfaTableRunner` 将匹配序列化到这些数组中的 DFA 机器。它们必须是 DFA，因为虽然可以序列化并在理论上可以在 `int[]` 形式的 NFA 上进行匹配，但实际上甚至学术/说明目的都不大，而且实际上，它并不比在 `FA` 图形式的 NFA 状态机上进行匹配效率更高。我几乎提供了它，但为了不让自己看起来很傻或过于痴迷，我决定不提供它。与其他类一样，您不需要直接实例化它们，因为 `FA.Run()` 有一个接受这些数组的重载。
序列化为和从 int[] 数组
任何状态机都可以序列化为整数数组或从整数数组反序列化。这主要用于创建最小化 DFA 数组，但它可以在任何机器上使用。
你可能会问为什么。一个用途可能是与第三方代码集成。例如，我用 TypeScript 编写了这个小引擎，它会愉快地使用这些数组。它甚至可以生成它们。
另一个原因是它是一种紧凑的状态机表示方式。它在二进制文件中占用的实际空间比编译的匹配器要少，同时匹配效率几乎相同，甚至在某些情况下更高（至少对于最小化的 DFA 来说）。当您有许多不同的匹配器时，基于表的匹配成为一个有吸引力的选项，因为它们都可以共享相同的匹配代码。唯一的区别是构成机器本身的数字列表。这使得偏差占用空间比相同系列编译匹配器要小得多。
FA q0 = FA.Parse("foo|bar|baz").ToMinimizedDfa();
int[] array = q0.ToArray();
foreach(FAMatch match in FA.Run("foo bar baz",array)) {
if(match.IsSuccess) {
Console.WriteLine("Found {0} at position {1}", match.Value, match.Position);
}
}
如果由于某种原因，您想从数组中获取一些 `FA[]` 实例，可以使用 `FA.FromArray()` 方法。这适用于任何状态机
FA newMachine = FA.FromArray(array); // effectively cloned q0 from above
这些数组没有进行任何验证，要做到这一点，我必须在数组中添加额外的元素，以便我可以检查签名和其他有效性。不要将无效数组传递给 `FromArray()`（用我最好的 C++ 语气），否则结果将是未定义的。
还应该注意的是，`FA` 实例可以关联元数据，例如通过 `ToDfa()` 创建的实例，它会跟踪它所产生的 NFA 的原始状态。此信息在序列化为数组时不会持久化。元数据不会改变状态机在输入方面接受的内容，因此通常这无关紧要，但值得一提。
数组结构
数组是一系列状态条目。
数组中的状态条目为
- 接受符号，或 -1
- 状态转换条目的数量
- 状态转换条目列表
一个状态转换条目是
- 数组中的目标状态索引。这是匹配时跳转到的位置。
- 代码点范围条目的数量
- 代码点范围条目列表
代码点范围条目为
- 最小值，或 -1 用于 epsilon 转换
- 最大值，或 -1 用于 epsilon 转换
编译运行器
从机器编译运行器非常简单，但请注意限制：您必须将 `VisualFA` 作为引用程序集使用，而不是静态嵌入在代码中（我们将介绍这种方法）。
您还必须引用匹配的 `VisualFA.Compiler` 程序集（如果针对 .NET Framework，您将需要使用 DNF 变体）。
一旦您这样做，FA 将会增加 CompileString() 和 CompileTextReader() 方法，分别生成 FAStringRunner 或 FATextReaderRunner 实例。它还会通过编译参数重载 Run() 方法。使用时请务必小心，因为它不会为同一台机器重用已编译的实例。我无法做到，因为没有简单/高性能的方法来确定机器自上次编译以来是否以任何方式发生了变化，所以我必须始终假设它发生了变化。因此，只需调用一次带 compiled=true 的 Run()，然后使用 Set() 和/或 Reset() 重复使用该运行器实例。
我对此有一些未来的想法，所以也许这会改变，但真正的挑战是确定状态机自上次编译以来是否已更改。基本上，在我解决这个问题之前，API 将它交由您处理。
using VisualFA;
FA q0 = FA.Parse("foo|bar");
FAStringRunner runner = q0.CompileString();
runner.Set("foo bar bar foo");
foreach(FAMatch match in runner)
{
if(match.IsSuccess)
{
Console.WriteLine(
"Found {0} at {1}",
match.Value,
match.Position);
}
}
// below is not recommended, but storing the result of
// FA.Run(<input>,<blockEnds>,true) in a variable is fine.
// reason is you can't reuse the runner below.
foreach (FAMatch match in
q0.Run("foo bar bar foo",null,true))
{
if (match.IsSuccess)
{
Console.WriteLine(
"Found {0} at {1}",
match.Value,
match.Position);
}
}
生成运行器代码
关于 CodeDOM 的说明
目前，Visual FA 使用 Microsoft 的 CodeDOM 技术以给定语言呈现代码。这与历史上用于在 ASP.NET 中的 ASPX 页面中托管 .NET 语言以及在 Visual Studio 的组件设计器中为“代码隐藏”文件提供代码生成的技术相同。现在这正在转向使用 Roslyn，但 Roslyn 需要大量的底层基础架构投入，包括在主机上运行 Microsoft 的编译器服务。如果您已经安装了 Visual Studio，这种投入是理所当然的，您已经拥有了，但在较“精简”的 .NET 安装中，例如在 .NET 服务器环境中，我真的不知道 Roslyn 在实践中有多可用。我hesitate 迁移，因为我还不清楚这一点，如果我连这样一个基本问题都无法回答，在我了解更多关于我将要处理的事情之前，我没有理由沿着这条路追逐代码。我几乎肯定会为 Visual FA 添加 Roslyn 支持和源代码生成器支持，并以 Microsoft 暴露其正则表达式源代码生成的方式来暴露它。我只是有很多前期研究需要先完成。
说到 CodeDOM
Deslang 介绍
Deslang 是一个巨大的可执行文件，潜伏在解决方案文件夹中。它是一个神奇的盒子。它所做的是
- 接受一个或多个用“Slang”编写的 `.cs` 文件——C# 的一个兼容 CodeDOM 的子集
- 解析、反射并修改它们成为 CodeDOM 树。这是制造香肠，各位。
- 将内存中的 CodeDOM 树转换为源代码，以便按需重新实例化该树。
这有点奇怪，但它所做的是让我能够有效地创建复杂的 CodeDOM 树，而无需键入太多内容。声明一个变量并为其赋值可能需要整整一段代码，仅仅是为了做 `StringBuilder sb = new StringBuilder();` 这样的事情。我很懒。我不想编写像 `new CodeVariableDeclarationStatement(new CodeTypeReference(typeof(StringBuilder)),"sb",new CodeObjectCreateExpression(new CodeTypeReference(typeof(StringBuilder))));` 这样的东西，所以 Deslang 只是让我将其写成 `StringBuilder sb = new StringBuilder();`，然后它会为我将其转换为那个乱七八糟的东西。然后我就可以将那个乱七八糟的东西渲染成 VB.NET 或 C# 或其他任何东西。
如果这仅仅是为了一个变量，您可以想象实现一个完整的源文件是什么样的。如果您像我一样宁愿不这样做，那么您可以将 VisualFA.Generator（和 DNF 变体）项目下的 Shared 文件夹中的代码视为 Deslang 的输入文件，而 DeslangedString.cs 和 DeslangedSpan.cs 则是输出。这些文件包含我的共享代码的 CodeDOM 抽象语法树，可按需获取。Deslang 将 Visual FA 提供给您的所有非平凡共享代码打包到一个代码树中，当它需要将其放入输出时，可以渲染该代码树。
有道理吗？没有？好吧，没办法。抱歉，这就是我能提供的最好的解释了。我从未成功地向任何人解释过它的作用，但我喜欢这个工具，即使它使用起来有点暴躁和挑剔。对于使用 CodeDOM 的项目，它仍然可以轻松地为我节省数小时甚至数天的工作。
幸运的是，您不需要真正理解它即可使用此代码。它是一个构建工具，但它解释了那些 `DeslangedXXXX.cs` 文件的内容。
好的，现在该实际生成一些代码了吗？
请原谅我。我们马上就到。我已经花了足够的时间在 VisualFA.Generator 的内部运作上。无论如何，要使用它不需要任何那些啰嗦的东西。除非您使用的是 .NET Framework，否则您“需要”做的是包含 Microsoft CodeDOM NuGet 包。在 .NET Framework 中，它本质上是固有的，存在于 `System.dll` 中。在 Core 和 Standard 中，它们已将其移至 NuGet 包，因此请相应地构建您的项目。
现在，您需要做的，类似于您使用编译功能的方式，是在您的项目中包含 `VisualFA.Generator`（或 DNF 变体），届时它将为 `FA` 增加一个 `Generate()` 方法。该方法的参数都是可选的，但您在使用时几乎总是需要填写一个 `FAGeneratorOptions` 类。在生成代码时需要考虑的控制太多了——类名是什么、命名空间是什么、依赖关系情况如何等等。我为所有内容提供了默认值，但它们只适用于少数情况，可能不是您的。我几乎将该参数设为必需参数，但由于我无法决定，所以我没有将其作为函数的第一个参数这一事实影响了我的决定。
无论如何，我想这里有很多内容，我无法预料到您所有的问题，所以我提供了一些测试代码，应该可以帮助您了解这一切是如何工作的。通常，您会将输出打印到文件，但在这里我将其写入控制台，以便您可以轻松地看到更改代码的各个部分如何改变输出。
using System.CodeDom;
using VisualFA;
using System.CodeDom.Compiler;
FA q0 = FA.Parse("foo|bar");
FAGeneratorOptions genopts = new FAGeneratorOptions();
// set to true to use table based runners
// instead of compiled runners. Typically
// generates smaller binaries - esp since
// multiple runners share code, with good
// performance.
genopts.GenerateTables = false;
// set to true to derive from FATextReaderRunner
// instead of FAStringRunner, allowing the use
// of TextReader as input instead of String
// a bit slower, but perhaps more realistic for
// lexing files
genopts.GenerateTextReaderRunner = false;
// the name of the runner class
genopts.ClassName = "FooOrBarStringRunner";
// the namespace to generate the code in
genopts.Namespace = "Demo";
// UseRuntime = Depend on Visual FA runtime library
// GenerateSharedCode = Generate necessary code to
// make dependency free runners. This creates FARunner
// classes as necessary to make your generated code
// work
// None = No dependencies, but do not generate shared code
// This will generate code that doesn't depend on the
// Visual FA runtimes, but will not generate the shared
// code necessary to make it work. Use this if a previous
// generation yielded shared code into this project under
// the same namespace. Both will use that code.
genopts.Dependencies = FAGeneratorDependencies.UseRuntime;
// The following setting only applies to FAStringRunner
// derivatives - use ReadOnlySpan<char>
// internally for string runners. It's better
// performing than string, but not supported across all
// flavors of .NET, and as far as I can tell, VB.NET
// doesn't like them either. turn it off if you're
// generating VB.NET code.
genopts.UseSpans = true;
CodeCompileUnit code = q0.Generate(null,genopts);
Microsoft.CSharp.CSharpCodeProvider prov = new Microsoft.CSharp.CSharpCodeProvider();
// alternatively
//Microsoft.VisualBasic.VBCodeProvider prov = new Microsoft.VisualBasic.VBCodeProvider();
CodeGeneratorOptions cdopts = new CodeGeneratorOptions();
cdopts.BlankLinesBetweenMembers = false;
cdopts.IndentString = " ";
cdopts.VerbatimOrder = true;
cdopts.BracingStyle = "BLOCK";
prov.GenerateCodeFromCompileUnit(code, Console.Out, cdopts);
我一直在思考如何使在常见场景中生成代码变得更容易。我之所以迟迟未动，有几个原因。
- 您已经可以使用我的 Code DOM Go Kit!，它包含 `CodeDomUtility`——一个让您处理所有 CodeDOM 相关事务更轻松的类。生成代码就像调用 `CodeDomUtility.ToString()` 一样简单。
- 正如我所说，我几乎肯定会添加 Roslyn/Source Generator 支持，这种协调机制避免了编写任何实际代码的需要。相反，您只需用一个属性标记一个局部方法，该属性告诉 C# 编译器应该告诉 Visual FA 生成什么。考虑到这一点，我不确定我是否想投入多少精力来简化 CodeDOM 生成机制。我觉得它最终可能只会是多余的。
通常，使用 LexGen 而不是自己生成代码是一个好主意。
绘制状态机图
如果您的 PATH 中安装了 Graphviz，Visual FA 可以创建您状态机的详细图表。它甚至可以绘制您在其中移动的路径。这个功能基本上就是 Visual FA 中“Visual”的来源。
绘制状态机图就像这样简单
FA q0 = FA.Parse("foo|bar");
q0.RenderToFile("fooBar.jpg");
// or
using(Stream stream = q0.RenderToStream("jpg")) {
// stream contains JPG data
}
这将处理基本图形绘制，但有时您需要更多控制。对于这些情况，您可以填充并传递一个 `FADotGraphOptions` 实例给渲染方法
// create an expanded NFA
FA nfa = FA.Parse("foo|bar", 0, false);
// we're going to show the
// subset construction in
// the graph. ToMinimuzedDfa()
// doesn't preserve that.
// So use ToDfa();
FA dfa = nfa.ToDfa();
FADotGraphOptions dgo = new FADotGraphOptions();
// the image is wide for this
// website. Let's make it a
// little less wide by making
// it top to bottom instead of
// left to right
dgo.Vertical = true;
// this expression does not use
// blockEnds. If we did, we'd
// put the block end array here
dgo.BlockEnds = null;
// let's show the NFA together
// with the DFA
dgo.DebugShowNfa = true;
// and so we give it
// the source NFA to use
dgo.DebugSourceNfa = nfa;
// we don't need to show the accept
// symbols. That's for lexers
dgo.HideAcceptSymbolIds = true;
// this is also for lexers
// it takes a string[] of names
// that map to the accept symbol
// of the same index in the array
// it works like blockEnds in
// terms of how it associates
dgo.AcceptSymbolNames = null;
// let's do something fun
// we can graph movement
// through the machine by providing
// an input string.
dgo.DebugString = "ba";
// finally, render it.
dfa.RenderToFile(@"5375850/dfa_subset.jpg", dgo);
这将为您带来以下图像
这张图片中发生了几件事情。首先是我们的机器最初的 NFA 状态机显示在左侧。右侧是 `ToDfa()` 的结果，带有一些额外信息。每个状态名称下方都有一组用大括号 **{ }** 括起来的状态。这组状态表示 DFA 中的状态是由 NFA 中的哪些状态产生的。实际上，它向您展示了用于将 NFA 转换为 DFA 的整体子集构造。最后，每个图中的某些状态是绿色的。这些表示基于 `DebugString` 内容的当前状态。我们走到了图表所示的“ba”。我们在 NFA 中的当前状态显示在左侧的绿色区域，在 DFA 中显示在右侧的绿色区域。
将 Visual FA 嵌入您自己的项目
携带额外的带有构建工具的 DLL 文件可能会很麻烦。幸运的是，Visual FA 已打包，允许将代码直接嵌入到您自己的项目中。
我通过将 VisualFA 和 VisualFA.Generator 项目“打包”成解决方案根文件夹中自包含的 `.brick.cs` 文件来简化此操作。这些文件包含其关联项目的所有源文件，在一个文件中，并进行了最小化。它被最小化的原因有两方面。其一，对于如此大的文件，您可能会在空白字符上浪费一兆字节，但更重要的是，我发现我会在调试会话期间修改 brick 文件以修复错误或调整某些内容，但从不将我的更改传播回原始源文件。我这样做是因为这比正确地重新引用 DLL 并针对库本身进行调试更容易，这对我来说更像是对工作流程的干扰，但这给我带来了无尽的问题。我对工作流程几乎没有冲动控制——我只关心效率，因此最小化源代码使我保持诚实。根项目文件夹中的 `csbrick.exe` 在关联项目中的构建后步骤中完成了这个混乱的工作。
请注意，我没有将编译器代码打包。编译功能不能与嵌入式代码一起使用，因为它们依赖于 DLL。
下一步？
在下一部分中，我们将详细介绍实现这一奇迹的代码——我是如何开发它的。
历史
- 2024 年 1 月 17 日 - 初次提交
- 2024 年 1 月 18 日 - 错误修复