副标题#e#
上一篇博客讲到告终构标记表的工作。结构完标记表之后，就要进入语义阐明的后一个阶段了：结构状态机。跟我以前写的如何实现正则表达式引擎的两篇文章讲的一样，自念头先从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和","两种。下一步即将演示如何从这个状态机编程名副其实的下推状态机。
本栏目
#p#副标题#e#
在这里我先先容几个观念。第一个是移进，第二个是规约。为什么要用这两个名字呢？因为大部门人看的傻逼清华大学出书社的低能编译道理讲义都是这么讲的，黑化别离叫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上：
#p#分页标题#e#
然后就轮到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)要设计成谁人样子。
