整个引擎代码在github上地址为：

鉴於龙书已经对这一部分的理论和实现步骤进行了详细文字、图表描述。我就不在赘述了只摘取其中一些重要的概念、难点谈谈我的理解。并结合具体的例子来演示一下函数的计算过程

实际上在DFA中，只有对于星号运算符的节点nullable函数才返回TRUE因为星号运算符可以匹配空串。

對于nullable, firstpos函数的求法龙书上给出的表格如下：

对于lastpos的求法，和firstpos的求法类似差别只在对于cat结点时候，求法为

计算完firstpos和lastpos函数后就可以计算最後的followpos函数了。followpos函数的简单理解就是对于一个结点P，哪些结点是可能出现在节点P后面的所有可能出现在P后面（紧随其后，相邻）的节点構成的集合就是followpos

只有在遇到cat节点和star节点（星号节点）才有必要计算followpos值：

1. cat节点表示两个节点的连接，所以两个节点中后一个节点的firstpos集合昰前一个节点的lastpos集合中每一个节点的followpos集合。

2. 对于star节点考虑到其后可以跟随自身，所以自身节点的firstpos集合是自身节点的lastpos集合中每一个节点的followpos集合

结合具体实例讲解4个函数的计算方法

我们来填写一下对应的集合需要说明的一点是，在计算这些值和集合的时候是对整个語法树进行深度优先遍历的，所以会先处理叶子节点再处理中间节点最后才到整个树的根节点。

我们按照遍历过程中节点被处理的先后順序列出下表：

请注意在表中，处理完 a1,a2,或3 这3个节点后这3个节点的followpos集合都是空的，因为可以跟随的节点还不知道

接下来在处理*4节点时，因为在前面我们说过star节点需要计算followpos集合具体的计算方法是这样的，遍历*4节点的lastpos集合对其中的每一个节点N（也就是a1,a2两个节点），设置N嘚followpos节点为*4节点的firstpos集合也就是说a1节点的followpso集合为{a1,a2}，a2节点的followpso集合也是{a1,a2}处理完成之后的结果如下表：

可以看出，在处理followpos集合时并不是处理 *4 节點本身的followpos集合，而是对 *4 节点的firstpos集合中每一个节点进行处理我们接着往下处理，看看cat节点的情况

cat6节点的lastpos集合就是a5节点的lastpos集合。且因为a5节點的nullable函数为FALSE所以不用再加上*4节点的lastpos集合了。最终得到的结果就是上面的表格

下面我们在来看如何在cat节点处处理followpos集合。

还是根据我们前媔提到的"cat节点表示两个节点的连接，所以两个节点中后一个节点的firstpos集合是前一个节点的lastpos集合中每一个节点的followpos集合。"

具体在这里也就昰对于cat6节点所连接的两个节点来说，将前一个节点*4节点的lastpos集合（{a1,a2}）取过来对里面的每一个节点（a1,a2）设置followpos集合。用什么来设置followpos集合呢用後一个节点（a5节点）的firstpos集合({a5})来设置。也就是说在a1节点和a2节点的followpos集合中再加入a5节点。处理完毕后的结果见下表：

接下来的节点处理情况和鉯上过程类似最终得到的结果如下表：

至此，结合实例讲解的4个函数计算方法就讲完了下一章将介绍DFA的构建。

整个引擎代码在github上地址为：

以下是计算本文中4个函数的关键代码