DISCLAIMER

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

TLDR

Статья предлагает взглянуть на опыт разработки парсер комбинаторов для Python, что вылилось в библиотеку PGPC для разработки парсеров на Python. Библиотека была вдохновлена Parsec.

Особый интерес представляет эмуляция do-нотации через Python генераторы, отсюда и название библиотеки: Python Generator based Parser Combinator library.

Пример использования библиотеки для разбора фразы "Hello, World!":

@topology
def parse_word(word: str):
  parsed = []
  for c in word:
    letter = yield char(c)
    parsed.append(letter)

  return parsed

text = "Hello, World!"
parser = parse_word(text)
print(parser(Scanner(text, Position())))

Мотивация

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

• лексера - программа, которая разбивает поток на токены или лексемы;

• парсера - программа, которая пытается сформировать какую-нибудь конструкцию языка на базе входной последовательности лексем.

Указанный подход подробно расписан в книге с драконом "Компиляторы. Принципы, подходы и инструментарий." за авторством А.В. Ахо, М.С. Лам, Р. Сети, Д.Д. Ульман.

С другой стороны, на парсер можно посмотреть как на функцию, которая:

• входной строке ставит в соответствие некий объект,

• возвращает остаток строки, который не был разобран:

Для Haskell тип парсера выглядит следующим образом: String -> (T, String).

На основании идеи, что парсер - это функция, а функции принято объединять в композиции, появились парсер комбинаторы. Смысл в том, чтобы из небольших парсеров, строить более сложные при помощи композиции парсеров.

Парсер комбинаторы

Парсер комбинаторы - это мощный и гибкий подход к разбору текста, который имеет свои преимущества перед классическими подходами:

• выразительный и читабельный код: парсер комбинаторы позволяют составлять парсеры через комбинацию простых парсеров, в результате получается код, который близок к BNF форме (форма Бэкуса-Наура);

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

• потоковый разбор: парсер комбинаторы могут работать в условиях, когда входная последовательность формируется в реальном времени;

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

• быстрое прототипирование: парсер комбинаторы отлично подходят для прототипов, что позволяет быстро начать работу над парсером без необходимости сложной настройки рабочего пространства;

• тестирование: каждый парсер состоит из более простых парсеров, а значит каждый парсер можно легко протестировать.

Парсер комбинаторы предлагают гибкий и интуитивный подход, который облегчает разработку парсеров и повышает читаемость кода. Они наиболее удобны для работы над DSL языками и различными форматами данных.

Разработка

Разработка парсер генераторов будет осуществляться на Python с активным использованием Type Hints.

Основные абстракции

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

Основными абстракциями являются:

• Position - текущее положение парсера во входной последовательности;

• Scanner - класс, параметризованный типом элемента входной последовательности, для абстракции входной последовательностью;

• Parser - класс, параметризованный типом разбираемого объекта, представляющий непосредственно парсер. Для использования объектов Parser в контексте функций, в классе переопределен __call__ метод.

Position

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

class Position:
    def __init__(self, offset: int = 0):
        self.__offset = offset

    def increase(self, offset: int):
        self.__offset += offset

Scanner

Класс Scanner, параметризованный типом элемента входной последовательности, позволяет абстрагировать входную последовательность. Стандартный интерфейс класса включает в себя методы:

• mark - запомнить текущую позицию, чтобы вернуться к ней позже;

• reset - вернуться к последней запомненной позиции;

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

class Scanner(Generic[ELEMENT]):
    def __init__(self, content: Sequence[ELEMENT], pos: Position):
        self.__pos: Position = pos
        self.__content: Sequence[ELEMENT] = content
        self.__marks: List[Position] = []

    def mark(self) -> None:
        self.__marks.append(self.__pos)

    def reset(self) -> None:
        if self.__marks:
            self.__pos = self.__marks.pop()

    @property
    def current(self) -> ELEMENT:
        if self.__pos.offset >= len(self.content):
            raise EOFError(f"No value at {self.__pos.offset}")
        result = self.content[self.pos.offset]
        return result

    def advance_if(self, predicate: Callable[[ELEMENT], bool]) -> ELEMENT | None:
        element = self.current
        if predicate(element):
            self.__pos.increase(1)
            return element
        else:
            return None

Parser

Класс Parser, параметризованный типом объекта после разбора, позволяет абстрагировать логику разбора. Парсер должен использоваться в контексте функций, а поэтому в нем переопределен __call__ метод, который принимает Scanner и возвращает объект указанного типа.

Примеры типов парсеров:

• Parser[datetime.date] - парсер, который умеет извлечь дату из входной последовательности;

• Parser[int] - парсер, который умеет извлечь число из входной последовательности.

При создании объекта Parser[V] в конструктор передается функция Callable[[Scanner], V], которая будет использоваться для извлечения данных из входной строки.

Стандартный интерфейс парсера включает в себя метод and_then, который позволяет склеить два парсера в один. На вход метод and_then принимает функцию consumer типа Callable[[V], Parser[U]] и реализует следующую логику:

• объект Scanner передается на вход текущему парсеру (self.__parser), который возвращает объект типа V;

• результирующий объект типа V текущего парсера попадает на вход функции consumer;

• функция consumer возвращает новый парсер, который является результатом метода and_then.

def and_then(self, consumer: Callable[[V], Parser[U]]) -> Parser[U]:
    def __with_scanner(scanner: Scanner) -> U:
        v = self.__parser(scanner)
        return consumer(v)(scanner)

    return Parser(__with_scanner)

Метод and_then называется монадическим связывателем в функциональных языках программирования, а в Haskell и Idris на его основе строится do-нотация, которая позволяет записывать функциональный код с коллбэками в виде "плоского" кода, напоминающим императивный код.

Обработка ошибок

Если входная последовательность не может быть разобрана парсером, то генерируется Parser.ParserError исключение, которое можно обрабатывать стандартными средствами Python.

Примитивные парсеры

Парсер satisfy

Парсер satisfy является основным примитивом, на базе которого строятся остальные парсеры. На вход он принимает предикат: Callable[[str], bool], а на выходе получается парсер Parser[str].

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

def satisfy(predicate: Callable[[str], bool]) -> Parser[str]:
    def __with_scanner(scanner: Scanner) -> str:
        result = scanner.advance_if(predicate)
        if not result:
            raise Parser.ParserError(f"Unexpected '{scanner.current}' at {scanner.pos}")
        return result

    return Parser(__with_scanner)

Парсер char

Парсер char принимает на вход символ и проверяет равен ли текущий элемент входной последовательности полученному символу.

def char(c: str) -> Parser[str]:
    return satisfy(lambda x: c == x)

Парсер ws

Парсер ws проверяет, является ли текущий символ пробельным.

def ws() -> Parser[str]:
    return satisfy(lambda x: x.isspace())

Парсер opt

Парсер opt является парсером, который принимает на вход парсер и возвращает парсер. Особенность заключается в том, что, если переданному парсеру не удалось разобрать входную последовательность, то это не является ошибкой. Этот парсер используется для разбора опциональных данных, которые могут отсутствовать во входной последовательности.

def opt(parser: Parser[V]) -> Parser[V | None]:
    def __with_scanner(scanner: Scanner) -> V | None:
        try:
            scanner.mark()
            return parser(scanner)
        except ValueError:
            scanner.reset()
            return None

    return Parser(__with_scanner)

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

Парсер many

Парсер many является парсером, который принимает на вход парсер и возвращает парсер. Особенность заключается в том, что переданный парсер применяется к входной последовательности до тех пор, пока не встретится ошибка. Результатом парсера является список из удачно разобранных объектов.

def many(parser: Parser[V]) -> Parser[List[V]]:
    def __with_scanner(scanner: Scanner) -> List[V]:
        result = []
        try:
            while True:
                element = parser(scanner)
                result.append(element)
        except ValueError:
            return result

    return Parser(__with_scanner)

Парсер alt

Парсер alt является парсером, который пытается применить к входной последовательности два парсера по очереди и возвращает результат первого удачного парсера. Парсер реализован в виде метода alt класса Parser:

class Parser(Generic[V]):

    ...

    def alt(self, parser: 'Parser[U]') -> 'Parser[V | U]':
        def __with_scanner(scanner: Scanner) -> V:
            try:
                scanner.mark()
                return self.__parser(scanner)
            except ValueError:
                scanner.reset()
                return parser(scanner)

        return Parser(__with_scanner)

Пример использования парсеров

Задача

Разработать парсер номеров телефонов. Требования к формату номеров телефонов:

1. начинается на 79 или 89,

2. в начале может опционально присутствовать +,

3. код (912, 964, и т.д) может быть внутри скобок,

4. между цифровыми группами могут быть дефисы,

5. пробелы отсутствуют.

Решение

Решение будет реализовано с учетом следующих идей:

• метод and_then позволяет "склеивать" парсеры в один большой парсер: применить первый парсер, за ним второй, третий и т.д.;

• метод and_then принимает лямбда функцию, которая первым аргументом принимает результат предыдущего парсера;

• результатом лямбда функции будет так же парсер, но у этого нового парсера так же можно вызывать метод and_then;

• продолжать вызов and_then можно неограниченно много раз;

• благодаря замыканию самый последний вызов and_then будет иметь доступ ко всем результатам предыдущих парсеров.

Приятный бонус в том, что обработка ошибок происходит внутри самих парсер комбинаторов, что ведет к более или менее чистому коду бизнес-логики.

def phone_number(phone_number: str) -> str:
    phone_parser: Parser[List[str]] = opt(char('+')) \
      .and_then(lambda _plus: char('7').alt('8')
      .and_then(lambda _seven_or_eight: opt(char('('))
      .and_then(lambda _: char('9')
      .and_then(lambda _nine: digit()
      .and_then(lambda code1: digit()
      .and_then(lambda code2: opt(char(')'))
      .and_then(lambda _: digit()
      .and_then(lambda d1: digit()
      .and_then(lambda d2: digit()
      .and_then(lambda d3: opt(char('-'))
      .and_then(lambda _: digit()
      .and_then(lambda d4: digit()
      .and_then(lambda d5: opt(char('-'))
      .and_then(lambda _: digit()
      .and_then(lambda d6: digit()
      .map(lambda d7: ['+', '7', '(', '9', code1, code2, ')', d1, d2, d3, '-', d4, d5, '-', d6, d7])
      )))))))))))))))

    result = phone_parser(Scanner(phone_number, Position()))
    return "".join(result)

print(phone_number("+7(964)111-11-11"))
print(phone_number("8964222-2222"))
print(phone_number("7(964)333-3333"))

Генераторы

Идея

Код из примера выше, хотя и решает поставленную задачу, имеет много синтаксического шума связанного с особенностями вызова and_then. В функциональных языках программирования метод and_then называется монадическим связывателем (monadic bind), и, например, в Haskell или Idris для него реализована do-нотация, которая позволяет превратить код с большим числом коллбэков в плоский код, похожий по форме на императивный.

В Python отсутствует понятие монадического связывателя, а также нет do-нотации, но зато есть генераторы. Генераторы предлагают двустороннее общение между клиентом и генератором посредством send метода:

• результат вызова send - это значение переданное в yield внутри генератора,

• входное значение send передается внутрь генератора и является результатом yield.

Таким образом, можно реализовать работу с парсерами через yield:

• передаваемое значение - парсер,

• возвращаемое значение - результат разбора парсера.

Реализация

Для удобства клиента функции, которые будут строить парсеры на базе генераторов, будут обернуты декоратором @topology.

Декоратор реализует обертку вокруг парсера, в которой:

• вызывается оригинальная функция парсера для получения объекта генератора,

• для запуска генератора вызывается функция next, которая вернет первый переданный в yield парсер,

• в парсер передается текущий объект Scanner, а на выходе получается результат разбора парсера,

• в бесконечном цикле в генератор передается результат разбора предыдущего парсера,

• исключение StopIteration появляется, когда в оригинальной функции вызывается return,

• результат оригинальной функции лежит в поле value исключения StopIteration,

• значение из поля value исключения StopIteration будет результатом итогового парсера.

def topology(parser_builder) -> Callable[..., Parser[V]]:
    def wrapper(*args: Any, **kwargs: Any) -> Parser[V]:
        gen = parser_builder(*args, **kwargs)

        def __with_scanner(scanner: Scanner) -> V:
            parser = next(gen)
            try:
                while True:
                    result = parser(scanner)
                    parser = gen.send(result)
            except StopIteration as e:
                return e.value

        return Parser(__with_scanner)

    return wrapper

Недостатком декоратора является тот факт, что тип возвращаемого значения поменяется с Generator[Any, Parser[Any], V] на Parser[V], что может привести к ложным срабатываниям mypy.

Пример

Реализовать задание с номерами телефонов из предыдущего раздела при помощи @topology декоратора можно следующим образом:

@topology
def phone_number_gen():
    yield opt(char('+'))

    yield char('7').alt(char('8'))

    yield opt(char('('))
    yield char('9')
    code1 = yield digit()
    code2 = yield digit()
    yield opt(char(')'))

    d1 = yield digit()
    d2 = yield digit()
    d3 = yield digit()

    yield opt(char('-'))

    d4 = yield digit()
    d5 = yield digit()

    yield opt(char('-'))

    d6 = yield digit()
    d7 = yield digit()

    return "".join(['+', '7', '(', '9', code1, code2, ')', d1, d2, d3, '-', d4, d5, '-', d6, d7])

def phone_number_gen_parser(phone_number: str) -> str:
    parser: Parser[str] = phone_number_gen()
    return parser(Scanner(phone_number, Position()))

print(phone_number_gen_parser("+7(964)111-11-11"))
print(phone_number_gen_parser("8964222-2222"))
print(phone_number_gen_parser("7(964)333-3333"))

Обращение к текущей позиции

Во время разбора может появиться необходимость обратиться к текущей позиции. Текущая позиция хранится в объекте Scanner, а доступ к объекту Scanner выполняется во время разбора. Значит получение текущей позиции можно также сделать объектом типа Parser[Position], другими словами получение позиции - это парсер:

def position() -> Parser[Position]:
    def __with_scanner(scanner: Scanner) -> Position:
        return copy(scanner.pos)

    return Parser(__with_scanner)

Пример

Использовать парсер position() можно так же как и любой другой парсер: через and_then или @topology.

Пример ниже запоминает текущую позицию в начале процесса парсера и в конце, и оба эти значения в итоге возвращаются клиенту.

@topology
def parse_text(text: str):
    start = yield position()
    
    for c in text:
        yield char(c)
    
    end = yield position()
    return start.offset, end.offset

value = "Hello, World!"
parser_hello_world = parse_text(value)
print(parser_hello_world(Scanner(value, Position())))

Заключение

В статье был продемонстрирован подход к реализации парсер комбинаторов на базе возможностей языка Python, который является достаточно выразительным для разработки парсер комбинаторов. В сочетании с генераторами можно достичь высокой степени абстракции, сохраняя при этом читаемость кода. Опыт разработки парсер комбинаторов привел к созданию библиотеки PGPC - Python Generator based Parser Combinator library. Библиотека только в самом начале своего развития, и в ней отсутствует большая часть традиционных парсер комбинаторов, поэтому приветствуется добавление новых парсеров от сторонних разработчиков. В качестве вдохновения можно посмотреть на библиотеку Parsec.

Источники

1. https://stepik.org/lesson/42245/step/1 - глава, посвященная парсерам в курсе по Haskell от Д.Н. Москвина

2. https://github.com/haskell/parsec - библиотека парсер комбинаторов Parsec