正则转nfa：bug出现。
2024-08-28 13:27:48
本人写的一个正则到nfa的bug
刚写完前面的那篇，自己用脑子过了一下，发现了一个bug。具体情况如下。
这个bug的产生条件是多次调用假名的时候，每次调用都会修改假名的nfa图。直接这么说不好理解，我就拿例子来讲吧。假设我们已经定义了一个假名num,而现在我们有一个正则表达式调用了两次这个假名，nums:[num][num],根据前面那篇文章里面所谈到的方法，会生成如下所示的nfa。这里假设num的开始节点为1，结束节点为2。
但是由于两个节点1和两个节点2引用的是相同的位置，所以上面的图等价于下面的图。
可以明显的看出这个并不是我们所需要的规则，图中所表示的是[num]+。之所以出现这种错误，是因为每次引用这个假名的时候，都会修改里面的内部节点。为了改掉这个bug，则必须在每次引用一个假名的时候，都生成两个新的节点，作为假名的头节点和尾节点。这个头节点与子节点的头节点有空转换边，同时子节点的尾节点到尾节点也有空转换边。这样就可以保证不会出现修改内部节点的情况了。修改后的nfa如图所示。
这个图可以简化为以下的图
可以看出，这个仍然不是我们所需要的规则，前面的那些设想都是错误的。
没办法，只有一个方法可以彻底解决这个假名问题，就是每次引用一个假名时，都生成一个这个假名的nfa的副本，并重命名节点的标号。在前面的代码中，我们构建了可以使用的信息。因为在生成假名的nfa之后，我们保留了他的开始节点和结束节点。从他的开始节点开始，遍历他的邻接表，每次碰到一个节点的时候，生成一个新的节点来替代原来的节点，并拷贝她的邻接表，并修改邻接表，使他指向一个新的等价的标号。由此我们就生成了一个等价的nfa图。每一个原来的nfa图的节点都有且只有一个处于新的nfa图的节点与之相配对。
具体代码将在下一篇中实现。
最新文章
- vs2010中的MSBuild输出warning MSB8012问题
- 迷信AgainAndAgain
- Trying to hack Redis via HTTP requests
- shell脚本学习
- BZOJ-1015 StarWar星球大战 并查集+离线处理
- c# TCPclient
- c# 加密/解密 哈希
- Entity Framework问题：ReferentialConstraint 中的依赖属性映射由存储生成的列
- editpuls查找替换通配符
- cf B. Jeff and Periods
- 【个人笔记】《知了堂》express模块
- 【BZOJ3223】文艺平衡树（Splay）
- matlab函数每天进步一点点
- ArrayList 的代码
- JavaBasic_11
- <亲测>centos安装 .net core 2.1
- CS229 6.12 Neurons Networks from self-taught learning to deep network
- 01. pt-align
- Linux下识别所有Android设备的方法
- jsp页面获取集合的长度