Tag: nfa

如何为基于NFA的正则expression式“a * b * a +”工作

我在JS中写了一个简单的正则expression式parsing器，parsing器只支持“*”和“+”，然后我发现一个问题。 “aa”匹配/ a * b * a + /的结果是错误的。 这是我的过程。 首先，我用REstring新build一个NFA图。 如图所示，状态5有一个计数器，如果计数器> = 1，状态5将指向“_end”，graphics将被连接。 从状态0开始，执行DFS，logging每个访问节点。 匹配string，如果两者相等，则下一个状态的计数器+1，然后从下一个状态开始DFS。 当string结束时，检查被访问节点，如果状态为6，则返回true，否则返回false。 这是我的代码。 var Graph = require(__dirname + '/../Graph.js'); var DFS = require(__dirname + '/../DFS.js'); var NFA = module.exports = function(regexp) { var ops = new Array(); // stack this.re = regexp; this.M = this.re.length; this.G = new Graph(this.M + […]