Регулярные грамматики по Хомскому — источник регулярных выражений

* полезная ссылка на Гитхаб, буквально план лекции

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

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

>>> import re  
>>> # самое простое рв — строка  
>>> re.search("we", "qwer")  
<re.Match object; span=(1, 3), match='we'>  
>>> # спец объект, о нём позже  
>>>
>>> re.findall(r"we", "qwert")  
['we']  
>>> # Подаём raw-строку, чуть позже  
>>> # Чтобы не думать  
>>>
>>> # Атомарное РВ — строка из одного символа, остальное — составное, вообще говоря  
>>>
>>>
>>> # . — любой символ алфавита  
>>> re.findall(r"w.", "qwertqweyrt")  
['we', 'we']  
>>> re.findall(r"w.", "qwertqwiyrt")  
['we', 'wi']  
>>> re.findall(r"w.", "qwertqwiyrtw")  
['we', 'wi']  
>>>
>>> # Диапазон  
>>> re.findall(r"w[a-g]", "qwertqwiyrtw")  
['we']  
>>> re.findall(r"w[a-ci]", "qwertqwiyrtw")  
['wi']  
>>> # С отрицанием  
>>> re.findall(r"w[^a-ci]", "qwertqwiyrtw")  
['we']  
>>>
>>>
>>>

>>> # Повторитель — применяется к АТОМАРНОМУ РВ  
>>>
>>> re.findall(r"we+", "wa_we_wee_weeeeeeex")  
['we', 'wee', 'weeeeeee']  
>>> # + — один или более раз. Правило матчинга — "Самый левый, самый длинный"
>>>
>>> # * — 0 или более раз  
>>> re.findall(r"we*", "wa_we_wee_weeeeeeex")  
['w', 'we', 'wee', 'weeeeeee']  
>>> re.findall(r"e*", "wa_we_wee_weeeeeeex")  
['', '', '', '', 'e', '', '', 'ee', '', '', 'eeeeeee', '', '']  
>>> # Ноль раз матчится вообще везде  
>>>
>>> # Диапазон повторения  
>>>
>>> re.findall(r"e{2}", "wa_we_wee_weeeeeeex")  
['ee', 'ee', 'ee', 'ee']  
>>> re.findall(r"e{2,}", "wa_we_wee_weeeeeeex")  
['ee', 'eeeeeee']  
>>> re.findall(r"e{,2}", "wa_we_wee_weeeeeeex")  
['', '', '', '', 'e', '', '', 'ee', '', '', 'ee', 'ee', 'ee', 'e', '', '']  
>>> re.findall(r"e{2,3}", "wa_we_wee_weeeeeeex")  
['ee', 'eee', 'eee']  
>>>
>>> # ? — ноль или 1 раз  
>>> re.findall(r"we?", "wa_we_wee_weeeeeeex")  
['w', 'we', 'we', 'we']  
>>>

>>> # Операции группировки — составное РВ делать атомарным  
>>> re.findall(r"we+", "wa_we_wee_weeeweewewex")  
['we', 'wee', 'weee', 'wee', 'we', 'we']  
>>> re.findall(r"(we+)", "wa_we_wee_weeeweewewex")  
['we', 'wee', 'weee', 'wee', 'we', 'we']  
>>> re.findall(r"((we+)+)", "wa_we_wee_weeeweewewex")  
[('we', 'we'), ('wee', 'wee'), ('weeeweewewe', 'we')]  
>>>
>>> # Карманы — считаются по открывающимся скобкам (т.е. от внешнего к внутренним слева направо)  
>>>
>>> re.findall(r"(?:we+)+", "wa_we_wee_weeeweewewex")  
['we', 'wee', 'weeeweewewe']  
>>> # (?:) — сделать группу , но не делать карман  
>>>
>>> # Если есть хоть один карман — выдастся только этот карман  
>>> re.findall(r"(?:(w)e+)+", "wa_we_wee_weeeweewewex")  
['w', 'w', 'w']  
>>>

>>> # Альтернативы  
>>>
>>> re.findall(r"w+|e+|[ab]+", "wa_we_wee_weeeweewewexabba")  
['w', 'a', 'w', 'e', 'w', 'ee', 'w', 'eee', 'w', 'ee', 'w', 'e', 'w', 'e', 'abba']  
>>> re.findall(r"w+|e+|[ab]+", "weeeweewewexabba")  
['w', 'eee', 'w', 'ee', 'w', 'e', 'w', 'e', 'abba']  
>>>

>>> # Зачем нам Raw-string: В Языке есть много сокращений. Н-р \w — любой идентификационный символ  
>>> re.findall(r"\w+", "wqdf;wvn 0823m_apsovj\\pfh")  
['wqdf', 'wvn', '0823m_apsovj', 'pfh']  
>>> re.findall(r"\W+", "wqdf;wvn 0823m_apsovj\\pfh") # Не такой символ  
[';', ' ', '\\']  
>>> re.findall(r"\d+", "wqdf;wvn 0823m_apsovj\\pfh")  
['0823']  
>>> re.findall(r"\D+", "wqdf;wvn 0823m_apsovj\\pfh")  
['wqdf;wvn ', 'm_apsovj\\pfh']  
>>> re.findall(r"\s+", "wqdf;wvn 0823m_apsovj\\pfh")  
[' ']  
>>> re.findall(r"\S+", "wqdf;wvn 0823m_apsovj\\pfh")  
['wqdf;wvn', '0823m_apsovj\\pfh']  
>>>
>>> # В рв есть символы позиционирования:  
>>> re.findall("we+", "wee-weeee")  
['wee', 'weeee']  
>>> re.findall("^we+", "wee-weeee")  
['wee']  
>>> re.findall("^we+", "_wee-weeee")  
[]  
>>> # Просмотр от начала. re.match так работает по умолчанию  
>>>
>>> # конец строки $  
>>>
>>> re.findall("we+$", "_wee-weeee")  
['weeee']  
>>> re.findall("we+$", "_wee-weeee*")  
[]  
>>> # \b — только если слово (то, что определяется \w) начинается с РВ
>>>
>>>

>>> # Группировки: Алгоритм матчинга РВ. В методе ничего про замену, а она есть  
>>>
>>> re.sub("we+", "QQ", "a we weee we/we/wee/we")  
'a QQ QQ QQ/QQ/QQ/QQ'  
>>> re.sub(r"we+", "QQ", "a we weee we/we/wee/we")  
'a QQ QQ QQ/QQ/QQ/QQ'  
>>> # Можно работать с карманами  
>>>
>>> re.sub(r"we+", "Q\1Q", "a we weee we/we/wee/we")  
'a Q\x01Q Q\x01Q Q\x01Q/Q\x01Q/Q\x01Q/Q\x01Q'  
>>> re.sub(r"(we+)", "Q\1Q", "a we weee we/we/wee/we")  
'a Q\x01Q Q\x01Q Q\x01Q/Q\x01Q/Q\x01Q/Q\x01Q'  
>>> re.sub(r"(we+)", r"Q\1Q", "a we weee we/we/wee/we")  
'a QweQ QweeeQ QweQ/QweQ/QweeQ/QweQ'  
>>>
>>> re.search(r"(we+).*\1", "_we-weeweeee")  
<re.Match object; span=(1, 9), match='we-weewe'>  
>>> re.findall(r"((we+).*\1)", "_we-weeweeee")  
Traceback (most recent call last):  
 File "<python-input-44>", line 1, in <module>
   re.findall(r"((we+).*\1)", "_we-weeweeee")
   ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 File "/usr/lib/python3.13/re/__init__.py", line 278, in findall
   return _compile(pattern, flags).findall(string)
          ~~~~~~~~^^^^^^^^^^^^^^^^
 File "/usr/lib/python3.13/re/__init__.py", line 350, in _compile
   p = _compiler.compile(pattern, flags)
 File "/usr/lib/python3.13/re/_compiler.py", line 748, in compile
   p = _parser.parse(p, flags)
 File "/usr/lib/python3.13/re/_parser.py", line 980, in parse
   p = _parse_sub(source, state, flags & SRE_FLAG_VERBOSE, 0)
 File "/usr/lib/python3.13/re/_parser.py", line 459, in _parse_sub
   itemsappend(_parse(source, state, verbose, nested + 1,
               ~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                      not nested and not items))
                      ^^^^^^^^^^^^^^^^^^^^^^^^^
 File "/usr/lib/python3.13/re/_parser.py", line 863, in _parse
   p = _parse_sub(source, state, sub_verbose, nested + 1)
 File "/usr/lib/python3.13/re/_parser.py", line 459, in _parse_sub
   itemsappend(_parse(source, state, verbose, nested + 1,
               ~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                      not nested and not items))
                      ^^^^^^^^^^^^^^^^^^^^^^^^^
 File "/usr/lib/python3.13/re/_parser.py", line 543, in _parse
   code = _escape(source, this, state)
 File "/usr/lib/python3.13/re/_parser.py", line 435, in _escape
   raise source.error("cannot refer to an open group",
                      len(escape))
re.PatternError: cannot refer to an open group at position 8  
>>> re.findall(r"((we+).*\2)", "_we-weeweeee")  
[('we-weewe', 'we')]  
>>>
>>> re.findall(r"[Aa]+[Aa]+", "baaaaaAb")  
['aaaaaA']  
>>> re.findall(r"([Aa]+)([Aa]+)", "baaaaaAb")  
[('aaaaa', 'A')]  
>>> # Яваный вид Самого левого Самого длинного  
>>> re.findall(r"([Aa]+)([Aa]{2,})", "baaaaaAb")  
[('aaaa', 'aA')]  
>>>

Лезем из базы РВ

>>> # Пред и постпросмотр. Есть элементы до/после, мы их находим, но не матчим  
>>>
>>> re.findall(r"(we+(?=we+))", "_we-weeweeeeeweeeeeee")  
['wee', 'weeeee']  
>>> re.findall(r"(we+(?!we+))", "_we-weeweeeeeweeeeeee")  
['we', 'we', 'weeee', 'weeeeeee']  
>>> re.findall(r"((?<=wee)we+)", "_we-weeweeeeeweeeeeee") # НЕ МОЖЕТ БЫТЬ ПЕРЕМЕННОЙ ДЛИНЫ  
['weeeee']  
>>> re.findall(r"((?<!wee)we+)", "_we-weeweeeeeweeeeeee")  
['we', 'wee', 'weeeeeee']  
>>>

Язык РВ разрабатываллся для парсинга именно строк в тексте. Строка — естественный способ ограничить контекст. Современные компьютеры вполне позволяют обрабатывать multiline (есть флаг re.M для этого)

Дальше за пределы регулярных грамматик

>>> # Ленивый повторитель — "Самый левый, самый короткий"  
>>>
>>> re.findall(r"we*we+", "_we-weeweeeeeweeeeeeee")  
['weeweeeee']  
>>> re.findall(r"(a*)(a+)", "_aaaaa_")  
[('aaaa', 'a')]  
>>> re.findall(r"(a*?)(a+)", "_aaaaa_")  
[('', 'aaaaa')]  
>>> # Очень опасная штука. Потому что при нарушении "Левый-Длинный" мы не можем сказать "Это наше решение"  
>>> re.findall(r"(a+?)(a+)", "_aaaaa_")  
[('a', 'aaaa')]  
>>> re.findall(r"((a+?)(a+))*", "_aaaaa_")  
[('', '', ''), ('aaaaa', 'a', 'aaaa'), ('', '', ''), ('', '', '')]  
>>> re.findall(r"((a+?)(a+))*?", "_aaaaa_")  
[('', '', ''), ('', '', ''), ('aaaaa', 'a', 'aaaa'), ('', '', ''), ('', '', '')]  
>>>

>>> # Алчные повторители — объясняются через DFA. Захватывают "Левый-Длинный" и не делают BackTrack  
>>>
>>> re.findall(r"(a+)(a+)", "aaaaw")  
[('aaa', 'a')]  
>>> re.findall(r"(a++)(a+)", "aaaaw")  
[]  
>>> # Ускоряется парсинг, но вопрос применения  
>>>

Подробнее про match object

>>> res = re.search(r"([we]+)", "weeweweeexabba")  
>>> res.group()  
'weeweweee'  
>>> res = re.search(r"([we]+).*([ab]+)", "weeweweeexabba")  
>>> res.group()  
'weeweweeexabba'  
>>> res.groups()  
('weeweweee', 'a')  
>>> res = re.search(r"([we]+).*?([ab]+)", "weeweweeexabba")  
>>> res.group()  
'weeweweeexabba'  
>>> res.groups()  
('weeweweee', 'abba')  
>>>
>>> # Карманы бывают именованные  
>>>
>>> res = re.search(r"(?P<WE>[we]+).*?([ab]+)", "weeweweeexabba")  
>>> res.groups()  
('weeweweee', 'abba')  
>>> res.groupdict()  
{'WE': 'weeweweee'}  
>>>
>>> res = re.search(r"(?P<WE>we+).*(?P=WE)", "wee.qwoifhq.weeee.a[spvj.w")  
>>> res.group  
<built-in method group of re.Match object at 0x7f442a8767a0>  
>>> res.group()  
'wee.qwoifhq.wee'  
>>> res.groups()  
('wee',)  
>>> res.groupdict()  
{'WE': 'wee'}  
>>>

>>> import re  
>>> re.escape(r"[a]b\c") # управляющие символы превратили в просто символы  
'\\[a\\]b\\\\c'  
>>> re.split(r"\W+", "psegj psnblkl  3o klp-\ o{SD ")
<python-input-3>:1: SyntaxWarning: invalid escape sequence '\ '  
['psegj', 'psnblkl', '3o', 'klp', 'o', 'SD', '']  
>>> re.split(r"\W+", "psegj psnblkl  3o klp-\\ o{SD ")
['psegj', 'psnblkl', '3o', 'klp', 'o', 'SD', '']  
>>> re.split(r"\s+", "psegj psnblkl  3o klp-\\ o{SD ")
['psegj', 'psnblkl', '3o', 'klp-\\', 'o{SD', '']  
>>> re.split(r"[=+]", "c=a+b")  
['c', 'a', 'b']  
>>> re.split(r"([=+])", "c=a+b")  
['c', '=', 'a', '+', 'b']  
>>> re.split(r"([=+]+)", "c+=a+b")  
['c', '+=', 'a', '+', 'b']  
>>> # Ещё и кладёт найденные карманы внутрь  
>>>