有限状态机实现正则表达式

　　最近在写语法分析东西。遇到了不是难题，也学到了不是东西。和大家分享一下
　　1.语法分析最笨的办法就是对应位置的对应关键字匹配（模式匹配），这个东西最简单，也最容易实现，这个就是所谓的穷举发。
　　今天我肯定不是来和大家说模式匹配，这个也没有必要说。
　　今天，最成熟的语法分析利器还要算正则表达式了，用户只需要些一些简单的语法，就可以匹配和分析出自己需要的东西。
　　但是，没有几人知道正则表达式的实现原理（在搜索的时候，基本没有发现将实现原理的）。
　　在大学时代，只要你是学计算机的，应该知道有一门课叫编译原理的，主要就是将语法分析的（我自己也些过几次语法分析器，但时间太久了，全都忘了），我就猜测，正则表达式的实现原理是不是有限状态机。
　　我查看c和java的源代码，发现他的解析器就是采用的有限状态机实现。
　　所以我在网上找到一篇很不错的文章： 正则表达式可以用来：
　　（1）验证字符串是否符合指定特征，比如验证是否是合法的邮件地址。
　　（2）用来查找字符串，从一个长的文本中查找符合指定特征的字符串，比查找固定字符串更加灵活方便。
　　（3）用来替换，比普通的替换更强大。
　　对于一个正则表达式一般有2种方式，以JS为例
　　其一为使用正则表达式文字常量：
　　var re = /^[Jj]ava[Ss]cript/i;
　　其二为使用RegExp构造函数：
　　var re = new RegExp("^[Jj]ava[Ss]cript","i");
　　而一个正则表达式解释器主要有3部分组成，分别是解析（parse）、编译（compile）与执行（execute）。
　　1 解析
　　正则的表达式的词法与语法比较简单，基本语法如下：
　　A）普通字符和元字符
　　普通字符是那些表示自身的字符，例如从a到z，A到Z，0到9等；
　　元字符具有特殊意义，如'.'，表示除了'\n'外的所有字符，其他具有此功能的有
　　表1 元字符 元字符 特殊意义 ^ 匹配输入字符串的开始位置。要匹配 "^" 字符本身，请使用 "\^" $ 匹配输入字符串的结尾位置。要匹配 "$" 字符本身，请使用 "\$" . 匹配除了换行符（\n）以外的任意一个字符。要匹配小数点本身，请使用 "\." * 修饰匹配次数为 0 次或任意次。要匹配 "*" 字符本身，请使用 "\*" + 修饰匹配次数为至少 1 次。要匹配"+" 字符本身，请使用 "\+" ? 修饰匹配次数为 0 次或 1 次。要匹配 "?" 字符本身，请使用 "\?" = 用于前向引用或向后引用 ! 用于前向引用或向后引用 : 用于前向引用或向后引用 | 用于前向引用或向后引用 \ 转义用 / 用于前向引用或向后引用 () 标记一个子表达式的开始和结束位置。要匹配小括号，请使用 "\(" 和 "\)" [] 用来自定义能够匹配 '多种字符' 的表达式。要匹配中括号，请使用"\[" 和 "\]" {} 修饰匹配次数的符号。要匹配大括号，请使用 "\{" 和 "\}" 元数据如要表示自身，那么需要用'\'来辅助转义
　　B）字符类
　　单个的字符可以组成字符类，其语法为用'['与']'组成，例如[abcA-Z79]表示可以匹配a，b，c与A到Z，7，9的字符
　　其中'-'为连字符，表示字符的跨度。
　　'^'在"[]"间也是特殊字符，表示取反
　　其他的特殊字符如下表：
　　表2 字符类中的预定义字符类 预定义字符类 特殊意义 ^ 在紧跟'['表示取反，表示自身要转义 - 在字符间，表示连字符，如要表示自身，须紧接在'['或'[^'之后 . 小数点可以匹配除了换行符（\n）以外的任意一个字符 \d 可以匹配任何一个 0~9 数字字符 \D D大写，可以匹配任何一个非数字字符 \s 可以匹配空格、制表符、换页符等空白字符的其中任意一个 \S S大写，可以匹配任何一个空白字符以外的字符 \w 可以匹配任何一个字母或者数字或者下划线 \W W大写，可以匹配任何一个字母或者数字或者下划线以外的字符 JavaScript无POSIX格式
　　C）限定符（重复）
　　限定符有2种形式，分别为'*','+','?'与' {'与'}'来表示
　　表3 限定符 限定符 特殊意义 * 表达式尽可能的多匹配，最少可以不匹配，相当于 {0, } + 表达式尽可能的多匹配，至少匹配1次，相当于 {1, } ? 表达式尽可能匹配1次，也可以不匹配，相当于 {0, 1} {m,n} 表达式尽可能重复n次，至少重复m次："ba{1,3}"可以匹配 "ba"或"baa"或"baaa" {m} 表达式固定重m次，比如："\w{2}" 相当于 "\w\w" {m,} 表达式尽可能的多匹配，至少重复m次："\w\d{2,}"可以匹配 "a12","x456"...   在正则中有贪婪与非贪婪之分，默认的情况下，正则是贪婪的
　　如果要把正则设置为非贪婪有2种方式，一种为设置在原先的限定符加上'?'就行，另一种在设置
　　举例说明，/.+/ 将匹配"abdddd"中的所有字符，/.+?/ 只将匹配"abdddd"中的第一个a，也就是默认的尽可能多的匹配字符，而非贪婪重复则尽可能上的匹配。
　　D）选择、分组和引用
　　选择的语法就是设置'|'，如a|bc，那么要么a或bc都可以匹配，如果(a|b)c则为匹配ac或bc。
　　如果我们在上例中设置了"()"，那么这就是分组，每个分组都可以被引用，如(a|b)c*(e|f)\1\2，\1与\2就是引用的语法，\1表示引用了(a|b)，\2表示引用(e|f)，以此类推。
　　这里要说明的是(a|b)c*(e|f)\1\2与(a|b)c*(e|f)(a|b)(e|f)乍一看两者等同，但实际上，前一个不可以匹配acebf，而后一个可以。究其原因就是引用处的配平必须与被引用处一致，此例中与之匹配的可以是aceac。
　　E）定位符(锚)和前向引用
　　定位符如下表所示
　　表4 定位符 限定符 特殊意义 ^ 匹配输入字符串的开始位置。要匹配 "^" 字符本身 $ 匹配输入字符串的结尾位置。要匹配 "$" 字符本身 ? 表达式尽可能匹配1次，也可以不匹配，相当于 {0, 1} \b 匹配单词边界，例如一个\w和\W的位置，或者一个\w与字符串的开始和结尾的位置 \B 和上面的想法，匹配一个非单词边界 如果正则表达式的匹配模式为 MULTILINE 模式，^ 可匹配一行文本的行首，$ 可匹配一行文本的行末。当 \b 被包含于字符集合中时，\b 代表退格符（ASCII码 = 8）。
　　除了这些预定义的定位符，还可以自定义定位符，这种类型的定位符叫做前向引用(look-ahead anchor)和后向引用(look-behind anchor，JavaScript不支持)。
　　前向引用使用(?=…)表示正的前向引用，(?!…)表示负的前向引用下面是一个前向引用的例子 /Java(?!Script)([A-Z]\w*)/ 其中(?!Script)匹配后面不跟Script的位置，而(?＝Script)匹配后面是Script的位置。
　　以上讲解了JavaScript的语法规则，下面我们来论述一下解析的过程。
　　解析的过程是语法分析（Lexical Analysis）与词法分析（Grammar Analysis）。
　　2 编译
　　编译（Compile）阶段，主要的工作就是生成字节流（Emit Byte Code）。而生成Byte Code的算法（规则）JS中就是NFA。生成的Byte Code是归于执行（Execute）时做匹配利用。各个状态即为正则中的语义（OPCODE）的表示，各个OPCODE以一定的格式与关系住成了状态机，JS中是组成NFA的状态机。
　　下面介绍下在流行的两种算法NFA（Nondeterministic Finite Automaton）与DFA（Deterministic Finite automaton），Perl，Python，JS等都是NFA的，而awk与grep等用的是DFA，两种算法的具体实现如下：
　　1）有限状态机（Finite Automation）
　　状态机是一个有一组不同状态的集合的系统。有一个特殊状态