如何自己动手开发编译器（三）：构建有穷自动机？

本文共计2820个文字，预计阅读时间需要12分钟。

回我我们说，用正规表述来表示词法分析中的单词规则。正规表述的规则易于理解，但正规表述本身并不能直接用来解析字符串。我们还需要引入一种适合转化为计算机程序的模型。

上回我们说到用正则表达式来表示词法分析中的单词规则。正则表达式的规则很容易理解，但是正则表达式并不能直接用来解析字符串，我们还要引入一种适合转化为计算机程序的模型。今天我们引入的这种模型就叫做有穷自动机（finite automation，FA）,有时也叫有穷状态机（finite state machine）。有穷自动机首先包含一个有限状态的集合，还包含了从一个状态到另外一个状态的转换。有穷自动机看上去就像是一个有向图，其中状态是图的节点，而状态转换则是图的边。此外这些状态中还必须有一个初始状态和至少一个接受状态。下面的图展示了一个有穷自动机，有根从外边来的箭头指向的状态表示初始状态，有个黑圈的状态是接受状态：

现在我们来看看有穷自动机怎么处理输入的字符串：

1. 一开始，自动机处于初始状态
2. 输入字符串的第一个字符，这时自动机会查询当前状态上与输入字符相匹配的边，并沿这条边转换到下一个状态。
3. 继续输入下一个字符，重复第二步，查询当前状态上的边并进行状态转换
4. 当字符串全部输入后，如果自动机正好处于接受状态上，就说该自动机接受了这一字符串。

刚才我们画的自动机，假如输入的字符串是"hello"（带引号）。