5.4正则表达式
在许多应用中，我们在查找子字符串的时候并没有查找模式的完整信息。文本编辑器的用户可能希望仅指定模式的一部分，或是指定某种能够匹配若干不同单词的模式，或是指定集中可能任意匹配的不同模式。
和上一节的KMP算法类似，本节也将使用一种能够在文本中查找模式的抽象自动机来描述三种基本操作，模式匹配算法同样会构造一个这样的自动机并且模拟它的运行，这种匹配自动机比KMP算法的DFA更加附加，但不会超出你的想象。你将会看到，我们为模式匹配问题给出的解答和计算机科学中最基础的问题紧密相连。我们会遇到非确定性这个概念，它在人们对高效算法的追求中起到了重要作用。
5.4.1 使用正则表达式描述模式
我们的重点是模式的描述，它由三种基本操作和作为操作数的字符组成。这里，我们使用语言指代一个字符串的集合（可能是无限的），用模式指代一种语言的详细说明。
5.4.1.1 连接操作
第一种基本操作就是5.3节使用过的连接操作，当我们写出AB时，就指定了一种语言{AB}。它含有一个由两个字符组成的字符串，由A和B连接而成。
5.4.1.2 或操作
第二种基本操作可以在模式中指定多种可能的匹配。如果我们在两种选择之间指定了一个或运算符，那么它们就属于同一种语言，我们使用竖线符号“|”来表示这个操作。例如，A|B指定的语言是{A,B}，连接操作的优先级高于或操作，因此AB|BCD指定的语言是{AB,BCD}。
5.4.1.3 闭包操作
第三种基本操作可以将模式的部分重复任意的次数。模式的闭包是由将模式和自身连接任意多次（包括0次）而得到的所有字符串所组成的语言。我们将“*”标记在需要被重复的模式之后，以表示闭包。闭包的优先级高于连接操作，例如，AB *指定的语言由一个A和0个或多个B的字符串自称，而A *B指定的语言由0个或多个A和一个B的字符串组成。所有文本字符串都有一个空字符串，例如A *
5.4.1.4 括号
我们使用括号来改变默认的优先级顺序。例如，C(AC|B)D指定的语言是{CACD,CBD}。（A|C)((B|C))D指定的语言是{ABD,CBD,ACD,CCD}，（AB）*指定的语言是将AB连接任务多次得到的所有字符串和空字符串。
5.4.3 正则表达式的实际应用
实际应用表明了正则表达式善于描述与语言有关的内容。因此，正则表达式使用广泛，这方面的研究也比较深入。
5.4.3.1 子字符串查找
我们的总体目标是开发一种算法，能够判定给定子字符串是否包含在给定正则表达式描述的字符串集合之中。如果文本包含在模式所描述的语言中，就称文本和模式相匹配。例如，要在一段文本txt中查找一个子字符串pat，就是检查txt是否存在于模式“. *pat. *”所描述的语言中。
5.4.3.2 合法性检查
使用互联网的时候，时常会碰到正则表达式。你可能希望检查输入的格式是否正确。进行这类检查的一种方法就是用代码检查所有可能出现的情况，如果输入一个美元金额，你可能会检查第一个字符是否是“$”
5.4.4 非确定有限状态自动机
我们可以将KMP算法看做一台由模式字符串构造的能够扫描文本的有限状态自动机。对于正则表达式，这个思想需要广而推之。KMP的有限状态自动机会根据文本中的字符改变自身的状态。当且仅当到达了停止状态才找到了一个匹配。算法本身就是模拟这种自动机，这种自动机的运行很容易模拟的原因是因为它是确定性的：每种状态的转换都完全由文本中的字符所决定。要处理正则表达式，需要一种更强大的抽象自动机。因为或操作的存在，自动机无法根据一个字符判断出模式是否出现；事实上，因为闭包的存在，自动机甚至无法知晓需要检查多少字符才会出现失败。为了克服这些困难，我们需要非确定性的自动机：当面对匹配模式的多种可能时，自动机能够“猜出正确的转换”，编写一个程序来构造非确定性有限状态自动机并且有效模拟它的运行时很简单的。正则表达式模式匹配程序的总体结构和KMP算法的总体结构几乎相同。
- 构造和给定正则表达式相对应的非确定有限状态自动机；
- 模拟NFA在给定文本上的运行轨迹
学习如何构造模式匹配的NFA之前，我们先来看一个示例，它说明了NFA的性质和操作。它所显示的NFA是用来判断一段文本是否包含在正则表达式((A*B|AC)D)所描述的语言之中。如这个示例所示，我们所定义的NFA有着以下特点。
- 长度为M的正则表达式中的每个字符在所对应的NFA中都有且只有一个对应的状态。NFA的起始状态为0并含有一个(虚拟的)接受状态M；
- 字母表中的字符所对应的状态都有一条从它指出的边，这条边指向模式中的下一个字符所对应的状态(图中黑色的边)。
- 元字符“（”，“）”、“|”和“*”所对应的状态至少含有一条指出的边(图中红色的边)，这些边可能指向其他的任意状态。
- 有些状态有多条指出的边，但一个状态只能有一条指出的黑色边。
NFA也是从状态开始读取文本中的第一个字符。NFA在状态的转换中有时会从文本中读取字符，从左向右一次一个。但它和DFA有些基本的不同：
- 在图中，字符对应的结点而不是边；
- NFA只有读取了文本中的所有字符后才能识别它，而DFA并不一定需要读取文本中的全部内容就能够识别一个模式。
现在的重点是检查文本和模式是否匹配-----为了达到这个目标，自动机需要读取所有文本并到达它的接受状态。在NFA中从一个状态转移到另一个状态的规则和DFA不同---NFA中状态的转换有以下两种方式。
- 如果当前状态和字母表中的一个字符相对应且文本中的当前字符和该字符匹配，自动机可以扫过文本中的该字符并（由黑色的边）转换到下一个状态。我们称这种转换为匹配转换。
- 自动机可以通过红色的边转换到另一个状态而不扫描文本中的任何字符。也就是说它所对应的“匹配”是一个空字符串。
5.4.5 模拟NFA的运行
我们可以检查所有可能的状态转换序列，只要存在能够到达接受状态的序列，我们就会找到它。
5.4.5.1 自动机的表示
首先，需要能够表示NFA。选择很简单，正则表达式已经给出了所有状态名（0到M之间的整数，其中M为正则表达式的长度）。用char数组re[]保存正则表达式本身，这个数组也表示了匹配转换(如果re[i]存在于字母表中，那么就存在一个从i到i+1的匹配转换)。转换最自然的表示方法就是有用想吐，它们都是连接0到M之间的各个顶点的有向边。
5.4.5.2 NFA的模拟与可达性
为了模拟NFA的运行轨迹，我们会记录自动机在检查当前输入字符时候可能遇到的所有状态集合。我们会查找所有从状态0通过转换可达的状态来初始化这个集合。对于集合中的每个状态，检查它是否可能与第一个输入字符相匹配。检查并匹配之后就得到了NFA在匹配第一个字符之后可能达到的状态的集合。匹配了第一个字符之后，转换有向图中的多点可达性问题就可能匹配第二个输入字符的状态集合。
重复这个过程可能有两种结果：
- 可能达到的状态集合中含有接受状态
- 可能达到的状态集合中不含有接受状态
- 第一个结果说明存在某种状态转换序列使NFA到达接受状态，第二种说明对于输入NFA总会停滞，导致匹配失败。
5.4.6 构造与正则表达式对应的NFA
5.4.6.1 连接操作
对于NFA，连接操作是最容易实现的了。状态的匹配转换和字母表中的字符对应关系就是连接操作的实现。
5.4.6.2 括号
我们将正则表达式字符串中所有左括号的索引压入栈中。每当我们遇到一个右括号，我们最终都会用后文所述的方法将左括号从栈中弹出。和Dijkstra算法一样，栈可以很自然的处理嵌套的括号。
5.4.6.3 闭包操作
闭包运算符(*)只可能出现在(i)单个字符之后(此时将在该字符和“ *”之间添加相互指向的转换)，或者是右括号之后，此时在对应的左括号（即栈顶元素）和“ *”之间添加相互指向的两条转换。
5.4.6.4 “或表达式”
在形如(A|B)的正则表达式中，A和B也是正则表达式。我们的湖里方式是添加两条转换。一条从左括号所对应的状态指向B中第一个字符所对应的状态，另一条从“|”所对应的状态指向右括号所对应的状态。
算法5.9 正则表达式的模式匹配(grep)
public class NFA {
private char[] re; //匹配转换
private Digraph G; //epsilon转换
private int M; //状态数量
public NFA(String regexp) {
//根据给定的正则表达式构造NFA
ArrayDeque<Integer> stack = new ArrayDeque<>();
re = regexp.toCharArray();
this.M = re.length;
G = new Digraph(M + 1);
for (int i = 0; i < M; i++) {
int lp = i;
if (re[i] == '(' || re[i] == '|') {
stack.push(i);
} else if (re[i] == ')') {
int or = stack.pop();
if (re[or] == '|') {
lp = stack.pop();
G.addEdge(lp, or + 1);
G.addEdge(or, i);
}
else lp=or;
}
if (i < M - 1 && re[i + 1] == '*') {
G.addEdge(lp, i + 1);
G.addEdge(i + 1, lp);
}
if (re[i] == '(' || re[i] == '*' || re[i] == ')')
G.addEdge(i, i + 1);
}
}
public boolean recognizes(String txt) {
//NFA能否识别文本txt
Bag<Integer> pc = new Bag<>();
DirectedDFS dfs = new DirectedDFS(G, 0);
for (int v = 0; v < G.getV(); v++) {
if (dfs.marked(v))
pc.add(v);
}
for (int i = 0; i < txt.length(); i++) {
//计算txt[i+1]可能到达的所有NFA状态
Bag<Integer> match = new Bag<>();
for (int v : pc) {
if (v < M) {
if (re[v] == txt.charAt(i) || re[v] == '.')
match.add(v + 1);
}
}
pc = new Bag<>();
dfs = new DirectedDFS(G, match);
for (int v = 0; v < G.getV(); v++) {
if (dfs.marked(v))
pc.add(v);
}
}
for (int v : pc)
if (v == M) return true;
return false;
}
}
