个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
26
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章正则表达式之回溯由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
关于“回溯”我也是第一次接触，对它也不算很了解。下面就把我所了解的做为一个心德记录下来，以备查看。 我们所使用的正则表达式的匹配基础大概分为：优先选择最左端（最靠开头）的匹配结果和标准的匹配量词（*、+、？和{m, n}）是匹配优先的。 “优先选择最左端的匹配”顾名思义就是从字符串的起始位置开始匹配直到匹配结束这是基础；“标准匹配量词”又分为“非确定型有穷自动机（NFA）”也可以叫做“表达式主导”；另外一种是“确定型有穷自动机（DFA）”也可以叫做“文本主导”。我们目前在JavaScript中所使用的正则表达式为“表达式主导”。表达式主导和文本主导解释起来有些麻烦，先看来一个例子可能会清楚些.
复制代码 代码如下
// 使用正则表达式匹配文本 var reg = /to(nite|knight|night)/; var str = 'doing tonight'; reg.test(str),
在上面的这个例子中，第一个元素[t]，它将会重复尝试，直到目标字符串中找到‘t'为止。之后，就检查紧随其后的字符是否能由[o]匹配，如果能，就检查下面的元素（nite|knight|night）。它的真正含义是“nite”或者“knight”或者“night”。引擎会依次尝试这3种可能。尝试[nite]的过程是先尝试[n]，然后[i]，然后[t]，最后是[e]。如果这种尝试失败，引擎会尝试另一种可能，如此继续下去，直到匹配成功或是报告失败。表达式中的控制权在不同的元素之间转换，所以称为“表达式主导”.
同样是上面的例子“文本主导”在扫描字符串时，会记录当前有效的所有匹配可。当引擎移动到t时，它会在当前处理的匹配可能中添加一个潜在的可能:
| 字符串中的位置 。 |
正则表达中的位置 。 |
| ……doing tonight 。 |
可能的匹配位置：/t↑o(nite|knight|nigth)/ 。 |
。
接下来扫描的每个字符，都会更新当前的可能匹配序列。继续扫描两个字符以后的情况是:
。
| 字符串中的位置 。 |
正则表达中的位置 。 |
| ……doing tonight 。 |
可能的匹配位置：/to(ni↑te|knight|ni↑gth)/ 。 |
。
有效的可能匹配变为两个（knight被淘汰出局）。扫描到g时，就只剩下一个可能匹配了。当h和t匹配完成后，引擎发现匹配已经完成，报告成功。“文本主导”是因为它扫描的字符串中的每个字符都对引擎进行了控制.
如果想要弄明白“表达式主导”是如何工作的，那就要看一下我们今天的主题“回溯（backtracking）”。回溯就像是在走岔路口，当遇到岔路的时候就先在每个路口做一个标记。如果走了死路，就可以照原路返回，直到遇见之前所做过的标记，标记着还未尝试过的道路。如果那条路也走不能，可以继续返回，找到下一个标记，如此重复，直到找到出路，或者直到完成所有没有尝试过的路.
在许多情况下，正则引擎必须在两个（或更多）选项中做出选择。当遇到/……x?……/时，引擎必须是否尝试匹配X。对于/……X+……/的情况，毫无疑问，X至少尝试匹配一次——因为加号要求必须匹配至少一次。第一个X匹配之后，此要求已经满足，需要决定是否尝试下一个X。如果决定进行，还要决定是否匹配第三个X，第四个X，如此继续。每次选择，其实就是做一个标记，用于提示此处还有另一个可能的选择，保留起来以备用。在回溯的过程中要考虑两个要点：哪个分支应当首先选择？回溯的时候使用的是哪个（或者是哪些个）之前保存的分支?
第一个问题是按下面这条重要原则来选择的:
如果需要在“进行尝试”和“路过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“路过尝试”.
第二个问题是按以下这条原则:
距离当前最近储存的选项就是当本地失败强制回溯时返回的。使用的原则是LIFO（last in first out，后进先出）.
我们先来看几个在道路中做标记的例子:
1、未进行回溯的匹配 。
用[ab?c]来匹配“abc”。[a]匹配之后，匹配的当前状态如下:
| “a↑bc” 。 |
a↑b?c 。 |
现在轮到[b?]了，正则引擎需要决定：是需要尝试[b]呢，还是跳过？因为[？]是匹配优先的，它会尝试匹配。但是，为了确保在这个尝试最终失败之后能够恢复，引擎会把:
| “a↑bc” 。 |
ab?↑c 。 |
添加到备用状态序列中。也就是说，稍后引擎可能从下面的位置继续匹配：从正则表达式中的[b?]之后，字符串的c之前（也就是说当前的位置）匹配。这实际上就是跳过[b]的匹配，而问题容许这样做。引擎做好标记后，就会继续向前检查[b]。在示例中，它能够匹配，所以新的当前状态变为:
| “ab↑c” 。 |
ab?↑c 。 |
最终的[c]也能成功匹配，所以整个匹配完成。备用状态不再需要了，所以不再保存它们.
2、进行了回溯的匹配 。
下面要匹配的文本是“ac”，在尝试[b]之前，一切都与之前的过程相同。显然，这次[b]无法匹配。也就是说，对[……？]进行尝试的路走不通了。因为有一个备用状态，这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯，也就是说，把“当前状态”切换为最近保存的状态.
| “a↑c” 。 |
ab?↑c 。 |
在[b]尝试之前保存的尚未尝试的选项。这时候，[c]可以匹配c，所以整个匹配宣告完成.
3、不成功的匹配 。
现在要匹配的文本是“abx”。在尝试[b]以前，因为存在问号，保存了这个备用状态:
| “a↑bx” 。 |
ab?↑c 。 |
[b]能够匹配，但这条路往下却走不通了，因为[c]无法匹配x。于是引擎会回溯到之前的状态，“交还”b给[c]来匹配。显然，这次测试也失败了。如果还有其他保存的状态，回溯会继续进行，但是此时不存在其他状态，在字符串中当前位置开始的整个匹配也就宣告失败.
目前对正则表达式的回溯只能理解这么多，以后我再慢慢补充吧！ 。
最后此篇关于正则表达式之回溯的文章就讲到这里了,如果你想了解更多关于正则表达式之回溯的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
26
4
0
我正在用 yacc/bison 编写一个简单的计算器。 表达式的语法看起来有点像这样: expr : NUM | expr '+' expr { $$ = $1 + $3; } | expr '-'
我开始学习 lambda 表达式，并在以下情况下遇到了以下语句: interface MyNumber { double getValue(); } MyNumber number; nu
这两个 Linq 查询有什么区别: var result = ResultLists().Where( c=> c.code == "abc").FirstOrDefault(); // vs. va
如果我们查看 draft C++ standard 5.1.2 Lambda 表达式 段 2 说(强调我的 future ): The evaluation of a lambda-expressio
我使用的是 Mule 4.2.2 运行时、studio 7.5.1 和 Oracle JDK 1.8.0_251。 我在 java 代码中使用 Lambda 表达式，该表达式由 java Invoke
我是 XPath 的新手。我有网页的html源 http://london.craigslist.co.uk/com/1233708939.html 现在我想从上面的页面中提取以下数据 完整日期 电子
已关闭。这个问题是 off-topic 。目前不接受答案。 想要改进这个问题吗？ Update the question所以它是on-topic用于堆栈溢出。 已关闭10 年前。 Improve th
我将如何编写一个 Cron 表达式以在每天上午 8 点和下午 3:30 触发？我了解如何创建每天触发一次的表达式，而不是在多个设定时间触发。提前致谢 最佳答案 你应该只使用两行。 0 8 * * *
这个问题已经有答案了: What do 3 dots next to a parameter type mean in Java? (9 个回答) varargs and the '...' argu
我是 python 新手，在阅读 BeautifulSoup 教程时，我不明白这个表达式“[x for x in titles if x.findChildren()][:-1]”我不明白？你能解释一
(?:) 这是一个有效的 ruby 正则表达式，谁能告诉我它是什么意思？ 谢谢 最佳答案 正如其他人所说，它被用作正则表达式的非捕获语法，但是，它也是正则表达式之外的有效 ruby 语法。 在
这个问题在这里已经有了答案: Why does ++[[]][+[]]+[+[]] return the string "10"? (10 个答案) 关闭 8 年前。 谁能帮我处理这个 JavaSc
这个问题在这里已经有了答案: What is the "-->" operator in C++? (29 个答案) Java: Prefix/postfix of increment/decrem
这个问题在这里已经有了答案: List comprehension vs. lambda + filter (16 个答案) 关闭 10 个月前。 我不确定我是否需要 lambda 或其他东西。但是，
C 中的 assert() 函数工作原理对我来说就像一片黑暗的森林。根据这里的答案https://stackoverflow.com/a/1571360 ，您可以使用以下构造将自定义消息输出到您的断言
在this页，John Barnes 写道: If the conditional expression is the argument of a type conversion then effec
我必须创建一个调度程序，它必须每周从第一天上午 9 点到第二天晚上 11 点 59 分运行 2 天(星期四和星期五)。为此，我需要提供一个 cron 表达式。 0-0 0-0 9-23 ? * THU
我正在尝试编写一个 Linq 表达式来检查派生类中的属性，但该列表由来自基类的成员组成。下面的示例代码。以“var list”开头的 Process 方法的第二行无法编译，但我不确定应该使用什么语法来
此 sed 表达式将输入字符串转换为两行输出字符串。两条输出行中的每一行都由输入的子串组成。第一行需要转换成大写: s:random_stuff\(choice1\|choice2\){\([^}]*
我正在使用 Quartz.Net 在我的应用程序中安排我的工作。我只是想知道是否可以为以下场景构建 CRON 表达式: Every second between 2:15AM and 5:20AM 最
我是一名优秀的程序员,十分优秀！