Tiebreaker для альтернативных регулярных выражений одинаковой длины с одинаковой начальной позицией - PullRequest
Новая
       26

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

5 голосов
/ 10 января 2020

Используя GNU sed (для ясности с флагом -r), следующие две замены во входной строке ab дают тот же результат: 

s/(.)(.)|(.)(.)$/\2\1\3\4/

и 

s/(.)(.)$|(.)(.)/\1\2\4\3/

оба дают ba. Казалось бы, альтернатива (.)(.) (без $) удачна в обеих заменах, независимо от того, является ли ее положение первой или второй альтернативой. Почему это так? Что такое t ie -разрушитель для таких альтернатив?

Спецификация регулярных выражений POSIX определяет 1 прерыватель связей, когда альтернативы начинаются с разные позиции (в этом случае предпочтительнее более ранняя позиция), и когда они начинаются в одной и той же позиции, но имеют разную длину (предпочтительнее более длинная позиция), но, по-видимому, не указывается поведение групп захвата, когда две альтернативы начинаются с в той же позиции и имеют одинаковую длину, оставляя это для реализации c.

Поиск соответствующей последовательности начинается в начале строки и заканчивается, когда первая последовательность соответствует выражение найдено, где «первый» определяется как «начинается самым ранним в строке». Если шаблон допускает переменное количество совпадающих символов и, таким образом, существует более одной такой последовательности, начинающейся в этой точке, то самая длинная такая последовательность сопоставляется. [...] - Базовые спецификации Open Group Issue 7, выпуск 2018 года

Вот пример работающего явления. 

echo ab|sed -r 's/(.)(.)|(.)(.)$/\2\1\3\4/'
echo ab|sed -r 's/(.)(.)$|(.)(.)/\1\2\4\3/'

Попробуйте онлайн!

1 Ответ

1 голос
/ 01 февраля 2020

Гипотеза об ответе.

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

Однако я бы сказал, что в момент совпадения (.)(.) с ab двигатель будет иметь один дополнительная проверка (против $), чтобы проверить, совпадает ли (.)(.)$ (то есть, совпадает ли она в EOL), и в этом случае последнее регулярное выражение не будет предпочтительным в любом случае , потому что оно имеет ту же длину и начался в той же точке, что и прежнее регулярное выражение, которое уже было найдено. Поэтому для меня имеет смысл, что движок возвращает ссылки на группы в (.)(.) без $.

Я думаю, что мои рассуждения подразумевают, что сопоставление является жадным по отношению к печатным символам, но ленивым по отношению к не -печатаемые.

Сравните / сопоставьте с этим: 

echo ab|sed -r 's/^(.)(.)|(.)(.)/\2\1\3\4/'
ba

echo ab|sed -r 's/(.)(.)|^(.)(.)/\2\1\3\4/'
ba

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

...