улучшить производительность регулярных выражений в JavaScript для тестирования всей строки

Question

У меня есть регулярное выражение, которое проверяет наличие паттерна, такого как ключ = значение и ключ1 = значение1. Это идет /^(?:(?:'[\w\s]+'|\w+|"[\w\s]+")+\s{0,}(?:=|>|<|>=|<=|!=)\s{0,}(?:'[\w\s]+'|\w+|"[\w\s]+")+\s{1,}(?:AND|OR)\s{1,})+(?:'[\w\s]+'|\w+|"[\w\s]+")+\s{0,}(?:=|>|<|>=|<=|!=)\s{0,}(?:'[\w\s]+'|\w+|"[\w\s]+")+\s{0,}$|(?:^(?:'[\w\s]+'|\w+|"[\w\s]+")+\s{0,}(?:=|>|<|>=|<=|!=)\s{0,}(?:'[\w\s]+'|\w+|"[\w\s]+")+\s{0,}$)|(?:^\s{0,}$)/.

Теперь это функционально правильно, но очень медленно после 20-25 символов и занимает около 30 секунд для оценки. Что можно улучшить здесь.

Я понимаю, что это не очень конкретный вопрос, но все же тот, который требует ввода ..

Answer 1

Вот упрощенная версия. Он использует схему, предоставленную Ry, за исключением того, что я удалил квантификатор для ключей и значений.

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

Demo

Answer 2

Ваше регулярное выражение становится медленным, потому что оно выполнит большой откат до того, как сможет прийти к выводу, что совпадения нет.

Я бы добавил немного 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);

Answer 3

Проблема заключается в следующем:

(?:'[\w\s]+'|\w+|"[\w\s]+")+

Многие движки регулярных выражений будут пытаться найти множество возможных совпадений для \w+ в общем +, если сопоставление не удастся. Замена \w+ на \w должна улучшить производительность.

Кроме того, ваше регулярное выражение имеет такую ​​структуру:

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

, которую можно упростить до

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

Возможно, было бы полезно создать это явно (выбор доброго имени на ваше усмотрение):

const FOO = /(?:\w|'[\w\s]+'|"[\w\s]+")/.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*$`;