Жадность против неохотно против притяжательных квантификаторов
Я нашел этот превосходный учебник по регулярным выражениям, и хотя я интуитивно понимаю, что делают "жадные", "неохотные" и "притяжательные" квантификаторы, в моем понимании есть серьезная дыра.
В частности, в следующем примере:
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" в конце выражения. Используйте собственнический квантификатор для ситуаций, когда вы хотите захватить все что-либо, даже не отступая (что означает отступление?); он превзойдет эквивалентный жадный квантификатор в случаях, когда совпадение не найдено немедленно.
7 ответов
Я сделаю это.
Жадный квантификатор сначала соответствует как можно большему количеству. Итак .* соответствует всей строке. Затем совпадение пытается соответствовать f следующие, но не осталось символов. Так что он "возвращается", заставляя жадный квантификатор соответствовать еще одной вещи (оставляя "o" в конце строки не имеющим аналогов). Это все еще не соответствует f в регулярном выражении, таким образом, он "возвращает назад" еще один шаг, заставляя жадный квантификатор снова совпадать на одну вещь меньше (оставляя "oo" в конце строки не имеющим аналогов). Это все еще не соответствует f в регулярном выражении, так что он возвращает еще один шаг (оставляя "foo" в конце строки без совпадения). Теперь совпадение, наконец, соответствует f в регулярном выражении, и o и следующий o тоже совпадают. Успех!
Неохотный или "не жадный" квантификатор сначала сопоставляется как можно меньше. Итак .* сначала ничего не совпадает, оставляя всю строку непревзойденной. Затем совпадение пытается соответствовать f далее, но непревзойденная часть строки начинается с "x", так что это не работает. Таким образом, средство сопоставления возвращает назад, что делает не жадный квантификатор еще одним совпадением (теперь оно соответствует "x", оставляя "fooxxxxxxfoo" не имеющим аналогов). Затем он пытается соответствовать f, который преуспевает, и o и следующий o в регулярном выражении тоже. Успех!
В вашем примере он затем запускает процесс заново с оставшейся непревзойденной частью строки, следуя тому же процессу.
Собственный квантификатор похож на жадный квантификатор, но он не возвращается. Так начинается с .* сопоставляя всю строку, ничего не оставляя равных. Тогда для него ничего не осталось бы сопоставить с f в регулярном выражении Так как притяжательный квантификатор не возвращается, матч проваливается там.
Это просто мой практический результат для визуализации сцены
Я не слышал точных терминов "срыгивать" или "отступать" раньше; Фраза, которая заменит их, - это "возвращение", но "регургитация" выглядит так же хорошо, как любая фраза для "контента, который был предварительно принят до того, как возврат был снова отброшен".
В большинстве движков регулярных выражений важно понимать, что они возвращаются назад: они предварительно примут потенциальное частичное совпадение, пытаясь сопоставить все содержимое регулярного выражения. Если регулярное выражение не может быть полностью сопоставлено с первой попытки, то механизм регулярного выражения будет возвращаться к одному из своих совпадений. Будет пытаться сопоставить *, +, ?, чередование или {n,m} повторение по-другому, и попробуйте еще раз. (И да, этот процесс может занять много времени.)
В первом примере используется жадный квантификатор.* Для поиска "чего угодно", ноль или более раз, за которым следуют буквы "f", "o", "o". Поскольку квантификатор является жадным, часть выражения.* Сначала съедает всю входную строку. На этом этапе общее выражение не может быть успешным, потому что последние три буквы ("f" "o" "o") уже были использованы (кем?).
Последние три буквы, f, o, а также o были уже потреблены начальным .* часть правила. Тем не менее, следующий элемент в регулярном выражении, f, ничего не осталось во входной строке. Двигатель будет вынужден вернуться на исходную .* сопоставить и попытаться сопоставить все, кроме самого последнего символа. (Это может быть разумно и вернуться к принципу "все, кроме последних трех", потому что в нем три буквальных термина, но я не знаю подробностей реализации на этом уровне.)
Таким образом, средство сравнения медленно отступает (справа налево?) По одной букве за раз, пока не произойдет регургитация самого правого вхождения "foo" (что это значит?), При котором
Это означает, что foo предварительно был в том числе при сопоставлении .*, Поскольку эта попытка не удалась, механизм регулярных выражений пытается принять на один символ меньше .*, Если бы был успешный матч до .* в этом примере, то двигатель, вероятно, попытается сократить .* match (справа налево, как вы указали, потому что это жадный квалификатор), и если он не смог сопоставить все входные данные, то он может быть вынужден переоценить то, что сопоставил до .* в моем гипотетическом примере.
Указать совпадение и поиск заканчивается.
Второй пример, однако, неохотен, поэтому он начинает с того, что сначала потребляет (кем?) "Ничего". Потому что "фу"
Начальное ничто не потребляется .?*, который потребляет минимально возможное количество из всего, что позволяет остальным регулярным выражениям совпадать.
не появляется в начале строки, она вынуждена глотать (кто глотает?)
Опять .?* потребляет первый символ, после возврата на первоначальный сбой, чтобы сопоставить все регулярное выражение с максимально коротким соответствием. (В этом случае механизм регулярных выражений расширяет совпадение для .*? слева направо, потому что .*? неохотно.)
первая буква ("х"), которая запускает первое совпадение в 0 и 4. Наш тестовый жгут продолжает процесс до тех пор, пока входная строка не будет исчерпана. Он находит другой матч в 4 и 13.
Третий пример не может найти соответствие, потому что квантификатор является притяжательным. В этом случае вся входная строка используется.*+, (Как?)
.*+ будет потреблять как можно больше и не будет возвращаться, чтобы найти новые совпадения, когда регулярное выражение в целом не сможет найти совпадение. Поскольку притяжательная форма не выполняет возврат, вы, вероятно, не увидите много вариантов использования с .*+, а скорее с классами символов или аналогичными ограничениями: account: [[:digit:]]*+ phone: [[:digit:]]*+,
Это может значительно ускорить сопоставление регулярных выражений, потому что вы говорите механизму регулярных выражений, что он никогда не должен возвращаться к потенциальным совпадениям, если входные данные не совпадают. (Если бы вам пришлось писать весь соответствующий код вручную, это было бы похоже на то, чтобы никогда не использовать putc(3) "отодвинуть" входной символ. Это было бы очень похоже на наивный код, который можно написать с первой попытки. За исключением того, что движки регулярных выражений намного лучше, чем одиночный символ push-back, они могут перематывать все назад до нуля и пытаться снова.:)
Но больше, чем потенциальные ускорения, это также позволяет вам писать регулярные выражения, которые точно соответствуют тому, что вам нужно. У меня возникают проблемы с простым примером:), но написание регулярных выражений с использованием квантификаторов "притяжательный против жадных" может дать вам разные совпадения, и одно или другое может быть более подходящим.
не оставляя ничего, чтобы удовлетворить "foo" в конце выражения. Используйте собственнический квантификатор для ситуаций, когда вы хотите захватить все что-либо, даже не отступая (что означает отступление?); это превзойдет
"Откат" в данном контексте означает "возврат" - отбрасывание пробного частичного совпадения, чтобы попробовать другое частичное совпадение, которое может или не может быть успешным.
эквивалентный жадный квантификатор в случаях, когда совпадение не найдено сразу.
http://swtch.com/~rsc/regexp/regexp1.html
Я не уверен, что это лучшее объяснение в Интернете, но оно достаточно хорошо написано и достаточно подробно, и я продолжаю возвращаться к нему. Вы можете проверить это.
Если вам нужен более высокий уровень (менее подробное объяснение), для простых регулярных выражений, таких как то, что вы просматриваете, механизм регулярных выражений работает путем возврата. По сути, он выбирает ("ест") часть строки и пытается сопоставить регулярное выражение с этим разделом. Если это соответствует, отлично. Если нет, движок изменяет свой выбор раздела строки и пытается сопоставить регулярное выражение с этим разделом и т. Д., Пока не попробует каждый возможный выбор.
Этот процесс используется рекурсивно: при попытке сопоставить строку с заданным регулярным выражением механизм разбивает регулярное выражение на части и применяет алгоритм к каждой части по отдельности.
Разница между жадными, неохотными и притяжательными квантификаторами возникает, когда двигатель выбирает, с какой частью строки пытаться сопоставить, и как изменить этот выбор, если он не работает в первый раз. Правила следующие:
Жадный квантификатор говорит механизму запустить всю строку (или, по крайней мере, все, что еще не сопоставлено предыдущими частями регулярного выражения) и проверить, соответствует ли она регулярному выражению. Если так, отлично; двигатель может продолжить с остальным регулярным выражением. Если нет, он пытается снова, но обрезает один символ (последний) из раздела строки, подлежащей проверке. Если это не сработает, он обрезает другого символа и т. Д. Таким образом, жадный квантификатор проверяет возможные совпадения в порядке от самого длинного до самого короткого.
Квантификатор неохотно говорит двигателю начать с самого короткого фрагмента строки. Если это соответствует, двигатель может продолжить; если нет, он добавляет один символ в раздел проверяемой строки и пытается это сделать, и так далее, пока не найдет совпадение или не будет использована вся строка. Таким образом, неохотный квантификатор проверяет возможные совпадения в порядке от самого короткого до самого длинного.
Притяжательный квантификатор подобен жадному квантификатору с первой попытки: он говорит, что двигатель запускается, проверяя всю строку. Разница в том, что если это не сработает, притяжательный квантификатор сообщает, что совпадение не удалось прямо сейчас. Движок не изменяет секцию просматриваемой строки и больше не предпринимает попыток.
Вот почему совпадение квантификаторов в вашем примере терпит неудачу: .*+ проверяется на всю строку, которой он соответствует, но затем движок продолжает поиск дополнительных символов foo после этого - но, конечно, он не находит их, потому что вы уже в конце строки. Если бы это был жадный квантификатор, он бы откатился назад и попытался бы сделать .* соответствует только последнему последнему символу, затем третьему последнему символу, затем четвертому или последнему символу, что успешно, потому что только тогда есть foo осталось после .* "съел" более раннюю часть строки.
Вот мой взгляд на использование позиций ячейки и индекса (см. Схему здесь, чтобы отличить ячейку от индекса).
Жадность - сопоставьте как можно больше с жадным квантификатором и всем регулярным выражением. Если совпадений нет, вернитесь на жадный квантификатор.
Строка ввода: xfooxxxxxxfoo
Регулярное выражение:. * 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
Сообщить о матче
Результат: 1 совпадение (я)
Я нашел текст "xfooxxxxxxfoo", начиная с индекса 0 и заканчивая индексом 13.
Неохотный - сопоставьте как можно меньше с неохотным квантификатором и сопоставьте все регулярные выражения. если совпадений нет, добавьте символы в квантификатор с неохотой.
Строка ввода: xfooxxxxxxfoo
Regex:. *? Foo
Вышеуказанное регулярное выражение состоит из двух частей:
(я).*? а также
(ii) 'foo'
Шаг 1:
.*? = '' (пусто) - PASS (Сопоставьте как можно меньше с неохотным квантификатором '.*?'. Индекс 0, имеющий '', соответствует.)
foo = xfo - FAIL (ячейка 0,1,2 - то есть индекс между 0 и 3)
Матч не удался.
Шаг 2:
.*? = x - PASS (Добавьте символы в квантификатор с неохотой '.*?'. Ячейка 0, имеющая 'x', соответствует.)
foo = foo - PASS
Сообщить о матче
Шаг 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)
Сообщить о матче
Шаг 10:
.*? = '' (пусто) - PASS (Сопоставьте как можно меньше с неохотным квантификатором '.*?'. Индекс 13 пуст.)
foo = Нет символа для сравнения - FAIL (после индекса 13 ничего не найдено)
Матч не удался.
Результат: 2 совпадение
Я нашел текст "xfoo", начиная с индекса 0 и заканчивая индексом 4.
Я нашел текст "xxxxxxfoo", начиная с индекса 4 и заканчивая индексом 13.
Притяжательный - сопоставьте как можно больше с притяжательным квантификатором и сопоставьте все регулярные выражения. НЕ возвращайтесь.
Строка ввода: xfooxxxxxxfoo
Регулярное выражение:. * + Foo
Вышеуказанное регулярное выражение состоит из двух частей: '.*+' И 'foo'.
Шаг 1:
. * + = xfooxxxxxxfoo - PASS (максимально сопоставить с притяжательным квантификатором '. *')
foo = Нет подходящего символа - FAIL (Ничего не найдено после индекса 13)
Матч не удался.
Примечание: возврат не разрешен.
Результат: 0 совпадений
Жадный: "соответствовать самой длинной последовательности символов"
Неохотно: "соответствовать самой короткой последовательности символов"
Притяжательный: Это немного странно, поскольку он НЕ (в отличие от жадного и неохотного) пытается найти соответствие для всего регулярного выражения.
Кстати: ни одна из реализаций регулярных выражений никогда не будет использовать возврат. Все реальные сопоставления с шаблонами чрезвычайно быстры - практически не зависят от сложности регулярного выражения!
Жадная количественная оценка включает сопоставление с образцом с использованием всех оставшихся непроверенных символов строки во время итерации. Непроверенные символы начинаются в активной последовательности. Каждый раз, когда совпадение не происходит, символ в конце помещается на карантин, и проверка выполняется снова.
Когда активной последовательностью удовлетворяются только начальные условия шаблона регулярного выражения, делается попытка проверить оставшиеся условия в отношении карантина. Если эта проверка прошла успешно, сопоставленные символы в карантине проверяются, а остаточные несопоставленные символы остаются непроверенными и будут использоваться, когда процесс начнется заново в следующей итерации.
Поток символов идет из активной последовательности в карантин. В результате получается, что как можно больше оригинальной последовательности включается в совпадение.
Неохотная количественная оценка в основном аналогична жадной квалификации, за исключением того, что поток символов противоположен - то есть они начинаются с карантина и переходят в активную последовательность. В результате получается, что в совпадение включено как можно меньше исходной последовательности.
Притяжательное количественное определение не имеет карантина и включает все в фиксированной активной последовательности.