2019-07-27

自己动手用java写编译器课时8 Thompson构造，将正则表达式转换为有限状态自动机

缘起

上一节我自己动手实现了一个识别整型、浮点型的FSM（构造该FSM并使用输入的字符来驱动它来实现对整型和浮点型的识别, 其实整个过程就是词法分析的本质）. 本节课继续研究FSM和正则表达式（下简称 RegExp）之间的关系

分析

回顾一下上一节开发的FSM，其实那个FSM对应着一组RegExp

1
2
3

D        [0-9]  表示0-9的字符类
{D}+     表示由 0-9 构成的整形数值
({D}+ | {D}*\. {D}+ | {D}+ \. {D}*)(e{D}+)? 表示浮点数或科学计数法

比如

1 2	其中{D}+ 对应着状态机中，由0到1，然后在1中自转这一流程。最后一个正则表达式，对应图中由状态0到状态2，或 4的流程。

也就是，我们通过构造一个FSM来实现了正则匹配. 那么问题来了，给定一个正则表达式，我们怎么使用这个正则表达式呢? 也就是这个时候我们再丢给你一个单词，问你正则表达式是否匹配的话, 你怎么写一个算法来判断匹配呢? 有了上一节课以及刚刚的分析，答案是显然的——将给定的regexp构造其相应的FSM, 然后读入需要匹配的字符串来驱动该FSM，到达接受状态就搞事情. 最终实现匹配.

实际上大部分正则表达式的识别程序（或者叫正则表达式引擎）其实就是将RegExp转换为相应的FSM，然后再通过读入字符串来驱动FSM的运行，最终达到正则匹配的过程. 所以将正则表达式转换为FSM是一件有趣的事情. 而且是这几节课的重点.

1
2
3

ps: 原先作为java程序员，使用正则表达式也仅仅是会用——其实有几个java程序员理解正则表达式背后的原理呢? 
其实正则表达式的这一算法如果理解了就不难知道其威力并不仅仅在正则表达式的运用上，其实对于一般的文本解析也
都是有好处的.

FSM的分类

DFA （Deterministic finite automaton，确定性有限状态自动机）

就是状态转移函数next是确定的FSM就是DFA. 例如上一节课我们实现的FSM就是DFA. 或者更严谨的说，DFA任何2条边对应不同的字符. 亦即从一个状态如果下一步要到达不同的状态，一定是不同的字符.
NFA（Nondeterministic finite automaton，非确定性有限状态机）

NFA和DFA是相对应的概念. 在实践中，要想顺利的将正则表达式转换为自动机,需要NFA的帮助. 正如NFA名字所示意的那样，从一个状态出去的2条边可以对应相同的字符. 即在一个状态的时候喂给自动机同一个字符可能到达的状态不一样. 而且NFA可以对应的特殊的字符是一种叫做空的字符. 该字符的符号是”ℇ”. 这种边表示不需要任何输入，就可以从当前状态进入下一个状态（ℇ边的存在是NFA的巨大特点——不需要输入任何字符就可以跳转）.

上面说的DFA和NFA的定义太抽象，下面以图来说明

表达式 (and|any) 对应的DFA如下

看到了没，不同的边对应的字符一定是不一样的.

而它对应的NFA如下

看到了没, 不同的边对应的字符可能是一样——都是a.

或者从初始状态分化两条对应字符为空字符ℇ的边，然后分别进入两个对应的状态机

第二种NFA在程序设计中容易实现，因此，在下一节的代码中，我们将采用第二种NFA的实现模式。

NFA有一个明显的弱点就是，在代码设计中，很难用数据结构来对它进行表示。特别是，当对应于一个输入字符，NFA可以跳转到多个状态，那么，要想利用NFA去识别输入字符串就比较困难（DFA才是在程序中比较好使用的）。一般而言，使用NFA的程序都需要经过下两个步骤：将正则表达式转换为NFA, 将NFA转换为DFA.

在后面的讨论中，我们将通过代码来展示这两种转换.