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

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)

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

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

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

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'овский
                                  # формат строк на питоновский, ну да ладно

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

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. Они отправляют в небытие все пробельные символы между токенами. (Не делайте так, если пишете парсер Питона!)

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

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
    # да что ж такое. ну тогда попытайся расп...
    # ...

Давайте поменяем три функции выше самым неожиданным образом: заменим 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)

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

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

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, то парсинг массива не удался

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 = 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_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

>>> 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}

Заключение

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

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

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

Комментарии (1)

• bak

  6 сентября 2016 в 00:17

  0

  ↑

  ↓

  Судя по первому абзацу думал что будет парсинг питона с поддержкой
  

  if foo = make_foo():
    # do work with foo