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

Question

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

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

а также

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

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

---

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

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

Вот наглядный пример явления.

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

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

Answer 1

Гипотетический ответ.

Учитывая строку ввода 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

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