使用增量測試的Javascript正則表達式

Question

我正在查找可以檢查字符串是否與增量式匹配正則表達式（即一次一個字符）並返回不確定結果的JavaScript庫（理想情況下爲node.js包）。例如，假設我有以下正則表達式：

j.*s.* 

而且我想測試字符串「javascript」。我想類似如下的API：

var iregex = new IncrementalRegex('j.*s.*'); 
var matcher = iregex.createMatcher(); 
matcher.append('j'); 
matcher.test(); //returns "possible match" 
matcher.append('a'); 
matcher.test(); //returns "possible match" 
matcher.append('v'); matcher.append('a'); matcher.append('s'); 
matcher.test(); //returns "match found" 
matcher.append('ript'); 
matcher.test(); //returns "match found" 

而如果我測試的字符串「foo」，我希望這樣的事情：

var matcher2 = iregex.createMatcher(); 
matcher.append('f'); 
matcher.test(); //returns "no match possible" 
//At this point I wouldn't bother appending "oo" because I know that no match is possible. 

編輯： 要清楚，追加是建立正在測試的字符串。一個新的匹配器開始對空字符串進行測試，並在matcher.append（'foo'）之後匹配foo。 appendToString或buildUpString可能是更好的名稱使用。

此外，我有一個想法，這可能是如何做到的，但我還沒有完全想到它通過。也許有可能從原始正則表達式中構建一個匹配字符串的「潛在匹配」正則表達式，當且僅當它們是原始正則表達式匹配的字符串的開始。

Answer 1

您的「IncrementalRegex」可以通過使用封裝的RegExp對象來實現。

function Matcher(pattern, flags) { 
    this.setExpression(pattern, flags); 
} 

Matcher.prototype.setExpression = function(pattern, flags) { 
    this.pattern = pattern; 
    this.flags = flags; 
    this.re = new RegExp(this.pattern, this.flags); 
}; 

Matcher.prototype.append = function(pattern) { 
    this.setExpression(this.pattern + pattern, this.flags); 
}; 

Matcher.prototype.test = function(str) { 
    return this.re.test(str); 
}; 

var matcher = new Matcher('j.*s.*', 'i'), 
    str = 'JavaScript'; 

function test() { 
    console.log(matcher.re.source, ':', matcher.test(str)); 
} 

test(); // true 
matcher.append('ri'); 
test(); // true 
matcher.append('.t'); 
test(); // true 
matcher.append('whatever'); 
test(); // false​ 

http://jsfiddle.net/f0t0n/Nkyyd/

你能描述準確的業務需求？也許我們會爲您的任務實施找到一些更優雅的方式。

Answer 2

如果你的解析器規則只使用適當的形式語言正則表達式（即沒有反向引用，前瞻或lookbehinds），你可以將它們翻譯成NFA（使用湯普森的構造或類似的），然後通過標準的雙向堆棧NFA模擬算法：如果角色沒有轉換，你就得到「否」。如果有一個，並且在當前狀態集中有一個最終狀態，那麼你已經有了「是」;否則你有「也許」。