图3-1 逆序环视匹配原理图
正则表达式“(?<=SubExp1)SubExp2”的匹配过程,可分为主匹配流程和子匹配流程两个流程,主匹配流程如下图所示。
图3-2 主匹配流程图
主匹配流程:
1、 由位置0处向右尝试匹配,在找到满足“(?<=SubExp1)”最小长度要求的位置前,匹配一定是失败的,直到找到这样一个的位置x,x满足“(?<=SubExp1)”最小长度要求;
2、 从位置x处向左查找满足“SubExp1”最小长度要求的位置y;
3、 由“SubExp1”从位置y开始向右尝试匹配,此时进入一个独立的子匹配过程;
4、 如果“SubExp1”在位置y处子匹配还需要下一轮子匹配,则再向左查找一个y'',也就是y-1重新进入独立的子匹配过程,如此循环,直到不再需要下一轮子匹配,子匹配成功则进入步骤5,最终匹配失败则报告整个表达式匹配失败;
5、 “(?<=SubExp1)”成功匹配后,控制权交给后面的子表达式“SubExp2”,继续尝试匹配,直到整个表达式匹配成功或失败,报告在位置x处整个表达式匹配成功或失败;
6、 如有必要,继续查找下一位置x'',并开始新一轮尝试匹配。
子匹配流程如下图所示。
图3-3 子匹配流程图
子匹配过程:
1、 进入子匹配后,源字符串即已确定,也就是位置y和位置x之间的子字符串,而此时的正则表达式则变成了“^SubExp1$”,因为在这一轮子匹配当中,一旦匹配成功,则匹配开始位置一定是y,匹配结束位置一定是x;
2、 子表达式长度固定时,要么匹配成功,要么匹配失败,返回匹配结果,并且不需要下一轮子匹配;
3、 子表达式长度不固定时,区分是非贪婪模式还是贪婪模式;
4、 如果是非贪婪模式,匹配失败,报告失败,并且要求进行下一轮子匹配;匹配成功,丢弃所有回溯状态,报告成功,并且不再需要尝试下一轮子匹配;
5、 如果是贪婪模式,匹配失败,报告失败,并且要求进行下一轮子匹配;匹配成功,丢弃所有回溯状态,报告成功,记录本次匹配成功内容,并且要求尝试下一轮子匹配,直到取得最长匹配为止;
在特定的一轮匹配中,x的位置是固定的,而逆序环视中的子表达式“SubExp1”,在报告最终的匹配结果前,匹配开始的位置是不可预知的,需要经过一轮以上的子匹配才能确定,但匹配结束的位置一定是位置x。
当然,这只是针对特定的一轮匹配而言的,当这轮匹配失败,正则引擎传动装置会向前传动,使x=x+1,再进入下一轮匹配尝试,直到整个表达式报告匹配成功或失败为止。
至此逆序环视的匹配原理已