正则到nfabug的解决方法

前面提到了这个bug，为了解决这个bug，我们必须在每次引用到一个假名的时候，都构建一个拷贝。现在假设我们遇到了一个假名，并得到了他的开始节点和结束节点，当前的难题就是构造这个假名所代表的nfa的副本。构造方法类似于子集构造法，我们设立一个集合，这个集合为R，集合中的每个元素都有一个标志位为访问位。初始化R为开始节点a，并让他的访问位为0。现在开始进入迭代，只要R中存在访问位为0的点，将他的访问位改为1，然后将他的邻接表中的点都加入到R中。加入的时候，考虑R中是否已经存在这个元素，如果已经存在，则不加入。如果不存在，则加入，并设置访问位为0。然后返回迭代判断。

最后当R中的元素不再增加的时候，为每一个元素设置一个新的节点，即对于每个元素a，都有一个f(a)与之对应。为f(a)设置邻接表，就是a的邻接表的拷贝，但是里面的目标地址b都变成了f(b)。这样我们就完成了nfa图的复制工作。由于有集合操作，主要任务为插入和查找，所以实现的时候考虑建立一个散列表，采取开放寻址的线性探查，来加速操作。

但是，如果我们证明了，任何一个假名的nfa节点的标号集合是一个连续的整数区间的话，我们就可以以非常高的效率来做到nfa图的复制。下面我们就来证明一个nfa图里面所有的标号刚好完全占据了一个整数区间，而这个证明需要数学归纳法。我们对一个正则表达式里面的假名嵌套深度来归纳。设s为嵌套深度。

当s为零的时候，即表达式里面没有引用。这个时候考虑我们在分配nfa节点时候的分配策略，我们保留了一个全局的nfa_node_number，每分配一个节点，这个就加1，然后把这个值当作节点的标号，这些节点都是一个一个连续分配的，而且他们没有进入的边，也没有出去的边。所以我们可以为这个正则表达式附加他的最小标号节点和最大标号节点，这样就可以避免集合操作，因为这之中的点都属于该正则表达式。而且这样在重新映射的时候，映射函数可以改为线性函数，直接采用加法规则就可以了。

现在考虑s为1的时候，即正则表达式中拥有一个s为0的假名的引用。由于nfa_node_number是全局的，我们考虑刚开始进入这个正则表达式的时候，可用的标号为a,当进入这个引用时，可用标号为b，即在拷贝nfa图的时候引起的节点分配是以b开始的。由于进行拷贝nfa图的时候，节点分配是连续的，假设拷贝完之后，可用标号为c，则b-c之间的标号都被使用了。由于a-b之间的标号都被使用了，所以a-c之间的标号也是都被使用了，因此a-c之间是连续的，并一直向右扩展，当这个正则表达式处理完的时候，可用标号为d，则a-d之间的标号都被这个正则表达式使用了，因此我们也可以设置这个正则表达式的开始标号与结束标号 。

虽然我们当前讨论的是不怎么严格的数学归纳，但是我们可以从上面的讨论可以看出，每一个假名所代表的正则表达式都有他的起始标号和结束标号，而且之间的标号都是被这个正则表达式所使用的，外部标号的节点不会跟这些标号的节点相连。因此我们可以将这两个域添加到这个假名的信息里面去。

我将用代码来描述如何维护这些信息，以及利用这些信息来做nfa图的复制。