走进RegExp(1).pptx

走进RegExp,什么是RegExpRegExp的基本语法RegExp的匹配原理RegExp的应用,什么是RegExp,正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑（匹配）。,普通字符/创建正则模式，不区分大小写varstr=ThisisaBox!;/创建要比对的字符串alert(pattern.test(str);/通过test()方法验证是否匹配/*使用字面量方式的test方法示例*/varpattern=/box/i;/创建正则模式，不区分大小写varstr=ThisisaBox!;alert(pattern.test(str);/*使用一条语句实现正则匹配*/alert(/box/i.test(ThisisaBox!);/模式和字符串替换掉了两个变量/*使用exec返回匹配数组*/varpattern=/box/i;varstr=ThisisaBox!;alert(pattern.exec(str);/匹配了返回数组，否则返回null,RegExp的匹配原理,正则表达式引擎正则引擎大体上可分为不同的两类：DFA（确定型有穷自动机）和NFA（非确定型有穷自动机），而NFA又基本上可以分为传统型NFA和POSIXNFA。DFA：文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。NFA：正则式去比文本，拿到一个字符，就把它跟正则式比较，匹配就记下来，然后接着往下匹配。一旦不匹配，就把刚拿的这个字符丢掉，一个个的丢掉，直到回到上一次匹配的地方。,引擎间的区别,引擎区别的例子：正则式：/perl|perlman/文本：perlmanbook如果是NFA，则以正则式为导向，手里捏着正则式，眼睛看着文本，一个字符一个字符的吃，吃完perl以后，跟第一个子正则式/perl/已经匹配上了，于是记录在案，往下再看，吃进一个m，这下糟了，跟子式/perl/不匹配了，于是把m吐出来，向上汇报说成功匹配perl，不再关心其他，也不尝试后面那个子正则式/perlman/，自然也就看不到那个更好的答案了。如果是DFA，它是以文本为导向，手里捏着文本，眼睛看着正则式，一口一口的吃。吃到/p/，就在手里的p上打一个钩，记上一笔，说这个字符已经匹配上了，然后往下吃。当看到/perl/之后，DFA不会停，会尝试再吃一口。这时候，第一个子正则式已经山穷水尽了，没得吃了，于是就甩掉它，去吃第二个子正则式的/m/。这一吃好了，因为又匹配上了，于是接着往下吃。直到把正则式吃完，成功匹配了perlman。,由于大多数语言和工具使用的是传统型的NFA引擎，所以接下来讲解的都是使用传统的NFA引擎匹配的正则。,字符串的组成,对于字符串abc而言，包括3个字符和4个位置,预备知识,占有字符和零宽度,占有字符：若子表达式匹配到的是字符内容，而非位置，并被保存到最终的匹配结果中，那么就认为这个子表达式是占有字符的。零宽度：如果子表达式匹配的仅仅是位置，或者匹配的内容并不保存到最终的匹配结果中，那么就认为这个子表达式是零宽度的。,注意：一个字符，同一时间只能由一个子表达式匹配一个位置，可以同时由多个零宽度的子表达式匹配,首先由字符“a”取得控制权，从位置0开始匹配，由“a”来匹配“a”，匹配成功。控制权交给字符b?；先尝试进行匹配，由“b?”来匹配“b”，同时记录一个备选状态，匹配成功。控制权交给“c”；由“c”来匹配“c”，匹配成功，记录的备选状态丢弃。,RegExp简单匹配过程,含有匹配优先量词匹配成功,首先由字符“a”取得控制权，从位置0开始匹配，由“a”来匹配“a”，匹配成功。控制权交给字符b?；先尝试进行匹配，由“b?”来匹配“b”，同时记录一个备选状态，匹配成功。控制权交给“c”；由“c”来匹配“d”，匹配失败，此时进行回溯，找到记录的备选状态，“b?”忽略匹配，即“b?”不匹配“b”，让出控制权。控制权交给“c”；由“c”来匹配“b”，匹配失败。此时第一轮匹配尝试失败。,含有匹配优先量词匹配失败,首先由字符“a”取得控制权，从位置0开始匹配，由“a”来匹配“a”，匹配成功。控制权交给字符“b?”；先尝试忽略匹配，即“b?”不进行匹配，同时记录一个备选状态。控制权交给“c”；由“c”来匹配“b”，匹配失败。此时进行回溯，找到记录的备选状态，“b?”尝试匹配，即“b?”来匹配“b”，匹配成功。把控制权交给“c”；由“c”来匹配“c”，匹配成功。,含有忽略优先量词的匹配匹配成功,首先由元字符“”取得控制权，从位置0开始匹配，“”匹配的就是开始位置“位置0”，匹配成功。控制权交给顺序环视“(?=a-z)”，“(?=a-z)”要求它所在位置右侧必须是字母才能匹配成功，同一个位置可以同时由多个零宽度子表达式匹配，所以它也是从位置0尝试进行匹配，位置0的右侧是字符“a”，符合要求，匹配成功。控制权交给“a-z0-9+”，因为“(?=a-z)”只匹配，并不将匹配到的内容保存到最后结果，并且“(?=a-z)”匹配成功的位置是位置0，所以“a-z0-9+”也是从位置0开始尝试匹配的，“a-z0-9+”首先尝试匹配“a”，匹配成功，继续尝试匹配，可以成功匹配接下来的“1”和“2”，此时已经匹配到位置3，位置3的右侧已没有字符。控制权交给“$”；它从位置3开始尝试匹配，它匹配的是结束位置，也就是“位置3”，匹配成功。,零宽度匹配,回溯,NFA引擎最重要的性质是，它会依次处理各个子表达式或组成元素，遇到需要在两个可能成功的可能中进行选择的时候，它会选择其一，同时记住另一个，以备稍后可能的需要。需要做出选择的情形包括量词（决定是否尝试另一次匹配）和多选结构（决定选择哪个多选分支，留下哪个稍后尝试）。不论选择那一种途径，如果它能匹配成功，而且正则表达式的余下部分也成功了，匹配即告完成。如果正则表达式中余下的部分最终匹配失败，引擎会知道需要回溯到之前做出选择的地方，选择其他的备用分支继续尝试。这样，引擎最终会尝试表达式的所有可能途径（或者是匹配完成之前需要的所有途径）。,回溯就像是在道路的每个分岔口留下一小堆面包屑。如果走了死路，就可以照原路返回，直到遇见面包屑标示的尚未尝试过的道路。如果那条路也走不通，你可以继续返回，找到下一堆面包屑，如此重复，直到找到出路，或者走完所有没有尝试过的路。,回溯小例子：字符串：hottonictonight!正则表达式：/to(nite|knight|night)/,“t”字符无法匹配“h”，所以第0个位置失败，一直到第5个位置，“t”匹配“t”，成功。第6个位置“o”匹配“o”，成功。开始3个分支的匹配，分别是/nite/、/knight/、/night/，由于没有优先匹配量词，所以按从左到右的顺序匹配。匹配第一个分支/nite/，“n”匹配“n”，成功。直到t匹配“c”，失败。但是此时并不意味着整个表达式失败，因为还有其他的分支（之前预留的面包屑）。第二个分支开始匹配，匹配又从第7个位置开始，但是很快就失败了，“k”与“n”不匹配。第三个分支开始匹配，明显成功，则整个表达式匹配成功。如果第三个分支也失败的话，就表明整个表达式匹配失败。,回溯两要点,多个选择时，哪个分支应首先选择若需在“进行尝试”和“跳过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”。对于忽略优先量词，引擎会优先选“跳过尝试”。回溯进行时，应选哪个保存状态距离当前最近的选项就是当本地失败强制回溯时返回的。使用原则是LIFO（后进先出）。,备用状态,用NFA正则表达式的术语来说，那些面包屑相当于“备用状态”。它们用来标记：在需要的时候，匹配可以从这里重新开始尝试。备用状态保存了两个位置：正则表达式中的位置未尝试的分支在字符串中的位置,备用状态例子,未进行回溯匹配：,当前是“a”已经匹配完了的状态,轮到了“b?”，引擎决定尝试匹配，但为了确保这个尝试最终失败后能够恢复，引擎把“b?”添加到备用状态中，稍后引擎还可以从正则表达式“b?”之后，字符串b之前（当前位置）匹配，即“b?”没有匹配，“？”可以这样。,最后引擎放下面包屑后，继续向前，检测“b”，在例子中可以匹配，所以新状态变成下面的，最终“c”也匹配成功，整个匹配成功，所以备用状态不需要了，便不再保存它们。,环视匹配,顺序肯定环视(?=Expression)当子表达式Expression匹配成功时，(?=Expression)匹配成功，并报告(?=Expression)匹配当前位置成功。顺序否定环视(?!Expression)当子表达式Expression匹配成功时，(?!Expression)匹配失败；当子表达式Expression匹配失败时，(?!Expression)匹配成功，并报告(?!Expression)匹配当前位置成功；,捕获组,什么是捕获组捕获组就是把正则表达式中子表达式匹配的内容，保存到内存中以数字编号或显式命名的组里，方便后面引用。当然，这种引用既可以是在正则表达式内部，也可以是在正则表达式外部。捕获组有两种形式，一种是普通捕获组，另一种是命名捕获组，通常所说的捕获组指的是普通捕获组。语法如下：普通捕获组：(Expression)命名捕获组：(?Expression)普通捕获组在大多数支持正则表达式的语言或工具中都是支持的，而命名捕获组目前只有.NET、PHP、Python等部分语言支持。,捕获组编号规则编号规则指的是以数字为捕获组进行编号的规则。普通捕获组编号规则若没有显式为捕获组命名，即没有使用命名捕获组，那么需要按数字顺序来访问所有捕获组。在只有普通捕获组的情况下，捕获组的编号是按照“(”出现的顺序，从左到右，从1开始进行编号的。正则表达式：(d4)-(d2-(dd),命名捕获组编号规则命名捕获组通过显式命名，可以通过组名方便的访问到指定的组，而不需要去一个个的数编号，同时避免了在正则表达式扩展过程中，捕获组的增加或减少对引用结果导致的不可控。不过容易忽略的是，命名捕获组也参与了编号的，在只有命名捕获组的情况下，捕获组的编号也是按照“(”出现的顺序，从左到右，从1开始进行编号的。正则表达式：(?d4)-(?d2-(?dd),捕获组的引用对捕获组的引用一般有以下几种：1)正则表达式中，对前面捕获组捕获的内容进行引用，称为反向引用；2)正则表达式中，(?(name)yes|no)的条件判断结构；3)在程序中，对捕获组捕获内容的引用。反向引用捕获组捕获到的内容，不仅可以在正则表达式外部通过程序进行引用，也可以在正则表达式内部进行引用，这种引用方式就是反向引用。