python

Незаметные достоинства регулярных выражений в Python

  • четверг, 7 января 2016 г. в 02:10:38
http://habrahabr.ru/company/mailru/blog/274349/

image

В стандартной библиотеке 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’е, наряду с некоторыми примерами использования.