上一篇博客讲到了构造符号表的事情。构造完符号表之后，就要进入语义分析的后一个阶段了：构造状态机。跟我以前写的如何实现正则表达式引擎的两篇文章讲的一样，自动机先从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和","两种。下一步即将演示如何从这个状态机编程名副其实的下推状态机。

在这里我先介绍几个概念。第一个是移进，第二个是规约。为什么要用这两个名字呢？因为大部分人看的傻逼清华大学出版社的低能编译原理课本都是这么讲的，黑化分别叫Shift和Reduce。好了，什么是Shift呢？IDList0跳到IDList2的时候，要移进IDList。IDList3跳到IDList1，要移进到ID。IDList0跳到IDList1也要移进到ID。这也就是说，状态转移经过一条非终结符的边的时候会移进到另一条文法的状态机里。ID1和IDList1作为ID和IDList的终结节点，要根据“从那里移进来的”分别规约然后跳转到“IDList2或者IDList1”。这也就是说，一旦你到达了一条闻法的状态机的终结状态，就要开始规约然后跳转到上一级的状态了。

有人要问，那我怎么知道规约结束的时候要跳转去哪里呢？这个问题问得非常好。让我们回想一下我以前写的如何手写语法分析器这一篇文章。里面怎么说的？当你手写递归下降的语法分析器的时候，每一条文法其实都是一个函数。那调用函数的时候程序怎么就知道函数结束的时候下一条指令是什么呢？那当然是因为编译器帮我们把“调用函数的时候的下一条指令的地址”给push进了调用堆栈。但是我们现在不手写语法分析器了，而用下推状态机来做，道理也是一样的。在“移进”的时候，先把当前的状态push进堆栈，规约的时候，就可以看一下“栈顶那几个状态都是什么”，配合一次向前查看（这就是Look Ahead。LALR的那个LA，LALR(1)就是在LA的时候偷看一个token），来决定规约到哪里去。至于LA在这里的深刻内涵我将下一篇文章再说。因为现在我还没有做到Nondeterministic到Deterministic的一步，里面有很多黑科技，我想集中讨论。

那现在让我们把上面那幅图的两个状态机连起来，产生一个下推自动机。但是在这里我先做第一步。因为IDList0到IDList1的跳转是一个左递归的过程，先暂时不管。

橙色的边都是一个输入非终结符的跳转，所以实际上在下推状态机里面是不存在的。在这张图里面我们处理了两条ID的边。IDList0会shift（就是在堆栈里面push）自己然后跳转到ID0，因此ID1在查看到栈顶是IDList0的时候，他就知道走的是IDList0 –> ID –> IDList1这条路，因此就reduce并跳转到了IDList1。IDList3同理。

但是Shift的时候并没有产生输入，所以实际上应该改成下面这个样子。

这样Shift边也就有输入了。而且ID0到ID1也废掉了。实际上ID0自己也应该废掉。现在还有一个问题没解决，就是左递归和Reduce不产生输入的问题。这两个问题实际上是一起的。我们先来考虑一下为什么这里没办法用相同的办法来把Reduce处理成产生输入的。实际上是因为，你在这一个阶段还不知道究竟Reduce要输入什么才能跳转，特别是token已经结束并且parse出了一个完整的IDList的时候。以前你们是不是在看《Parsing Techniques》和《龙书》都对为什么一个字符串结尾要产生一个$字符感到很困惑呢？实际上他是特别有用的。现在我们来给他加上大家就明白了。在这里，这个文法的目标是产生一个IDList结构，所以$当然也要加在IDList的终结状态——IDList1上：

然后就轮到Reduce。ID1应该是Reduce到哪里了？第一步自然是Reduce到IDList1。那么IDList1又要Reduce到哪里呢？我们可以看到，在IDList结束的时候，要么就是跳到IDList2，要么就是跳到FINISH。但是IDList2是通过左递归产生的，我们先不管他。跳到FINISH需要什么条件呢？第一个是输入$，第二个是Pop完状态之后堆栈会为空。所以这个时候我们可以先修改一下ID1到IDList1的Reduce边：

最后就是左递归了。左递归的处理有点像hack，因为实际上你不能预先判断你要不要左递归（也就是看一下token stream有多少个逗号），然后先shift几个IDList0进去，再慢慢来。所以我们只有在满足跳转关系的时候临时插入一些IDList0。那么这个关系是什么呢？左递归的IDList结束——也就是从IDList0跳到IDList2——之后只有一种可能，就是输入","。而且所有指向IDList1的边都是输入ID，所以这条左递归的线应该从ID1（ID的终结状态）连到IDList2，并且在链接的时候补充“假shift IDList0”：

橙色的两个状态分别是整个parsing过程的起始状态和终结状态。这个时候我们把所有没用的边和状态都干掉，就变成了：

是不是觉得特别亲切呢，这不就是正则表达式NAME ( “,” NAME)*的状态机吗？这也是因为这个文法刚好可以表达为一个正则文法才有这样的结果，如果我们给他加点儿括号改变点优先级什么的，那就会变成一个复杂得多的状态机了。好了。现在我们来模拟一下下推状态机的状态转换和堆栈操作过程，来分析一下A,B,C$这个输入吧。

在下面的标示图里面，我们用s|abc|def来分别表达当前状态s、当前堆栈里的状态abc（栈顶在右边）和正在等待的输入def。那么初始状态肯定就是
IDList0 | null | A,B,C$

然后就开始了！（用文字表达实在是太难看了，所以贴成图）

如果成功到达FINISH并且堆栈和输入都全部没有了的话，那就证明，parsing过程完美结束，没有任何错误发生。

如何从文法生成下推自动机并完成parsing工作的大概过程就写到这里了。目前开发进度是到“生成非确定性下推自动机”这里。当我完成了生成“确定性下推自动机”——也就是上面的最后一个状态机图的时候——就会开始写下一篇文章，讲面对复杂的文法的时候，下推自动机将要如何调整。同时将重点描述Look Ahead部分，以及为什么LALR(1)要设计成那个样子。