JSONY парсер
Все любят JSON. Поэтому в вашей компании хотят написать свой формат, очень похожий на него, но с дополнительными возможностями. Однако для начала нужно создать основу, и этот таск повесили на вас.
Вам предстоит реализовать простой парсер (десириалайзер?) небольшого формата данных, а в дополнительном задании и генератор (серилиалайзер?). Описание формата ниже.
Формат
Целое число без ведущих нулей. Опускаем подробности его длины для простоты.
Строка. Начинается и заканчивается "
. Внутри строки могут быть другие "
, и они должны быть экранированы. Например, "\""
- строка, содержащая "
.
Массив. Начинается с [
и заканчивается ]
. Все элементы перечисляются через ,
.
Объект. Начинается с {
и заканчивается }
. Внутри объект представляется как пара ключ:значение
. Ключом является стандартное имя переменной - набор букв, цифр и нижнего подчеркивания. При этом ключ не может начинаться с цифры.
Объекты и массивы могут быть вложенными.
Каждая строка содержит ровно один объект. Т.е. каждая строка начинается с {
и заканчивается }
.
Вы можете считать, что на вход всегда подается корректная строка.
Примеры
Дополнительные задания
Напишите метод serialize
. Он должен из переданного объекта генерировать строку в формате JSONY. Все строки должны быть экранированы. jsony.parse(jsony.serialize(obj))
должен всегда равняться obj
, как и jsony.serialize(jsony.parse(str))
должен всегда равняться str
, с точностью до пробела, переноса строки, таба и прочих пробельных символов.
Для особо жаждающих - напишите хорошую обработку ошибок, которая будет говорить, в каком месте возникла ошибка и с чем она связана.
Решение
Мы будем пользоваться техникой, на которой построены все компиляторы и интерпретаторы. Типичный этап компиляции в общем выглядит примерно так:
- Лексинг
Сначала мы имеем простую строку из букв - код нашей программы. Разобьем ее на другие единицы - токены, с которыми нам удобнее будет работать. Токен - это пара двух параметров: тип токена и его строковое представление. Например, число
123
превратиться в токен(int, "123")
, фигурная скобка{
- в `(curlyBrace, “{“) и так далее. Стоит заметить, что для каждого знака препинания выделяется отдельный тип токена - так ими проще манипулировать.
Процесс превращения строки в массив таких токенов и называется лексинг.
- Парсинг
Теперь из последовательности токенов нам нужно собрать так называемое AST-дерево - абстрактное синтаксическое дерево. По сути, это представление исходной программы в виде дерева, которое, в отличие простой последовательности токенов, имеет иерархическую структуру. Например, если мы пользуемся стандартными правилами порядка выполнения операций из математики, строка
5 + 6*3
после лексинга и парсинга превратиться в такое дерево
а немного другая строка в 6*3 + 5
в
Видно, что по сути они одинаковые. Однако во второй строке сначала идет умножение, и плохо написанные правила для парсера или сам парсер могут привести к такому результату
И такого мы скорее всего не хотим.
В нашем случае нам достаточно превратить последовательность токенов в конечный объект, и на этом наша работа по парсингу исходной строки закончится. Для компилятора же работа, можно сказать, только начинается. Лексинг и парсинг - задача фронтенда (внешней части) компилятора. Затем такое AST-дерево передается бэкенду (внутренней части), где оно оптимизируется, компилируется в машинный (или другой) код, и происходит еще много разной магии. Советую ознакомиться с полным процессом компиляции, например написав свой пробный язык программирования (Туториал по LLVM, Создай свой Lisp) - крайне интересная и широкая тема.
Код
Хватит теории, переходим к кодингу. Для начала напишем основу.
Хочу сразу предупредить, код получился не очень маленьким (но и не большим) - около 200 строк. Немного практики в разборе чужого кода никогда не будет лишней :)
Тут, надеюсь, все понятно. Переходим к самой реализации лексинга.
Напишем основную функцию _tokenize
. Ее задачей будет пройтись по всем символам исходной строки, и для каждого символа описать дальнейшие действия. Например, если мы встретили {
, то просто добавляем токен (curlyBrace, “{“) в массив. Если встречаем начало числа, строки или ключа - вызываем нужную функцию, которая сама с ним разберется.
Суть вспомогательных методов проста. Например, _addNumber
читает строку, пока ему попадаются числа, и затем добавляет полученный токен в массив. Внизу представлен процесс его работы на строке [1]23a
, где [x]
означает, что текущий индекс _ci
указывает на этот символ.
Другие методы работают аналогично.
Немного про реализацию _addToken
. Она именно такая, потому что в дальнейшем мы можем захотеть расширить ее функционал, например, проверять, что переданный нам тип вообще существует, что переданная строка не пустая (если только не возможно обратное) и т.д. Поэтому в конце каждого метода мы вызываем именно _addToken
, а не просто пушим в массив.
Теперь переходим непостредственно к парсингу. Помним, что теперь мы уже работаем с последовательностью токенов. _parseTokens
принимает массив токенов, хотя в данном контексте это и лишнее. Это сделано для того, чтобы в дальнейшем при надобности мы могли его использовать отдельно, не вызывая _tokenize
.
_parseAt(i)
делает простую вещь - проверяет, что сейчас предстоит распарсить - объект или массив, и вызываем нужный метод.
_parseObj
возвращает нужный объект. Он продолжает добавлять пары ключ: значение
в объект, пока не встретит закрывающую скобку {
. Можно заметить, что мы не делаем никаких проверок на то, чтобы после ключа не шел еще один ключ и подобное - обработка ошибок в данном случае не тривиальна, и является отдельной темой. Мы же предполагаем, что исходная строка, а значит и последовательность токенов всегда корректны.
И, наконец, парсим массив.
Вот и все! Мы закончили с парсингом нашего JSONY формата. Генерацию, обработку ошибок и расширение формата оставляю как домашнее задание.
Решения сообщества
Хорошее решение прислал Мартин Шульц. В нем реализована и генерация, и обработка ошибок. Стоит отметить, что Мартин не пошел по стандартной схеме лексинг -> парсинг, а сделал все на месте, чего для данной задачи вполне хватило.
Заключение
Формальные языки - большая и сложная тема для изучения, надеюсь это маленькое упражнение пробудит в вас интерес к ней.
Спасибо за внимание!
Комментарии