Пишем изящный парсер на Питоне

В C++17 появляется новый синтаксис для оператора if, позволяющий объявлять переменные прямо в заголовке блока. Это довольно удобно, поскольку конструкции вида…

Foo* foo = make_foo();
if(foo != nullptr) {
    // do work with foo
}
// never use foo again

… довольно общеупотребительны. Код выше лёгким движением руки программиста (и тяжёлым движением руки комитета по стандартизации) превращается в:

if(Foo* foo = make_foo(); foo != nullptr) {
    // do work with foo
}
// never use foo again (well, you can't anyway)

Стало чуть-чуть лучше, хотя всё ещё не выглядит идеально. В Python нет и такого, но если вы ненавидите if в Python-коде так же сильно, как я, и хотите научиться быстро писать простые парсеры, то добро пожаловать под кат. В этой статье мы попытаемся написать короткий и изящный парсер для JSON на Python 2 (без каких-либо дополнительных модулей, конечно же).

Что такое парсинг и с чем его едят

Парсинг (по-русски «синтаксический анализ») — это бессмертная задача разобрать и преобразовать в осмысленные единицы нечто, написанное на некотором фиксированном языке, будь то язык программирования, язык разметки, язык структурированных запросов или главный язык жизни, Вселенной и всего такого. Типичная последовательность этапов решения задачи выглядит примерно так:

1. Описать язык. Конечно, сначала надо определиться, какую именно задачу мы решаем. Обычно описание языка — это очередная вариация формы Бэкуса-Наура. (Вот, например, описание грамматики Python, использующееся при построении его парсера.) При этом устанавливаются как правила «построения предложений» в языке, так и правила определения валидных слов.
2. Разбить ввод на токены. Пишется лексический анализатор (в народе токенайзер), который разбивает входную строку или файл на последовательность токенов, то есть валидных слов нашего языка (или ноет, что это нельзя сделать).
3. Проверить синтаксис и построить синтаксическое дерево. Проверяем, соответствует ли последовательность токенов описанию нашего языка. Здесь в ход идут алгоритмы вроде метода рекурсивного спуска. Каждое валидное предложение языка включает какое-то конечное количество валидных слов или других валидных предложений; если токены смогли сложиться в стройную картину, то на выходе мы автоматически получаем дерево, которое и называется абстрактным синтаксическим деревом.
4. Сделать, наконец, работу. У вас есть синтаксическое дерево и вы можете наконец сделать то, что хотели: посчитать значение арифметического выражения, организовать запрос в БД, скомпилировать программу, отобразить веб-страницу и так далее.

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

Модельная задача

Написание парсера проиллюстрируем на простом, но не до конца тривиальном примере — парсинге JSON. Грамматика выглядит примерно так:

root ::= value
value ::= string | number | object | array | 'true' | 'false' | 'null'

array ::= '[' ']' | '[' comma-separated-values ']'
comma-separated-values ::= value | value, comma-separated-values

object ::= '{' '}' | '{' comma-separated-keyvalues '}'
comma-separated-keyvalues ::= keyvalue | keyvalue, comma-separated-keyvalues
keyvalue ::= string ':' value

Здесь нет правил для string и number — они, вместе со всеми строками в кавычках, будут нашими токенами.

Парсим JSON

Полноценный токенайзер мы писать не станем (это скучно и не совсем тема статьи) — будем работать с целой строкой и бить её на токены по мере необходимости. Напишем две первые функции:

import re

# без re.DOTALL мы сломаемся на первом же переносе строки
number_regex = re.compile(r"(-?(?:0|[1-9]d*)(?:.d+)?(?:[eE][+-]?d+)?)s*(.*)", re.DOTALL)
def parse_number(src):
    match = number_regex.match(src)
    if match is not None:
        number, src = match.groups()
        return eval(number), src  # использовать eval - не лучшее решение, но самое простое

string_regex = re.compile(r"('(?:[^\']|\['\/bfnrt]|\u[0-9a-fA-F]{4})*?')s*(.*)", re.DOTALL)
def parse_string(src):
    match = string_regex.match(src)
    if match is not None:
        string, src = match.groups()
        return eval(string), src  # здесь мы вообще подменили JSON'овский
                                  # формат строк на питоновский, ну да ладно

(Я обещал без if'ов, но это последние, чесслово!)

Для всего остального напишем одну функцию, генерящую простенькие функции-парсеры:

def parse_word(word, value=None):
    l = len(word)
    def result(src):
        # добавьте в следующую строчку вызовы .lower() для case-insensitive языка!
        if src.startswith(word):  # опять if! вот живучая тварь!
            return value, src[l:].lstrip()  # lstrip нужен для игнорирования пробелов, см. ниже
    result.__name__ = "parse_%s" % word  # для отладки
    return result

parse_true = parse_word("true", True)
parse_false = parse_word("false", False)
parse_null = parse_word("null", None)

Итого, по какому принципу мы строим наши функции:

1. Они принимают строку, которую нужно парсить.
2. Они возвращают пару (результат, оставшаяся_строка) при успехе (то есть когда требуемая конструкция нашлась в начале строки) и None при провале.
3. Они отправляют в небытие все пробельные символы между токенами. (Не делайте так, если пишете парсер Питона!)

Собственно, на этих трёх функциях проблемы с токенами решены, и мы можем перейти к интересной части.

Парсим правило с ветвлением

Как должна выглядеть функция parse_value, соответствующая грамматике выше? Обычно как-то так:

def parse_value(src):
    # попытайся распарсить строковый литерал
    match = parse_string(src)
    if match is not None:
        # получилось!
        return match
    # не получилось; ну тогда попытайся распарсить число
    match = parse_number(src)
    if match is not None:
        return match
    # да что ж такое. ну тогда попытайся расп...
    # ...

Ну уж нет, эти if достали меня!

Давайте поменяем три функции выше самым неожиданным образом: заменим return на yield! Теперь они возвращают генераторы — пустые, если парсинг не удался, и ровно с одним элементом, если удался. Да-да, мы разворачиваем на 90 градусов наш принцип номер 2: все наши функции мы будем теперь писать в таком стиле:

number_regex = re.compile(r"(-?(?:0|[1-9]d*)(?:.d+)?(?:[eE][+-]?d+)?)s*(.*)", re.DOTALL)

def parse_number(src):
    match = number_regex.match(src)
    if match is not None:
        number, src = match.groups()
        yield eval(number), src
    # если управление дошло до сюда без yield, числа обнаружить не удалось.
    # ну что же, пустой генератор тоже генератор.

string_regex = re.compile(r"('(?:[^\']|\['\/bfnrt]|\u[0-9a-fA-F]{4})*?')s*(.*)", re.DOTALL)

def parse_string(src):
    match = string_regex.match(src)
    if match is not None:
        string, src = match.groups()
        yield eval(string), src

def parse_word(word, value=None):
    l = len(word)
    def result(src):
        if src.startswith(word):
            yield value, src[l:].rstrip()
    result.__name__ = "parse_%s" % word
    return result  # здесь возвращаем функцию-парсер, не yield'им

parse_true = parse_word("true", True)
parse_false = parse_word("false", False)
parse_null = parse_word("null", None)

Во что же превратится наша parse_value? На первый взгляд во что-то такое:

def parse_value(src):
    for match in parse_string(src):
        yield match
        return
    for match in parse_number(src):
        yield match
        return
    # ...

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

# весьма полезная itertools.cycle объединяет переданные ей итераторы
# в цепочку, не трогая ни один раньше времени
from itertools import chain

def parse_value(src):
    for match in chain(
        parse_string(src),
        parse_number(src),
        parse_array(src),
        parse_object(src),
        parse_true(src),
        parse_false(src),
        parse_null(src),
    ):  # закрывающей скобке грустно, но веселье только начинается
        yield match
        return

При этом эффективность остаётся на прежнем уровне — каждая функция начнёт выполняться (а стало быть, делать работу, проверяя регулярные выражения) только тогда, когда предыдущая не даст результата. return гарантирует, что лишняя работа не будет выполнена, если где-то в середине списка парсинг удался.

Парсим последовательности конструкций

Перейдём к следующему номеру нашей программы — функции parse_array. Выглядеть она должна как-то так:

parse_left_square_bracket = parse_word("[")
parse_right_square_bracket = parse_word("]")

def parse_array(src):
    # здесь потребуется временная переменная tsrc, иначе даже при неудачном
    # парсинге пустого массива открывающая скобка может быть "съедена"
    for _, tsrc in parse_left_square_bracket(src):
        for _, tsrc in parse_right_square_bracket(tsrc):
            # если мы здесь, то нам удалось последовательно распарсить '[' и ']'
            yield [], tsrc
            return
    # здесь переменную src уже не жалко -- за этим циклом только боль и пустота
    for _, src in parse_left_square_bracket(src):
        for items, src in parse_comma_separated_values(src):
            for _, src in parse_right_square_bracket(src):
                yield items, src
    # если управление дошло сюда без yield, то парсинг массива не удался

Ни одного if, как и обещано, но что-то всё равно не так… Давайте напишем небольшую вспомогательную функцию, которая поможет нам соединять функции-парсеры в последовательности подобно тому, как cycle помогла соединять их в режиме «или». Эта функция должна будет аккуратно брать все результаты и вернуть все первые элементы результатов (результаты анализа) и последний второй элемент (оставшуюся непроанализированной часть строки). Мой вариант выглядит так:

def sequence(*funcs):
    if len(funcs) == 0:  # ну простите, не могу в рекурсию без if'а
        def result(src):
            yield (), src
        return result
    def result(src):
        for arg1, src in funcs[0](src):
            for others, src in sequence(*funcs[1:])(src):
                yield (arg1,) + others, src  # конкатенируем содержательные результаты
    return result

С этим мощным (пусть и страшноватым) инструментом наша функция перепишется в виде:

parse_left_square_bracket = parse_word("[")
parse_right_square_bracket = parse_word("]")
parse_empty_array = sequence(parse_left_square_bracket, parse_right_square_bracket)

def parse_array(src):
    for _, src in parse_empty_array(src):  # увы, эта функция недостаточно умна, чтобы вернуть []
        yield [], src
        return  # этот return нужен, чтобы не пойти радостно парсить
                # дальше в конструкции вида {} {"a": 1}

    for (_, items, _), src in sequence(
        parse_left_square_bracket,
        parse_comma_separated_values,
        parse_right_square_bracket,
    )(src):
        yield items, src
    # если управление дошло сюда без yield, то парсинг массива не удался

Ну а дописать функцию parse_comma_separated_values — раз плюнуть:

parse_comma = parse_word(",")

def parse_comma_separated_values(src):
    for (value, _, values), src in sequence(
        parse_value,
        parse_comma,
        parse_comma_separated_values  # я говорил, что не могу в рекурсию без if? я соврал
    )(src):
        yield [value] + values, src
        return

    for value, src in parse_value(src):
        yield [value], src

Приведёт ли такое решение к бесконечной рекурсии? Нет! Однажды функция parse_comma не найдёт очередной запятой, и до последующей parse_comma_separated_values выполнение уже не дойдёт.

Идём дальше! Объект:

parse_left_curly_bracket = parse_word("{")
parse_right_curly_bracket = parse_word("}")
parse_empty_object = sequence(parse_left_curly_bracket, parse_right_curly_bracket)

def parse_object(src):
    for _, src in parse_empty_object(src):
        yield {}, src
        return
    for (_, items, _), src in sequence(
        parse_left_curly_bracket,
        parse_comma_separated_keyvalues,
        parse_right_curly_bracket,
    )(src):
        yield items, src

parse_colon = parse_word(":")

def parse_keyvalue(src):
    for (key, _, value), src in sequence(
        parse_string,
        parse_colon,
        parse_value
    )(src):
        yield {key: value}, src

def parse_comma_separated_keyvalues(src):
    for (keyvalue, _, keyvalues), src in sequence(
        parse_keyvalue,
        parse_comma,
        parse_comma_separated_keyvalues, # тут снова рекурсия, не проглядите
    )(src):
        keyvalue.update(keyvalues)
        yield keyvalue, src
        return
        
    for keyvalue, src in parse_keyvalue(src):
        # к сожалению, питон не умеет в генераторе возвращать другой генератор
        yield keyvalue, src

Ну, что там дальше?

Собственно, всё! Остаётся добавить простую интерфейсную функцию:

def parse(s):
    s = s.strip()  # наш токенайзер убивает пробелы после токенов, но не терпит до
    match = list(parse_value(s))
    if len(match) != 1:
        # где-то что-то пошло не так. про отладку расскажу в другой раз :)
        raise ValueError("not a valid JSON string")
    result, src = match[0]
    if src.strip():
        # мы распарсили, но в строке ещё что-то осталось. это ошибка.
        raise ValueError("not a valid JSON string")
    return result

Вуаля!

from itertools import chain
import re

def sequence(*funcs):
    if len(funcs) == 0:
        def result(src):
            yield (), src
        return result
    def result(src):
        for arg1, src in funcs[0](src):
            for others, src in sequence(*funcs[1:])(src):
                yield (arg1,) + others, src
    return result

number_regex = re.compile(r"(-?(?:0|[1-9]d*)(?:.d+)?(?:[eE][+-]?d+)?)s*(.*)", re.DOTALL)

def parse_number(src):
    match = number_regex.match(src)
    if match is not None:
        number, src = match.groups()
        yield eval(number), src

string_regex = re.compile(r"('(?:[^\']|\['\/bfnrt]|\u[0-9a-fA-F]{4})*?')s*(.*)", re.DOTALL)

def parse_string(src):
    match = string_regex.match(src)
    if match is not None:
        string, src = match.groups()
        yield eval(string), src

def parse_word(word, value=None):
    l = len(word)
    def result(src):
        if src.startswith(word):
            yield value, src[l:].lstrip()
    result.__name__ = "parse_%s" % word
    return result

parse_true = parse_word("true", True)
parse_false = parse_word("false", False)
parse_null = parse_word("null", None)

def parse_value(src):
    for match in chain(
        parse_string(src),
        parse_number(src),
        parse_array(src),
        parse_object(src),
        parse_true(src),
        parse_false(src),
        parse_null(src),
    ):
        yield match
        return

parse_left_square_bracket = parse_word("[")
parse_right_square_bracket = parse_word("]")
parse_empty_array = sequence(parse_left_square_bracket, parse_right_square_bracket)

def parse_array(src):
    for _, src in parse_empty_array(src):
        yield [], src
        return

    for (_, items, _), src in sequence(
        parse_left_square_bracket,
        parse_comma_separated_values,
        parse_right_square_bracket,
    )(src):
        yield items, src

parse_comma = parse_word(",")

def parse_comma_separated_values(src):
    for (value, _, values), src in sequence(
        parse_value,
        parse_comma,
        parse_comma_separated_values
    )(src):
        yield [value] + values, src
        return

    for value, src in parse_value(src):
        yield [value], src

parse_left_curly_bracket = parse_word("{")
parse_right_curly_bracket = parse_word("}")
parse_empty_object = sequence(parse_left_curly_bracket, parse_right_curly_bracket)

def parse_object(src):
    for _, src in parse_empty_object(src):
        yield {}, src
        return
    for (_, items, _), src in sequence(
        parse_left_curly_bracket,
        parse_comma_separated_keyvalues,
        parse_right_curly_bracket,
    )(src):
        yield items, src

parse_colon = parse_word(":")

def parse_keyvalue(src):
    for (key, _, value), src in sequence(
        parse_string,
        parse_colon,
        parse_value
    )(src):
        yield {key: value}, src

def parse_comma_separated_keyvalues(src):
    for (keyvalue, _, keyvalues), src in sequence(
        parse_keyvalue,
        parse_comma,
        parse_comma_separated_keyvalues,
    )(src):
        keyvalue.update(keyvalues)
        yield keyvalue, src
        return

    for keyvalue, src in parse_keyvalue(src):
        yield keyvalue, src

def parse(s):
    s = s.strip()
    match = list(parse_value(s))
    if len(match) != 1:
        raise ValueError("not a valid JSON string")
    result, src = match[0]
    if src.strip():
        raise ValueError("not a valid JSON string")
    return result

130 строк. Попробуем запустить:

>>> import my_json
>>> my_json.parse("null")
>>> my_json.parse("true")
True
>>> my_json.parse("false")
False
>>> my_json.parse("0.31415926E1")
3.1415926
>>> my_json.parse("[1, true, '1']")
[1, True, '1']
>>> my_json.parse("{}")
{}
>>> my_json.parse("{'a': 1, 'b': null}")
{'a': 1, 'b': None}

Успех!

Заключение

Конечно, я рассмотрел далеко не все ситуации, которые могут возникнуть при написании парсеров. Иногда программисту может потребоваться ручное управление выполнением, а не запуск последовательности chainов и sequenceов. К счастью, это не так неудобно в рассмотренном подходе, как может показаться. Так, если нужно попытаться распарсить необязательную конструкцию и сделать действие в зависимости от её наличия, можно написать:

for stuff, src in parse_optional_stuff(src):
    # опциональная конструкция на месте -- работаем
    break # предотвращает выполнение else
else:
    # опциональная конструкция отсутствует -- грустим
    pass

Здесь мы пользуемся малопопулярной фишкой Питона — блоком else у циклов, который выполняется, если цикл дошёл до конца без break. Это выглядит не так привлекательно, как наш код в статье, но точно не хуже, чем те if, от которых мы столь изящно избавились.

Несмотря на неполноту и неакадемичность изложения, я надеюсь, что эта статья будет полезна начинающим программистам, а может, даже удивит новизной подхода программистов продвинутых. При этом я прекрасно отдаю себе отчёт, что это просто новая форма для старого доброго рекурсивного спуска; но если программирование — это искусство, разве не важна в нём форма если не наравне, то хотя бы в степени, близкой к содержанию?..

Как обычно, не откладывая пишите в личку обо всех обнаруженных неточностях, орфографических, грамматических и фактических ошибках — иначе я сгорю от стыда!

Автор: saluev

Источник