首页 / 软件开发 / C++ / 可配置语法分析器开发纪事（三） 生成下推自动机

可配置语法分析器开发纪事（三） 生成下推自动机2014-11-01 cnblogs 陈梓瀚（vczh）上一篇博客讲到了构造符号表的事情。构造完符号表之后，就要进入语义分析的后一个阶段了：构造状态机。跟我以前写的如何实现正则表达式引擎的两篇文章讲的一样，自动机先从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/