Незаметные достоинства регулярных выражений в Python
- четверг, 7 января 2016 г. в 02:10:38
http://habrahabr.ru/company/mailru/blog/274349/
В стандартной библиотеке Python есть немало кошмарных модулей, но этого нельзя сказать о модуле re. Несмотря на его преклонный возраст и многолетнее отсутствие обновлений, я считаю этот модуль одним из лучших среди всех динамических языков.
Python — один из немногих динамических языков, в которых отсутствует встроенная поддержка регулярных выражений, но это компенсируется проработанной базовой системой (с точки зрения API). В то же время он весьма причудлив. К примеру, поведение написанного на Python парсера может вас удивить. Если вы попытаетесь в ходе импорта профилировать Python, то, скорее всего, 90% времени вы проведёте в работе с модулем re.
Модуль регулярных выражений в Python был разработан давно и по умолчанию используется в стандартной библиотеке. Если не считать Python 3, то этот модуль никак не развивался с момента своего появления, за исключением внедрения поддержки Unicode. И по сей день в нём некорректно работает перечисление участников (member enumeration) (посмотрите, что возвращает функция dir() у объекта шаблона регулярного выражения).
«Старость» модуля играет ему на руку в том смысле, что он не меняется в зависимости от версии Python и доказал свою надёжность. Мне не раз приходилось что-то переделывать только потому, что вносились изменения в модуль регулярных выражений. А если учесть, сколько этих самых выражений мне приходится писать, неизменность модуля не может не радовать.
Интересная деталь: парсер и компилятор написаны на Python, а матчер — на C. Это означает, что в случае необходимости мы можем передавать внутренние структуры из парсера в компилятор без полного парсинга регулярных выражений. В документации это не описано, но работает.
Есть немало других интересных моментов, связанных с регулярными выражениями, которые не упомянуты или плохо освещены в документации. Так что я приведу здесь несколько примеров, характеризующих с лучшей стороны модуль регулярных выражений в Python.
Несомненно, лучшей особенностью регулярных выражений в Python является чёткое различие между сравнением и поиском. Этим могут похвастаться далеко не все движки. В частности, вы можете использовать индекс для смещения проверки совпадения, но сам объект совпадения останется привязанным к определённой позиции. Например, можно сделать нечто подобное:
Это крайне полезное свойство при создании лексеров. Ведь вы можете использовать символ ^ для обозначения начала всей строки. Нужно просто увеличить индекс для последующего сравнения. Это также означает, что можно обойтись без нарезки самих строк, тем самым экономится куча памяти и не тратятся ресурсы на многократное копирование строк. Хотя нельзя сказать, что в целом по этим критериям Python выделяется в лучшую сторону.
Помимо сравнения, в Python можно осуществлять поиск, то есть пропускать до тех пор, пока не будет обнаружено совпадение:
Важной проблемой является дороговизна обработки ситуации, когда совпадения отсутствуют. Допустим, нам нужно написать токенизатор для wiki-подобного языка, скажем Markdown. Между обозначающими форматирование токенами содержится большое количество текста, который тоже нужно обработать. И когда мы определяем wiki-синтаксис между необходимыми токенами, нам приходится обрабатывать ещё больше токенов. Как нам решить эту проблему?
Один из способов заключается в том, чтобы объединить группу регулярных выражений в один список и прогонять одно за другим. Если совпадений не обнаруживается, то мы пропускаем символ:
Решение не идеальное и не самое быстрое. Чем меньше совпадений, тем ниже производительность, поскольку мы продвигаемся по одному символу за раз, а цикл выполняется в интерпретируемом коде Python. Также этот метод не слишком гибок: для каждого токена у нас есть только совпадающий текст, а если используются группы токенов, то код придётся переработать.
Существует ли какое-то более удобное решение? Что, если бы можно было дать команду движку просканировать на наличие каких-то регулярных выражений на выбор?
Вопрос интересный. В целом именно это мы и делаем, когда пишем регулярки с подшаблонами: (a|b). В этом случае осуществляется поиск либо a, либо b. Так что можно сформировать из всех имеющихся регулярок одну огромную и сравнивать уже с ней. Но обратной стороной такого решения является то, что в конце концов мы обязательно запутаемся со всеми этими группами.
Последние лет 15 в движке регулярных выражений существует один недокументированный инструмент: сканер. Это свойство объекта шаблонов SRE, при котором движок после обнаружения совпадения продолжает искать следующее. Есть даже недокументированный класс re.Scanner, работающий поверх сканера шаблонов SRE, предоставляющего интерфейс несколько более высокого уровня.
К сожалению, сам по себе сканер, находящийся в модуле re, не слишком полезен с точки зрения ускорения работы с «несовпадениями». Но если проанализировать его исходный код, то становится ясно, что сканер реализован поверх примитивов SRE. Работает он следующим образом: берёт список регулярок и соответствующие callback’и. Каждому совпадению он сопоставляет callback с образцом и на основе этого создаёт результирующий список. Под капотом это реализовано с помощью создания SRE-шаблона и объектов подшаблонов. В принципе, он создаёт более крупную регулярку, не осуществляя её парсинг. Вооружившись этими знаниями, что мы можем сделать с данным кодом?
Например, вот что:
Если лексический анализ не удастся, то выскочит ошибка EOFError. Но если указать skip=True, тогда не поддающиеся анализу части будут пропускаться, что облегчает процесс создания таких вещей, как лексические анализаторы wiki-синтаксиса.
Для обозначения участков, которые должны быть пропущены, мы можем использовать match.start() и match.end(). Пример:
Раздражает тот факт, что наши групповые индексы не являются локальными по отношению к нашему собственному регулярному выражению, в отличие от комбинированного. То есть, например, нельзя обратиться с помощью индекса к группе, если есть правило (a|b). Для этого придётся повозиться с классом, выступающим в виде обёртки для SRE-образца, позволяющим настроить индексы и имена групп. Если вас интересуют подробности, то можете изучить вариант реализации подобной обёртки на GitHub’е, наряду с некоторыми примерами использования.
В стандартной библиотеке Python есть немало кошмарных модулей, но этого нельзя сказать о модуле re. Несмотря на его преклонный возраст и многолетнее отсутствие обновлений, я считаю этот модуль одним из лучших среди всех динамических языков.
Python — один из немногих динамических языков, в которых отсутствует встроенная поддержка регулярных выражений, но это компенсируется проработанной базовой системой (с точки зрения API). В то же время он весьма причудлив. К примеру, поведение написанного на Python парсера может вас удивить. Если вы попытаетесь в ходе импорта профилировать Python, то, скорее всего, 90% времени вы проведёте в работе с модулем re.
Старый, но проверенный
Модуль регулярных выражений в Python был разработан давно и по умолчанию используется в стандартной библиотеке. Если не считать Python 3, то этот модуль никак не развивался с момента своего появления, за исключением внедрения поддержки Unicode. И по сей день в нём некорректно работает перечисление участников (member enumeration) (посмотрите, что возвращает функция dir() у объекта шаблона регулярного выражения).
«Старость» модуля играет ему на руку в том смысле, что он не меняется в зависимости от версии Python и доказал свою надёжность. Мне не раз приходилось что-то переделывать только потому, что вносились изменения в модуль регулярных выражений. А если учесть, сколько этих самых выражений мне приходится писать, неизменность модуля не может не радовать.
Интересная деталь: парсер и компилятор написаны на Python, а матчер — на C. Это означает, что в случае необходимости мы можем передавать внутренние структуры из парсера в компилятор без полного парсинга регулярных выражений. В документации это не описано, но работает.
Есть немало других интересных моментов, связанных с регулярными выражениями, которые не упомянуты или плохо освещены в документации. Так что я приведу здесь несколько примеров, характеризующих с лучшей стороны модуль регулярных выражений в Python.
Итеративное сравнение
Несомненно, лучшей особенностью регулярных выражений в Python является чёткое различие между сравнением и поиском. Этим могут похвастаться далеко не все движки. В частности, вы можете использовать индекс для смещения проверки совпадения, но сам объект совпадения останется привязанным к определённой позиции. Например, можно сделать нечто подобное:
>>> pattern = re.compile('bar')
>>> string = 'foobar'
>>> pattern.match(string) is None
True
>>> pattern.match(string, 3)
<_sre.SRE_Match object at 0x103c9a510>
Это крайне полезное свойство при создании лексеров. Ведь вы можете использовать символ ^ для обозначения начала всей строки. Нужно просто увеличить индекс для последующего сравнения. Это также означает, что можно обойтись без нарезки самих строк, тем самым экономится куча памяти и не тратятся ресурсы на многократное копирование строк. Хотя нельзя сказать, что в целом по этим критериям Python выделяется в лучшую сторону.
Помимо сравнения, в Python можно осуществлять поиск, то есть пропускать до тех пор, пока не будет обнаружено совпадение:
>>> pattern = re.compile('bar')
>>> pattern.search('foobar')
<_sre.SRE_Match object at 0x103c9a578>
>>> _.start()
3
Несовпадение — это тоже совпадение
Важной проблемой является дороговизна обработки ситуации, когда совпадения отсутствуют. Допустим, нам нужно написать токенизатор для wiki-подобного языка, скажем Markdown. Между обозначающими форматирование токенами содержится большое количество текста, который тоже нужно обработать. И когда мы определяем wiki-синтаксис между необходимыми токенами, нам приходится обрабатывать ещё больше токенов. Как нам решить эту проблему?
Один из способов заключается в том, чтобы объединить группу регулярных выражений в один список и прогонять одно за другим. Если совпадений не обнаруживается, то мы пропускаем символ:
rules = [
('bold', re.compile(r'\*\*')),
('link', re.compile(r'\[\[(.*?)\]\]')),
]
def tokenize(string):
pos = 0
last_end = 0
while 1:
if pos >= len(string):
break
for tok, rule in rules:
match = rule.match(string, pos)
if match is not None:
start, end = match.span()
if start > last_end:
yield 'text', string[last_end:start]
yield tok, match.group()
last_end = pos = match.end()
break
else:
pos += 1
if last_end < len(string):
yield 'text', string[last_end:]
Решение не идеальное и не самое быстрое. Чем меньше совпадений, тем ниже производительность, поскольку мы продвигаемся по одному символу за раз, а цикл выполняется в интерпретируемом коде Python. Также этот метод не слишком гибок: для каждого токена у нас есть только совпадающий текст, а если используются группы токенов, то код придётся переработать.
Существует ли какое-то более удобное решение? Что, если бы можно было дать команду движку просканировать на наличие каких-то регулярных выражений на выбор?
Вопрос интересный. В целом именно это мы и делаем, когда пишем регулярки с подшаблонами: (a|b). В этом случае осуществляется поиск либо a, либо b. Так что можно сформировать из всех имеющихся регулярок одну огромную и сравнивать уже с ней. Но обратной стороной такого решения является то, что в конце концов мы обязательно запутаемся со всеми этими группами.
Сканер
Последние лет 15 в движке регулярных выражений существует один недокументированный инструмент: сканер. Это свойство объекта шаблонов SRE, при котором движок после обнаружения совпадения продолжает искать следующее. Есть даже недокументированный класс re.Scanner, работающий поверх сканера шаблонов SRE, предоставляющего интерфейс несколько более высокого уровня.
К сожалению, сам по себе сканер, находящийся в модуле re, не слишком полезен с точки зрения ускорения работы с «несовпадениями». Но если проанализировать его исходный код, то становится ясно, что сканер реализован поверх примитивов SRE. Работает он следующим образом: берёт список регулярок и соответствующие callback’и. Каждому совпадению он сопоставляет callback с образцом и на основе этого создаёт результирующий список. Под капотом это реализовано с помощью создания SRE-шаблона и объектов подшаблонов. В принципе, он создаёт более крупную регулярку, не осуществляя её парсинг. Вооружившись этими знаниями, что мы можем сделать с данным кодом?
from sre_parse import Pattern, SubPattern, parse
from sre_compile import compile as sre_compile
from sre_constants import BRANCH, SUBPATTERN
class Scanner(object):
def __init__(self, rules, flags=0):
pattern = Pattern()
pattern.flags = flags
pattern.groups = len(rules) + 1
self.rules = [name for name, _ in rules]
self._scanner = sre_compile(SubPattern(pattern, [
(BRANCH, (None, [SubPattern(pattern, [
(SUBPATTERN, (group, parse(regex, flags, pattern))),
]) for group, (_, regex) in enumerate(rules, 1)]))
])).scanner
def scan(self, string, skip=False):
sc = self._scanner(string)
match = None
for match in iter(sc.search if skip else sc.match, None):
yield self.rules[match.lastindex - 1], match
if not skip and not match or match.end() < len(string):
raise EOFError(match.end())
Например, вот что:
scanner = Scanner([
('whitespace', r'\s+'),
('plus', r'\+'),
('minus', r'\-'),
('mult', r'\*'),
('div', r'/'),
('num', r'\d+'),
('paren_open', r'\('),
('paren_close', r'\)'),
])
for token, match in scanner.scan('(1 + 2) * 3'):
print (token, match.group())
Если лексический анализ не удастся, то выскочит ошибка EOFError. Но если указать skip=True, тогда не поддающиеся анализу части будут пропускаться, что облегчает процесс создания таких вещей, как лексические анализаторы wiki-синтаксиса.
Сканирование с промежутками
Для обозначения участков, которые должны быть пропущены, мы можем использовать match.start() и match.end(). Пример:
scanner = Scanner([
('bold', r'\*\*'),
('link', r'\[\[(.*?)\]\]'),
])
def tokenize(string):
pos = 0
for rule, match in self.scan(string, skip=True):
hole = string[pos:match.start()]
if hole:
yield 'text', hole
yield rule, match.group()
pos = match.end()
hole = string[pos:]
if hole:
yield 'text', hole
Исправление групп
Раздражает тот факт, что наши групповые индексы не являются локальными по отношению к нашему собственному регулярному выражению, в отличие от комбинированного. То есть, например, нельзя обратиться с помощью индекса к группе, если есть правило (a|b). Для этого придётся повозиться с классом, выступающим в виде обёртки для SRE-образца, позволяющим настроить индексы и имена групп. Если вас интересуют подробности, то можете изучить вариант реализации подобной обёртки на GitHub’е, наряду с некоторыми примерами использования.