上一篇博客讲到了构造符号表的事情。构造完符号表之后，就要进入语义分析的后一个阶段了：构造状态机。跟我以前写的如何实现正则表达式引擎的两篇文章讲的一样，自动机先从Epsilon Nondeterministic Automaton开始，然后一步一步构造成Deterministic Automaton。但是语法分析和正则表达式有很大不同，那么这个自动机是什么样子的呢？
（对学术感兴趣的人可以去wiki一下“下推自动机”）
下推自动机和有限自动机的区别是，下推自动机扩展成普通的自动机的时候，他的状态的数目是无限的（废话）。但是无限的东西是没办法用编程来表达的，那怎么办呢？那就加入一个不定长度的“状态描述”。下面我举一个简单的文法：
ID = NAME
IDList = ID | IDList “,” ID
这样就构成了一个简单的文法，用来分析带逗号分割的名字列表的。那么写成状态机就是如下的形式：
ID0 = ● NAME
ID1 = NAME ●
IDList0 = ● (ID | IDList “," ID)
IDList1 = (ID | IDList “,” ID) ●
IDList2 = (ID | IDList ● “,” ID)
IDList3 = (ID | IDList “,” ● ID)
ID0 –> NAME –> ID1
IDList0 –> ID –> IDList1
IDList0 –> IDList –> IDList2
IDList2 –> “,” –> IDList3
IDList3 –> ID –> IDList1
可以很容易的看出，ID0和IDList0是文法的起始状态，而ID1和IDList1是文法的终结状态，画成图如下：
开发纪事（三） 生成下推自动机-可配置词法生成器">
（PowerPoint画图复制到LiveWriter里面是一幅图面简直太方便了）
但是这样还没完。IDList0跳到IDList2的时候的输入“IDList”其实还不够，因为用作输入的token其实只有NAME和","两种。下一步即将演示如何从这个状态机编程名副其实的下推状态机。
本栏目更多精彩内容：http://www.bianceng.cn/Programming/cplus/