A regular expression(简写成RegEx) defines a search pattern for strings. 正则表达式在文本的搜索编辑的场景中很有用处。
RegEx并不是Java发明的，可以说很久很久以前就出现了。1950年代，美国数学家Stephen Cole Kleene提出，后来随着Unix普及开。它从左往右逐个字符扫描文本，找到匹配的模式，继续往下扫描，模式可以使用一次或者多次。JDK1.4版本开始支持了。
我们不用编程序就在用正则了。一个例子就是在command窗口执行命令dir *.txt或者dir test?.txt就可以找出符合这个模式的文件来。
Java里面有一个util.regex包，常用下面两个类：
util.regex.Pattern Used for defining patterns
util.regex.Matcher Used for performing match operations on text using patterns
JDK文档中有一个简单例子：
Pattern p = Pattern.compile("a*b");
Matcher m = p.matcher("aaaaab");
boolean b = m.matches();
结果是返回true。模式ab代表的是以a开头b结尾中间有0个或者多个字符的一切串。所以按照这个模式去搜索，aaaaab是符合条件的。 更简单的写法就是boolean b = Pattern.matches("ab", "aaaaab");不过这种写法性能不好，无法重用pattern对象。如果只用一次，可以这么简写。
再看一个识别数值的例子：
Pattern pattern = Pattern.compile("^\\d+(\\.\\d+)?");
Matcher matcher = pattern.matcher("5.67");
boolean b = matcher.matches();
结果是返回true。模式^\d+(\.\d+)?代表的是以一个或多个数字开头后面可以跟一个小数点.之后再跟一个或多个数字。所以5.67, 5, 3.5都符合，但是.35或者1.2.3不符合。
上面的模式串有一点奇怪，本来应该是^\d+(.\d+)?，但是再Java语法规则中“\”是一个特殊符号，表示转义，因此为了不让它转义我们在前面要再加上一个\，这样整个模式串由^\d+(.\d+)?变成了^\d+(\.\d+)?
再细说一下上面的模式串^\d+(.\d+)?，分成几段：
^ 这是一个标记，规定文本要以后面的段开头
\d+ \d表示的是数字，+表示一个或者多个。结合前面的^，即规定了文本要以一个多个数字开头
(.\d+) ()括号本身不是用来搜索的，只是给模式串分段的，表示里面的内容构成一个段。.表示的是小数点.，\d表示表示的是数字，+表示一个或者多个。整个段合在一起，表示以小数点打头后面有一个多个数字
? 这是一个标记，表示前面的段是可选项，可以出现也可以不出现。结合前面的段，表示小数点及数字可以有也可以没有。所以能同时匹配5.67和5两种情况。
下面是一个识别ip地址的例子：
String str = "192.168.1.23";
String regEx = "^\\d{1,3}.\\d{1,3}.\\d{1,3}.\\d{1,3}$";
Pattern pattern = Pattern.compile(regEx);
Matcher matcher = pattern.matcher(str);
boolean rs = matcher.matches();
这个模式串^\d{1,3}.\d{1,3}.\d{1,3}.\d{1,3}$比较简单，就是由.分隔开的四段数字，每段数字是一到三位数。
再看一个：
Pattern pattern = Pattern.compile("[^\\u4e00-\\u9fa5]");
Matcher matcher = pattern.matcher("手把手*&%教你学@#编程1234");
System.out.println(matcher.replaceAll(""));
结果是包含非中文字符的串变成了“手把手教你学编程”，所有非中文字符都去掉了。模式串[^\u4e00-\u9fa5]表示字符集合，\u4e00-\u9fa5代表unicode编码中的中文范围，前面的^表示的是“非”操作，所以这个模式串代表的是非中文字符集合。
从上面简单的例子，我们也可以感受到正则表达式的功用，再对文本的查找处理的时候非常有用，各类词法分析中都要用。文本编辑器，搜索引擎，开发环境，编译器或者解释器，都是要用到的。
也正是因为这样，计算机科学里面对它是有正式的定义的。后面我会讲到。
上面是一个一个的孤立的例子，那有没有一个全一点的清单让人了解如何写这些模式？有，但是并没有一个唯一的标准，实现过程中有不同的文法。现在比较广泛使用的有POSIX标准和Perl文法。这个也称为派别之争。世界上的事情，都有正反两面，有时候我们想有一个统一的标准，简化大家的工作，但是有时候又希望多样性，促进竞争和发展，不要被某一个思想或者标准垄断。
不同的语言使用的正则文法有差别，烦不胜烦，气得有的程序员一气之下自己搞一个正则解释器，重新造*。我后面的讲座也会讲怎么构造正则解释器。
我们是讲Java，所以我们以JDK文档为准。下面也列出一些常用的基本构造。
Characters，单个字符还有特殊字符\
x The character x
\\ The backslash character
\uhhhh The character with hexadecimal value 0xhhhh
\n The newline (line feed) character ('\u000A')
\r The carriage-return character ('\u000D')
Character classes字符集合
[abc] a, b, or c
[^abc] Any character except a, b, or c (这是一个反向声明)
[a-zA-Z] a through z or A through Z, inclusive (字符范围)
[a-d[m-p]] a through d, or m through p: [a-dm-p] (并集)
[a-z&&[def]] d, e, or f (交集)
[a-z&&[^bc]] a through z, except for b and c: [ad-z] (subtraction)
[a-z&&[^m-p]] a through z, and not m through p: [a-lq-z](subtraction)
Predefined character classes，几个特殊字符集合，注意大写是指反向
. Any character (may or may not match line terminators)
\d A digit: [0-9]
\D A non-digit: [^0-9]
\s A whitespace character: [ \t\n\x0B\f\r]
\S A non-whitespace character: [^\s]
\w A word character: [a-zA-Z_0-9]
\W A non-word character: [^\w]
Boundary matchers，边界指示
^ The beginning of a line
$ The end of a line
\b A word boundary
\B A non-word boundary
Greedy quantifiers，通配符
X? X, once or not at all
X* X, zero or more times
X+ X, one or more times
X{n} X, exactly n times
X{n,} X, at least n times
X{n,m} X, at least n but not more than m times
Logical operators逻辑指示
XY X followed by Y
X|Y Either X or Y
(X) X, as a capturing group
好，我们还是举例子，进一步加深了解。
来一个身份证号码的验证。这个在中国的实际场景中很常见。身份证由15位或者18位数字组成（严格地说，18位的最后一位可以是X，校验符），分成几段，第一段式地区，六位数字，后面一段生日YYMMDD或YYYYMMDD格式，再后面的一段是三位数字，如果是18位的号码最后有一个校验位数字或者X。代码如下(IDTest.java)：
public class IDTest {
public static void main(String[] args) {
String str = "120104199903093168";
String regEx = "^(\\d{6})(18|19|20)?(\\d{2})([01]\\d)([0123]\\d)(\\d{3})(\\d|X|x)?$";
Pattern pattern = Pattern.compile(regEx);
Matcher matcher = pattern.matcher(str);
boolean b = matcher.matches();
System.out.println(b);
}
}
我们只解释模式串(去掉Java转义符):
^(\d{6})(18|19|20)?(\d{2})([01]\d)([0123]\d)(\d{3})(\d|X|x)?$
拆开看，分几段：
^(\d{6}) 以六位数字开头
(18|19|20)? 接下来是一个可选的段，对于18位的号码，YYYY前两个Y
(\d{2}) 这是生日的年份，YYYY后两个Y
([01]\d) 两位月份，01，02，...，09，10，11，12。所以第一位是0或1
([0123]\d) 两位日期，第一位只会出现0，1，2，3四个数字，第二位随意
(\d{3}) 这一段是三个数字
(\d|X|x)?$ 以这一段结尾，这一段是一位数字或者是X字符，?表示这一段可选。
上面这个就是一个基本达到实用程度的模式串了，能够初步过滤掉明显不对的身份证号码。
再看一个邮件格式校验的例子。这个也是实战常见的场景。邮件的格式是由@分成的两部分，后一部分由.分隔的多段，名字可以出现字母数字和特定的字符如_-.之类：
public class EmailTest {
public static void main(String[] args) {
String str = "abc_1-2.345678@net.com.cn";
String regEx = "[\\w|.|-]+@(([a-zA-z0-9]-*){1,}\\.){1,3}[a-zA-z\\-]{1,}";
Pattern pattern = Pattern.compile(regEx);
Matcher matcher = pattern.matcher(str);
boolean b = matcher.matches();
System.out.println(b);
}
}
还是只解释模式串：[\w|.|-]+@(([a-zA-z0-9]-){1,}.){1,3}[a-zA-z-]{1,} 拆开看，分几段： [\w|.|-]+ 这是邮件名，由\w以及.-符号组成，\w就是字母数字和_ @ 这是邮件分隔符号 (([a-zA-z0-9]-){1,}.){1,4} 一个或者最多四个域名子段，字段里面是字母数字和-
[a-zA-z-]{1,} 最后一节域名子段，一个以上的字母及-
通过上面的例子，我们可以看出同一个规则可以有不同的方式表达，如\w就跟[a-zA-z0-9]是等效的，[a-zA-z-]{1,}跟[a-zA-z-]+也是等效的。
再来一个识别的程序。这段程序的目的是从HTML文本中识别出标签，并读出标签里的属性来。
代码如下(FontTagTest.java)：
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class FontTagTest {
public static void main(String[] args) {
String str = "<font face=\"Arial\" size=\"2\" color=\"red\">";
String regEx = "<\\s*font\\s*([^>]*)\\s*>";
Pattern pattern = Pattern.compile(regEx);
Matcher matcher = pattern.matcher(str);
String str2 = "";
String regEx2 = "([a-zA-Z]+)\\s*=\\s*\"([^\"]+)\"";
if (matcher.find()) {
str2 = matcher.group(1);
System.out.println(str2);
Pattern pattern2 = Pattern.compile(regEx2);
Matcher matcher2 = pattern2.matcher(str2);
while (matcher2.find()) {
System.out.println("Field value: " + matcher2.group(0) );
System.out.println("Field value: " + matcher2.group(1) );
System.out.println("Field value: " + matcher2.group(2) );
}
}
}
}
简单解释一下，文本是<font face="Arial" size="2" color="red">（也是去掉了Java转义符）。模式串是<\s*font\s*([^>]*)\s*>，还是老办法，拆分段：
< 这是HTML标签的开头字符
\s* 后面可以跟多个空字符，\s与[ \f\n\r\t\v]等效
font 这一段标识 font标签
\s* 又可以跟多个空字符
([^>]*) 多个任意字符，除了>，到了>就表示结束了
\s* 又可以跟多个空字符
> 这是HTML标签的结尾字符
这个模式串里面并没有处理 face="Arial" size="2" color="red"的模式，我们是把它们看成一个整体，之后在细分。
我们用了matcher.find()语句找符合模式的部分，然后由matcher.group(1)语句读出内容。这个要解释一下。matcher.find()会按照模式把匹配的内容都找出来，按照组分开存放，下标从1开始，而规定matcher.group(0)表示全部内容。比如，我们用matcher.group(0)得到的结果是，而matcher.group(1)得到的结果是face="Arial" size="2" color="red"。这个结果的理解要回到模式<\sfont\s([^>])\s>,我们看里面有一段([^>]),这个就是分组，整个模式串中也只有这一个组，所以就得到了这个结果。 拿到了这组的内容face="Arial" size="2" color="red"后，我们要继续模式匹配。于是用了一个新的模式串：([a-zA-Z]+)\s=\s"([^"]+)"，还是拆分看一下： ([a-zA-Z]+) 这是一个多个字母 \s 随意个数空字符
= =分隔符
\s* 随意个数空字符
" “双引号里面是值
([^"]+) 除了双引号之外的任意多个字符
" “双引号结尾
```
按照这个模式，matcher2.find()就能找到三个匹配的串，face="Arial"和 size="2"以及 color="red"。由于我们给这个模式里面建了两个组([a-zA-Z]+)和([^"]+)，所以matcher2.group(1)和matcher2.group(2)将会把key如face和value如 Arial取出来。
运行上面的程序，结果为：
face="Arial" size="2" color="red"
Field value: face="Arial"
Field value: face
Field value: Arial
Field value: size="2"
Field value: size
Field value: 2
Field value: color="red"
Field value: color
Field value: red
这只是HTML一个标签的解析，由此想开出去，把HTML的各个标签都列出一个模式来，我们就可以对HTML文本进行很多解析。
除了匹配，我们还可以进行查找替换操作。下面有一个例子，代码如下(ReplaceTest .java)：
public class ReplaceTest {
public static void main(String[] args) {
String EXAMPLE_TEST = "This is an example string.";
Pattern pattern = Pattern.compile("\\w+");
Matcher matcher = pattern.matcher(EXAMPLE_TEST);
while (matcher.find()) {
System.out.print("Start index: " + matcher.start() + " ");
System.out.print("End index: " + matcher.end() + " ");
System.out.println(matcher.group());
}
Pattern replace = Pattern.compile("\\s+");
Matcher matcher2 = replace.matcher(EXAMPLE_TEST);
System.out.println(matcher2.replaceAll(" "));
}
}
将这句话分词，注意我们在字符串里面有一个空格两个空格三个空格几种不同的情况，\w都能识别出来并分开。matcher.start()和matcher.end()能将扫描到的词的开始结束位置获取到。最后通过\s+匹配所有空格字符，包括空格制表等符号，统一用空格替换：matcher2.replaceAll(" ")。
运行上面的程序，结果为：
Start index: 0 End index: 4 This
Start index: 6 End index: 8 is
Start index: 12 End index: 14 an
Start index: 15 End index: 22 example
Start index: 23 End index: 29 string
This is an example string.
从应用来讲，Java里的正则表达式基本用法就是这样，大家要找任务自己练习。我的讲座是教大家怎么用Java语言处理问题，不是关于Java文法和API的，大家学习过程中要自己掌握基本文法和API，多看看JDK文档参考。
下面，我们进一步探讨一下。简单地阐述一下理论，并扩展讨论。讨论的原因是知晓原理，并初步了解到我们自己如何分析出正则表达式，进一步理解如何进行词法分析，为今后实现更大的任务做基础准备。也许这个过程很枯燥，但是不要着急，须知我们在做一件了不起的事情。循着这个进路，你最后会发现自己会写解释器编译器，理解人类语言，甚至自己也能发明一种新语言，知道那些改变人类的伟大发明怎么做出来的，窥探往圣如何启绝学安天下，是不是有一种无比荣耀的成就感？
正则表达式是有严格的定义的，我们一般采用递归定义如下：
对给定的有限字母表Σ, 下面的常量定义为正则表达式:
(空集) ∅ denoting the set ∅.
(空串) ε
(字母) a in Σ
对于正则表达式R and S, 运用下面的规则也产生正则表达式:
(连接) RS,例如 R = {"ab", "c"}, and S = {"d", "ef"}. Then, RS = {"abd", "abef", "cd", "cef"}.
(选择) R | S，这是 R and S的并集. 例如, R={"ab", "c"} and S={"ab", "d", "ef"}, 那么R | S = {"ab", "c", "d", "ef"}.
(*) R*，这是由R中的元素按照任意数量次组合而成的集合。例如, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", ... }.
例子：
a|b* = {ε, "a", "b", "bb", "bbb", ...}
(a|b)* = {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", ...}
ab*(c|ε) = {"a", "ac", "ab", "abc", "abb", "abbc", ...}
(0|(1(01*0)*1))* = { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }
有了这个文法的定义，我们如何构造一个机制来识别某个串是否属于这个语言集合呢？理论上我们会用到状态自动机。如：
这个自动机就可以识别L((a|b)*abb)这种正则语言。判断方法就是把字符串一个个字符输进去，看是否能走到最后的接收状态，能就是属于该语言，不能则不属于。
1、一个有限的状态集合S；其中，一个状态S0被指定为开始状态，也就是最开始接受输入字符的状态，有且只有一个；S的一个子集F被指定为终止状态集合。
2、一个输入符号集合∑，即输入字母表（input alphabet）；
3、一个转换函数T（transition function），为每个状态和∑中的每个符号都给出了相应的后续状态（next state）。
正则表达式方便人理解，而自动机更方便算法构造。对于每个正则表达式，都有一个自动机与之对应。像Tompson算法就是干这个的。这些就是自己做正则引擎的基础。
自然，本次讲座不会教授这些具体知识和算法，只是让同学们了解一下理论，知道我们如何自己下手写正则引擎词法分析器编译器。从这里起步，开启一段了不起之旅。
我们看到了，正则是处理字符串的，所以正好用于文本分析的分词。我们程序员用的最多的文本其实就是程序源代码。所以对程序源代码的解释编译都要用到正则表达式，用到自动机，当然，编译过程不仅仅只是词法分析，还有语法和语义分析以及目标代码生成技术在里面，但是词法分析是基础。
到此为止，从正则出发，我们初步接触了自动机。当然这不是全部内容，中文词法分析就复杂很多，因为没有类似于英文空格的边界符号，词法分析我们未来会有专题讲到。
好，本次讲座就是这些内容，我们从简单的正则表达式出发，逐步深入了解了复杂一点的用法，又进一步了解了词法分析的理论和自动机。这种逐次扩展的进路，是掌握技术的好方法。大家学习技术时，不要拘泥于眼前的小技巧小景象，登高望远，见微知著。
时常会想到，坐在书房里面，抬头望窗外，见一叶落而知天下秋。遥想杜甫当年，颠沛流离，寄身驿馆，居斗室而推窗远望，发出“窗含西岭千秋雪，门泊东吴万里船”的千秋比兴，真谓“吾道不孤也！”