正则详解

1. 正则回溯

• 基本思想：当不能再前进时，后退一步或若干步再走，本质上就是深度优先搜索算法
• 即：尝试匹配失败时，接下来的一步通常就是回溯

1.1 正则可视化工具

• Regexper
• Regulex

1.2 回溯分析

示例一：目标字符串 abbbc
ab{1,3}c 不会回溯

示例二：目标字符串字符串 abbc
ab{1,3}c 一次回溯
当尝试匹配第三个 b 时，发现接下来的字符是“c”，那么就认为 b{1,3} 就已经匹配完毕

示例三：目标字符串 abbbc
ab{1,3}bbc 两次回溯

2. 正则引擎

• DFA (Deterministic finite automaton) 确定型有穷自动机
• NFA (Non-deterministic finite automaton) 非确定型有穷自动机

2.1 DFA

• 文本主导：按照文本的顺序执行（先看文本，再看正则）
• 字符串只看一遍，不会发生回溯

2.2 NFA

• 表达式主导：按照表达式的一部分执行，如果不匹配换其他部分继续匹配，直到表达式匹配完成（先看正则，再看文本）
• 回溯是 NFA 引擎才有的，并且只有在正则中出现量词或多选分支结构时，才可能会发生回溯
• 绝大多数的编程语言都采用的是NFA引擎，Java 使用的是 NFA 引擎

3. 量词（Quantifiers）

• 文档 https://docs.oracle.com/javase/tutorial/essential/regex/quant.html

Greedy	Reluctant	Possessive	Meaning
X?	X??	X?+	X, once or not at all
X*	X*?	X*+	X, zero or more times
X+	X+?	X++	X, one or more times
X{n}	X{n}?	X{n}+	X, exactly n times
X{n,}	X{n,}?	X{n,}+	X, at least n times
X{n,m}	X{n,m}?	X{n,m}+	X, at least n but not more than m times

量词有三类:
贪婪型量词（Greedy quantifiers）
勉强型量词（Reluctant quantifiers），惰性量词，贪婪型量词加?
占有型量词（Possessive quantifiers），贪婪型量词加+

量词默认是贪婪的，贪婪型量词会使被修饰字符重复尽可能多的次数
勉强型量词会使被修饰字符重复尽可能少的次数
占有型量词让被修饰字符重复最大次数

其他

• 真正的难点是问题分解
• 能用多个简单正则表达式解决的，⼀定不要苛求用一个复杂的正则表达式
  • 比如：输入条件的验证，“必须包含数字、小写字母、大写字母、特殊符号中的至少两种，且长度在 8 到 16 之间”

References

• 《正则表达式必知必会》
• 《正则指引》

结束语

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.