Понимание квантификаторов

Question

Я изучал Java Tutorial по квантификаторам.

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

Я не могу понять, в чем именно разница.

Объяснение предоставляется следующим образом:

Enter your regex: .*foo  // greedy quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo  // reluctant quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo // possessive quantifier
Enter input string to search: xfooxxxxxxfoo
No match found.

В первом примере используется жадный квантификатор.* Для поиска "чего угодно", ноль или более раз, за ​​которым следуют буквы "f", "o", "o". Поскольку квантификатор является жадным, часть выражения.* Сначала съедает всю входную строку. На этом этапе общее выражение не может быть успешно выполнено, поскольку последние три буквы ("f", "o", "o") уже использованы. Таким образом, устройство сопоставления медленно откатывает одну букву за раз, пока не произойдет регургитация самого правого вхождения "foo", после чего совпадение будет успешным и поиск закончится.

Второй пример, однако, неохотно, поэтому он начинает с потребления "ничего". Поскольку "foo" не появляется в начале строки, он вынужден проглотить первую букву ("x"), что вызывает первое совпадение в 0 и 4. Наш тестовый жгут продолжает процесс до тех пор, пока входная строка не будет истощены. Он находит другой матч в 4 и 13.

Третий пример не может найти соответствие, потому что квантификатор является притяжательным. В этом случае вся входная строка используется.*+, Не оставляя ничего, чтобы удовлетворить "foo" в конце выражения. Используйте собственнический квантификатор для ситуаций, когда вы хотите захватить все что-либо, даже не отступая; он превзойдет эквивалентный жадный квантификатор в случаях, когда совпадение не найдено немедленно.

Answer 1

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

• Ленивый регистр всегда, после одного совпадения, уступит фокусировку соответствующего движка следующему оператору в регулярном выражении. Если следующий оператор терпит неудачу, структура возврата заставит ленивый случай повторяться, и это будет продолжаться до тех пор, пока не завершатся операторы или целевой текст; например, в вашем примере переход к соответствию char f после каждого успешного матча, поэтому всякий раз, когда у вас был foo Фраза, вы получите совпадение, поэтому мы получаем несколько совпадений от его использования.

. *? Foo

x fooxxxxxxfoo
В начале, ленивый случай будет иметь успешный матч с x (после успешного пустого совпадения) и передать фокус следующему оператору; foo часть регулярного выражения, и так как это присутствует после xмы получаем совпадение для этого фрагмента, ту же идею для вторичной части строки.

• Жадный случай противоположен, он продолжит свое сопоставление до тех пор, пока не потерпит неудачу, никогда не передаст фокус следующему оператору, только если неудачное сопоставление не вступит в силу, обратное отслеживание вступит в силу, и следующие операторы будут сопоставлены с обратного;

. * Foo

xfooxxxxxxfoo
Когда жадный случай находится в этой точке (последний символ), сопоставление не удастся, так как мы не могли сопоставить foo часть регулярного выражения. Чем откат заставит жадный случай backtrace его шаги и применять следующий оператор foo, похожий на ленивый случай;

xfooxxxxxxf oo
На данный момент, foo part получит успешное совпадение и, таким образом, завершится удачным совпадением всей строки.

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

. * + Foo

xfooxxxxxxfoo
Подобно жадному падежу, мы достигли конца строки, но притяжательный падеж все еще может соответствовать ему, поэтому не будет передавать факел backtrack структура, и вызовет соответствующий сбой.

Answer 2

Основные правила

Базовые знания о квантификаторах ?, *, а также + (соответственно "ноль или один", "ноль или более", "один или более") понимается.

• Мы говорим, что квантификатор является жадным, если он пытается разработать как можно больше символов.
• Мы говорим, что квантификатор неохотно (ленив), если пытается выработать как можно меньше символов.
• Мы говорим, что квантификатор является притяжательным, если он жадный и не позволяет вернуться.

Вы можете понять, что означает "обратная трассировка", только если знаете, как работают парсеры регулярных выражений (см. "Динамический пример" ниже).

Одиночные объяснения

• ?: первый тест 1 вхождение, затем 0; если вы нашли 1 случай, а затем вам нужно отменить его, вы можете сделать это
• ??: сначала проверить 0 вхождений, затем 1
• ?+: первый тест 1 вхождение, затем 0; если вы нашли 1 случай, а затем вам нужно от него отказаться, вы не сможете этого сделать
• *: попытаться получить как можно больше вхождений (даже 0); если вы нашли N вхождений, а затем вам нужно отменить (некоторые из них) их, вы можете сделать это, начиная с последнего
• *?: попытаться получить как можно меньше вхождений (даже 0)
• *+: попытаться получить как можно больше вхождений (даже 0); если вы нашли N вхождений, а затем вам нужно отбросить (некоторые из них) их, вы не сможете этого сделать
• +: постарайтесь получить как можно больше вхождений (не менее 1); если вы нашли N вхождений, а затем вам нужно отменить (некоторые из них) их, вы можете сделать это, начиная с последнего
• +?: постарайтесь получить как можно меньше вхождений (хотя бы 1)
• ++: постарайтесь получить как можно больше вхождений (не менее 1); если вы нашли N вхождений, а затем вам нужно отбросить (некоторые из них) их, вы не сможете этого сделать

Динамический пример

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

1) Дело /.*foo/ :

Сначала настала очередь subpattern /.*/, Начинается разработка первого персонажа:

xfooxxxxxxfoo
^

Затем он пытается разработать максимально возможное количество символов:

xfooxxxxxxfoo
^^
xfooxxxxxxfoo
^^^
[...]
xfooxxxxxxfoo
^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^^^^

Курсор достиг конца, но подшаблон /foo/ еще не сыграл свою роль. Таким образом, курсор "возвращается" для разрешения подшаблона /foo/ чтобы получить совпадение:

xfooxxxxxxfoo
^^^^^^^^^^^^

/foo/ все еще не могу найти совпадение, поэтому нам нужно вернуться снова:

xfooxxxxxxfoo
^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^

Теперь подшаблон /foo/ можно получить совпадение:

xfooxxxxxxfoo
^^^^^^^^^^^^^

Таким образом, совпадение всей строки xfooxxxxxxfoo,

2) Дело /.*?foo/ :

Сначала настала очередь subpattern /.*?/, Это ленивый, поэтому мы хотели бы, чтобы он соответствовал 0 символам. Но если это так, субпаттерн /foo/ не удалось получить совпадение, поэтому он должен разработать один символ:

xfooxxxxxxfoo
^

Теперь это foo очередь:

xfooxxxxxxfoo
^^^^

Итак, матч xfoo,

(если вы установите тип global для регулярного выражения, то парсер будет перезапущен с первого символа после совпадения, давая второе совпадение xxxxxxfoo)

3) Дело /.*+foo/ :

Сначала настала очередь subpattern /.*+/, Он пытается разработать как можно больше персонажей:

xfooxxxxxxfoo
^
[...]
xfooxxxxxxfoo
^^^^^^^^^^^^^

Курсор достиг конца, но подшаблон /foo/ еще не сыграл свою роль. Таким образом, курсор "возвращается"... о нет, как жаль, он не может (потому что он притяжательный)!

Так что у нас нет матчей.