Open ditunes opened 8 years ago
? * + {min,max}都是匹配优先
?
*
+
{min,max}
+? *? ?? 只尽量少匹配符合要求的字符,先执行忽略。除非下一个表达式无法匹配字符发生回溯的时候才执行匹配。
+?
*?
??
?+
*+
++
{m,n}+
(?>表达式)
总的而言在匹配位置离开占有优先或固化分组表达式的时候其备用状态将给予清除,如正则表达式(?>.+) 它属于匹配优先,备用状态栈中会存放多个备用状态(即表达式下一个位置和文本中执行与当前表达式匹配的位置)。一旦成为固化分组,则栈内所有备用状态都将被清除。占有优先量词也是类似(?>.+)=(.)++. 放弃备用状态会产生什么影响呢?
匹配位置离开占有优先或固化分组表达式的时候其备用状态将给予清除
(?>.+)
(.)++
\w+;
subject
;
\w++
(?>w+)
.*123
ab 123 ab
(?>.*) 123
NFA
DFA
在此可以用如下概念以方便理解: 备用状态:记录正则表达式的当前位置(即标注分支表达式位于整个表达式哪个位置)以及未尝试分支在文本中的位置(即标注该分支表达式要从文本哪个字符开始比较)。 备用状态栈:当表达式存在匹配分支的时候,备用状态会入栈,以备后续执行回溯。 初始状态:记录首次或重新进行文本与表达式匹配时,文本的起始点位置。因为一旦某段文本与表达式匹配失败,则传动装置启动,将继续在文本中前行,再次尝试正则表达式比较。此时初始状态发生变化。如果已经执行到文本末位则认为初始状态不存在,匹配结束。 全局匹配: 只要符合下面任意一条件,全局匹配即成立。
备用状态
备用状态栈
初始状态
全局匹配
有如下正则表达式:a(b|c|d)X 匹配的文本:abM ,_记录了当前表达式or文本的匹配位置。
a(b|c|d)X
abM
_
当正则表达式中的'a'匹配到文本中的'a'之后,正则表达式出现匹配分支即遇可能匹配 b or c or d ,此时将会把可能匹配的备用状态入栈,备用状态、初始状态如下:
b
c
d
引擎继续向前运行,当表达式b和文本'b'匹配上后,a(b|c|d)_X | ab_M接下来就是表达式X与文本的M匹配,因为表达式没有匹配分支,则直接匹配,此时出现不匹配则需要回溯,即备用状态栈出栈,再执行匹配而事实上这次匹配又一次失败
a(b|c|d)_X | ab_M
X
M
以此类推,继续出栈此时匹配仍然失败,那么备用状态栈中已经为空了,此时我们需要变更初始状态了,即将文本_abM转变为a_bM重新执行表达式匹配。
_abM
a_bM
依据此规律直到初始状态为abM_备用状态栈为空,且表达式依然没有全局匹配成功,则表示表达式与文本匹配失败。
abM_
匹配优先的本质是在表达式出现匹配分支的时候优先选择匹配量词最大值进行匹配,而把匹配量词最小值情况放入备用状态栈中。那么忽略优先的情形则是将量词最大值放入备用状态栈中,匹配量词最小值直接进行匹配。我们可以通过*和+元字符来理解
*
+
.+
.*
如正则表达式:^.+[0-9][0-9]文本 abc 123456 abc; 由于.+表示匹配优先,则其会尽力匹配足够多的文本内容。而只匹配一个的情况会成为备用状态。当前正要执行文本c与表达式.+的匹配
^.+[0-9][0-9]
abc 123456 abc
如正则表达式:^.*[0-9][0-9]文本 abc 123456 abc; 由于.*表示匹配优先,则其会尽力匹配足够多的文本内容。而忽略的情况会成为备用状态。当前正要执行文本c与表达式.+的匹配
^.*[0-9][0-9]
*和+的差别无非就是*遇到文本字符时候就出现匹配分支(更多 or 忽略)而+匹配文本字符成功后才出现匹配分支(更多 or end)
正则表达式的匹配原理
正则中的量词
标准量词是匹配优先
?
*
+
{min,max}
都是匹配优先忽略优先量词
+?
*?
??
只尽量少匹配符合要求的字符,先执行忽略。除非下一个表达式无法匹配字符发生回溯的时候才执行匹配。占有优先量词和固化分组
?+
*+
++
{m,n}+
(?>表达式)
总的而言在
匹配位置离开占有优先或固化分组表达式的时候其备用状态将给予清除
,如正则表达式(?>.+)
它属于匹配优先,备用状态栈中会存放多个备用状态(即表达式下一个位置和文本中执行与当前表达式匹配的位置)。一旦成为固化分组,则栈内所有备用状态都将被清除。占有优先量词也是类似(?>.+)
=(.)++
. 放弃备用状态会产生什么影响呢?\w+;
匹配subject
如果正常匹配,需要从subject尾部不断回溯以匹配;
.如果\w++
or(?>w+)
则无需回溯,一次就发现失败。.*123
是可以匹配ab 123 ab
的,但是(?>.*) 123
则直接无法匹配。因为基于匹配优先会,一旦没有回溯匹配位置就再也回不去了。NFA与DFA
NFA
非确定型有穷自动机,其以表达式为主导(表达式决定了文本是否匹配)的匹配引擎,DFA
确定型有穷自动机,其以文本为主导(文本决定了表达式的取舍与选择)的匹配引擎。NFA的 匹配的原理
在此可以用如下概念以方便理解:
备用状态
:记录正则表达式的当前位置(即标注分支表达式位于整个表达式哪个位置)以及未尝试分支在文本中的位置(即标注该分支表达式要从文本哪个字符开始比较)。备用状态栈
:当表达式存在匹配分支的时候,备用状态会入栈,以备后续执行回溯。初始状态
:记录首次或重新进行文本与表达式匹配时,文本的起始点位置。因为一旦某段文本与表达式匹配失败,则传动装置启动,将继续在文本中前行,再次尝试正则表达式比较。此时初始状态发生变化。如果已经执行到文本末位则认为初始状态不存在,匹配结束。全局匹配
: 只要符合下面任意一条件,全局匹配即成立。多选结构下的正则匹配流程
有如下正则表达式:
a(b|c|d)X
匹配的文本:abM
,_
记录了当前表达式or文本的匹配位置。当正则表达式中的'a'匹配到文本中的'a'之后,正则表达式出现匹配分支即遇可能匹配
b
orc
ord
,此时将会把可能匹配的备用状态入栈,备用状态、初始状态如下:引擎继续向前运行,当表达式
b
和文本'b'匹配上后,a(b|c|d)_X | ab_M
接下来就是表达式X
与文本的M
匹配,因为表达式没有匹配分支,则直接匹配,此时出现不匹配则需要回溯,即备用状态栈出栈,再执行匹配而事实上这次匹配又一次失败以此类推,继续出栈此时匹配仍然失败,那么备用状态栈中已经为空了,此时我们需要变更初始状态了,即将文本
_abM
转变为a_bM
重新执行表达式匹配。依据此规律直到初始状态为
abM_
备用状态栈为空,且表达式依然没有全局匹配成功,则表示表达式与文本匹配失败。回溯与匹配优先、忽略优先
匹配优先的本质是在表达式出现匹配分支的时候优先选择匹配量词最大值进行匹配,而把匹配量词最小值情况放入备用状态栈中。那么忽略优先的情形则是将量词最大值放入备用状态栈中,匹配量词最小值直接进行匹配。我们可以通过
*
和+
元字符来理解.+
表示一个或多个匹配且为匹配优先,此时最大值为尽可能多个,最小值为1个,一旦表达式匹配到了文本中字符则表达式面临两个选择:.+
表达式匹配(因为已经符合量词最小值的要求),进入表达式的下一个位置.+
的匹配,尽量匹配更多个.*
表示0个或匹配尽量多个,此时最大值为尽可能多个,最小值为0个即忽略当前匹配。一旦表达式开始与文本字符进行正则表达式匹配时候,表达式有两个选择:.*
进行匹配且尽量匹配多个(最大值).*
进行匹配直接略过进入表达式的下一个位置(最小值)。如正则表达式:
^.+[0-9][0-9]
文本abc 123456 abc
; 由于.+
表示匹配优先,则其会尽力匹配足够多的文本内容。而只匹配一个的情况会成为备用状态。当前正要执行文本c
与表达式.+
的匹配如正则表达式:
^.*[0-9][0-9]
文本abc 123456 abc
; 由于.*
表示匹配优先,则其会尽力匹配足够多的文本内容。而忽略的情况会成为备用状态。当前正要执行文本c
与表达式.+
的匹配*
和+
的差别无非就是*
遇到文本字符时候就出现匹配分支(更多 or 忽略)而+
匹配文本字符成功后才出现匹配分支(更多 or end)