正则表达式的匹配原理

时间:2022-12-16 05:56:54

匹配原则

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

废话不多说,上题:
“indicates cat”用cat进行匹配结果就是indicates。
“indicates cat fat”用/fat|cat/进行匹配结果就是indicates,因为正则表达式的每一次尝试都要进行到底。

标准的匹配量词(*、+、?、{m,n})优先匹配

标准匹配两次的结果“可能”并非所有可能中最长的,但是它们总是尝试匹配尽可能多的字符,直到匹配上线为止。如果最终结果并不是可能中最长的,原因是匹配字符过多导致匹配失败。
举个栗子,/\b\w+s\b/中,对于单词his,\w能够匹配整个单词,但是,这样的话s就没办法匹配了,这个时候\w只能匹配到hi,把s留给s\b。

过度的优先匹配

这里需要注意的是“尽可能匹配”“强迫释放”

举个栗子/^.*([0-9][0-9])/匹配”abcdefg12hijkl”。其中,/.*/匹配整个字符串,然后,第一个/[0-9]/的匹配强迫/.*/ 释放字符l(最后一个字符),但是不能匹配数字成功,/.*/ 就继续释放字符,指导匹配到2,但后第二个/[0-9]/ 有强迫其释放,从而匹配成功。
再举个栗子,/^.*[0-9]+/匹配”abcdefg123”的结果是3,而不是123.

NFA引擎——表达式主导

回溯会依次处理各个子表达式或这组成元素,遇到两个可能中进行选择的时候,会选择其一,记住另一个,以备稍后可能的需要。

举个栗子使用/to(nite|knight|night)/ 匹配文本”tonight”,从t开始匹配,然后匹配o,然后尝试匹配nite,不成功,回退到to,开始匹配knight,不成功,再回退到to,匹配night,成功。

要点:面对选择,那个分支优先选择?
如果在“进行尝试”和“跳过尝试”之间选择,对于匹配优先量词,引擎会优先选择“进行尝试”,而对于忽略优先量词(也就是懒惰匹配),会选择“跳过尝试”。

正则表达式的匹配原理
正则表达式的匹配原理
正则表达式的匹配原理

DFA引擎——文本主导

正则表达式的匹配原理