Жадность против неохотно против притяжательных квантификаторов

357

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

В частности, в следующем примере:

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.

Объяснение упоминает ест всю строку ввода, буквы были потребляется , согласованями отступая , крайнее справа появление «Foo» было выплюнули и т.д.

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

В качестве альтернативы, если кто-то может объяснить в несколько иной формулировке следующий абзац, это будет высоко ценится:

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

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

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

Regex Rookie
источник
22
Максимальные кванторам нравятся *, +и ?являются жадными. Минимально кванторы нравится *?, +?и ??являются ленивыми. Притяжательные кванторам нравятся *+, ++и ?+являются липкими.
tchrist
6
Этот вопрос был добавлен в FAQ по регулярному выражению переполнения стека в разделе «Квантификаторы> Подробнее о различиях ...».
aliteralmind
Интересны: Учебные руководства по Java ™ - различия между жадными, неохотными и притяжательными квантификаторами - прокрутите вниз, чтобы увидеть раздел.
Гай Кодер

Ответы:

495

Я сделаю это.

Жадные кванторный первые матчи как можно больше. Таким образом, .*соответствует всей строке. Затем совпадение пытается соответствовать fследующему, но не осталось символов. Так что он «возвращается», заставляя жадный квантификатор совпадать на один символ меньше (оставляя «o» в конце строки без совпадения). Это по-прежнему не соответствует fв регулярном выражении, поэтому он возвращает еще один шаг, заставляя жадный квантификатор снова соответствовать на один символ меньше (оставляя «oo» в конце строки без совпадения). Это все еще не соответствует fв регулярном выражении, поэтому он возвращает еще один шаг (оставляя «foo» в конце строки без совпадения). Теперь совпадение, наконец, соответствует fв регулярном выражении,ooтоже совпадают. Успех!

Неохотой или «не жадный» Квантор первые матчи как можно меньше. Таким образом, .*сначала ничего не совпадает, оставляя всю строку бесподобной. Затем средство сопоставления пытается сопоставить fследующее, но непропорциональная часть строки начинается с «x», так что это не работает. Таким образом, средство сравнения возвращает обратный путь, заставляя не жадный квантификатор соответствовать еще одному символу (теперь он соответствует «x», оставляя «fooxxxxxxfoo» не имеющим аналогов). Затем он пытается сопоставить то f, что успешно, oи следующее и следующее oв регулярном выражении тоже совпадают. Успех!

В вашем примере он затем запускает процесс заново с оставшейся непревзойденной частью строки «xxxxxxfoo», следуя тому же процессу.

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

аномия
источник
15
+1 Хороший ответ. Я бы только добавил: иди почитай Мастеринг регулярных выражений (3-е издание)
ridgerunner
@Anomie, немного опоздал, но в притяжательной части, я думаю, вы имели в виду, так что все начинается с .*+ (обратите внимание на «+»)
RD
3
что именно тогда делает собственнический квантификатор? если это не соответствует этому? (Я имею в виду, какой в ​​этом смысл, если после вас не может быть символов)
relipse
4
@relipse: Вы бы использовали его в ситуации, когда вы знаете, что откат назад не поможет, вероятно, не с тем, .*+что соответствует всему. Например, если у вас есть шаблон [xyz]*foo, то нет способа, чтобы при обратном отслеживании совпадающих по [xyz]*битам значений x, y и z когда-либо совпадал следующий fooбит, поэтому вы можете ускорить процесс, сделав его притяжательным.
Аномия
4
@moodboom, никогда не было случаев (математический факт), когда собственнические квантификаторы будут давать совпадение , которое не будет производиться простыми жадными квантификаторами. Бывают случаи, когда они не дают совпадений, когда жадные квантификаторы дают совпадения. Для ВСЕХ других случаев (когда жадные и притяжательные результаты дают одинаковые результаты), притяжательные квантификаторы дают прирост производительности.
Wildcard
49

Это просто мой практический результат для визуализации сцены.

Визуальное изображение

SIslam
источник
3
За исключением того, что я думаю, что последний случай, притяжательный, не должен иметь n проходов - просто захватите всю строку сразу.
хорошо относитесь к своим модам
@phyzome Я думаю, теперь все в порядке?
SIslam
1
Спасибо за наглядное объяснение :)
Lars Moelleken
В EXPRESSION .*?foo(), не должны ли [f] [o] [o]прямоугольники быть желтыми в 5th pass?
tonix
1
@tonix да! Желтая окраска должна быть сделана для соответствующей части в выражении .*?fooи .*+foo.
SIslam
24

Я не слышал точных терминов «срыгивать» или «отступать» раньше; Фраза, которая заменит их, - это «возвращение», но «регургитация» выглядит так же хорошо, как любая фраза для «контента, который был предварительно принят до того, как возврат был снова отброшен».

В большинстве движков регулярных выражений важно понимать, что они возвращаются назад : они предварительно принимают потенциальное частичное совпадение, пытаясь сопоставить все содержимое регулярного выражения. Если регулярное выражение не может быть полностью сопоставлено с первой попытки, то механизм регулярного выражения будет возвращаться к одному из своих совпадений. Он будет пытаться согласования *, +, ?, чередование или {n,m}повторение по- разному, и повторите попытку. (И да, этот процесс может занять много времени.)

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

Последние три буквы, f, oи oуже потребляются начальной .*части правила. Однако у следующего элемента в регулярном выражении fничего не осталось во входной строке. Движок будет вынужден вернуться к исходному .*совпадению и попытаться сопоставить все, кроме самого последнего символа. (Это может быть разумно и вернуть все, кроме последних трех, потому что в нем три буквальных термина, но я не знаю подробностей реализации на этом уровне.)

Таким образом, средство сравнения медленно отступает ( справа налево? ) По одной букве за раз, пока не произойдет регургитация самого правого вхождения «foo» ( что это значит? ), При котором

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

Указать совпадение и поиск заканчивается.

Второй пример, однако, неохотен, поэтому он начинает с того, что сначала потребляет ( кем? ) «Ничего». Потому что "фу"

Исходное ничто не потребляется .?*, что потребляет минимально возможное количество из всего, что позволяет остальным регулярным выражениям совпадать.

не появляется в начале строки, он вынужден глотать ( кто глотает?)

Снова .?*потребляет первый символ, после возврата на первоначальный сбой, чтобы сопоставить все регулярное выражение с максимально коротким соответствием. (В этом случае механизм регулярных выражений расширяет совпадение .*?слева направо, потому что .*?неохотно.)

первая буква («х»), которая запускает первое совпадение в 0 и 4. Наш тестовый жгут продолжает процесс до тех пор, пока входная строка не будет исчерпана. Он находит другой матч в 4 и 13.

Третий пример не может найти соответствие, потому что квантификатор является притяжательным. В этом случае вся входная строка используется. * +, ( Как? )

A .*+будет потреблять как можно больше и не будет возвращаться, чтобы найти новые совпадения, когда регулярное выражение в целом не сможет найти совпадение. Поскольку притяжательная форма не выполняет откаты, вы , вероятно , не будете видеть много применений с .*+, а классами символов или аналогичными ограничениями: account: [[:digit:]]*+ phone: [[:digit:]]*+.

Это может значительно ускорить сопоставление регулярных выражений, потому что вы говорите механизму регулярных выражений, что он никогда не должен возвращаться к потенциальным совпадениям, если входные данные не совпадают. (Если бы вам пришлось писать весь соответствующий код вручную, это было бы похоже на то, чтобы никогда не использовать putc(3)«отодвигать» входной символ. Это было бы очень похоже на наивный код, который можно написать с первой попытки. За исключением механизмов регулярных выражений намного лучше, чем одиночный символ push-back, они могут перематывать все назад до нуля и пытаться снова. :)

Но больше, чем потенциальные ускорения, это также позволяет вам писать регулярные выражения, которые точно соответствуют тому, что вам нужно. У меня возникают проблемы с простым примером :), но написание регулярного выражения с использованием квантификаторов «притяжательный против жадных» может дать вам разные совпадения, и один или другой может быть более подходящим.

не оставляя ничего, чтобы удовлетворить «foo» в конце выражения. Используйте собственнический квантификатор для ситуаций, когда вы хотите захватить все что-либо, даже не отступая ( что означает отступление? ); это превзойдет

«Откат» в данном контексте означает «возврат» - отбрасывание пробного частичного совпадения, чтобы попробовать другое частичное совпадение, которое может или не может быть успешным.

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

sarnold
источник
2
Я подозреваю, что никогда не бывает случая, когда собственнический квантификатор будет соответствовать чему-то, чего не подойдет жадный квантификатор. Я полагаю, что следующее доказывает это: жадный квантификатор всегда совпадает настолько, насколько это возможно, затем возвращается, если не может найти совпадение. Собственный квантификатор соответствует как можно большему количеству, а затем выходит, если не может найти совпадения. Таким образом, может существовать что-то, что соответствует жадному квантификатору, а не собственно квантификатору, но не наоборот, потому что они оба ищут «дерево» в одной и той же последовательности, квантификатор притяжений просто сдается легче. ;)
Wildcard
2
Подтверждено: «Для этого нужны атомная группировка и собственнические квантификаторы: эффективность за счет запрета возврата». from регулярные-выражения.info Так что утверждение в этом ответе «Но больше, чем потенциальные ускорения, это также может позволить вам писать регулярные выражения, которые точно соответствуют тому, что вам нужно для соответствия». на самом деле не совсем точно.
Wildcard
1
@Wildcard, спасибо за комментарии; это может объяснить, почему у меня возникли проблемы с примером. Хехе.
sarnold
19

http://swtch.com/~rsc/regexp/regexp1.html

Я не уверен, что это лучшее объяснение в Интернете, но оно достаточно хорошо написано и достаточно подробно, и я продолжаю возвращаться к нему. Вы можете проверить это.

Если вам нужен более высокий уровень (менее подробное объяснение), для простых регулярных выражений, таких как то, что вы просматриваете, механизм регулярных выражений работает путем возврата. По сути, он выбирает («ест») часть строки и пытается сопоставить регулярное выражение с этим разделом. Если это соответствует, отлично. Если нет, механизм изменяет свой выбор раздела строки и пытается сопоставить регулярное выражение с этим разделом и т. Д., Пока не попробует каждый возможный выбор.

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

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

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

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

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

Вот почему совпадение квантификаторов притяжения в вашем примере терпит неудачу: .*+проверка проверяется по всей строке, которой он соответствует, но затем движок продолжает искать дополнительные символы foo- но, конечно, он не находит их, потому что вы уже в конце строки. Если бы это был жадный квантификатор, он бы откатился назад и попытался сделать .*единственное совпадение до следующего за последним символа, затем до третьего до последнего символа, затем до четвертого до последнего символа, что успешно, потому что только тогда там fooслева после того, .*как "съел" более раннюю часть строки.

Дэвид З
источник
1
Это отличный источник. Я люблю диаграммы состояний машин. :)
Regex Rookie
@Regex Rookie: рад, что вам понравилось :) Однако, просмотрев этот сайт, я думаю, что должен прояснить, что его целью является продвижение альтернативной реализации механизма регулярных выражений. Алгоритм возврата, который я (частично) и другие ответы описываю, является медленным ; это совершенно отдельный алгоритм от идеи NFA / DFA, описанной на веб-странице. Отступить назад проще для понимания, именно поэтому регулярные выражения обычно объясняются новичкам.
Дэвид З
@ Давид Заславский: Хорошее объяснение. Ваши комментарии в квадратных скобках в «Жадном квантификаторе говорят двигателю запускаться со всей строкой (или, по крайней мере, со всеми, которые еще не были сопоставлены предыдущими частями регулярного выражения)». Они применяются также к неохотным и притяжательным квантификаторам. Это делает ваше объяснение совместимым с тем, что происходит, когда мы изменяем наши примеры шаблонов с (". * Foo"; ". *? Foo"; и ". * + Foo") на ("foo. *"; "Foo. *? "; и" foo. * + ").
Джон Бентли
На самом деле, xfooxxxxxxfoo соответствует. * Foo в обычном (в смысле информатики) регулярном выражении. NFA будет состоянием, в котором он зацикливается между собой с любым персонажем, а затем может перейти к foo. DFA будет простым переводом этого NFA. Это можно сделать в 8 штатах.
user4951
@ JimThio да, потому что это не собственнический квантификатор.
Дэвид З
13

Вот мой взгляд на использование позиций ячейки и индекса (см. Схему здесь, чтобы отличить ячейку от индекса).

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

Входная строка: xfooxxxxxxfoo
Regex:. * Foo

Вышеуказанное регулярное выражение состоит из двух частей:
(i) '. *' И
(ii) 'foo'.

Каждый из приведенных ниже шагов проанализирует две части. Дополнительные комментарии для соответствия «Пройти» или «Неудачно» объясняются в фигурных скобках.

Шаг 1:
(i). * = Xfooxxxxxxfoo - PASS ('. *' Является жадным квантификатором и будет использовать всю входную строку)
(ii) foo = Не осталось символов для сопоставления после индекса 13 -
Ошибка FAIL Match.

Шаг 2:
(i). * = Xfooxxxxxxfo - PASS (возврат на жадный квантификатор '. *')
(Ii) foo = o - FAIL
Соответствие не выполнено.

Шаг 3:
(i). * = Xfooxxxxxxf - PASS (возврат на жадный квантификатор '. *')
(Ii) foo = oo - FAIL
Совпадение не удалось.

Шаг 4:
(i). * = Xfooxxxxxx - PASS (отслеживание жадного квантификатора '. *')
(Ii) foo = foo - совпадение
отчета PASS

Результат: 1 совпадение (
я ) Я нашел текст "xfooxxxxxxfoo", начиная с индекса 0 и заканчивая индексом 13.

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

Входная строка: xfooxxxxxxfoo
Regex:. *? Foo

Вышеуказанное регулярное выражение состоит из двух частей:
(i) '. *?' и
(ii) 'foo'

Шаг 1:.
*? = '' (пусто) - PASS (Сопоставьте как можно меньше с неохотным квантификатором '. *?'. Индекс 0, имеющий '', соответствует.)
foo = xfo - FAIL (Ячейка 0,1,2 - т.е. индекс между 0 и 3)
Матч не удался.

Шаг 2:.
*? = x - PASS (Добавить символы в квантификатор с неохотой '. *?'. Ячейка 0, имеющая 'x', совпадает.)
foo = foo - PASS
Отчет MATCH

Шаг 3:.
*? = '' (пусто) - PASS (Сопоставьте как можно меньше с неохотным квантификатором '. *?'. Индекс 4, имеющий '', соответствует.)
foo = xxx - FAIL (Ячейка 4,5,6 - то есть индекс между 4 и 7)
Матч не удался.

Шаг 4:.
*? = x - PASS (Добавить символы в квантификатор с неохотой '. *?'. Ячейка 4.)
foo = xxx - FAIL (Ячейка 5,6,7 - то есть индекс между 5 и 8)
Совпадение не удалось.

Шаг 5:.
*? = xx - PASS (Добавить символы в квантификатор с неохотой '. *?'. Ячейка с 4 по 5.)
foo = xxx - FAIL (Ячейка 6,7,8 - то есть индекс между 6 и 9)
Совпадение не удалось.

Шаг 6:.
*? = xxx - PASS (Добавить символы в квантификатор с неохотой '. *?'. Ячейка с 4 по 6.)
foo = xxx - FAIL (Ячейка 7,8,9 - то есть индекс между 7 и 10)
Совпадение не удалось.

Шаг 7:.
*? = xxxx - PASS (Добавить символы в квантификатор с неохотой '. *?'. Ячейка с 4 по 7.)
foo = xxf - FAIL (Ячейка 8,9,10 - то есть индекс между 8 и 11)
Совпадение не удалось.

Шаг 8:.
*? = xxxxx - PASS (Добавить символы в квантификатор с неохотой '. *?'. Ячейка с 4 по 8.)
foo = xfo - FAIL (Ячейка 9,10,11 - то есть индекс между 9 и 12)
Совпадение не удалось.

Шаг 9:.
*? = xxxxxx - PASS (Добавить символы в квантификатор с неохотой '. *?'. Ячейка с 4 по 9.)
foo = foo - PASS (Ячейка 10,11,12 - то есть индекс между 10 и 13)
Report MATCH

Шаг 10:.
*? = '' (пусто) - PASS (Сопоставьте как можно меньше с неохотным квантификатором '. *?'. Индекс 13 пуст.)
foo = Не осталось символов для сопоставления - FAIL (После индекса 13 ничего не найдено)
Совпадение не смогли.

Результат: 2 совпадение (
я ) Я нашел текст «xfoo», начиная с индекса 0 и заканчивая индексом 4.
Я нашел текст «xxxxxxfoo», начиная с индекса 4 и заканчивая индексом 13.

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

Входная строка: xfooxxxxxxfoo
Regex:. * + Foo

Приведенное выше регулярное выражение состоит из двух частей: '. * +' И 'foo'.

Шаг 1:.
* + = Xfooxxxxxxfoo - PASS (сопоставить как можно больше с притяжательным квантификатором '. *')
Foo = Нет соответствующего символа для сопоставления - FAIL (ничего не найдено после индекса 13)
Совпадение не удалось.

Примечание: возврат не разрешен.

Результат: 0 совпадений

Raka
источник
1

Жадный: «соответствовать самой длинной последовательности символов»

Неохотно: «соответствовать самой короткой последовательности символов»

Притяжательные: это немного странно, поскольку НЕ (в отличие от жадных и неохотных) не пытается найти соответствие для всего регулярного выражения.

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

Тило Кербс
источник
Насколько я знаю, большинство реализаций общего назначения в настоящее время упакованы настолько полно, что стало невозможно не использовать возвратный путь. Поэтому в теории они должны быть чрезвычайно (экспоненциально) медленными в некоторых случаях. Но для большинства из этих случаев есть специальные оптимизации, встроенные в шаблон соответствия.
Роберт
0

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

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

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

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

Притяжательное количественное определение не имеет карантина и включает все в фиксированной активной последовательности .

Чад Филип Джонсон
источник