如何为基于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 + 1, regexp); for (var i = 0; i < this.M; i++) { if (this.re[i] == '*' || this.re[i] == '+') { this.G.addEdge(i, i - 1); this.G.addEdge(i - 1, i); } if (this.re[i] == '*') this.G.addEdge(i, i + 1); } }; NFA.prototype.recognize = function(txt) { var pc = new Array(); var dfs = new DFS(this.G, 0); for (var v = 0; v < this.G.getV(); v++) { if (dfs.marked[v] == true) { pc.push(v); } } for (var i = 0; i < txt.length; i++) { var match = new Array(); for (var v = 0; v < pc.length; v++) { if (pc[v] < this.M) { if (this.re[pc[v]] == txt[i]) { match.push(pc[v] + 1); this.G.counter[pc[v] + 1]++; var cnt = this.G.counter[pc[v] + 1]++; if (cnt == 1) { this.G.addEdge(pc[v] + 1, pc[v] + 2); } } } } pc = new Array(); dfs = new DFS(this.G, match); for (var v = 0; v < this.G.getV(); v++) { if (dfs.marked[v] == true) { pc.push(v); } } } for (var v = 0; v < pc.length; v++) { if (pc[v] == this.M) { return true; } } return false; }; 结果：
- “aa”match / a * b * a + / true
- “aab”match / a * b * a + / true（应该是false）
- “aab”match / a * b * aa * / false（这是我的临时处理方法）
- “aa”match / a * b * aa * / true
我想知道该怎么办才能修复这个bug，我不想用临时处理的方法。 非常感谢。