Learning notes for mastering Reg

构建扫描器程序的两个重要方法

boolean hitEnd()

• 返回true，说明结尾有更多的字符可能会改变本次的匹配结果(匹配成功变成失败，失败变成成功，或者匹配内容发生改变)
• 返回false，说明结尾有更多的字符不会改变本次的匹配结果

---

boolean requireEnd()
只有匹配成功该方法的返回值才有意义

• 返回true，说明结尾有更多的字符可能会使得本次匹配失败
• 返回false，说明结尾有更多的字符不可能会使得本次匹配失败，虽然可能会影响本次匹配的细节，如匹配内容发生改变

消除循环

(normal)*(special(normal)*)*

• 防止special部分造成的循环

---

special要能写成start(middle)*end

1. start-end 和middle 匹配的是无交集的两部分
2. start和end是固化的文本，且start和end至少存在一部分,middle可不存在

• start(middle)* 是为了防止此模式匹配成功后，外层(...)*表达式还能够继续匹配，导致内部和外部递归匹配一段文本,加上start，当middle回溯文本时，外部无法再匹配内部交还的文本
• (middle)*end 是为了防止本次的匹配成功，如果本次不能匹配成功，那么外部也无法继续应用该表达式了，

---

• 防止normal部分造成的循环

---

• 把start看成special，middle看成normal，也就保证了(special(normal))不会造成无休止的匹配了,这是(start(middle)end)缺少end的一种形式

表达式的优化

• 对于(.*)(Suffix)这种以.*匹配优先开始的表达式通常可以在开头使用行开头锚点标记^,
  得到^(.*)(Suffix)

• 这样传动装置只会在文本开头应用一次该表达式，因为匹配优先总是能够匹配完全部的文本，当(Suffix)匹配时，会强迫之前的表达式归还文本，所以如果能够匹配成功，(Suffix)匹配的总是文本中最后一个满足的匹配，以后的文本不存在能够与(Suffix)相匹配的了，所以后面的尝试都是多余的，而使用^行锚点标记，传动装置将不会做多余的尝试.

---

• 将结尾部分分散到多选结构内，使用(?:com\b|edu\b|org\b|int\b|net\b|biz\b|coop\b|areo\b)而不使用(?:com|edu|org|int|net|biz|coop|areo)\b，后者每当一个多选分支匹配成功后，将退出多选分支，但是在\b将失败，此时又会回溯，如果将\b添加在多选结构内，则在未退出多选结构就能发现匹配失败，这个优化是有风险的，如果表达式是(?:this|that):则改(?:this:|that:)就违背了将独立文本单独出来的思想，任何的优化都是平等的，可能会因小失大，
• 考虑到如果是位置匹配之类的可以放入到多选结构内，但是如果尾部是$，即行结尾标记，则又将失去行结束锚点的优化，也就是除了一些特殊的位置标记，其他可以放入到多选结构内，而一些单纯的文本则不放入，将他们单独分离出来，可以得到文本中必须出现字符或字符串优化.

---

\G使用之前匹配结束的位置

• regex = "\\G(?:\\d{5})*?(44\\d{3})?"
  如果使用该表达式匹配文本，一旦匹配的文本长度为0，则将不会在进行匹配，因为使用的是之前匹配结束的位置，传动装置将不会驱动，使用引擎能知道下次在该处匹配也得到相同的结果，会无限循环

匹配44开头的5位数美国邮政编码(ZIP Codes)

• 目标文本是类似这样的
  03824531449411615213441829505344272752010217443235
• 匹配的难题是在某次匹配失败时，传动装置会驱动前进一个字符，再次进行匹配，而如果此时的匹配成功显然不是我们需要的，因为这个邮政编码在数据中可能根本不存在，
• 我使用的办法是在进行匹配的开始，要保证左边必须是5的倍数数字，所以使用正则表达式(?<=^(?:\d{5})*)44\d{3},但这将使用逆序环视进行扫描不定长度的文本，一些正则引擎可能不支持，
• 另一个办法是保证数据的协调性，出现匹配错误数据的原因主要是传动装置的驱动，导致了数据的错位，实际上如果不是从5的倍数的位置开始匹配，即使成功，也是没有意义的数据，所以可以使用一些表达式来跳过(匹配)不是44开头的的5位数ZIP Codes，

---

3个办法

• [1235-9]\d{4}|\d[1235-9]\d{3} (如果开头44则失配)
• (?!44)\d{5} (如果开头不是44则匹配)
• (\d{5}*?) 使用忽略优先量词，当我们使用的44\d{3}不能匹配的时候，强制要求该表达式进行匹配，这样就可以进行一次44开头的5位数匹配，失败，则直接跳过(匹配)不需要的5位数，再次进行尝试，

---

总结

• 上面的办法就可以保证每次在需要匹配我们需要的数据的时候，位置是从5的倍数的位置开始匹配的，因为能保证总是能够匹配，

---

匹配失败时候仍然会出现数据的不协调性

• 当最后不存在任何以5的倍数位置开始的44开头的5位数的ZIP Codes时(但存在其他的ZIP Codes)，这个时候会整体匹配失败，接下里，数据的不协调性问题又出现了，
• 接下来由于传动装置的驱动，强制在下一个位置进行尝试匹配，这就导致在不是5的倍数的位置上进行匹配，是没有意义的，
• 所以此时的急救措施可能会对我们要匹配数据的表达式使用可选的匹配——(44\d{3})?，
• 但是这也确实能够解决这个问题，除了第三个表达式不可以，因为他将总是能够成功，可能会匹配0长度文本，仍然导致传动装置的驱动，另外两个的表达式都是匹配优先的，当最后匹配到文本结束时，尝试(44\d{3})?，其只能够成功，所以也就不存在失配导致的数据不协调性了。

---

优缺点

• 即使内容中不存在任何我们需要的44开头的5位数ZIP Codes，但它也总是能够匹配成功，
• 但是却具有较高的匹配速度,因为不需要回溯，匹配过程中也不会有传动装置的驱动

推荐解决方法

• 更加通用的办法是使用\G

正确表达式正确匹配一个字符串

• "(\\.|[^"\\\n])*+"
  该表达式使用占有优先量词纯粹是为了提高报告匹配失败的速度
• "(\\.|[^"\n])*+"
  该表达式必须使用占有优先量词，防止回溯使得第二个分支匹配\

关于正则引擎

• NFA支持一些DFA不支持的功能

1. 捕获型括号
2. 反向引用(是因为不支持1)
3. 忽略优先量词(因为DFA尽量保证匹配当前位置最长的文本,所以没有意义)
4. 所以也不会支持占有优先量词，和固化分组，和3的道理一样
5. 不支持环视

---

• 但是DFA具有匹配效率很快，稳定，总是能得到确定的结果(匹配最左最长的文本)，但其在编译阶段会花费较长的时间和内存
• 传统型的NFA是控制能力最强的正则引擎，因此使用者可以使用该引擎的表达式主导的性质来精确控制匹配过程。

传统型NFA的多选分支

• 它既不是匹配优先的也不是忽略匹配优先的，而是按照表达式在多选分支的顺序逐个尝试，当当前的表达式匹配失败后，将尝试下一个表达式，即为每个表达式匹配开始时候都保存一个备用状态，
• 正是因为如此，所以如果备用的表达式存在多个可以与原文本匹配的可能，一定要控制好顺序，
• 像这样的多选分支没有意义a((ab)\*|a\*)因为第一个子表达式(ab)*永远也不会匹配失败，

一些匹配上的细节

• 关于捕获型括号
  ((regex)?)在这个表达式中存在两个group，其中group1和group2都可能成功捕获到regex匹配的内容，但是group1还可能捕获到长度为0的字符串，但此时，group2没有被应用，其值为NULL

用肯定环视模拟固化分组

当环视成功以后，其中的备用状态将会被丢弃，所以可以使用回溯引用来捕获刚刚环视的内容如(?=(regex))\1,这个时候\1就是一段固定的文本值了，在对文本值\1进行匹配的过程中显然不会保存任何备用状态。所以使用\1的匹配达到了一个固化分组的匹配效果

• (?>regex)可以使用(?=(regex))\1来模拟，但通常固化分组的效率要更高些，因为环视的尝试匹配后，接下来\1还会在重复进行一次匹配，只不过这次将会消费文本.

关于regex测试器

• java和intellij的regex都是采用当前匹配的开始位置
• regexr.com的regex采用之前匹配的结束位置

关于NFA和DFA

• NFA 表达式主导
• DFA 文本主导
• NFA支持忽略优先量词，DFA不支持，
• 对于哪个分支应答首先选择？
  优先量词将采取进行尝试，而忽略优先量词采取跳过尝试
• 备用状态，回溯进行时，应该选取哪个保存的状态？
  当本地失败时将选择最近保存的状态，使用的原则是LIFO(后进先出，类似栈)

简单的判断正则引擎

• 首先如果该引擎支持忽略优先量词，那么基本就能确定这是traditional nfa引擎了，因为忽略优先量词在dfa中不支持，且在POSIX nfa引擎中也没有意义(我的猜测是这这个引擎的标准量词可能默认是贪婪型的)，为了测试这一点可以使用模式nfa|nfa not匹配nfa not如果成功匹配的只是nfa，那么则能确定这是traditional nfa引擎，否则nfa not都能匹配，那么只可能是POSIX nfa或dfa引擎了
• 如果之前的判断排除它是traditional nfa引擎的可能，那么接下来要判断它是POSIX nfa还是dfa引擎，dfa引擎是不支持捕获性括号，所以自然也不支持回溯引用，但是一些混合使用两种引擎的系统，当没有使用捕获型括号，那么将使用dfa引擎
• 所以单纯的通过其是否支持某些特性来判断一个引擎将过于草率，其实可以通过下面的这个测试例子即可判断出是POSIX nfa还是dfa引擎

使用模式:
X(.+)+X
匹配文本:
XX-----------------------------------------------------------------------

如果匹配要花费很长的时间，那就是

之前匹配的结束位置，还是当前匹配的开始位置

在对一个文本进行多次匹配时，如果之前匹配的文本长度大于0，则下次匹配的时候将使用之前匹配的结束位置，否则传动装置将强行前进到下一个字符，就使用当前匹配的开始位置

匹配模式(?mode)和作用域

模式

• i 忽略大小写匹配
• x 宽松排列和注释模式
• s 点号通配模式
• m 增强的行锚点模式

作用域

• (otherRegex)(?mode)(targetRegex)(?-mode)(otherRegex)
  在上面的例子中(?mode)会启用该模式并作用于targetRegex直到(?-mode)将停用此功能
• (otherRegex)(?:(?mode)targetRegex)(otherRegex)
  在上面的例子中(?mode)会启用该模式并作用于targetRegex直到闭括号的结束
• (otherRegex)(?mode:targetRegex)(otherRegex)
  上面表达式的一种简写方式，表示模式的修饰范围只在括号内有效

(page: 135)

Java regex 字符组集合操作

假如要匹配除元音字母的其他任意英语小写字母，则可写为
[[a-z]&&[^aeiou]]
[...]&&[^....]来表示-的集合操作

同时也可以使用环视来模拟此功能:

• [a-z](?<![aeiou])
• [a-z](?<=[^aeiou])

上面的意思是先匹配一个字母，然后再确保匹配好的字符不能是元音字母

---

• (?![aeiou])[a-z]
• (?=[^aeiou])[a-z]

上面的意思是先把光标定位到除元音字母以外的任意字符的左边，然后匹配小写字母

Java使用regex的/x模式，内嵌注释

String regex = "(?x)M" +
                "#This is an Note\n" +
                "A#666\n";

• 实际上得到的正则表达式是：(?x)MA
• 也即#和Ln包括它们之间的字符都将被视为注释

Java字符串文本与正则表达式的关系

regex = "(?x)S S\t\\t\n\\n"

status	value
Java src text	(?x)S S\t\\t\n\\n
Java compiled text	(?x)S STab\tLn\n
regex	(?x)SS\t\n

因为(/x)的模式的影响，忽略所有的空白字符作为最后的regex，这可能会让人有点疑惑，那为什么\t和\n依然存在，这是因为\t和\n分别是两个字符\, t和\, n字符的组合，这些字符本身都不是空白字符，只是regex用来匹配的时候会将\t和\n视为元序列字符，分别匹配制表符和换行符

环视

• 肯定顺序环视(?=)
• 肯定逆序环视(?<=)
• 否定顺序环视(?!)
• 否定逆序环视(?<!)
• 利用环视可以模拟一些流派上不支持的正则表达式符号，

metacharacter	lookaround
</	(?<=\W)(?=\w)
/>	(?<!\W)(?!\w)
\b	</|/>, (?<=\W)(?=\w)|(?<=\w)(?=\W)
\B	(?<=\W)(?=\W)|(?<=\w)(?=\w)

但元字符却具有更高的效率

为451545类似的数值从右往左每3个数字添加一个逗号,且最右边不添加

• 真正解决这个问题应该使用表达式
  (?<=\d)(?=(?:\d{3})+\b)只能使用环视，因为在一个数值中要添加多次逗号，
  而通常的做法是只要每次匹配到3个数字且它们前面还有数字的话，它们的前面就应该添加一个逗号，前面有逗号的话，只需要逆序环视(?<=\d)即可，但是考虑到匹配后面3的整数倍的数值，只能使用顺序环视，因为简单使用(\d{3})+\b将会消费后面的所有文本，

• 所以只能添加一个逗号，而且还会出错，
  应该使用顺序环视(?=(\d{3})+\b)可以重复检查后面的文本，依次找出所有需要添加逗号的位置

• 在这样之所以使用(?:...)非捕获型的括号是因为反正这个regex的该子表达式捕获到的$1不会被使用，而且它效率更高，因为引擎不需要记忆捕获的文本。但是却丢失了一定的可读性

Intellij IDEA的regex的特点

• 对于匹配同一个位置，常常可被匹配到两次，这很可能是因为他即匹配一个字符结束位置，也匹配一个字符的开始位置，所以同-个位置可能被视为2个位置----开始和结束

[ \t]*和( *|\t*)的区别

• ( *|\t*)只能匹配sapce或\t的连续序列，而不能匹配它们的混合序列
• [ \t]*不但能匹配包括( *|\t*)能够匹配的内容，还能匹配sapce和\t的混合序列
• 实际上[ \t]*和( |\t)*逻辑上是等价的，但是字符组的效率却更高一些

非捕获型括号(?:...)

• (?:...)只分组不捕获
• (...)即分组又捕获

如表达式([+-]?\d+(\.\d*)?)\s*([CF])和([+-]?\d+(?:\.\d*)?)\s*([CF])

RegEx	([+-]?\d+(\.\d*)?)\s*([CF])	([+-]?\d+(?:\.\d*)?)\s*([CF])
\1	([+-]?\d+(\.\d*)?)	([+-]?\d+(?:\.\d*)?)
\2	(\.\d*)	([CF])
\3	([CF])	NULL

书中可能的错误列表

• 但我们知道 First|1st与 (fir|1)st表示的是同一个意思 (page: 13)
• \w 应该还能匹配_ (page: 49)
• E-mail Message范本倒数第三行可能在一些英文单词上少了一些空格 (page: 54)
• 下面的程序段可能存在过多的}字符 (page: 57)
• 在a标签的href引用的链接应该用双引号包围 (page: 74)
• 关于字符串文字的若干例子, 字符串文本[\t\x2A]在/x模式下只能匹配* (page: 102)
• 十进制编码015,应该是八进制编码才对 (page: 115)
• [^LMNOP]通常等价于[\x00-KQ-\xFF]而不是[\x00-kQ-\xFF] (page: 119)
• 匹配HTML Tag，使用的表达式是<("[^"]"|'[^']'|[^">'])*+>,这样会匹配到<>,所以应该使用<("[^"]"|'[^']'|[^">'])++> (page: 200)

疑问列表

1. 表达式(a)?b\1还能匹配除文本aba以外的其他文本吗？(待研究)

API

• 元字符 (page: 32)
• 一些语法 (page: 114)
• 字母表 (page: 123)

子表达式定义

子表达式是只正则表达式中的一部分，通常是括号内的表达式
如^(Subject|Date):中，(Subject|Date)通常被视为一个子表达式
其中Subject和Date也算是子表达式。而且，严格来讲
S u b j …… 这些都算是子表达式。

匹配位置的元字符\B，\b，\<，\>

1. 它们都匹配一个位置
2. 它们都是元字符序列

• \B匹配的位置在\W与\W或\w与\w之间
• \b匹配的位置在\W与\w或\w与\W之间
• \<匹配的位置在\W与\w之间
• \>匹配的位置在\w与\W之间

使用regex检索文本的精确度

取决于我们对需要检索的文本的了解程度。
举个极端的例子，要匹配一个文件内的所有数字，显然可以使用
\d，但是如果我们清楚的明白我们的文件内的内容都是纯数字的话，
可以简单的使用.

关于grep

grep会在检查regex之前把换行符删除掉，
然后再用regex与每行删除完换行符剩下的内容进行匹配

关于在字符组中的元字符^

[^……]将会匹配未被列出的任意字符，
而且只有当^出现在[的最左边时，它才是一个元字符
[^^]第二个^就只是普通字符，这个模式的含义是它将匹配出除^字符以外的任意字符

关于元字符^和$

• ^匹配行开头
• $匹配行结尾

更具体的说明

但如果使用了增强的行锚点模式

• 那么^不但能狗匹配字符串开头还能匹配每个换行符后面的位置(但不能匹配字符串结束位置)
• 同样$还能匹配每个换行符的开始位置(左边)
• 所以使用\A，可以总是匹配字符串的开头
• 使用\Z和\z，可以总是匹配字符串的结束

关于在字符组中的连字符-

• [0-9A-Z_!.?]能够匹配一个数字，大写字母，下划线，惊叹号，点号，或者是问号。
• 只有在字符组内部，连字符才有可能是元字符----否则他就只能匹配普通的连字符号，
• 当不能形成一个范围的时候，它就是一个普通的连字符号
• 如[a-z-]第二个连字符就将被解释为一个普通的连字符号