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

Ответ 1

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

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

. *? Foo

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

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

. * Foo

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

xfooxxxxxx f oo
На этом этапе часть foo будет иметь успешное совпадение и, таким образом, завершится успешным совпадением всей строки.

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

. * +foo

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

Ответ 2

Общие правила

Подразумевается базовое знание кванторов ?, * и + (соответственно, "нуль или один", "ноль или более", "один или несколько" ).

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

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

Объяснения по одному случаю

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

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

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

1) Случай /.*foo/:

Сначала это поворот подшаблона /.*/. Он начинает разработку первого символа:

xfooxxxxxxfoo
^

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

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

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

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

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

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

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

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

Таким образом, совпадение представляет собой целую строку xfooxxxxxxfoo.

2) Случай /.*?foo/:

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

xfooxxxxxxfoo
^

Теперь он foo поворачивается:

xfooxxxxxxfoo
^^^^

Итак, совпадение xfoo.

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

3) Случай /.*+foo/:

Сначала это поворот подшаблона /.*+/. Он пытается выработать как можно больше символов:

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

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

Итак, у нас нет совпадений.