正则表达式手册.pptVIP

两种不同引擎 qed--erep--Egrep awk\lex sed POSIX Perl 正则的起源与流派 DFA Deterministic finite automaton 确定型有穷自动机 NFA Non-deterministic finite automaton　非确定型有穷自动机 Traditional NFA POSIX NFA 引擎类型 程序 DFA Awk(多数版本)、egrep(多数版本)、flex、lex、Mysql 传统NFA GUN Emacs、JAVA、GREP(多数版本)、less、more、PREL、PHP(3套)、Python、ruby、sed(多数版本)、vi POSIX NFA DFA/NFA混合 Gun awk、gun grep/egrep DFA与NFA的区别 DFA引擎因为不需要回溯，所以匹配快速，但不支持捕获组，所以也就不支持反向引用和$number这种引用方式，目前使用DFA引擎的语言和工具主要有awk、egrep?和 lex。 POSIX NFA主要指符合POSIX标准的NFA引擎，它的特点主要是提供longest-leftmost匹配，也就是在找到最左侧最长匹配之前，它将继续回溯。同DFA一样，非贪婪模式或者说忽略优先量词对于POSIX NFA同样是没有意义的。 大多数语言和工具使用的是传统型的NFA引擎，它有一些DFA不支持的特性： 捕获组、反向引用和$number引用方式； 　　环视(Lookaround，(?=…)、(?!…)、(?=…)、(?!…)) 　　忽略优化量词（??、*?、+?、{m,n}?、{m,}?） 　　占有优先量词（?+、*+、++、{m,n}+、{m,}+，目前仅Java和PCRE支持），固化分组(?…)。 本次培训只讨论标准NFA引擎 匹配基础规则 有限选择最左端匹配结果 标准量词优先匹配 为啥要了解“这么深入”？ 网页小偷程序(100k内容 PHP就超时) url 重写 (apache nginx对url处理了2ms) 日志分析 (1G日志处理了1天) 想自己写个像python、php一样的语言 想开发自己的DB，想知道DB语法分析器执行原理 本来就是个爱钻研的人 遇到以上情况，或者符合其中一条的，请继续 字符串组成 cf 位置0 位置1 位置2 字符1 字符0 占有字符与零宽度 正则表达式匹配过程中，如果子表达式匹配到的是字符内容，而非位置，并被保存到最终的匹配结果中，那么就认为这个子表达式是占有字符的；如果子表达式匹配的仅仅是位置，或者匹配的内容并不保存到最终的匹配结果中，那么就认为这个子表达式是零宽度的。 占有字符是互斥的，零宽度是非互斥的。也就是一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配。 控制权和传动 正则的匹配过程，通常情况下都是由一个子表达式（可能为一个普通字符、元字符或元字符序列组成）取得控制权，从字符串的某一位置开始尝试匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的。如正则表达式： (子表达式一)(子表达式二) 假设(子表达式一)为零宽度表达式，由于它匹配开始和结束的位置是同一个，如位置0，那么(子表达式二)是从位置0开始尝试匹配的。 假设(子表达式一)为占有字符的表达式，由于它匹配开始和结束的位置不是同一个，如匹配成功开始于位置0，结束于位置2，那么(子表达式二)是从位置2开始尝试匹配的。 而对于整个表达式来说，通常是由字符串位置0开始尝试匹配的。如果在位置0开始的尝试，匹配到字符串某一位置时整个表达式匹配失败，那么引擎会使正则向前传动，整个表达式从位置1开始重新尝试匹配，依此类推，直到报告匹配成功或尝试到最后一个位置后报告匹配失败。 简单的匹配过程 源字符串：abc 正则表达式：abc 匹配过程： 首先由字符“a”取得控制权，从位置0开始匹配，由“a”来匹配“a”，匹配成功，控制权交给字符“b”；由于“a”已被“a”匹配，所以“b”从位置1开始尝试匹配，由“b”来匹配“b”，匹配成功，控制权交给“c”；由“c”来匹配“c”，匹配成功。 此时正则表达式匹配完成，报告匹配成功。匹配结果为“abc”，开始位置为0，结束位置为3。 含有匹配优先量词的匹配过程(成功) 源字符串：abc 正则表达式：ab?c 量词“?”属于匹配优先量词，在可匹配可不匹配时，会先选择尝试匹配，只有这种选择会使整个表达式无法匹配成功时，才会尝试让出匹配到的内容。这里的量词“?”是用来修饰字符“b”的，所以“b?”是一个整体。 匹配过程： 首先由字符“a”取得控制权，从位置0