正则表达式可视化、模拟器和交叉编译工具

本文是正则表达式系列的一部分。*有关要可视化的更多正则表达式示例，请查看此正则表达式测试用例列表。

下面的C源代码是上面生成的任何代码示例所需的公共代码。只需将以下代码与上面动态生成的代码一起复制并粘贴到名为main.c&39；的文件中，即可生成执行您想要的正则表达式搜索的硬编码程序。确保在上面动态生成的代码之前传递下面的代码。*您可以使用以下命令编译代码：

代码应该编译时没有任何问题，并生成可执行程序'；a.out'；。*您可以使用以下命令运行此程序：

请注意，代码并不代表正则表达式的快速实现(事实上，它是最慢的实现之一)。这里的目标是为了教育目的而制作一个非常简短和易于理解的程序，而不是制作一个快速而复杂的程序。

#include<；stdio.h>；#include<；unistd.h>；#include<；stdarg.h>；#include<；stdlib.h>；#include<；sys/wait.h>；#include<；string.h>；#定义GREEDY_BRANCH 1#定义LAZY_BRANCH 0 INT SPLIT(INT BRANCH1，INT BRANCH2){/*。调用将拆分此进程并执行调用此函数的外部'；If'；语句的'；Branch1'；，THEN'；的'；Branch1'；，Then'；Branch2'；。它还将顺序等待'；分支1'；完成，然后再运行'；分支2&39；，而不是并行运行这两个分支。如果'；分支1'；返回0表示成功，则'；分支2&39；将永远不会运行。*/pid_tChild_pid；pid_t wpid；int status=0；if((Child_pid=fork())>；0)WHILE((wpid=Wait(&；status))>；0)；/*等待孩子在'；分支1'；中完成。*/否则返回分支1；/*如果这是子级，则在'；分支1'；中返回并连续。*/IF(WIFEXITED(状态)){IF(WEXITSTATUS(状态)==0)/*在'；分支1'；中找到匹配项，以0退出父级。*/EXIT(0)；ELSE/*继续检查第二个分支...。*/；}Else{printf("；意外错误情况。\n"；)；EXIT(1)；}IF((CHILD_PID=fork())>；0)WHILE((wpid=WAIT(&；status))>；0)；/*等待孩子在'；分支2'；中完成。*/否则返回分支2；/*如果这是子级，则在'；分支2'；中返回并连续。*/IF(WIFEXITED(状态)){IF(WEXITSTATUS(状态)==0)/*在'；分支2'；中找到匹配项，以0退出父级。*/EXIT(0)；ELSE EXIT(1)；/*两个分支均未找到匹配项。*/}Else{printf("；意外错误情况。\n"；)；exit(1)；}}int matches_one_of_this_character(char c，int num_chars，...){va_list arglist；va_start(arglist，num_chars)；int i；int find=0；for(i=0；i<；num_chars；i++){int d=(Char)va_arg(arglist，int)；if(c==d){find。}int matches_this_character(可用字符，需要字符){if(Available==Required){Return 1；}Else{return 0；}}char security_get_character(const char*str*str，int Offset，int pos，int str_len){if(Offset+pos<；str_len){return str[Offset+Pos]；}Else{退出(1)；/*到达字符串末尾。*/}}int is_start_of_text(Int Position_In_String){return position_in_string==0；}int is_end_of_text(int position_in_string，int str_len){return str_len==position_in_string；}。

在上面，您将发现一个交互式可视化，您可以使用它来模拟正则表达式。“您可以键入任何正则表达式，该工具将自动创建两个与您的正则表达式相对应的图表。*这两个图表都是交互式的、可缩放的，并且都包括对全屏模式的支持。

第一个图是解析树。构建解析树是正则表达式引擎执行的第一步，以确定每个字符将具有什么含义。

您可以单击解析树中的各个节点来突出显示正则表达式中的相应字符。您也可以反过来单击正则表达式中的单个字符，以便在解析树中快速找到相应的字符。因此，通过查看字符在解析树中是如何分组在一起的，您可以深入了解各个字符的含义以及它们在正则表达式中如何相互关联。

第二张图显示了与您的正则表达式相对应的控制流图。此控制流程图说明了每当您的正则表达式与一段文本匹配时所采取的逐步过程。*尝试匹配正则表达式时，该过程从'；Begin'；节点开始，在'；Match'；或'；Failure'；节点结束。从'；BEGIN'；节点到'；Match'；节点的任何路径都对应于与您的正则表达式匹配的一段文本。

控制流图中的大多数节点直接对应于正则表达式中的一个或多个字符。您可以单击控制流图中的节点，查看在原始正则表达式和解析树中突出显示的相应节点。还要注意，单击正则表达式中的字符还会突出显示控制流图中的任何关联节点。

如果不看到正则表达式在尝试匹配给定文本时所做的决定，就很难真正理解它是如何工作的。*因此，每次您对正则表达式进行更改时，此可视化工具都会自动生成一段文本，其中包含至少一个与您的正则表达式匹配的内容。如果您想查看匹配过程如何处理您自己的自定义文本，只需更改搜索字符串的输入值，动画就会自动更新。

匹配正则表达式的过程从'；BEGIN'；节点开始，然后跟随箭头到达实际执行正则表达式本身工作的节点。

在撰写本文时，此可视化工具支持的所有正则表达式最终都转换为控制流图，该图由以下5种类型的节点组成：

1)*Char：此节点类型检查正在搜索的文本中当前位置的特定字符。如果字符匹配，我们将继续控制流图中的下一个节点。如果不匹配，控制流程图将移至故障节点。

2)类：此节点类型检查正在搜索的文本中当前位置的字符类。此节点类型实际上与第一个节点类型执行相同的操作，不同之处在于它允许在搜索文本的当前位置有多个可能的字符。*如果文本中的当前字符在此节点指定的可接受字符列表中，我们将继续控制流图中的下一个节点。如果不匹配，控制流程图将移至故障节点。

3)此节点类型的拆分执行拆分操作。这是正则表达式匹配器有多条可能的路径继续通过控制流图的情况。*在编程方面，此节点有效地执行与派生进程或将工作拆分到两个单独线程中相同的操作。这也可以在单个线程中实现，方法是尝试两条路径，一次一条，并将保存的信息推送到堆栈上。在计算机科学理论中，这种节点类型应该会提醒您DFAS和NFA之间的区别。

4)此节点类型的锚点表示常用的字符串开头或字符串结尾正则表达式字符。此节点的类型非常简单，因为它只检查字符串中的当前位置分别是在第一个位置还是最后一个位置。如果检查成功，我们将继续到控制流图中的下一个节点。如果没有，控制流程图将移至故障节点。

5)此节点类型的进展对于避免某些正则表达式中的无限循环是必要的，这些正则表达式可能包括重复的可能为零长度的字符串。*如果没有此节点，控制流图可能会潜在地包含导致我们永远四处移动而没有任何进展的循环。当每次访问进度节点时，它会确保自上次访问以来我们在匹配正则表达式方面取得了一些进展。如果我们已经取得进展，我们将移动到控制流图中的下一个节点。如果没有，控制流图将移至故障节点。

您可能会感到惊讶，但是最常用的正则表达式可以用上述5种简单的节点类型来描述。

此可视化工具的主要目的是帮助您了解正则表达式中字符的精确含义。因此，该工具还会将您的正则表达式交叉编译为硬编码的C程序，该程序实现对您指定的正则表达式模式的搜索。*控制流图中的每个节点都与两个图下面表示的几行C源代码有直接对应关系。*您可以单击控制流图中的节点，查看哪些代码行与您选择的节点相对应。

对于'；Char'；节点的实现，我们首先使用'；security_get_character'；函数从要搜索的字符串中挑选出下一个字符。'；SAFE_GET_CHARACTER'；函数的实现在'；通用C代码部分中列出。此函数非常简单，因为它只是检查以确保我们仍在正在搜索的字符串的范围内，如果在，则返回当前位置的字符。如果我们超过了字符串的末尾，我们就直接退出该过程。*这对应于移动到控制流图中的失败节点。

在获得当前字符之后，我们使用'；matches_this_character'；函数检查以确保它与正则表达式中指定的文字字符匹配。下面是matches_this_character函数的实现。如您所见，此函数非常简单，因为它只检查要搜索的字符串中的当前字符是否与正则表达式中提供的文字字符相同。

'；class'；节点的实现与'；char'；节点的实现非常相似。与'；Char'；节点一样，与此节点类型对应的C代码将尝试挑选出要搜索的字符串中的下一个字符。*如果返回一个字符，我们会将其传递给'；matches_one_of_this_characters'；函数，该函数也列在上面的'；通用C代码部分中。此函数与'；matches_this_character'；函数非常相似，除了这一次，在正则表达式中的此位置有多个可接受的字符可以匹配。*传递给此函数的参数包括要搜索的字符串中的当前字符、要测试的字符选项的数量，以及我们要检查的字符选项的完整列表。

'；matches_one_of_this_character'；函数看起来有点复杂，但它实际上与'；matches_this_character'；函数非常相似。不同之处在于，对于此函数，我们需要通过数量可变的参数进行检查，以查看当前字符是否与我们在调用此函数时提供的任何字符匹配。在C中，访问可变长度的参数列表是通过声明va_list并使用特殊的va_start、va_arg和va_end宏来完成的。

IF(Split(BRANCH1，BRANCH2)>；0){/*先尝试分支1指令...。*/}否则{/*第二次尝试分支2指令...。*/}。

IF(Split(BRANCH2，BRANCH1)>；0){/*第二次尝试分支1指令...。*/}否则{/*先尝试分支2指令...。*/}。

第三个节点类型是'；Split'；节点。此节点类型作为C程序的实现是迄今为止最复杂的。事实上，有多种正确的方法可以将此节点类型实现为C程序。一种方法是显式使用内存堆上分配的堆栈。另一种方式是隐式使用当前线程的堆栈内存中分配的堆栈。还有一种方法是使用进程分叉和GOTO语句，这是这里将说明的方法。这种方法产生的代码非常慢，效率极低，但它也非常简短，这正是像这样的教育工具所需要的。

当'；Split'；节点类型出现在上面生成的代码中时，它看起来像是对If语句的简单检查，但在'；Split'；函数的实现内部是一系列过程控制语句。*'；Split'；函数首先创建一个子进程，以返回并执行调用'；Split'；的外部If语句中的一个分支。如果该子进程通过带1退出进程而到达故障节点，父进程将在此处等待检测。父级然后将派生第二个子进程，以继续作为外部'；IF'；语句的相反分支。*如果任何一个分支返回0以指示找到成功的匹配，父进程将检测到这一点并退出，返回代码为0，以向任何进一步的父进程发出成功的信号。*如果两个分支都找不到匹配，则Split函数将退出，并返回代码1，以向任何父进程指示搜索的两个分支都已失败。

该节点作为C程序具有最简单的实现。*如前所述，当使用文本'；开始或'；文本结束元字符时，会出现锚节点。它只是简单地检查搜索文本中的当前位置分别是在开始位置还是在结束位置。*请注意，锚定字符通常根据上下文的不同而有不同的解释，它们既可以表示相对于当前行的位置，也可以表示相对于整个文本的位置。*锚节点的C代码可以根据希望它们表示的解释而略有不同地实现。

第五个也是最后一个节点类型也有一个相当简单的C程序实现。*控制流图中的所有进度节点都可以表示为一个数字数组，用于描述正则表达式在最后一次访问每个进度节点期间接受的字符数。所有进度值都初始化为-1，每次访问进度节点时，我们都会检查上次访问该节点时有多少个字符匹配。*如果自上次访问以来匹配了更多字符，则我们更新该节点的计数并继续。如果不是，进程退出，返回代码为1，向父进程发送失败信号。

这结束了对实现基本正则表达式匹配器所需的所有C源代码的审查。这段代码没有涵盖所有可能的正则表达式功能，但它有望使正则表达式变得不那么神秘。

本文讨论的理论内容深受拉斯·考克斯关于正则表达式的著作的影响。尤其是，我建议阅读正则表达式匹配：虚拟机方法作为本文的补充。这些著作中表达的思想揭示了正则表达式、计算理论和操作系统开发之间令人惊讶的深刻联系。