第2章　正则表达式匹配算法

正则表达式作为表示复杂语义的模式串的有力工具，它的定义是递归的：一个正则表达式要么是一个简单的字符串，要么是正则表达式的串联、并联或重复。匹配正则表达式的算法相当复杂，只有在模式串不能用更简单的方法来表示的时候才会使用正则表达式来表示。

一方面，正则表达式的匹配通常是用有限自动机来解决的，具体又可以分为非确定性有限状态自动机（Non-deterministic Finite Automata，NFA）和确定性有限状态自动机（Deterministic Finite Automata，DFA）两种，后者可以由前者转化而来。另一方面，字符串其实是正则表达式的特殊情况，它本身不一定需要借助生成自动机来匹配，它的匹配有更丰富的算法可选择。本章对简单字符串和普通正则表达式的匹配手段进行梳理和介绍。