Несоответствие между регулярными выражениями 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 может совпадать с правильным, а не с левым. Любое понимание было бы весьма благодарным.

2 Solutions collect form web for “Несоответствие между регулярными выражениями sed и python”

Интересная головоломка, которую вы создали. Из того, что я читал, двигатели регулярных выражений как 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, потому что не могу доказать это из текущих текстов.

  • Как я могу разбить эту строку?
  • Отменить токенину новой строки в одном токене на строки файлов? - Unix
  • Использовать имя папки в виде столбца в текстовом файле
  • Shell: вставьте пустую / новую строку на две строки над рисунком
  • обрезать большой файл журнала
  • Использование grep для чтения журнала для pattern1 в файле и печати только строк, содержащих pattern1. Прекратите поиск, когда pattern2 найден в файле
  • Как обрабатывать огромные текстовые файлы, содержащие символы EOF / Ctrl-Z, используя Python в Windows?
  • Как случайным образом удалить несколько строк из большого файла?
  •  
    Interesting Posts for Van-Lav

    Как печатать каждую строку скрипта, поскольку она запускается только для запуска сценария верхнего уровня?

    ReportLab: автоматическое изменение размера текста в соответствии с блоком

    Эффективные математические операции на небольших массивах на питоне с помощью cython

    Python string.strip, зачищающий слишком много символов

    Преобразовать sql-результат в список python

    Обработка строки Python 3.3 C (wchar_t vs char)

    регулярное выражение python более одного раза соответствует индексу строки поиска

    python pandas объединяет две или более строки текста в одну строку

    Как обрабатывать центр изображения как источник для вычисления тригонометрических функций в OpenCV?

    Динамически обновляемый сюжет в matplotlib

    Многомерная нормальная плотность в Python?

    Выдержка продолжительности видеофайла без внешнего процесса в python

    Не удается привязать адрес после сбоев программы сокета

    python tkinter с потоковой обработкой

    SQLAlchemy и пустые столбцы

    Python - лучший язык программирования в мире.