提高 JavaScript 中正则表达式的性能，以针对整个字符串进行测试

Question

我有一个正则表达式，用于测试键=值和键1 = 值1等模式。 它走/^(?:(?:'[ws]+'|w+|"[ws]+")+s{0,}(?:=|>|<|>=|<=|!=)s{0,}(?:'[ws]+'|w+|"[ws]+")+s{1,}(?:AND|OR)s{1,})+(?:'[ws]+'|w+|"[ws]+")+s{0,}(?:=|>|<|>=|<=|!=)s{0,}(?:'[ws]+'|w+|"[ws]+")+s{0,}$|(?:^(?:'[ws]+'|w+|"[ws]+")+s{0,}(?:=|>|<|>=|<=|!=)s{0,}(?:'[ws]+'|w+|"[ws]+")+s{0,}$)|(?:^s{0,}$)/.

现在这在功能上是正确的，但在 20-25 个字符后非常慢，大约需要 30 秒才能评估。这里可以改进什么。

我知道这不是一个非常具体的问题，但仍然是一个需要输入的问题。

Answer 1

问题是这些：

(?:'[ws]+'|w+|"[ws]+")+

当匹配失败时，许多正则表达式引擎会尝试许多可能的匹配，以便在整体+内进行w+。将w+替换为w应该可以提高性能。

此外，您的正则表达式具有如下结构：

^(TERM (AND|OR) )+TERM$|^TERM$|^$

可以简化为

^(TERM (AND|OR) )*TERM$|^$

像这样显式构造它可能会有所帮助(好的名字选择取决于你(：

const FOO = /(?:w|'[ws]+'|"[ws]+")/.source;
const COMPARE = /(?:=|>|<|>=|<=|!=)/.source;
const BAR = String.raw`(?:${FOO}+s*${COMPARE}s*${FOO}+)`;
const BAZ = String.raw`^(?:${BAR}s+(?:AND|OR)s+)*${BAR}s*$|^s*$`;

Answer 2

这是一个简化版本。它使用 Ry 提供的架构，除了我删除了键和值的量词。

^
# key 
(?:'[ws]+'|w+|"[ws]+")
# operator
s*
(?:[=><]|[><!]=)
s*
# value
(?:'[ws]+'|w+|"[ws]+")
# 0 or more Boolean operator, key operator value
(?:
s+(?:AND|OR)s+
(?:'[ws]+'|w+|"[ws]+")
s*
(?:[=><]|[><!]=)
s*
(?:'[ws]+'|w+|"[ws]+")
)*
s*
$

演示

Answer 3

您的正则表达式变得很慢，因为它会在得出没有匹配项的结论之前进行大量回溯。

我会在这个过程中添加一些JavaScript，这样你不仅可以得到格式是否正确，还可以得到标记化版本，以防它是正确的。然后，该输出也可以删除包装引号：

// Returns array of tokens when given string has valid format, otherwise: undefined
function parse(s) {
let regex = /(["'])(.+?)1|((AND|OR)|(w+))|(!=|<=?|>=?|=)|S/gi;
let result = [];
if (!s.trim().length) return result; // boundary case: empty input
function nextToken(i, j) { 
let match = regex.exec(s);
// Arguments i[, j] define which capture group(s) should be scanned for a value 
match = match && (match[i] || match[j]);
return match && result.push(match);
}

const logical = () => nextToken(4); // AND or OR
const value = () => nextToken(2, 3); // quoted or unquoted non-empty string
const comparator = () => nextToken(6); // <, <=, =, !=, >=, >
const comparison = () => value() && comparator() && value();
do {
if (!comparison()) return; // invalid format
} while (logical());
return regex.lastIndex ? undefined : result; // ok if at end of input
}
// Example call:
let res = parse(`"a key" = "it's value" AND '100-1' <= 99 OR what=that   `);
console.log(res);