Что именно делает квантор * +?

Question

Идею ленивых и жадных легко понять, но я только видел/использовал *+ один раз в своем регулярном выражении (на Java) [A]|[^B]*+(?!C) (A, B, C - произвольные значения) просто потому, что он работал, когда ленивый модификатор привел к ошибка StackOverflow.

Из-за неспособности большинства поисковых систем искать символы, я не могу найти документацию по этому вопросу. Итак, что именно делает * + и как оно это делает?

Answer 1

Жадный квантификатор соответствует всему, что он может, а затем шаблон возвращается назад, пока совпадение не завершится успешно.

Ленивый квантор вперед, пока матч не завершится успешно.

Притяжательный квантификатор соответствует всем возможностям и никогда не возвращается назад.

+ обозначает притяжательный квантор. Если их можно использовать как, например, ++ или *+.

Эта способность предотвращения обратного слежения означает, что она может остановить catastrophic backtracking.

Answer 2

X * + означает X, ноль или более раз (Притяжательные)

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

Answer 3

Как следует из других ответов, *+ является «притяжательным квантором». Он соответствует предыдущему элементу как можно чаще, как жадный квантификатор, но никогда не отступает.

Почему Полезно? Только как оптимизация производительности. Кроме того, только как оптимизация производительности , когда регулярное выражение не соответствует. Это важный момент для понимания регулярных выражений: их наихудшая производительность всегда возникает, когда не соответствует.

В зависимости от используемого двигателя регулярных выражений и деталей самого регулярного выражения, производительность худшего случая иногда может быть потрясающе плоха. Для простого примера возьмите это регулярное выражение: a*a*a*b, сопоставленное с этой строкой: aaaaac.

Столкнувшись с такой ситуацией, стандартный «НКА» типа регулярных выражений будет делать что-то вроде этого:

1. Попробуйте соответствие 1-ые a 5 раз, 2-й a ноль раз, и 3-й a ноль раз.
2. Попробуйте сопоставить b с c - это терпит неудачу.
3. «Обратный путь» и матч 1-го a 4 раза, 2-й 1 раз и 3-е ноль раз.
4. Повторите попытку, используя b - он не работает.
5. Возвратитесь назад, попробуйте 1-й a 4 раза, 2-ое нулевое время и 3-й 1 раз.
6. ...
7. Backtrack, попробуйте 1-й a 3 раза, 2-й в 2 раза, а 3-й ноль раз ...

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

Если регулярное выражение было a*+a*a*b, этого никогда не произойдет. Это будет больше похожее:

1. Попробуйте сопоставить первый a 5 раз, второе нулевое время и 3-е ноль.
2. Попробуйте сопоставить b - это не удается.
3. С 1-го a является «притяжательным», как только он соответствует 5 раз, он никогда не сможет попытаться сопоставить меньшее количество раз. И так как нет a s слева в строке для другого a* s для соответствия, они могут совпадать только с нулевым временем. Нет ничего, что можно было бы попробовать, поэтому матч в целом не удался.
4. Нет шага 4. Вы готовы. Пока ваши друзья ждут, чтобы их регулярные выражения закончили выполнение, вы можете отбросить свои каблуки и взломать свой холодный напиток по своему выбору.