刚刚发了上一篇文章之后就发现状态机画错了。虽然LiveWriter有打开博客并修改文章的功能，不过为了让我留下一个教训，我还是决定发一篇勘误。这个教训就是，作分析的时候不要随便“跳步”，该一步一步来就一步一步来。其实人呢，就是很容易忘掉以前的教训的了。第一个告诉我不能这么干的人其实是小学三年级的数学老师。当时我因为懒得写字，所以计算应用题的时候省了几步，被批评了。
故事就从状态机开始。文法我就不重复了，见上一篇文章。现在我们从状态机开始。第一个状态机是直接从文法变过来的：
开发纪事（三点五） 生成下推自动机的具体步骤-可配置交换显卡没有了">
然后我们把所有的非终结符跳转都通过Shift和Reduce连接到该非终结符所代表的状态机的状态上面，就会变成下面的图。具体的做法是，对于每一条非终结符的跳转，譬如说S0 –> Symbol –> S1。首先抹掉这条跳转。然后增加两条边，分别是S0到Symbol的起始节点，操作是Shift<S0>。还有从Symbol的终结节点到S0，操作是Pop<S0> Reduce。Shift<S>等于把状态S给push到堆栈里，然后Pop<S>等于在状态里面弹出内容是S的栈顶元素。如果失败了怎么办呢？那就不能用这条跳转。跟上图一样，所有输入$跳转到Finish的边，操作都是要Pop<Null>的。在刚开始分析的时候，堆栈有一个Null值，用来代表“语法分析从这里开始”。
这个图的粗虚边代表所有跟左递归有关的跳转。这些边是成对的，分别是左递归跳转的Shift和Reduce。如果不是为了实现高性能的语法分析的话，其实这个状态机已经足够了。这个图跟语法分析的“状态跳转轨迹”有很大的关系。虽然IDList0你不知道第一步要跳转到IDList0还是ID0，不过没关系，现在我们先假设我们可以通过某种神秘的方法来预测到。那么，当输入是A,B,C$的时候，状态跳转轨迹就会是如下的样子：