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

Question

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

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

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.

В объяснении упоминается употребление всей входной строки, букв использованных , соответствий бэкoff , самое правое вхождение "foo" было отрыжка и т. д.

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

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

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

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

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

Answer 1

Я попробую.

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

указывает на совпадение, и поиск заканчивается.

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

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

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

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

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

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

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

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

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

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

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

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

Answer 4

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

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

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

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

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

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

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

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

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

Answer 5

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

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

Строка ввода: xfooxxxxxxfoo Regex: . * Foo

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

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

Шаг 2:(i). * = xfooxxxxxxfo - PASS (возврат на жадный квантификатор '. *')(ii) foo = o - FAILМатч не удался.

Шаг 3:(i). * = xfooxxxxxxf - PASS (отслеживание жадного квантификатора '. *')(ii) foo = oo - FAILМатч не удался.

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

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

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

Строка ввода: xfooxxxxxxfoo Регулярное выражение: . *? Foo

Вышеуказанное регулярное выражение состоит из двух частей:(я) '. *?'а также(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)Отчет MATCH

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

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

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

Строка ввода: xfooxxxxxxfoo Регулярное выражение: . * + Foo

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

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

Примечание: Возврат запрещен.

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

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