Greedy and Non-Greedy matching in Python re

Question

Пожалуйста, помогите мне узнать, является ли это ошибкой в ​​Python (2.6.5), в моей компетенции при написании регулярных выражений или в моем понимании соответствия шаблонов.

(Я принимаю, что возможный ответ «Улучшайте Python».)

Я пытаюсь разобрать Yubikey маркер, позволяющий для дополнительных опций.

Когда я использую это регулярное выражение для соответствия маркеров без каких-либо дополнительных опций (то есть, содержащий только материал, который соответствует две группы захвата), матч терпит неудачу:

r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32})\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$' 

Однако, если я делаю первая группа, не являющаяся жадным:

r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32}?)\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$' 

Успешно.

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

Оба Expresso и Regex Coach похожи на оба шаблона.

Что я пропустил?

---

Вот две строки, которые я тестирую. не

Нет дополнительными (те, что может выйти из строя):

"vvbrentlnccnhgfgrtetilbvckjcegblehfvbihrdcui" 

С дополнительными услугами (не удалось до сих пор; фактические вкладки показаны здесь как "_"):

"_!_8R5Gkruvfgheufhcnhllchgrfiutujfh_" 
"_!1U4Knivdgvkfthrd_brvejhudrdnbunellrjjkkccfnggbdng_" 

---

Я попытался воспроизвести его, используя предложение от Alex Martelli, и это не сработает в исходной среде Python, поэтому я собираюсь пересмотреть мой код (я на самом деле разбираюсь в yubikey-python) ; Я отправлю отчет через день или около того.

---

Приношу свои извинения всем. Я не могу воспроизвести проблему. Когда это произошло, я читал ввод через getpass; Я подозреваю, что случайное инородное нажатие мешало.

Я собираюсь закрыть вопрос. Если тот, кто поддержал этот вопрос, хочет удалить свой голос, это справедливо.

Очень жаль.

Answer 1

Я бы рекомендовал использовать yubikey-python для интерфейса Python для yubikey - но это побочная (и строго прагматическая) проблема ;-).

Теоретически не должно быть случаев, когда выбор между жадным и не жадным приводит к тому, что RE будет соответствовать одному случаю и потерпеть неудачу в другом - он должен влиять только на то, что соответствует (и, как вы говорите, о производительности) не соответствует ли совпадение вообще, поскольку REs должны возвращаться для этой цели.

Проблема в том, что я не могу воспроизвести проблему - у меня нет юбикея под рукой, а тесты в this file не показывают различий между двумя режимами соответствия/отсутствия соответствия REs.

Не могли бы вы отправить несколько неудачных примеров (где один совпадает, а другой нет), в идеале, отредактировав свой вопрос, чтобы я мог воспроизвести проблему и попытаться сократить ее до минимума? Похоже, что может быть ошибка RE, но без воспроизводимых случаев я не могу проверить, если и когда она была исправлена, уже сообщено или что. Благодаря!

Редактировать ОП теперь разместил один неисправного пример, но я до сих пор не могу воспроизвести:

$ py26 
Python 2.6.5 (r265:79359, Mar 24 2010, 01:32:55) 
[GCC 4.0.1 (Apple Inc. build 5493)] on darwin 
Type "help", "copyright", "credits" or "license" for more information. 
>>> import re 
>>> r1 = re.compile(r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32})\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$') 
>>> r2 = re.compile(r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32}?)\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$' 
...) 
>>> nox="vvbrentlnccnhgfgrtetilbvckjcegblehfvbihrdcui" 
>>> r1.match(nox) 
<_sre.SRE_Match object at 0xcc458> 
>>> r2.match(nox) 
<_sre.SRE_Match object at 0xcc920> 
>>> 

т.е. матч преуспевает в обоих случаях, как следует - и это точно такой же 2,6. 5 Используется версия Python в качестве OP. OP, pls, показать результаты этой простой последовательности команд на вашей платформе и рассказать нам, что такое платформа, так как она выглядит как странная зависящая от платформы ошибка ... спасибо!

Answer 2

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

(Следующий «решение» не применяется, но вопрос еще не означает, что матч не чувствительны к регистру это выполняется, поэтому я оставлю его.)

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