副标题#e#
方才发了上一篇文章之后就发明状态机画错了。固然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$的时候，状态跳转轨迹就会是如下的样子：
#p#副标题#e#
为什么要这么做呢？我们把这幅图想象成为
1：想做的箭头暗示push一个状态
2：向下的箭头暗示修改当前状态
3：向右的状态暗示pop一个状态并修改当前状态
因此当输入到B的时候，达到ID1，并跳转到IDList1。这个时候IDList1【左边】的所有【还留在仓库里】的状态时Null和IDList0，当前状态IDList1，输入剩下,C$。这个图出格的有用。当我们阐明完而且把结构语法树的指令附着在这些箭头上面之后，按顺序执行这些指令就可以结构出一颗完整的语法树了。
可是在实际操纵内里，我们并没有步伐预测“这里要左递归两次”，也没步伐在多次reduce的时候选择毕竟要从那边跳到那边。所以实际上我们要进修从EpsilonNFA到DFA的谁人计较进程，把Shift和Reduce当成Epsilon，把吃掉一个token当成非Epsilon边，然后执行我之前写的《结构可设置词法阐明器》一文中的谁人去Epsilon边算法（如何从Nondeterministic到Deterministic，以及相关的Look Ahead，是下一篇文章的内容），然后就可以把状态机酿成这样：
本栏目
上面粗体的Pop<IDList0>暗示，这一个Pop是对应于谁人左递归Shifting操纵的。实际上这是做了一个奈何的变革呢？从“物理表明”上来讲，其实是把“状态跳转轨迹”内里那些除了左递归shifting之外的所有不吃掉token的边都去掉了：
在这里我们可以看到，为什么当仓库是IDList0, IDList0和IDList0, IDList3的时候，从ID0都可以通过吃掉一个”,”从而跳转到IDList3。在上面这张“状态跳转轨迹”内里，这两个工作都产生了，别离是第一条向左的箭头和第二条向左的偏向。并且这两条边恰好对应于上图带有蓝色粗体文字的跳转，属于左递归Reducing操纵。
所以，其实在这个时候，我们同时办理了“应该在什么时候举办左递归Shifting”的问题。只要当左递归Reducing已产生，我们立即在轨迹上面补上一条左递归Shifting就好了。因此，我们在一开始做parsing的时候，基础不需要预先做左递归Shifting。所以当方才输入A的时候，“状态跳转轨迹”是这样子的：
然后碰着一个”,”，发明之前“做漏”了一个左递归Shifting，因此就酿成下面这个样子：
这也就是上一篇文章谁人Fake-Shift所做的工作了。
