7.4 有限状态自动机FA

有限状态自动机（finate automaton）是用来判断字符串（句子）是否和正则表达式匹配的假想机器，它有一个字母表 Σ 、一个状态集合 S ，一个转换函数 T ，当它处于某个状态时，若它读入了一个字符（必须是字母表里的字符），则会根据当前状态和读入的字符自动转换到另一个状态，它有一个初始状态，还有一些所谓的接受状态。

它的工作过程是：首先自动机处于初始状态，之后它开始读入字符串，每读入一个字符，它都根据当前状态和读入字符转换到下一状态，直到字符串结束，若此时自动机处于其接受状态，则表示该字符串被此自动机接受。如下图：图7.2 典型的有限状态自动机

上图中圆圈表示各种状态，各箭头及签头上的字符表示状态的转换表，自动机只有一个初始状态，用一个不含字符的箭头指向此状态，可以认为此为自动机的入口，自动机可以有一个或多个接受状态，用双圆圈表示。上图中的自动机的字母表为 {a, b}，初始状态为 S1 ，当它读入一个 a 后，就转到状态 S2 ，若读入的是 b ，则转到 S4，然后一个接一个字符的转换其状态，若字符结束时自动机处在其接受状态，则表示此字符串被其接受。经过观察可知，此图中的自动机能接受的字符串为 “ab”, “abb”, “abbb”, … ，也就是说，此自动机与正则表达式 ab+ 是等价的。

简单的有限状态自动机可以通过上一小节的 与、连接和重复 搭建出复杂的自动机。数学家们已经证明了：任何一个正则表达式都有一个等价的有限状态自动机，任何一个有限状态自动机也有一个等价的正则表达式。

可以看出有限状态自动机的判断速度是非常快的，它只要求对字符串扫描一遍就可以了，显然比前面介绍的直接扫描法要快多了。

总而言之，正则表达式的匹配判断可以通过构造有限状态自动机来进行，以上仅介绍了构造有限状态自动机的大体思路：先构造基本的自动机，再根据正则表达式的结构搭建出复杂的自动机。构造有限状态自动机的具体算法十分复杂，本站不再深入介绍了，还是借用前人已经做好的工具吧，下一章中，将介绍如何使用 flex 来进行基于正则匹配的词法分析。

第 7 章完