Стандартное регулярное выражение и несоответствие регулярному выражению Python

Question

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

b*(abb*)*(a|∊) - Strings of a's and b's with no consecutive a's.

Теперь я попытался преобразовать его в python так:

>> p = re.compile(r'b*(abb*)*(a|)') # OR
>> p = re.compile(r'b*(abb*)*(a|\b)')

# BUT it still doesn't work
>>> p.match('aa')
<_sre.SRE_Match object at 0x7fd9ad028c68>

У меня вопрос двоякий:

1. Что эквивалентно epsilon в python для работы приведенного выше примера?
2. Может кто-нибудь объяснить мне, почему теоретический или стандартный способ выполнения регулярных выражений не работает в python? Может быть, это как-то связано с самым длинным или самым коротким соответствием?

Разъяснение: для людей, спрашивающих, что такое стандартное регулярное выражение - это формальный стандарт теории языка: http://en.wikipedia.org/wiki/Regular_expression#Formal_language_theory

Answer 1

На самом деле, пример работает просто отлично ... до мелочей. Я бы написал:

>>> p = re.compile('b*(abb*)*a?')
>>> m = p.match('aa')
>>> print m.group(0)
'a'
>>> m = p.match('abbabbabababbabbbbbaaaaa')
>>> print m.group(0)
abbabbabababbabbbbba

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

Как видите, выражение соответствует последовательности a и b без повторения a. Если действительно, вы хотите проверить всю строку, вам нужно немного изменить:

>>> p = re.compile('^b*(abb*)*a?$')
>>> m = p.match('aa')
>>> print m
None

^ и $ принудительно распознают начало и конец строки.

Наконец, вы можете объединить оба метода, используя первое регулярное выражение, но с проверкой в ​​конце:

>>> len(m.group(0)) == len('aa')

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

Answer 2

Спасибо за ответы. Я чувствую, что каждый ответ был частью ответа. Вот что я искал.

1. ? это просто сокращение для (что-то | & epsilon;) . Таким образом, (a | & epsilon;) можно переписать как a? . Итак, пример становится:

   b*(abb*)*a?
   

   В питоне мы бы написали:

   p = re.compile(r'^b*(abb*)*a?$')
   

2. Причина, по которой прямой перевод синтаксиса регулярного регулярного выражения на python (т.е. копирование и вставка) не работает, заключается в том, что python соответствует самой короткой подстроке (если символы $ или ^ отсутствуют), в то время как теоретические регулярные выражения соответствуют самой длинной начальной подстроке .
   Так, например, если у нас была строка:

   s = 'aa'
   

   Регулярное выражение нашего учебника b * (abb *) * a? не будет соответствовать ему, потому что у него два a Однако, если мы скопируем его прямо в python:

   >> p = re.compile(r'b*(abb*)*a?')
   >> bool(p.match(s))
   True
   

   Это потому, что наше регулярное выражение соответствует только подстроке 'a' нашей строки 'aa'.
   Чтобы заставить python сопоставлять всю строку, мы должны указать, где находится начало и конец строки, с символами ^ и $ соответственно:

   >> p = re.compile(r'^b*(abb*)*a?$')
   >> bool(p.match(s))
   False
   

   Обратите внимание, что регулярное выражение python match () соответствует началу начало строки, поэтому оно автоматически принимает ^ в начале. Однако функция search () этого не делает, и поэтому мы сохраняем ^ .
   Так, например:

   >> s = 'aa'
   >> p = re.compile(r'b*(abb*)*a?$')
   >> bool(p.match(s))
   False                 # Correct
   >> bool(p.search(s))
   True                  # Incorrect - search ignored the first 'a'
   

Answer 3

Я не совсем уверен, как работает match в python, но я думаю, что вам может понадобиться добавить ^ .... $ к вашему RE. Соответствие RegExp обычно соответствует подстрокам, и оно находит наибольшее совпадение, в случае p.match ('aa') это "a" (вероятно, первое). ^ ... $ удостоверится, что вы соответствуете ВСЕЙ строке, и я верю, что вы хотите.

Теоретические / стандартные reg exps предполагают, что вы всегда соответствуете всей строке, потому что вы используете ее для определения языка строк, которые не соответствуют, а не находят подстроку во входной строке.

Answer 4

1

• Используйте bool(p.match('aa')), чтобы проверить, соответствует ли регулярное выражение или нет

• p = re.compile('b*(abb*)*a?$')

• \b соответствует границе строки; место между \w и \W (буквенные и несловные символы)

2

Regexp вполне стандартно для Python. Тем не менее, каждый язык имеет некоторый вкус, они не на 100% портативны. Есть небольшие отличия, которые вы ожидаете найти перед использованием regexp на любом конкретном языке.

Добавление

\epsilon не имеет специального символа в питоне. Это пустой набор символов.

В вашем примере a|\epsilon эквивалентно (a|) или просто a?. После которого $ обязательно совпадает с концом строки.

Answer 5

проблема с вашим выражением в том, что оно совпадает с пустой строкой, что означает, что если вы это сделаете:

>>> p = re.compile('b*(abb*)*(a|)')
>>> p.match('c').group(0)
''

и так как re.match пытается соответствовать началу строки, вы должны указать ему, чтобы он совпадал до конца строки. просто используйте $ для этого

>>> p = re.compile(r'b*(abb*)*(a|)$')
>>> print p.match('c')
None
>>> p.match('ababababab').group(0)
'ababababab'

ps - вы, возможно, заметили, что я использовал r'pattern 'вместо' pattern 'подробнее об этом здесь (первые абзацы)

Answer 6

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

Что бы ни стоило, ваш шаблон соответствует «а». То есть это соответствует:

• ноль или более "b" с (выбор ноль)
• ноль или более "(abb*)" с (выбор ноль)
• один "a" или окончание слова (выбор а).

Как отметил Джонатан Фейнберг, если вы хотите, чтобы вся строка соответствовала, вы должны привязать начало ('^') и конец ('$') вашего регулярного выражения. Вы также должны использовать необработанную строку при создании регулярных выражений в python: r'my regex '. Это предотвратит чрезмерную обратную косую черту, избежав путаницы.

Answer 7

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

re.compile(r'^(a(?!a)|b)*$')