正则表达式匹配原理

前端之家收集整理的这篇文章主要介绍了正则表达式匹配原理前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

表达式的匹配原理

Created Friday 02 August 2013

优先选择最左端的匹配结果

起始位置最靠左的匹配总是优先于其他可能的匹配结果。这条规则并没有规定优先的匹配结果的长度,只是规定在所有可能的匹配结果中,优先选择开始位置最左端的。实际上,因为可能有多个匹配结果的起始位置都在最左端,也许我们应该把这条规则中的“某个匹配结果”改为“该匹配结果”。
匹配先从需要查找的字符串的起始位置尝试匹配。
尝试匹配的意思是,在当前位置测试整个正则表达式能匹配的每样文本。如果在当前位置测试了所有的可能之后不能找到匹配结果,就需要从字符串的第二个字符之前的位置开始重新尝试。在找到匹配结果以前必须在所有的位置重复此过程。只有在尝试过所有的起始位置都不能找到匹配结果的情况下,才能报告“匹配失败”。

正则引擎中的零件分为几类:文字字符(literal character)、量词(qualifiers)、字符组(character classes)和括号等等。

标准量词是匹配优先的

标准匹配量词(?、*、+以及{min,max})都是匹配优先的。它们总是希望获得最长的匹配。匹配优先量词之所以得名,是因为它们总是或尝试匹配多余匹配成功下限的字符。
例如\b\w+s\b可以匹配regexes,按照匹配优先则\w+会匹配regexes,但这样s就无法匹配,因此\w+会匹配regexe以达到其他部分能够成功匹配。

NFA:表达式主导

如果表达式不匹配,引擎就会尝试另一种可能,如此继续下去,直到匹配成功或是报告失败。表达式中的控制权在不同的元素之前转换,所以称为表达式主导。
实质上,在表达式主导的匹配过程中,每一个子表达式都是独立的。这不同于反向引用,子表达式之间不存在内在联系,而只是整个正则表达式的各个部分。在子表达式于正则表达式的控制结构(多选分支、括号以及匹配量词)的层级关系(layout)控制了整个匹配过程。

DFA:文本主导

与表达式主导的NFA不同,DFA引擎扫描字符串时,会记录“当前有效”的所有匹配可能。它扫描字符串中的每个字符都对引擎进行了控制。在本例中,某个未完成的匹配也许是任意多个匹配的开始,不合适的匹配能在扫描后继文字时被除去。

回溯的两个要点

1.面对众多选择时哪个分支应当首先选择?

如果需要在“进行尝试”和“跳过尝试”之间选择,对于优先匹配量词,引擎会优先选择“进行尝试”,而对于忽略优先量词,会选择“跳过尝试”。

2.回溯进行时,应该选取哪个保存的状态?

距离当前最近存储的选项就是当本地失败强制回溯时返回的。使用的原则是LIFO(last in first out)。

原文链接:https://www.f2er.com/regex/362690.html

猜你在找的正则表达式相关文章