正则表达式匹配解析过程的讨论与分析(正则表达式匹配原理)

关于正则表达式的介绍已经有很多文章了。随着我们越来越多地使用正则表达式，我们希望优化性能并减少我们的正则表达式编写和匹配错误。我们要进一步了解正则表达式的执行过程。让我们一起学习，分析一下正则表达式的执行过程。我们将使用Regex Puddy测试工具分解执行过程。具体的工具用法可以看如下：正则表达式性能测试工具推荐和优化工具推荐(Regex Puddy推荐)。在理解正则表达式的解析过程之前，我们应该先熟悉几个概念。

常见的正则表达式引擎引擎决定了正则表达式的匹配方法和内部搜索过程，所以了解它非常重要。目前主要流行的发动机有：DFA和NFA，我们比较一下。

引擎差异DFA确定性有限自动机确定性有限自动机DFA引擎不需要回溯(因此它们从不测试相同的字符两次)，因此匹配速度很快！DFA引擎还可以匹配最长的可能字符串。然而，DFA引擎只包含有限数量的状态，因此它无法匹配具有反向引用的模式，也无法捕获子表达式。典型的例子有awk、egrep、flex、lex、MySQL、procmail NFA非确定性有限自动机和传统的NFA、Posix NFA传统的NFA引擎运行所谓的“贪婪”匹配回溯算法(最长-最左边)来测试正则表达式的所有可能的扩展，以指定的顺序并接受第一个匹配。传统的NFA回溯可以多次访问同一个状态。在最坏的情况下，它的执行速度可能非常慢，但它支持匹配。代表语言有GNU emacs、Java、ergp、less、more、net语言、pcre库、perl、PHP、python、ruby、sed、VI等。一般的高级语言都采用这种模式。DFA将正则表达式中的字符串一一匹配，而NFA专注于正则表达式，并逐个搜索字符串。虽然速度慢，但是对操作人员来说比较简单，所以应用广泛！以NFA引擎为例说明解析过程！

解析引擎眼中的字符串构成对于字符串“DEF”，它包括三个字符d、e和f以及四个数字位置0、1、2和3: 0D1E2F3。对于正则表达式，所有源字符串都有字符和位置。正则表达式将从位置0开始逐个匹配。

在用零宽度正则表达式匹配字符的过程中，如果子表达式匹配的是字符内容，而不是位置，并且保存在最终的匹配结果中，则认为子表达式是字符占用的。如果子表达式只匹配位置，或者匹配内容没有保存在最终的匹配结果中，那么子表达式被认为是零宽度的。占有字符互斥，零宽度不互斥。即一个字符只能同时匹配一个子表达式，而一个位置可以同时匹配多个宽度为零的子表达式。常见的零宽度字符有：=)等。

正则表达式匹配过程的详细说明示例我们已经掌握了上述概念，接下来我们分析以下常见的解析过程。结合软件regexBuddy来分析。

Demo1:源字符DEF，对应标记为0D1E2F3，匹配正则表达式为：/DEF/

这个过程可以理解为：首先正则表达式字符/D/获得控制权，匹配从位置0开始，与/D/匹配“D”。匹配成功后，控制权移交给角色/e/；由于“D”已被/D/，所以/E/尝试从位置1匹配，而/E/匹配“E”。匹配成功，控制权移交给/f/。用/F/匹配“F”，匹配成功。

Demo2:源字符DEF，对应标记为0D1E2F3，匹配正则表达式为：/D\w F/

这个过程可以理解为：首先正则表达式字符/D/获得控制权，匹配从位置0开始，与/D/匹配“D”。匹配成功后，控制权移交给字符/\ w/；因为“D”已被/D/，匹配，/\ w/尝试从位置1匹配。\w在贪婪模式下，会记录一个备选状态，默认匹配最长的字符，直接匹配到EF，匹配成功，当前位置为3。并将控制权交给/f/；/F/匹配失败。\w匹配将回溯一位，当前位置将更改为2。并将控制权交给/F/，并且/F/成功匹配字符F。所以这里\ w the字符匹配，匹配完成！

Demo3:源字符DEF，对应标记为0D1E2F3，匹配正则表达式为：/(？=D)[D-F] $/

这个过程可以理解为：元字符//和/$/只匹配位置，环顾四周/(？=D)/(匹配当前位置，右侧是否有字符“D”)只匹配，不占用字符，不将匹配的内容保存到最终匹配结果，所以都是零宽度。首先，元字符//获得控制权，匹配从位置0开始。//匹配的是起始位置“位置0”。匹配成功后，控制权交给顺序环视/(？=D)/；/(?=D])/要求其位置右侧必须是字母“D”才能匹配成功。零宽度子表达式并不互斥，即同一个位置可以同时被多个零宽度子表达式匹配，所以也尝试从位置0开始匹配，位置0的右侧是字符“d”，符合要求。如果匹配成功，控制权交给/[d-f]/；因为/(？=D)/仅匹配，不将匹配的内容保存到最终结果中，/(？=D)/成功匹配的位置是位置0，所以/[D-F]/也尝试从位置0开始匹配。/[D-F]/先试着匹配“D”，再试着匹配成功，直到“EF”完成。此时已经匹配到位置3，位置3右侧没有字符。此时，控制权将移交给/$/。此时，正则表达式匹配完成，并报告匹配成功。匹配结果为“DEF”，起始位置为0，结束位置为3。其中//匹配位置0，/(？=D)/匹配位置0，/[D-F]/匹配字符串“DEF”，/$/匹配位置3。

后记：在上面的例子中，我们分析了正则表达式的普通匹配，以及回溯过程，然后是零宽度字符的匹配过程。当然，给出的例子相对简单，实际过程中会遇到更长更复杂的正则表达式。然而，想法是相似的。只要我们把我的分析原理，我们可以一个一个分解。好了，就这样。欢迎交流！