- PVSM.RU - https://www.pvsm.ru -
В 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 (без каких-либо дополнительных модулей, конечно же).
Парсинг (по-русски «синтаксический анализ») — это бессмертная задача разобрать и преобразовать в осмысленные единицы нечто, написанное на некотором фиксированном языке, будь то язык программирования, язык разметки, язык структурированных запросов или главный язык жизни, Вселенной и всего такого. Типичная последовательность этапов решения задачи выглядит примерно так:
Вообще область эта изучена вдоль и поперёк и полна замечательных результатов, и по ней написаны сотни (возможно, хороших) книг. Однако, теоретическая разрешимость задачи и написание кода — не одно и то же.
Написание парсера проиллюстрируем на простом, но не до конца тривиальном примере — парсинге 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
— они, вместе со всеми строками в кавычках, будут нашими токенами.
Полноценный токенайзер мы писать не станем (это скучно и не совсем тема статьи) — будем работать с целой строкой и бить её на токены по мере необходимости. Напишем две первые функции:
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)
Итого, по какому принципу мы строим наши функции:
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
! Теперь они возвращают генераторы [4] — пустые, если парсинг не удался, и ровно с одним элементом, если удался. Да-да, мы разворачиваем на 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
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/183878
Ссылки в тексте:
[1] формы Бэкуса-Наура: https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0_%D0%91%D1%8D%D0%BA%D1%83%D1%81%D0%B0_%E2%80%94_%D0%9D%D0%B0%D1%83%D1%80%D0%B0
[2] Вот: https://github.com/python/cpython/blob/master/Grammar/Grammar
[3] метода рекурсивного спуска: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0
[4] генераторы: https://wiki.python.org/moin/Generators
[5] Источник: https://habrahabr.ru/post/309242/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.