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

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

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

принять регулярное выражение, которое явно пытается сопоставить выражение после конца строки ввода ^[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]
- Чтобы задать вопрос более остро: почему функциональность, предназначенная для поиска нескольких совпадающих совпадений регулярного выражения, т.е. Глобального соответствия, решает даже попробовать другое совпадение, если оно знает, что весь вход уже потреблен, независимо от того, что регулярное выражение (хотя вы никогда не увидите симптом с регулярным выражением, которое по крайней мере не соответствует пустой строке)
- Следующие языки/двигатели демонстрируют удивительное поведение:.NET, Python (и 2.x и 3.x) ^[2] Perl (оба 5.x и 6.x), Ruby, Node.js(JavaScript)

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

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

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

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

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

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

Ответ 1

^{Замечания:}^{* Мой вопрос содержит два связанных, но разных вопроса, для которых я должен был создать отдельные сообщения, как я теперь понимаю.}^{* Другие ответы здесь сосредоточены на одном из вопросов каждый, поэтому частично этот ответ дает " дорожную карту", на какие ответы адресуется этот вопрос.}

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

dawg отвечает, что бессмысленные комбинации, такие как $.+ вероятно, не исключены по прагматическим причинам; их решение не может стоить усилий.
Ответ Тима показывает, как определенные выражения могут иметь смысл после $, а именно отрицательные утверждения lookbehind.
Во второй половине ответа ivan_pozdeev ответ убедительно синтезирует ответы Dawg и Tim.

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

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

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

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

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

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

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

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

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

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

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

Например, механизм регулярных выражений.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 ниже.

Ответ 2

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

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

Мы могли бы написать следующую схему:

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

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

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

или же

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

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

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

Ответ 3

Вспомните несколько вещей:

^ и $ - утверждения с нулевой шириной - они соответствуют сразу после логического начала строки (или после каждой строки, заканчивающейся в многострочном режиме с флагом m в большинстве реализаций регулярных выражений) или на логическом конце строки (или в конце строки ПЕРЕД символ конца строки или символы в многострочном режиме.)
.* потенциально совпадает с нулевой длиной совпадения. Версия с нулевой длиной будет равна $(?:end of line){0} DEMO (что полезно в качестве комментария, я думаю...)
. не соответствует \n (если у вас нет флага s), но соответствует символу \r в конце строки Windows CRLF. Таким образом, $.{1} только концам строк Windows (но не делайте этого. Вместо этого используйте литерал \r\n).

Нет особых преимуществ, кроме простых случаев побочных эффектов.

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

Для примеров заметок рассмотрим следующий сценарий 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

Печать:

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

Ответ 4

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

неясно, в чем польза такого поведения.

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

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

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

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

Это соответствие нулевой длины (подробнее об эпсилонном переходе).

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

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

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

Ответ 5

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

|a|b|c|   <- input line

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

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

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

Например, regex \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.

Ответ 6

Я не знаю, откуда возникла путаница.
Двигатели 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 действительно начинается с самого начала и проверяет каждого персонажа?
№ .* Немедленно начинается в конце строки (или линии, в зависимости) и запускается
возвраты.

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

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