Несоответствие между регулярными выражениями sed и python

Прошу прощения, если это где-то опубликовано, но мой беглый поиск ничего не нашел.

Выполняя некоторое программирование на Python, я заметил, что следующая команда:

re.sub("a*((ab)*)b", r"\1", "aabb") 

возвращает пустую строку. Но эквивалентная команда в sed:

 echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/" 

возвращает ab .

Для меня имеет смысл, что директива «a *» в начале регулярного выражения python будет соответствовать как «s», так и «ab» * », чтобы соответствовать нулю, но я понятия не имею, как sed подходит к ab . Кто-нибудь знает, какая разница между двумя двигателями регулярных выражений, которые это порождают? Я считаю, что они по-умолчанию соответствуют звездам по умолчанию, но мне пришло в голову, что sed может совпадать с правильным, а не с левым. Любое понимание было бы весьма благодарным.

Интересная головоломка, которую вы создали. Из того, что я читал, двигатели регулярных выражений как python, так и sed основаны на регулярной регулярной библиотеке Генри Спенсера (как и Perl), которая полагается на обратное отслеживание. (К сожалению, я не могу найти статью, на которой я основываюсь).

Во всяком случае, это не то, что должно быть детализация реализации: поведение Python противоречит стандарту POSIX, для которого REs должны (a) соответствовать как можно скорее, и (b) соответствовать самой длинной возможной строке, которая начинается с этой точки , (См. man 7 regex (в Linux) для этого и многое другое.)

Чтобы найти самое длинное совпадение, механизм регулярного выражения backtracking («NFA-type») должен продолжить изучение альтернатив после того, как он найдет одно совпадение. Поэтому неудивительно, что разработчики срезали углы. Очевидно, что поведение python является несоответствующим, поскольку не удается найти самое длинное совпадение. Согласно странице руководства sed, sed также не всегда соответствует «по соображениям производительности». Но, очевидно, это правильно.

Кстати, ваши команды не полностью эквивалентны: re.sub будет выполнять подстановку столько раз, сколько возможно, в то время как sed s/a/b/ будет выполнять ее только один раз. Версия sed должна была быть:

 echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/g" 

Это объясняет, почему мы получаем пустую строку в python: RE соответствует aab в первый раз, а второй – второй раз, удаляя каждую часть (поскольку все они совпадают с a* и окончательным b регулярного выражения). Вы можете видеть это по следующему варианту:

 >>> re.sub("a*((ab)*)b", r"X\1Y", "aabb") 'XYXY' 

Как Python, так и sed являются жадными по умолчанию, но … Python regex пытается оценивать слева направо при любых обстоятельствах, несмотря на то, что в конечном итоге он должен сделать обратную трассировку в предыдущем состоянии, если ветка, которую судили, не может продолжить путем сопоставления. Опция Sed regex наоборот оптимизирована перед оценкой, чтобы предотвратить ненужную обратную трассировку, переписывая регулярное выражение в более детерминированную форму. Поэтому объединенный факультативный шаблон «aab», вероятно, проверяется перед простым «a», потому что сначала проверяется самая конкретная возможная строка.

Шаблон Python совпадает с строкой «aabb» дважды «aab» + «b» (помечен между «<>»)

 >>> re.sub("a*((ab)*)b", r"<\1>", "aabb") '<><>' 

в то время как sed соответствует целому «aabb» одной заменой:

 $ echo "aabb" | sed "s/a*\(\(ab\)*\)b/<\1>/" <ab> 

Алгоритм обратного преобразования регулярных выражений Python хорошо объясняется в regex howto – Повторяющиеся вещи в двух параграфах, введенные словами «Пошаговый пример …». Это IMO именно то, что описано regex docs : «По мере сканирования целевой строки REs разделяются на« | » судимы слева направо ».

демонстрация

Порядок «(| a | aa)» btw. «(aa | a |)» соблюдается Python

 >>> re.sub("(?:|a|aa)((ab)*)b", r"<\1>", "aabb") '<ab>' >>> re.sub("(?:aa|a|)((ab)*)b", r"<\1>", "aabb") '<><>' 

но этот порядок игнорируется sed, потому что sed оптимизирует регулярные выражения. Согласование «aab» + «b» можно воспроизвести, удалив опцию «a» из шаблона.

 $ echo "aabb" | sed "s/\(\|a\|aa\)\(\(ab\)*\)b/<\2>/g" <ab> $ echo "aabb" | sed "s/\(aa\|a\|\)\(\(ab\)*\)b/<\2>/g" <ab> $ echo "aabb" | sed "s/\(aa\|\)\(\(ab\)*\)b/<\2>/g" <><> 

Изменить : я удалил все о DFA / NFA, потому что не могу доказать это из текущих текстов.