JSONY парсер
Все любят JSON. Поэтому в вашей компании хотят написать свой формат, очень похожий на него, но с дополнительными возможностями. Однако для начала нужно создать основу, и этот таск повесили на вас.
Вам предстоит реализовать простой парсер (десириалайзер?) небольшого формата данных, а в дополнительном задании и генератор (серилиалайзер?). Описание формата ниже.
Формат
Целое число без ведущих нулей. Опускаем подробности его длины для простоты.
Строка. Начинается и заканчивается "
. Внутри строки могут быть другие "
, и они должны быть экранированы. Например, "\""
- строка, содержащая "
.
Массив. Начинается с [
и заканчивается ]
. Все элементы перечисляются через ,
.
Объект. Начинается с {
и заканчивается }
. Внутри объект представляется как пара ключ:значение
. Ключом является стандартное имя переменной - набор букв, цифр и нижнего подчеркивания. При этом ключ не может начинаться с цифры.
Объекты и массивы могут быть вложенными.
Каждая строка содержит ровно один объект. Т.е. каждая строка начинается с {
и заканчивается }
.
Вы можете считать, что на вход всегда подается корректная строка.
Примеры
let jsony = new JSONY();
jsony.parse('{ hello: \"world\" }'); // { hello: "world" } - возвращаемый объект
jsony.parse('{ age: 10, height: 120 }'); // { age: 10, height: 120 }
jsony.parse('{ people: [\"Ann\", \"Alice\", \"Bob\"] }'); // { people: ["Ann", "Alice", "Bob"] }
jsony.parse('{ config: { servers: [10, 15, 13], ngnix: { gate: 0, ip: \"127.0.0.1\" } } }');
/*
{
config: {
servers: [10, 15, 13],
ngnix: {
gate : 0,
ip: "127.0.0.1"
}
}
}
*/
Дополнительные задания
Напишите метод serialize
. Он должен из переданного объекта генерировать строку в формате JSONY. Все строки должны быть экранированы. jsony.parse(jsony.serialize(obj))
должен всегда равняться obj
, как и jsony.serialize(jsony.parse(str))
должен всегда равняться str
, с точностью до пробела, переноса строки, таба и прочих пробельных символов.
Для особо жаждающих - напишите хорошую обработку ошибок, которая будет говорить, в каком месте возникла ошибка и с чем она связана.
Решение
Мы будем пользоваться техникой, на которой построены все компиляторы и интерпретаторы. Типичный этап компиляции в общем выглядит примерно так:
- Лексинг
Сначала мы имеем простую строку из букв - код нашей программы. Разобьем ее на другие единицы - токены, с которыми нам удобнее будет работать. Токен - это пара двух параметров: тип токена и его строковое представление. Например, число
123
превратиться в токен(int, "123")
, фигурная скобка{
- в `(curlyBrace, “{“) и так далее. Стоит заметить, что для каждого знака препинания выделяется отдельный тип токена - так ими проще манипулировать.
Процесс превращения строки в массив таких токенов и называется лексинг.
- Парсинг
Теперь из последовательности токенов нам нужно собрать так называемое AST-дерево - абстрактное синтаксическое дерево. По сути, это представление исходной программы в виде дерева, которое, в отличие простой последовательности токенов, имеет иерархическую структуру. Например, если мы пользуемся стандартными правилами порядка выполнения операций из математики, строка
5 + 6*3
после лексинга и парсинга превратиться в такое дерево
[сложить]
/ \
(int, 5) [умножить]
/ \
(int, 6) (int, 3)
а немного другая строка в 6*3 + 5
в
[сложить]
/ \
[умножить] (int, 5)
/ \
(int, 6) (int, 3)
Видно, что по сути они одинаковые. Однако во второй строке сначала идет умножение, и плохо написанные правила для парсера или сам парсер могут привести к такому результату
[умножить]
/ \
[сложить] (int, 6)
/ \
(int, 3) (int, 5)
И такого мы скорее всего не хотим.
В нашем случае нам достаточно превратить последовательность токенов в конечный объект, и на этом наша работа по парсингу исходной строки закончится. Для компилятора же работа, можно сказать, только начинается. Лексинг и парсинг - задача фронтенда (внешней части) компилятора. Затем такое AST-дерево передается бэкенду (внутренней части), где оно оптимизируется, компилируется в машинный (или другой) код, и происходит еще много разной магии. Советую ознакомиться с полным процессом компиляции, например написав свой пробный язык программирования (Туториал по LLVM, Создай свой Lisp) - крайне интересная и широкая тема.
Код
Хватит теории, переходим к кодингу. Для начала напишем основу.
Хочу сразу предупредить, код получился не очень маленьким (но и не большим) - около 200 строк. Немного практики в разборе чужого кода никогда не будет лишней :)
"use strict";
class JSONY{
constructor(){
this._ci = 0; // Текущий индекс
this._tokens = [];
}
parse(str){
let tokens = this._tokenize(str); // Лексим
return this._parseTokens(tokens); // Парсим
}
}
class Token {
constructor(type, str){
this.type = type;
this.str = str;
}
}
// Имена довольно краткие, потому что ими обычно приходится
// пользоваться часто
Token.Type = {
OCB: "{", // Opening curly brace
CCB: "}", // Closing curly brace
OSB: "[", // Opening square brace
CSB: "]", // Closing square brace
COM: ",", // ну и т.д.
COL: ":",
INT: "INT",
STR: "STR",
KEY: "KEY",
};
// Стандартная библиотека JS не предоставляет даже базовые
// утилиты, поэтому их приходится писать самим.
function isNumber(c){
let n = parseInt(c);
return n <= 9 && n >= 0;
}
function isAlphanumeric(c){
// Только английские буквы в ключах
let re = /^[a-zA-Z_0-9]$/;
return re.test(c);
}
function isWhitespace(c){
"\t" - табуляция
"\n" - перенос строки
return c === " " || c === "\t" || c === "\n";
}
Тут, надеюсь, все понятно. Переходим к самой реализации лексинга.
Напишем основную функцию _tokenize
. Ее задачей будет пройтись по всем символам исходной строки, и для каждого символа описать дальнейшие действия. Например, если мы встретили {
, то просто добавляем токен (curlyBrace, “{“) в массив. Если встречаем начало числа, строки или ключа - вызываем нужную функцию, которая сама с ним разберется.
...
_tokenize(str){
this._ci = 0;
this._tokens = [];
this._str = str;
while(this._ci < str.length){
if(str[this._ci] === "{"){
this._addToken(Token.Type.OCB, "{");
} else if(str[this._ci] === "}"){
this._addToken(Token.Type.CCB, "}");
} else if(str[this._ci] === "["){
this._addToken(Token.Type.OSB, "[");
} else if(str[this._ci] === "]"){
this._addToken(Token.Type.CSB, "]");
} else if(str[this._ci] === ","){
this._addToken(Token.Type.COM, ",");
} else if(str[this._ci] === ":"){
this._addToken(Token.Type.COL, ":");
} else if(isNumber(str[this._ci])){
this._addNumber();
} else if(isAlphanumeric(str[this._ci])){
this._addKey();
} else if(str[this._ci] === "\""){
this._addString();
} else if(isWhitespace(str[this._ci])){
this._skipWhitespaces();
} else {
// По самому заданию на вход всегда подается корректная строка.
// Однако для будущей обработки ошибок и просто деббагинга удобно.
throw new Error("Wtf is this " + str[this._ci] + " at " + this._ci);
}
}
return this._tokens;
}
...
Суть вспомогательных методов проста. Например, _addNumber
читает строку, пока ему попадаются числа, и затем добавляет полученный токен в массив. Внизу представлен процесс его работы на строке [1]23a
, где [x]
означает, что текущий индекс _ci
указывает на этот символ.
[1]23a - текущее число 1
1[2]3а - текущее число 12
12[3]a - текущее число 123
123[a] - встретили не число, добавляем токен (int, "123") и прекращаем работу метода
Другие методы работают аналогично.
Немного про реализацию _addToken
. Она именно такая, потому что в дальнейшем мы можем захотеть расширить ее функционал, например, проверять, что переданный нам тип вообще существует, что переданная строка не пустая (если только не возможно обратное) и т.д. Поэтому в конце каждого метода мы вызываем именно _addToken
, а не просто пушим в массив.
...
_addToken(type, str, inc){
this._tokens.push(new Token(type, str));
if(inc !== false){
this._ci++;
}
}
_addNumber(){
let num = "";
let str = this._str;
while(isNumber(str[this._ci])){
num += str[this._ci];
this._ci++;
}
this._addToken(Token.Type.INT, num, false);
}
_addKey(){
let key = "";
let str = this._str;
while(isAlphanumeric(str[this._ci])){
key += str[this._ci];
this._ci++;
}
this._addToken(Token.Type.KEY, key, false);
}
_addString(){
let string = "";
let str = this._str;
// Ignore opening "
this._ci++;
while(str[this._ci] !== "\""){
string += str[this._ci];
this._ci++;
}
// Ignore closing "
this._ci++;
this._addToken(Token.Type.STR, string, false);
}
_skipWhitespaces(){
let str = this._str;
while(isWhitespace(str[this._ci])){
this._ci++;
}
}
...
Теперь переходим непостредственно к парсингу. Помним, что теперь мы уже работаем с последовательностью токенов. _parseTokens
принимает массив токенов, хотя в данном контексте это и лишнее. Это сделано для того, чтобы в дальнейшем при надобности мы могли его использовать отдельно, не вызывая _tokenize
.
_parseAt(i)
делает простую вещь - проверяет, что сейчас предстоит распарсить - объект или массив, и вызываем нужный метод.
_parseTokens(tokens){
this._tokens = tokens;
this._ci = 0;
return this._parseAt(0);
}
_parseAt(i){
if(this._tokens[this._ci].type === Token.Type.OCB){
this._ci++;
return this._parseObj();
} else if(this._tokens[this._ci].type === Token.Type.OSB){
this._ci++;
return this._parseArray();
} else {
throw new Error("Called _parseAt(i) not in the beggining of object or array, but at " + this._ci);
}
}
_parseObj
возвращает нужный объект. Он продолжает добавлять пары ключ: значение
в объект, пока не встретит закрывающую скобку {
. Можно заметить, что мы не делаем никаких проверок на то, чтобы после ключа не шел еще один ключ и подобное - обработка ошибок в данном случае не тривиальна, и является отдельной темой. Мы же предполагаем, что исходная строка, а значит и последовательность токенов всегда корректны.
_parseObj(){
let obj = {}, key;
while(this._tokens[this._ci].type !== Token.Type.CCB){
let token = this._tokens[this._ci];
if(token.type === Token.Type.KEY){
key = token.str;
} else if(token.type === Token.Type.STR){
obj[key] = token.str;
} else if(token.type === Token.Type.INT){
obj[key] = parseInt(token.str);
} else if(token.type !== Token.Type.COL && token.type !== Token.Type.COM){
// We met another object or array
obj[key] = this._parseAt(this._ci);
}
this._ci++;
}
return obj;
}
И, наконец, парсим массив.
_parseArray(){
let arr = [];
while(this._tokens[this._ci].type !== Token.Type.CSB){
let token = this._tokens[this._ci];
if(token.type === Token.Type.INT){
arr.push(parseInt(token.str));
this._ci++;
} else if(token.type === Token.Type.STR){
arr.push(token.str);
this._ci++;
} else if(token.type === Token.Type.COM){
this._ci++;
} else {
// We met another object or array
arr.push(this._parseAt());
}
}
return arr;
}
Вот и все! Мы закончили с парсингом нашего JSONY формата. Генерацию, обработку ошибок и расширение формата оставляю как домашнее задание.
Решения сообщества
Хорошее решение прислал Мартин Шульц. В нем реализована и генерация, и обработка ошибок. Стоит отметить, что Мартин не пошел по стандартной схеме лексинг -> парсинг, а сделал все на месте, чего для данной задачи вполне хватило.
Заключение
Формальные языки - большая и сложная тема для изучения, надеюсь это маленькое упражнение пробудит в вас интерес к ней.
Спасибо за внимание!
Комментарии