Почему движки регулярных выражений разрешают / автоматически пытаются выполнить сопоставление в конце входной строки?

Question

<sup>Примечание:
* Python используется для иллюстрации поведения, но этот вопрос не зависит от языка.
* Для целей данного обсуждения предположим, однострочный только ввод , потому что наличие новых строк (многострочный ввод) вносит изменения в поведение $ и ., которые случайны для рассматриваемых вопросов.</sup>

Большинство механизмов регулярных выражений:

• принимает регулярное выражение, которое явно пытается найти выражение после конца входной строки ^[1] .

  $ python -c "import re; print(re.findall('$.*', 'a'))"
  [''] # !! Matched the hypothetical empty string after the end of 'a'
  

• при поиске / замене глобально , т. Е. При поиске всех неперекрывающихся соответствует заданному регулярному выражению и, достигнув конца строки , неожиданно попытайтесь снова сопоставить ^[2] , как объяснено в этого ответана связанный вопрос :

  $ python -c "import re; print(re.findall('.*$', 'a'))"
  ['a', ''] # !! Matched both the full input AND the hypothetical empty string
  

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

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

• не очевидно, в чем выгода этого поведения.
• и наоборот, в контексте поиска / замены глобально шаблонами, такими как .* и .*$, поведение совершенно неожиданно. ^[3]
  • Чтобы задать вопрос более остро: почему функциональность, предназначенная для поиска множественных непересекающихся совпадений регулярного выражения, т. Е. global match, решает даже попытка другое совпадение , если он знает, что весь ввод уже использовался , независимо от того, что такое регулярное выражение (хотя вы никогда не увидите симптом с регулярным выражением, которое неминимум также соответствует пустой строке)
  • Следующие языки / движки демонстрируют удивительное поведение: .NET, Python (оба 2.x и 3.x) ^[2] , Perl (и 5.x, и 6.x), Ruby, Node.js (JavaScript)

---

Обратите внимание, что движки регулярных выражений различаются в зависимости от поведения где продолжить сопоставление после нулевой длины (empty-string) match.

Любой выбор (начинать с той же позиции символа и начинать со следующей) оправдан - см. главу о совпадениях нулевой длины на сайте www.regular-expressions.info .

В отличие от этого, случай .*$, обсуждаемый здесь, отличается тем, что для любого непустого ввода совпадение first для .*$ равно , а не совпадение нулевой длины, поэтому разница в поведении не применяется - вместо этого позиция персонажа должна продвинуться безоговорочно после первого соответствия, что, конечно, невозможно, если вы ужев конце.
Опять же, меня удивляет тот факт, что предпринято еще одно сопоставление, хотя по определению ничего не осталось.

---

^{[1] Я использую $ в качестве маркера конца ввода здесь, хотя в некоторых движках, таких как .NET, он может отмечать конец конца ввода , за которым может следовать завершающий символ новой строки .Тем не менее, поведение в равной степени применимо, когда вы используете безусловный маркер конца ввода, \z.}

^{[2] Python 2.x и 3.x до 3.6.x, казалось бы, особого случая замена поведение в этом контексте: python -c "import re; print(re.sub('.*$', '[\g<0>]', 'a'))" используется для получения только [a] - то есть только одно совпадение было найдено и заменено.
Начиная с Python 3.7, поведение теперь такое же, как и в большинстве других движков регулярных выражений, где выполняется две замены, что приводит к [a][].}

^{[3] Вы можете избежать этой проблемы, либо (а) выбрав метод замены, предназначенный для поиска не более одного соответствия, либо (b) используйте ^.* для предотвращения нескольких совпаденийбыть найденным с помощью привязки начала ввода.
(a) может не быть вариантом, в зависимости от того, как данный язык функционирует;например, оператор -replace PowerShell неизменно заменяет все вхождений;рассмотрим следующую попытку заключить все элементы массива в "...":
'a', 'b' -replace '.*', '"$&"'.Из-за совпадения дважды , это дает элементы "a""" и "b""";
, опция (b), 'a', 'b' -replace '^.*', '"$&"', решает проблему.}

Answer 1

«Void в конце строки» - это отдельная позиция для двигателей регулярных выражений, потому что механизм регулярных выражений имеет дело с позициями между входными символами:

|a|b|c|   <- input line

^ ^ ^ ^
positions at which a regex engine can "currently be"

Все остальные позиции можно описать как «перед N-м символом», но в конце нет символа, на который можно сослаться.

Согласно Соответствия регулярного выражения нулевой длины - Regular-expressions.info также необходимо поддерживать совпадения нулевой длины (которые поддерживаются не всеми разновидностями регулярных выражений):

• Например, регулярное выражение \d* над строкой abc будет соответствовать 4 раза: перед каждой буквой ив конце.

---

$ разрешено в любом месте регулярного выражения для единообразия: он обрабатывается так же , как и любой другой токен и соответствуетв этой волшебной позиции "конец строки".Если «завершить» работу с регулярным выражением, это приведет к ненужной несогласованности в работе движка и предотвратит другие полезные вещи, которые могут там совпадать, например, lookbehind или \b (в основном, все, что может быть совпадением нулевой длины) - т.е.было бы как усложнением конструкции, так и функциональным ограничением без какой-либо выгоды.

---

Наконец, чтобы ответить , почему движок регулярных выражений может или не может пытаться сопоставить «снова» в той же позиции, давайте обратимся к Продвижение после соответствия регулярному выражению нулевой длины - Соответствия регулярному выражению нулевой длины - Regular-expressions.info :

Скажем, у нас есть регулярное выражение \d*|x, строка темы x1

Первое совпадение - пустое совпадение в начале строки.Теперь, как мы можем дать другим токенам шанс, не застревая в бесконечном цикле?

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

Это может дать нелогичные результаты - например, приведенное выше регулярное выражение будет соответствовать '' в начале, 1 и '' в конце - но не x.

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

Который "пропускает" совпадения меньше за счет некоторых дополнительныхсложность.Например, приведенное выше регулярное выражение будет выдавать '', x, 1 и '' в конце.

В статье показано, что здесь не существует лучших практик иразличные движки регулярных выражений активно пробуют новые подходы , чтобы попытаться получить более «естественные» результаты:

Одним исключением является движок JGsoft.Движок JGsoft продвигается на один символ после совпадения нулевой длины, как это делает большинство движков.Но у него есть дополнительное правило для пропуска совпадений нулевой длины в позиции, где закончилось предыдущее совпадение, поэтому вы никогда не сможете получить совпадение нулевой длины, непосредственно примыкающее к совпадению ненулевой длины.В нашем примере движок JGsoft находит только два совпадения: совпадение нулевой длины в начале строки и 1.

Python 3.6 и предшествующее продвижение после совпадений нулевой длины.Функция gsub () для поиска и замены пропускает совпадения нулевой длины в позиции, где закончилось предыдущее совпадение, отличное от нулевой длины, но функция finditer () возвращает эти совпадения.Таким образом, поиск и замена в Python дает те же результаты, что и приложения Just Great Software, но перечисление всех совпадений добавляет совпадение нулевой длины в конце строки.

Python 3.7 изменил все это.Он обрабатывает совпадения нулевой длины, такие как Perl.gsub () теперь заменяет совпадения нулевой длины, которые соседствуют с другим соответствием.Это означает, что регулярные выражения, которые могут найти совпадения нулевой длины, несовместимы между Python 3.7 и предыдущими версиями Python.

PCRE 8.00 и более поздних версий, а PCRE2 обрабатывает совпадения нулевой длины, такие как Perl,возвраты. Они больше не продвигаются на один символ после нулевой длины соответствует как PCRE 7.9.

Функции регулярного выражения в R и PHP основаны на PCRE, поэтому они избегают застрять в матче нулевой длины, возвращаясь назад, как это делает PCRE. Но функция gsub () для поиска и замены в R также пропускает совпадения нулевой длины в позиции, где предыдущая ненулевая длина матч закончился, как gsub () в Python 3.6 и предыдущих версиях. Другой Функции регулярного выражения в R и все функции в PHP позволяют совпадения нулевой длины, непосредственно соседствующие с совпадениями ненулевой длины, так же, как и сам PCRE.

Answer 2

Я не знаю, откуда возникла путаница.
Движки Regex в основном глупы .
Они как Майки, они будут есть все.

$ python -c "import re; print(re.findall('$.*', 'a'))"
[''] # !! Matched the hypothetical empty string after the end of 'a'

Вы можете поместить тысячу необязательных выражений после $, и оно все равно будет соответствовать
EOS.Двигатели тупые.

$ python -c "import re; print(re.findall('.*$', 'a'))"
['a', ''] # !! Matched both the full input AND the hypothetical empty string

Подумайте об этом, здесь есть два независимых выражения
.* |$.Причина в том, что первое выражение является необязательным.
Это просто происходит против утверждения EOS.
Таким образом, вы получаете 2 совпадения с непустой строкой.

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

Класс вещей, называемых утверждениями, не существует в позициях символов.
Они существуют только МЕЖДУ позициями символов.
Если они существуют врегулярное выражение, вы не знаете, был ли использован весь ввод.
Если они могут быть выполнены как независимый шаг, но только один раз, они будут совпадать с
независимо.

Помните, регулярное выражение - это предложение left-to-right.
Также помните, что двигатели глупы .
Это специально.
КаждыйКонструкция - это состояние в движке, это как конвейер.
Сложность наверняка обречёт на неудачу.

Кроме того, .*a фактически начинается с начала и проверяет каждый символ?
Нет. .* немедленно начинается в конце строки (или строки, в зависимости от) и начинается
возвраты.

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

Удачи!Не беспокойтесь, движки регулярных выражений просто ... ну, глупо .

Answer 3

<sup>Примечание:
* Мой пост с вопросом содержит два связанных, но разных вопроса , для которых я должен был создать отдельные посты, как я теперь понимаю.
* Другие ответы здесь сосредоточены на по одному вопросов каждый, поэтому отчасти этот ответ дает дорожную карту того, какие ответы отвечают на какой вопрос .</sup>

---

Что касается того, почему такие шаблоны, как $<expr> разрешены / когда они имеют смысл:

• ответ Дога утверждает, что бессмысленные комбинации, такие как $.+ , вероятно, , не предотвращаются по прагматическим причинам; исключение их может не стоить усилий.

• Ответ Тима показывает, как определенные выражения могут имеют смысл после $, а именно отрицательный взгляд за утверждениями .

• Вторая половина ответа Ивана_Поздеева ответа убедительно синтезирует ответы Дога и Тима.

---

Что касается того, почему глобальное соответствие находит два совпадения для таких шаблонов, как .* и .*$:

• ответ revo содержит отличную справочную информацию о сопоставлении нулевой длины (с пустой строкой), к чему и сводится проблема в конечном итоге .

Позвольте мне дополнить его ответ, связав его более непосредственно с тем, как поведение противоречит моим ожиданиям в контексте глобального соответствия:

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

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

  • Если имеющееся регулярное выражение совпадает с пустой строкой (создает совпадение нулевой длины; например, регулярные выражения, такие как .* или a?), оно соответствует этой позиции и возвращает пустую строку матч.

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

Хотя это предоставляет техническое объяснение поведения, оно все равно не сообщает нам почему соответствует после последнего символа, который был реализован.

Самая близкая вещь, которую мы имеем, - это образованное предположение от Wiktor Stribiżew в комментарии (выделение добавлено), которое снова предлагает прагматическую причину поведения :

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

Первая половина ответа ivan_pozdeev объясняет поведение более технически подробно, говоря нам, что пустое поле в конце строки [input] является допустимой позицией для сопоставления, как и любая другая символьная граница позиция.
Однако, хотя обработка всех таких позиций однозначно внутренне непротиворечива и, по-видимому, упрощает реализацию , поведение по-прежнему не поддается здравому смыслу и не имеет очевидных преимуществ для пользователя .

---

Дополнительные наблюдения по сопоставлению пустой строки:

^{Примечание. Во всех приведенных ниже фрагментах кода глобальная строка замена выполняется для выделения итоговых совпадений: каждое совпадение заключено в [...], тогда как несоответствующие части входных данных передаются черезкак есть.}

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

Например, механизм регулярных выражений .NET не делает это (пример PowerShell):

PS> 'a1' -replace '\d*|a', '[$&]'
[]a[1][]

То есть:

• \d* соответствует пустой строке до a
• a, а затем не ,это означает, что позиция символа была продвинутой после пустого соответствия.
• 1 было сопоставлено с \d*
• Позиция конца строки объекта быласнова соответствует \d*, что приводит к другому совпадению с пустой строкой.

Perl 5 является примером механизма, который возобновляет сопоставление при в том же позиция символа:

$ "a1" | perl -ple "s/\d*|a/[$&]/g"
[][a][1][]

Обратите внимание, что a также сопоставлялось.

Интересно, что Perl 6 не только ведет себя по-разному.у, но демонстрирует еще один вариант поведения:

$ "a1" | perl6 -pe "s:g/\d*|a/[$/]/"
[a][1][]

По-видимому, если чередование находит и и пустое и непустое совпадение, сообщается только о непустом - см.Комментарий Revo ниже.

Answer 4

В чем причина использования .* с глобальным модификатором?Потому что кто-то ожидает, что пустая строка будет возвращена как совпадение, или он / она не знает, что такое квантификатор *, иначе глобальный модификатор не должен быть установлен..* без g не возвращает двух совпадений.

не очевидно, в чем выгода этого поведения.

Не должно быть выгоды,На самом деле вы ставите под сомнение существование совпадений нулевой длины.Вы спрашиваете , почему существует строка нулевой длины?

У нас есть три допустимых места, где существует строка нулевой длины:

• Начало строки субъекта
• Между двумя символами
• Конец строки темы

Мы должны искать причину, а не преимущество этого второго вывода совпадения нулевой длины, используя .*с модификатором g (или функцией, которая ищет все вхождения).Эта позиция нулевой длины после входной строки имеет некоторое логическое применение.Ниже приведена диаграмма состояний из debuggex для .*, но я добавил эпсилон при прямом переходе из начального состояния в состояние принятия, чтобы продемонстрировать определение:

Это совпадение нулевой длины (подробнее о epsilon transition ).

Все это относится к жадности и не жадности.Без позиций нулевой длины регулярное выражение типа .?? не имело бы значения.Сначала он не пробует точку, а пропускает.Для этой цели она соответствует строке нулевой длины, чтобы перевести текущее состояние во временное допустимое состояние.

Без позиции нулевой длины .?? никогда не сможет пропустить символ во входной строке, что приведет к совершенно новому вкусу.

Определение жадности / лени приводит к совпадениям нулевой длины.

Answer 5

Напомним несколько вещей:

1. ^ и $ являются утверждениями нулевой ширины - они совпадают сразу после логического начала строки (или послекаждая строка заканчивается в многострочном режиме с флагом m в большинстве реализаций регулярных выражений) или на логическом конце строки (или конце строки ДО конца символа строки или символов в многострочном режиме.)

2. .* потенциально представляет собой совпадение нулевой длины , не совпадающее вообще.Версия только нулевой длины будет $(?:end of line){0} DEMO (что полезно, как комментарий, я думаю ...)

3. . не соответствует \n (если только у вас нет флага s), но он совпадает с \r в окончаниях строк Windows CRLF.Так, например, $.{1} соответствует только концу строки Windows (но не делайте этого. Используйте вместо него литерал \r\n.)

Особого преимущества * 1035 нет* кроме простых случаев побочных эффектов.

1. Регулярное выражение $ полезно;
2. .* полезно.
3. Регулярные выражения ^(?a lookahead) и (?a lookbehind)$ являются общими и полезными.
4. Регулярные выражения (?a lookaround)^ или $(?a lookaround) потенциально полезны.
5. Регулярное выражение $.* бесполезно и достаточно редко, чтобы не оправдать реализацию какой-либо оптимизации, чтобы остановить остановку двигателя в этом крайнем случае.Большинство движков регулярных выражений делают приличный анализ синтаксиса;например, отсутствующая скобка или скобка.Чтобы разбирать движок $.* как бесполезный, потребовалось бы разобрать значение этого регулярного выражения, отличное от $(something else)
6. То, что вы получите, будет сильно зависеть от вида регулярного выражения и статуса s иm flags.

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

#!/bin/bash

echo "perl"
printf  "123\r\n" | perl -lnE 'say if s/$.*/X/mg' | od -c
echo "sed"
printf  "123\r\n" | sed -E 's/$.*/X/g' | od -c
echo "python"
printf  "123\r\n" | python -c "import re, sys; print re.sub(r'$.*', 'X', sys.stdin.read(),flags=re.M) " | od -c
echo "awk"
printf  "123\r\n" | awk '{gsub(/$.*/,"X")};1' | od -c
echo "ruby"
printf  "123\r\n" | ruby -lne 's=$_.gsub(/$.*/,"X"); print s' | od -c

Prints:

perl
0000000    X   X   2   X   3   X  \r   X  \n                            
0000011
sed
0000000    1   2   3  \r   X  \n              
0000006
python
0000000    1   2   3  \r   X  \n   X  \n                                
0000010
awk
0000000    1   2   3  \r   X  \n                                        
0000006
ruby
0000000    1   2   3   X  \n                                            
0000005

Answer 6

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

• начинается с трех цифр
• , за которым следуют одна или несколько букв, цифр, дефиса или подчеркивания
• оканчивается только буквами и цифрами

Мы можем написать следующий шаблон:

^\d{3}[A-Za-z0-9\-_]*[A-Za-z0-9]$

Но это немного громоздко, потому что мы должны использовать два одинаковых класса символов, смежные друг с другом. Вместо этого мы могли бы написать шаблон как:

^\d{3}[A-Za-z0-9\-_]+$(?<!_|-)

или

^\d{3}[A-Za-z0-9\-_]+(?<!_|-)$

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

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