{M, n}?regex на самом деле минимизирует количество повторений или минимизирует количество совпавших символов?

Question

Согласно документации Python3 Regex :

{m,n}?

Вызывает совпадение полученного RE от m до n повторений предыдущего RE, пытаясь сопоставить как можно меньше повторенийнасколько это возможно.Это нежадная версия предыдущего классификатора.Например, в 6-символьной строке «aaaaaa» {3,5} будет соответствовать 5 символам «a», а {3,5}?будет соответствовать только 3 символам.

Однако, похоже, это противоречит следующему эксперименту:

import re
regex = re.compile('(abc|d|abcde){1,2}?(e|f)')
regex.match('abcdef')

... что соответствует 'abcde'.Это обязательно включает в себя 2 повторений (abc | d | abcde), а именно 'abc' и 'd'.Тем не менее, был альтернативный кандидат на совпадение, который включал только 1 повторение (abc | d | abcde), а именно 'abcde'.

Я неправильно прочитал документацию или {m,п}?фактически свести к минимуму количество совпавших символов (или какую-то другую цель), а не количество повторений?

Answer 1

{m,n}? пытается совпадать как можно меньше раз, но он не достигнет abc|d|abcde и не изменит поведение |. | все еще пробует левый вариант первым.

(abc|d|abcde){1,2}? пытается сопоставить (abc|d|abcde) один раз и успешно, сопоставляя abc. Затем механизм регулярных выражений продолжает работу с остальной частью шаблона и пытается сопоставить (e|f), что не удается. Он отслеживает и пытается найти другое повторение abc|d|abcde и соответствует d. Он снова продолжается до (e|f) и успешно соответствует e.

Возможно, вы ожидали, что при возврате к предыдущей версии (abc|d|abcde) будет другой вариант, а затем вторая (abc|d|abcde). Это не делает этого. В конце концов, он попытался бы, если бы это было необходимо, но сначала нужно попробовать больше совпадений для {1,2}?.

Answer 2

Минимальное количество повторений не вызывается, просто позволяет сопоставлять меньшее количество раз.

Когда у вас есть несколько альтернатив, которые могут совпадать, движки регулярных выражений обрабатывают вещи по-разному. Некоторые «стремятся» и используют первые подходящие альтернативы, другие используют правило «самого длинного соответствия». Видимо Python очень хочет Таким образом, (abc|d|abcde) будет соответствовать abc, а не abcde, и тогда следующее повторение будет соответствовать e. Он не проверяет, есть ли результат с меньшим количеством повторений.

Решение состоит в том, чтобы поставить более длинные альтернативы на первое место. Измените его на

regex = re.compile('(abcde|abc|d){1,2}?(e|f)')

Answer 3

Regex не оценивает все возможные опции и выбирает наименьший - если доставляет первый, который находит:

import re
regex = re.compile('(abc|def|gh|abcde|fghi){2,3}?(i|j)')
rex.match('abcdefghij')

Первое совпадение для {2,3}: abc|def|gh (слева направо).

Если вы измените порядок своего шаблона, вы получите то, что хотите:

import re
rex = re.compile('(abcde|fghi|abc|def|gh){2,3}?(i|j)')
print(rex.match('abcdefghij').group()) 

Выход:

abcdefghij

Answer 4

Чередование в группе начинает сопоставление слева и имеет не жадный квантификатор {1,2}?, который соответствует минимальному количеству и применяется к этой группе.Python не пытается найти самое длинное совпадение в чередовании , но первое совпадение .

Когда начинается сопоставление, механизм сначала находит abc, а затем пытается сопоставить eили f next, что не соответствует, потому что есть d после abc.

Но поскольку квантификатор равен {1,2}?, у остается еще одна опция, чтобы попробовать для первой группы и возврата, чтобы попытаться найти совпадение снова.Он не может соответствовать abc, но может соответствовать d.Затем он пытается сопоставить e или f снова, где он может соответствовать e

Answer 5

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

Обратите внимание, что двигатель все равно сделает все возможное, чтобы найти совпадение. Если более длинное выражение позволит двигателю возвращать совпадение, а более короткое - не будет, то двигатель выберет такое, которое позволит ему вернуть совпадение.

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

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