可配置语法分析器开发纪事（五）——构造一个真正能用的状态机（中）

上一篇博客写到了如何给一个非终结符的文法规则构造出一个压缩过的下推状态机，那么今天说的就是如何把所有的文法都连接起来。其实主要的idea在（三）和他的勘误（三点五）里面已经说得差不多了。但是今天我们要处理的是带信息的transition，所以还有一些地方要注意。

所以在这里我们先把几条文法的最后的状态机都列出来（大图）：

接下来的这一步，就是要对所有靠非终结符（Exp啊Term这些）进行跳转的transition都执行上一篇文章所说的传说中的交叉链接。在产生链接的时候，我们给shift和reduce的边分别加上shift和reduce。而shift和reduce是有参数的——就是被shift走的状态的id。这样可以在parse的时候匹配和处理状态堆栈。在这里我门对e3->e1这一步做一下操作做为例子。红色的边是被删掉的，而粗壮的绿色边是被新加进去的：

红色的边变成了两条绿色的边，红色的边附带的信息则被复制到了绿色的reduce边上。当我们使用这个状态机的时候，shift(s3)就表示往堆栈里面压入s3，reduce(s3)就表示从堆栈里面弹出(s3)。当然弹出不一定会成功，所以如果不成功的话，这条边就不能在当时使用。因此这也就是为什么在e3跳转到t0之后，t1知道往回跳的是e1而不是别的什么地方——就如同为什么C++的函数执行完之后总是知道如何跳转回调用它的地方一样——因为把信息推入了堆栈。

那现在我们就来看一下，当所有的非终结符跳转都处理掉之后，会变成什么样子吧（这个图真是复杂和乱到我不想画啊），为了让图变得不那么糟糕，我把shift都变成紫色，reduce都变成绿色：

在添加shift和reduce边之前，每一条边都是有输入token的。但是我们刚刚添加上去的shift和reduce边却是不输入token的，所以他们是epsilon边，下一步就是要消除他们。上面这个图消除了epsilon边之后，会变成一个状态很少，但是每一条边附带的信息都会非常多，而且像n1这种经常到达的状态（因为四则运算里面有很多数字）将恢复射出无数条边。到了这里这个状态机已经再也画不出来了。所以我下面就只拿两个例子来画。下面要展示的是用Exp来parse单独的一个数字会走的边，当然就是Exp –> Term –> Factor –> Number了：

就会被处理成：

注意边上面的信息是要按顺序重新叠加在一起的。当所有的epsilon边都去掉了之后，我们就得到了最终的一个状态机。最重要的一件事情出现了。我们知道，发明LR和LALR这种东西就基本上是为了处理左递归的，所以这种图就可以在去除epsilon边的过程中自动发现左递归。这是怎么做到的呢？只要在去除epsilon边的时候，发现了一条完全由shift这种epsilon边组成的环，那么左递归就发现了。为了方便，我们可以只处理直接左递归——就是这种环的长度是1的。不包含间接左递归的问法是很容易写出来的。当然这种环并不一定是首尾相接的，譬如说我们在处理e0的时候就会发现e0->t0->t0这种环（当然严格来说环只有最后一截的这个部分）。我们的程序要很好地应对这种情况。因为我们只接受直接左递归，所以类似这种结构的epsilon路径可以直接的抛弃他，因为t0->t0会被t0状态单独处理掉。因此这样做并不会漏掉什么。

细心的朋友可能会发现，这个结构的图是不能直接处理右递归的（总之左递归和右递归总要有一个会让你的状态机傻逼就是了！）。关于如何处理有递归（其实内容也不复杂）地方法会在“下篇”描述出来。那处理左递归有什么用呢？举个例子，我们的e0->e2就是一个左递归，而他会在之前的步骤被处理成shift(e0->e0)和reduce(e1->e2)。我们要记下shift和reduce的对应关系，那么当我们找到一个左递归的shift之后，我们就可以把对应的reduce给标记成“left-recursive-reduce”。这是一个在构造语法树的时候，非常关键的一种构造指令。

处理完这些之后，我们可以把左递归的shift边全部删掉，最后把token和state都统统处理成连续的数字，做成一张[state, token] –> [transitions]的二维表，每一个表的元素是transition的列表。为什么是这样呢？因为我们对一个state输入一个token之后，由于保存着state的堆栈（你还记得吗？shift==push，reduce==pop）的栈顶若干个元素的不同，可能会走不通的路线。于是最后我们就得到了这么一张图。

下面这张图可以通过运行gac.codeplex.com上面的CommonUnitTestUnitTest.sln（VS2012限定）之后，在CommonUnitTestTestFilesParsing.Calculator.Table.txt里面找到。这一组文件都是我在测试状态机的时候log下来的。

如果大家有VS2012的话，通过运行我准备的几个输入，譬如说“1*2+3*4”，就可以在Parsing.Calculator.[2].txt里面找到所有状态跳转的轨迹。因为我们总是需要parse一个Exp，所以我们从22: Exp.RootStart开始。我们假设token stream的第一个和最后一个分别是$TokenBegin和$TokenFinish。上图的$TryReduce是为了应对右递归而设计出来的一种特殊输入。由于四则运算里面并没有右递归，所以这一列就是空的：

StartState: 22[Exp.RootStart]
$TokenBegin => 23[Exp.Start]
    State Stack:
NUMBER[1] => 2[Number.1]
    State Stack: 23[Exp.Start], 21[Term.Start], 19[Factor.Start]
    Shift 23[Exp]
    Shift 21[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
MUL[*] => 5[Term.3]
    State Stack: 23[Exp.Start]
    Reduce 19[Factor]
    Using
    Reduce 21[Term]
    Using
    LR-Reduce 21[Term]
    Assign firstOperand
    Setter binaryOperator = Mul
    Create BinaryExpression
NUMBER[2] => 2[Number.1]
    State Stack: 23[Exp.Start], 5[Term.3], 19[Factor.Start]
    Shift 5[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
ADD[+] => 10[Exp.3]
    State Stack:
    Reduce 19[Factor]
    Using
    Reduce 5[Term]
    Assign secondOperand
    Reduce 23[Exp]
    Using
    LR-Reduce 23[Exp]
    Assign firstOperand
    Setter binaryOperator = Add
    Create BinaryExpression
NUMBER[3] => 2[Number.1]
    State Stack: 10[Exp.3], 21[Term.Start], 19[Factor.Start]
    Shift 10[Exp]
    Shift 21[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
MUL[*] => 5[Term.3]
    State Stack: 10[Exp.3]
    Reduce 19[Factor]
    Using
    Reduce 21[Term]
    Using
    LR-Reduce 21[Term]
    Assign firstOperand
    Setter binaryOperator = Mul
    Create BinaryExpression
NUMBER[4] => 2[Number.1]
    State Stack: 10[Exp.3], 5[Term.3], 19[Factor.Start]
    Shift 5[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
$TokenFinish => 11[Exp.RootEnd]
    State Stack:
    Reduce 19[Factor]
    Using
    Reduce 5[Term]
    Assign secondOperand
    Reduce 10[Exp]
    Assign secondOperand

我们把所有跳转过的transition的信息都记录下来，就可以构造语法苏了。我们想象一下，在执行这些指令的时候，遇到NUMBER[4]就等于获得了一个内容为4的token，shift的话就是往堆栈里面push进一个状态的名字，而reduce则是弹出。

相对应的，因为每一个文法都会创建一个对象，所以我们在初始化的时候，要先放一个空对象在堆栈上。shift一次就再创建一个空的对象push进去，reduce的时候就把栈顶的对象弹出来作为“待处理对象”，using了就把待处理对象和栈顶对象合并，left-reduce就是把栈顶对象弹出来作为待处理对象的同时，push一个空对象进去。assign fieldName就是把“待处理对象”保存到栈顶对象的叫做fieldName的成员变量里面去。如果栈顶对象为空，那么被保存的对象就是刚刚输入的那个token了。因此我们从头到尾执行一遍之后，就可以得到下面的一颗语法树：

BinaryExpression {
    binaryOperator = [Add]
    firstOperand = BinaryExpression {
        binaryOperator = [Mul]
        firstOperand = NumberExpression {
            value = [1]
        }
        secondOperand = NumberExpression {
            value = [2]
        }
    }
    secondOperand = BinaryExpression {
        binaryOperator = [Mul]
        firstOperand = NumberExpression {
            value = [3]
        }
        secondOperand = NumberExpression {
            value = [4]
        }
    }
}

基本上parsing的过程就结束了。在“下篇”——也就是（六）——里面，我会讲述如何处理右递归，然后这个系列基本上就要完结了。