正则表达式引擎之简单匹配过程详细剖析解释

《正则表达式引擎之简单匹配过程详细剖析解释》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、正则表达式引擎之简单匹配过程详细剖析解释┏━DFA确定型有穷自动机正则表达式引擎━┫┏━TraditionalNFA:传统型┗━NFA非确定型有穷自动机━┫┗━POSIXNFA:IEEE可移植性标准英文释义：DFA:Deterministicfiniteautomaton.NFA:Non-deterministicfiniteautomaton.POSIX:PortableOperatingSystemInterfaceofUnix.DFA引擎因为不需要回溯，所以匹配快速，但不支持捕获组，所以也就不支持反向引用和$n

2、umber这种引用方式，目前使用DFA引擎的语言和工具主要有awk、egrep和lex。POSIXNFA主要指符合POSIX标准的NFA引擎，它的特点主要是提供longest-leftmost匹配，也就是在找到最左侧最长匹配之前，它将继续回溯。同DFA一样，非贪婪模式或者说忽略优先量词对于POSIXNFA同样是没有意义的。大多数语言和工具使用的是传统型的NFA引擎，它有一些DFA不支持的特性：　　捕获组、反向引用和$number引用方式；　　环视(Lookaround，(?<=…)、(?

3、))，或称预搜索；　　忽略优化量词（??、*?、+?、{m,n}?、{m,}?），或称非贪婪模式；　　占有优先量词（?+、*+、++、{m,n}+、{m,}+），目前仅Java和PCRE支持，固化分组(?>…)。预备知识字符串组成对于字符串“ABC”而言，包括A、B、C三个字符和0、1、2、3四个数字位置。0A1B2C3占有字符和零宽度正则表达式匹配过程中，如果子表达式匹配到的是字符内容，而非位置，并被保存到最终的匹配结果中，那么就认为这个子表达式是占有字符的；如果子表达式匹配的仅仅是位置，或者匹配的内容并不保存到最

4、终的匹配结果中，那么就认为这个子表达式是零宽度的。占有字符是互斥的，零宽度是非互斥的。也就是一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配。控制权和传动正则的匹配过程，通常情况下都是由一个子表达式（可能为一个普通字符、元字符或元字符序列组成）取得控制权，从字符串的某一位置开始尝试匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的。如正则表达式：(子表达式一)(子表达式二)假设(子表达式一)为零宽度表达式，由于它匹配开始和结束的位置是同一个，如位置0

5、，那么(子表达式二)是从位置0开始尝试匹配的。假设(子表达式一)为占有字符的表达式，由于它匹配开始和结束的位置不是同一个，如匹配成功开始于位置0，结束于位置2，那么(子表达式二)是从位置2开始尝试匹配的。而对于整个表达式来说，通常是由字符串位置0开始尝试匹配的。如果在位置0开始的尝试，匹配到字符串某一位置时整个表达式匹配失败，那么引擎会使正则向前（右）传动，整个表达式从位置1开始重新尝试匹配，依此类推，直到报告匹配成功或尝试到最后一个位置后报告匹配失败。正则表达式简单匹配过程详解基础匹配过程源字符串：“ABC”0A1

6、B2C3正则表达式：/ABC/ABC首先由字符/A/取得控制权，从位置0开始匹配，由/A/来匹配“A”，匹配成功，控制权交给字符/B/；由于“A”已被/A/匹配，所以/B/从位置1开始尝试匹配，由/B/来匹配“B”，匹配成功，控制权交给/C/；由/C/来匹配“C”，匹配成功。此时正则表达式匹配完成，报告匹配成功。匹配结果为“ABC”，开始位置为0，结束位置为3。含有匹配优先量词的匹配过程——匹配成功（一）源字符串：“ABC”0A1B2C3正则表达式：/AB?C/AB?C量词/?/属于匹配优先量词，在可匹配可不匹配时，

7、会先选择尝试匹配，只有这种选择会使整个表达式无法匹配成功时，才会尝试让出匹配到的内容。这里的量词/?/是用来修饰字符/B/的，所以/B?/是一个整体。/B?/的意思就是：首先找出可匹配的（该整体），如找不到可匹配的，也可以忽略。首先由字符/A/取得控制权，从位置0开始匹配，由/A/来匹配“A”，匹配成功，控制权交给字符/B?/；由于/?/是匹配优先量词，所以会先尝试进行匹配，由/B?/来匹配“B2”，匹配成功，控制权交给/C/，同时记录一个备选状态；由/C/来匹配“C”，匹配成功。记录的备选状态丢弃。此时正则表达式匹

8、配完成，报告匹配成功。匹配结果为“ABC”，开始位置为0，结束位置为3。含有匹配优先量词的匹配过程——匹配成功（二）源字符串：“ABC”0A1C2正则表达式：/AB?C/AB?C首先由字符/A/取得控制权，从位置0开始匹配，由/A/来匹配“A”，匹配成功，控制权交给字符/B?/；先尝试进行匹配，由/B?/来匹配“C”，同时记录一个备选状态，匹配