В C++17 (нет-нет, Питон скоро будет, вы правильно зашли!) появляется новый синтаксис для оператора if, позволяющий объявлять переменные прямо в заголовке блока. Это довольно удобно, поскольку конструкции вида
Foo foo = make_foo();
if(foo.is_nice()) {
// do work with foo
}
// never use foo again
// foo gets deleted
довольно общеупотребительны. Код выше лёгким движением руки программиста (и тяжёлым движением руки комитета по стандартизации) превращается в:
if(Foo foo = make_foo(); foo.is_nice()) {
// do work with foo
} // foo gets deleted
// never use foo again (well, you can't anyway)
Стало чуть-чуть лучше, хотя всё ещё не выглядит идеально. В Python нет и такого, но если вы ненавидите if в Python-коде так же сильно, как я, и хотите научиться быстро писать простые парсеры, то добро пожаловать под кат. В этой статье мы попытаемся написать короткий и изящный парсер для JSON на Python 2 (без каких-либо дополнительных модулей, конечно же).
Что такое парсинг и с чем его едят
Парсинг (по-русски «синтаксический анализ») — это бессмертная задача разобрать и преобразовать в осмысленные единицы нечто, написанное на некотором фиксированном языке, будь то язык программирования, язык разметки, язык структурированных запросов или главный язык жизни, Вселенной и всего такого. Типичная последовательность этапов решения задачи выглядит примерно так:
Описать язык. Конечно, сначала надо определиться, какую именно задачу мы решаем. Обычно описание языка — это очередная вариация формы Бэкуса-Наура. (Вот, например, описание грамматики Python, использующееся при построении его парсера.) При этом устанавливаются как правила «построения предложений» в языке, так и правила определения валидных слов.
Разбить ввод на токены. Пишется лексический анализатор (в народе токенайзер), который разбивает входную строку или файл на последовательность токенов, то есть валидных слов нашего языка (или ноет, что это нельзя сделать).
Проверить синтаксис и построить синтаксическое дерево. Проверяем, соответствует ли последовательность токенов описанию нашего языка. Здесь в ход идут алгоритмы вроде метода рекурсивного спуска. Каждое валидное предложение языка включает какое-то конечное количество валидных слов или других валидных предложений; если токены смогли сложиться в стройную картину, то на выходе мы автоматически получаем дерево, которое и называется абстрактным синтаксическим деревом.
Сделать, наконец, работу. У вас есть синтаксическое дерево и вы можете наконец сделать то, что хотели: посчитать значение арифметического выражения, организовать запрос в БД, скомпилировать программу, отобразить веб-страницу и так далее.
Вообще область эта изучена вдоль и поперёк и полна замечательных результатов, и по ней написаны сотни (возможно, хороших) книг. Однако, теоретическая разрешимость задачи и написание кода — не одно и то же.
Модельная задача
Написание парсера проиллюстрируем на простом, но не до конца тривиальном примере — парсинге 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 = repile(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 = repile(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)
Итого, по какому принципу мы строим наши функции:
Они принимают строку, которую нужно парсить.
Они возвращают пару (результат, оставшаяся_строка) при успехе (то есть когда требуемая конструкция нашлась в начале строки) и None при провале.
Они отправляют в небытие все пробельные символы между токенами. (Не делайте так, если пишете парсер Питона!)
Собственно, на этих трёх функциях проблемы с токенами решены, и мы можем перейти к интересной части.
Парсим правило с ветвлением
Как должна выглядеть функция 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 = repile(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 = repile(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.chain объединяет переданные ей итераторы
# в цепочку, не трогая ни один раньше времени
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, как и обещано, но что-то всё равно не так… Давайте напишем небольшую вспомогательную функцию, которая поможет нам соединять функции-парсеры в последовательности подобно тому, как chain помогла соединять их в режиме «или». Эта функция должна будет аккуратно брать все результаты и вернуть все первые элементы результатов (результаты анализа) и последний второй элемент (оставшуюся непроанализированной часть строки). Мой вариант выглядит так:
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 = repile(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 = repile(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, от которых мы столь изящно избавились.
Несмотря на неполноту и неакадемичность изложения, я надеюсь, что эта статья будет полезна начинающим программистам, а может, даже удивит новизной подхода программистов продвинутых. При этом я прекрасно отдаю себе отчёт, что это просто новая форма для старого доброго рекурсивного спуска; но если программирование — это искусство, разве не важна в нём форма если не наравне, то хотя бы в степени, близкой к содержанию?..
Как обычно, не откладывая пишите в личку обо всех обнаруженных неточностях, орфографических, грамматических и фактических ошибках — иначе я сгорю от стыда!
