Подтвердить что ты не робот

Жадность ведет себя по-разному в JavaScript?

Был этот вопрос, который заставило меня понять, что жадность квантификаторов не всегда одинакова в некоторых двигателях регулярных выражений. Взяв регулярное выражение из этого вопроса и немного изменив его:

!\[(.*?)*\]

(я знаю, что * здесь избыточно, но я нашел, что следующее является довольно интересным поведением).

И если мы попытаемся сопоставить с:

![][][]

Я ожидал, что первая группа захвата будет пустой, потому что (.*?) ленив и остановится при первом ], который он встретит. Это действительно то, что происходит в:

Я просмотрел несколько других языков, например ruby ​​, java, С#, но все ведут себя так, как я ожидал от них (т.е. возвращают пустые группы захвата).

(regexplanet golang, по-видимому, также получает непустые группы захвата)

Кажется, что JavaScript-механизм regex интерпретирует второй * для преобразования .*? от ленивого к жадному. Обратите внимание, что преобразование второго * в *?, похоже, заставляет регулярное выражение работать так, как я ожидал (как и полное удаление квантификатора, потому что я знаю, что он избыточен в этой ситуации, но это не точка).

* был использован в регулярном выражении, но это поведение похоже на +, ? или {m,n} и преобразование их в их ленивую версию дает те же результаты, что и с *?.

Кто-нибудь знает, что на самом деле происходит?

4b9b3361

ОТВЕТЫ

Ответ 1

Короткий ответ

Поведение определяется в спецификациях ECMA-262 в разделе 15.10.2 Семантика шаблонов, особенно в 15.10.2.5, где обсуждается семантика производственного термина:: Atom Quantifier.

Как небольшое обобщение: пусть E будет шаблоном, который может соответствовать пустой строке. Если существует входная строка S, где пустая строка является первым подходящим выбором в E, затрагиваются шаблоны, содержащие жадное повторение шаблона E. Например:

(a*?)*              against     aaaa
!\[(.*?)*\]         against     ![][][]
(.*?){1,4}          against     asdf
(|a)*               against     aaaa
(a|()|b){0,4}       against     aaabbb

Firefox и другие браузеры на основе Webkit, похоже, внимательно следят за спецификациями, в то время как IE отключен от спецификаций в случае отсутствия продолжения затронутого шаблона.

Длинный ответ

Соответствующая часть спецификаций приведена ниже. Некоторая часть спецификаций опущена ([...]), чтобы держать обсуждение актуальным. Я объясню, сконденсировав информацию из спецификаций, сохраняя ее просто.

Словарь

  • Состояние - это упорядоченная пара (endIndex, capture), где endIndex - целое число, а capture - внутренний массив значений NcapturingParens. Состояния используются для представления состояний частичного соответствия в алгоритмах согласования регулярных выражений. EndIndex - это плюс плюс индекс последнего входного символа, сопоставленного до сих пор шаблоном, в то время как захваты содержат результаты захвата круглых скобок. [...]. Из-за обратного отслеживания многие государства могут использоваться в любое время во время процесса сопоставления.
  • MatchResult - это состояние или специальный токен отказ, который указывает, что совпадение не удалось.

Здесь не должно быть путаницы. Государство отслеживает позицию, которая была обработана до сих пор (а также снимки, на которые нас сейчас не интересует). MatchResult, ну, это результат матча (duh!).

  • Процедура продолжения - это внутреннее закрытие (т.е. внутренняя процедура с некоторыми аргументами, уже привязанными к значениям), которая принимает один аргумент состояния и возвращает результат MatchResult. Если внутреннее замыкание связывает переменные, связанные с функцией, которая создает замыкание, замыкание использует значения, которые эти переменные имели во время создания замыкания. Продолжение пытается совместить оставшуюся часть (заданную аргументами уже привязанных к закрытию) шаблона против входной строки, начиная с промежуточного состояния, заданного его аргументом состояния. Если совпадение выполнено успешно, Continuation возвращает конечное состояние, которое оно достигло; если совпадение не выполняется, Continuation возвращает отказ.
  • Процедура Matcher - это внутреннее закрытие, которое принимает два аргумента - состояние и продолжение - и возвращает результат MatchResult. Матчи пытаются сопоставить средний подшаблон (заданный аргументами с привязкой уже привязанных) шаблона к входной строке, начиная с промежуточного состояния, заданного его аргументом состояния. Аргумент продолжения должен быть закрытием, которое соответствует остальной части шаблона. После сопоставления подшаблона шаблона для получения нового состояния, Matcher затем вызывает Continuation в этом новом состоянии, чтобы проверить, может ли остальная часть шаблона также соответствовать. Если это возможно, Matcher возвращает состояние, возвращенное Continuation; если нет, Матчи могут попробовать разные варианты в своих точках выбора, неоднократно вызывая Продолжение, пока это не удастся или все возможности не исчерпаны.

A Matcher содержит код для соответствия подшаблону, который он представляет, и он будет вызывать Continuation для продолжения совпадения. И Продолжение содержит код для продолжения матча, с которого закончил Matcher. Они оба признают государство в качестве аргумента, чтобы знать, с чего начать сопоставление.

Производственный срок:: Atom Quantifier

Производственный Term:: Atom Quantifier оценивается следующим образом:

  • Вычислить Atom для получения Matcher m.
  • Вычислить квантификатор, чтобы получить три результата: целое число min, целое число (или ∞) max и булевское жадное.
  • Если max является конечным и меньше, чем min, то бросьте исключение SyntaxError.
  • Пусть parenIndex - это количество левых скобок для скобок во всем регулярном выражении, которое находится слева от этого производственного расширения Term. [...]
  • Пусть parenCount - это число левых захватных скобок в расширении этого продукта Atom. [...]
  • Возвращает внутреннее закрытие Matcher, которое принимает два аргумента, состояние x и продолжение c, и выполняет следующее:
    • Вызов RepeatMatcher (m, min, max, greedy, x, c, parenIndex, parenCount) и возвращает его результат.

Обратите внимание, что m - это Matcher для Atom, который повторяется, и Continuation c передается из кода, созданного с помощью правил более высокого уровня.

Абстрактная операция RepeatMatcher принимает восемь параметров: Matcher m, целое число min, целое число (или ∞) max, булевское жадное, состояние x, продолжение c, целочисленное значение parenIndex и целочисленное значение parenCount и выполняет следующее:

  • Если max равно нулю, тогда вызовите c (x) и верните его результат.
  • Создайте внутреннее закрытие продолжения d, которое принимает один аргумент состояния y и выполняет следующее:
    • Если min равно нулю и y endIndex равен x endIndex, верните отказ.
    • Если min равно нулю, то пусть min2 равно нулю; в противном случае пусть min2 будет min - 1.
    • Если max ∞, то пусть max2 ∞; в противном случае max2 будет max - 1.
    • Вызовите RepeatMatcher (m, min2, max2, greedy, y, c, parenIndex, parenCount) и верните его результат.
  • Пусть cap - свежая копия x-захвата внутреннего массива.
  • Для каждого целого k, удовлетворяющего parenIndex < k и k? parenIndex + parenCount, установите колпачок [k] на undefined.
  • Пусть e будет x endIndex.
  • Пусть xr - это состояние (e, cap).
  • Если min не равно нулю, тогда вызовите m (xr, d) и верните его результат.
  • Если жадным является false, тогда
    • Вызов c (x) и пусть z - его результат.
    • Если z не является отказом, верните z.
    • Вызвать m (xr, d) и вернуть его результат.
  • Вызов m (xr, d) и z - его результат.
  • Если z не является отказом, верните z.
  • Вызовите c (x) и верните его результат.

Шаг 2 определяет продолжение d, в котором мы пытаемся сопоставить другой экземпляр повторяющегося Atom, который позже вызывается на шаге 7 (min > 0 case), шаг 8.3 (ленивый случай) и шаг 9 (жадный случай) через Матчи m.

Шаг 5 и 6 создает копию текущего состояния для цели обратного отслеживания и обнаружения пустого соответствия строк на шаге 2.

В шагах отсюда описаны 3 отдельных случая:

  • Шаг 7 охватывает случай, когда квантификатор имеет ненулевое минимальное значение. Жадность, несмотря на это, нам нужно сопоставить хотя бы минимальные экземпляры Atom, прежде чем нам позволено называть Continuation c.

  • Из-за условия на шаге 7 min равно 0 от этой точки. Шаг 8 посвящен случаю, когда квантификатор ленив. Шаг 9, 10, 11 касается случая, когда квантификатор является жадным. Обратите внимание на обратный порядок вызова.

Вызов m (xr, d) означает совпадение одного экземпляра Atom, затем вызов продолжения d для продолжения повторения.

Вызов продолжения c (x) означает выход из повторения и соответствие тому, что будет дальше. Обратите внимание, как Продолжение c передается в RepeatMatcher внутри продолжения d, так что он доступен для всех последующих повторений повторения.

Объяснение причуды в JavaScript RegExp

Шаг 2.1 является виновником, который вызывает несоответствие результата между PCRE и JavaScript.

  • Если min равно нулю и y endIndex равен x endIndex, верните отказ.

Условие min = 0 достигается, когда квантификатор изначально имеет 0 как min (* или {0,n}) или через шаг 7, который должен вызываться до тех пор, пока min > 0 (исходный квантификатор + или {n,} или {n,m}).

Когда min = 0 и, квантификатор жадный, на этапе 9 будет вызываться Matcher m, который пытается сопоставить экземпляр Atom и продолжить вызов d, который настроен на шаге 2 Продолжение d рекурсивно вызовет RepeatMatcher, который, в свою очередь, снова вызовет Matcher m (шаг 9).

Без шага 2.1, если Matcher m имеет пустую строку в качестве своего первого возможного выбора для продвижения вперед на входе, итерация (теоретически) будет продолжаться вечно без продвижения вперед. Учитывая ограниченные возможности, поддерживаемые JavaScript RegExp (без обратных ссылок или других причудливых функций), нет необходимости продолжать другую итерацию, когда текущая итерация соответствует пустой строке - пустая строка будет повторена в любом случае, Шаг 2.1 - это метод JavaScript, связанный с повторением пустой строки.

Как показано на шаге 2.1, когда min = 0, механизм синтаксиса JavaScript обрабатывается, когда пустая строка сопоставляется с Matcher m (return failure). Эта эффективно отклоняет "пустую строку, повторяемую конечным числом раз, является пустой строкой.

Другим побочным эффектом шага 2.1 является то, что из точки, когда min = 0, до тех пор, пока существует один экземпляр, где Matcher m соответствует непустой строке, последнее повторение Atom гарантируется быть непустым.

Напротив, кажется, что PCRE (и другие двигатели) принимает "пустую строку, повторяемую конечным числом раз, является пустой строкой", и продолжайте с остальной частью шаблона. Это объясняет поведение PCRE в перечисленных выше случаях. Что касается алгоритма, PCRE останавливает повторение после сопоставления пустой строки дважды в строке.

Ответ 2

Я сделал несколько тестов и обнаружил, что в Firefox и Chrome, если группа имеет жадный квантификатор и прямо или косвенно содержит один или несколько ленивых кванторов с нулем в качестве минимального количества итераций, то для итераций жадного квантора, где минимальное количество итераций уже выполнено, крайний левый квантификатор, который может соответствовать одной или нескольким итерациям, будет соответствовать одной итерации, если группа найдет совпадение нулевой длины, если ленивый квантификатор будет соответствовать нулевым итерациям.

например. (.{0,2}?){5,8} соответствует "abc" в "abcdefghijklmnopqrstuvwxyz", потому что .{0,2}? соответствует одной итерации для итераций 6, 7 и 8 из {5,8}.

Если после группы есть маркеры с жадным квантором, которые невозможно сопоставить, тогда ленивый квантификатор расширяет количество итераций. Перестановки с нулевыми итерациями никогда не предпринимаются. Но жадный квантификатор все еще может вернуться к минимальному количеству итераций.

В одной и той же теме строка (.{0,3}?){5,6}[ad] соответствует "abcd", а (.{0,3}?){5,6}a соответствует "a".

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

То же самое происходит в Internet Explorer, если и только если есть токены, которые не являются необязательными после группы с жадным квантификатором. Если после группы нет токенов или все они являются необязательными, то IE ведет себя так же, как и большинство других механизмов регулярных выражений.

Объяснение поведения в Firefox и Chrome представляется комбинацией двух шагов в разделе 15.10.2.5 в стандарте JavaScript. Шаг 2.1 для RepeatMatcher заставляет механизм regex сбрасывать итерации нулевой длины кванторов, которые уже соответствуют минимальному количеству требуемых итераций, вместо того, чтобы просто останавливать продолжение итерации. Шаг 9 оценивает все, что приходит после ленивого квантора, прежде чем оценивать сам ленивый квантификатор. В этих примерах, которые включают продолжение повторения жадного квантификатора. Когда этот жадный квантификатор выходит из строя на шаге 2.1, ленивый квантификатор вынужден повторять хотя бы один раз.

Итак, чтобы ответить, является ли это ошибкой, я бы сказал, что это ошибка в спецификации JavaScript. Это поведение не приносит пользы и делает JavaScript-регулярное выражение ненужным по сравнению с другими (популярными) механизмами регулярного выражения backtracking regex. Я не ожидаю, что будущие спецификации JavaScript изменят это, хотя.

Опера ведет себя по-другому. (.{0,2}?){5,8} соответствует "abcd", а (.{0,2}?){6,8} соответствует "abcde". Кажется, что Opera заставляет ленивый квантификатор соответствовать хотя бы одной итерации для всех, кроме первой итерации жадного квантификатора, а затем прекратить итерацию, когда жадный квантификатор нашел требуемое минимальное количество итераций.

Я рекомендую не использовать группы или альтернативы, в которых все необязательно. Убедитесь, что каждая альтернатива и каждая группа соответствуют чему-то. Если группа должна быть необязательной, используйте ?, чтобы сделать всю группу необязательной, вместо того чтобы сделать все внутри группы опциональным. Это уменьшит количество перестановок, которые должен выполнить механизм регулярного выражения.

Ответ 3

Это не отвечает, почему grediness ведет себя по-разному в Javascript, но это показывает, что это не ошибка, и она была проверена, чтобы вести себя так. Я возьму в качестве примера движок google v8. Я нашел аналогичный пример в своих тестах.

/test/mjsunit/third_party/regexp-pcre.js:

line 1085: res[1006] = /([a]*?)*/;
line 4822: assertToStringEquals("aaaa,a", res[1006].exec("aaaa "), 3176);

https://code.google.com/p/v8/source/browse/trunk/test/mjsunit/third_party/regexp-pcre.js#1085

Этот код хорошо работает для Javascript http://regex101.com/r/nD0uG8, но он не имеет того же выхода для php и python PCRE.

UPDATE: О вашем вопросе:

Кажется, что JavaScript regex engine интерпретирует второй * для преобразования. *? от ленивых до жадных

https://code.google.com/p/v8/source/browse/trunk/src/parser.cc#5157

RegExpQuantifier::QuantifierType quantifier_type = RegExpQuantifier::GREEDY;
if (current() == '?') {
    quantifier_type = RegExpQuantifier::NON_GREEDY;
    Advance();
} else if (FLAG_regexp_possessive_quantifier && current() == '+') {
    // FLAG_regexp_possessive_quantifier is a debug-only flag.
    quantifier_type = RegExpQuantifier::POSSESSIVE;
    Advance();
}