Увлекательным аспектом разработки программного обеспечения является преобразование последовательности символов в текстовом файле в набор инструкций, которые могут выполняться на ЦП для получения значимых результатов. Для человека, читающего код, вполне очевидно (ну, может быть, не совсем очевидно, в зависимости от языка), каков желаемый результат.
Это потому, что человеческий разум развился, чтобы быть в состоянии эффективно структурировать поток символов в значимые группы, которые появляются в осмысленном порядке. Это то, что позволяет людям общаться и реагировать, и это деятельность, которая часто воспринимается как должное.
Это совсем другая история для компьютеров. У них нет психических процессов, которые автоматически структурируют содержание, которое затем можно использовать для управления их действиями; поток символов - это просто поток символов. Чтобы это было чем-то другим, компьютер нужно научить понимать это.
О том, что это несложная задача (по крайней мере, теперь, благодаря предыдущим поколениям компьютерных ученых и инженеров, которые проложили путь в этой области), свидетельствует множество языков программирования, форматов файлов и методов десериализации данных, которые инженеры-программисты используют каждый день для решать задачи. Любой инженер может добавить в этот список еще один язык программирования, еще один формат файла или еще одну технику сериализации. Единственным реальным предварительным условием является наличие некоторых знаний и опыта в анализе текста.
Разбор
Синтаксический анализ — это, по сути, преобразование последовательности символов (или, в более общем смысле, битов) в структурированные данные. Для целей этой статьи мы будем иметь дело с символами, хотя такие вещи, как форматы файлов, имеют дело с битами.
Упрощенно говоря, процесс преобразования строки во что-то структурированное и осмысленное состоит из двух этапов:
- лексический анализ: поток отдельных символов преобразуется в поток токенов (т.е., сгруппированных символов)
- синтаксический анализ: поток токенов преобразуется в абстрактное синтаксическое дерево (структура данных, которая выражает отношения между токенами в тексте, а также может записывать важные метаданные о них)
Обычно синтаксический анализ — это только первый шаг в более масштабной работе. Например, компиляция файла Golang в исполняемый файл требует синтаксического анализа в качестве первого шага, но также имеет много других действий, которые дополнительно преобразуют AST в инструкции ЦП.
Независимо от того, каков конечный результат, любой успешный этап синтаксического анализа требует указания формальной грамматики. Это удобочитаемая спецификация, которая объясняет, что представляют собой соответствующие токены, а также в каком порядке они должны появляться.
В простейшей форме грамматику можно описать как набор правил для перезаписи строк. Некоторые строки могут быть переписаны в терминах других строк, а некоторые строки не могут быть переписаны дальше — они называются нетерминальными и терминальными символами соответственно. Токены, которые распознаются на лексической стадии, включают в себя набор терминальных символов этой грамматики, который, кроме того, включает набор нетерминальных символов (существует отношение 1 ко многим между нетерминальными и терминальными символами).
Простой пример грамматики, которую может использовать калькулятор для разбора математического выражения, может выглядеть так:
EXPRESSION
: EXPRESSION '+' EXPRESSION
| EXPRESSION '-' EXPRESSION
| EXPRESSION '*' EXPRESSION
| EXPRESSION '/' EXPRESSION
| number
;
(На самом деле это плохая грамматика по причинам, выходящим за рамки этой статьи; она используется только для иллюстрации форм, которые будут использоваться позже.)
Эта грамматика определяет терминальные символы +, -, *, / и number и указывает, что они могут быть организованы пятью различными способами, четыре из которых допускают рекурсивную организацию. Например, EXPRESSION '+' EXPRESSION можно расширить до EXPRESSION '+' EXPRESSION '-' EXPRESSION. Это позволяет выражать сложные группы токенов в очень небольшом количестве правил. В соответствии с этой грамматикой стандартное арифметическое выражение, такое как 12 + 41 * 3, может быть сопоставлено как выражение, подвергнувшись следующим переписываниям:
EXPRESSION '+' EXPRESSION (rewrite the rightmost EXPRESSION) -> EXPRESSION '+' EXPRESSION * EXPRESSION -> number '+' number '*' number
Как происходит синтаксический анализ, как грамматика используется для распознавания допустимого математического выражения, является основной темой этой статьи. Существует два основных подхода к парсингу: использование одной из множества библиотек-генераторов парсеров (которые реализуют хорошо зарекомендовавшие себя алгоритмы парсинга) или написание ее вручную. Использование генератора абстрагирует большую часть работы от разработчика и отлично подходит для сложных ситуаций, но при попытке понять, как вообще работает процесс, лучше написать парсер вручную.
С этой целью в этой статье будет создан парсер для того, что разработчики JavaScript используют каждый день: JSON. К концу этой статьи будет рабочая версия метода JSON.parse, в которой исследуются виды путей, которые необходимо выбрать, и решения, которые необходимо принять для преобразования текста JSON в значения JavaScript.
Разбор JSON (облегченный)
Чтобы сохранить согласованность словарного запаса в остальной части этой статьи, «анализ» будет означать весь процесс преобразования неструктурированной строки символов в структурированный фрагмент данных. Парсинг будет состоять из этапа токенизации (лексического анализа), за которым следует этап (синтаксического) анализа.
Грамматика
Чтобы подготовить почву для создания токенизатора и анализатора, будет предоставлена точная грамматика, выражающая JSON для анализа. Эта грамматика не будет читать все возможные строки, соответствующие полной спецификации JSON; для этого потребуется углубиться в мелочи и отвлечься от цели более высокого уровня, заключающейся в широком понимании конвейера синтаксического анализа.
Возможными значениями, которые может представлять строка JSON, являются строки, числа, логические значения, нулевое значение, а также объекты и массивы (оба из которых могут содержать любое количество значений JSON). Это дает грамматике ее главное правило:
JSON
: JSON_STRING
| number
| null
| JSON_BOOL
| JSON_ARRAY
| JSON_OBJECT
;
Соглашение, которое будет использоваться для именования символов в этой грамматике, будет следующим:
- все нетерминальные символы будут в верхнем регистре
- терминальные символы, которые представляют класс символов, будут все в нижнем регистре
- терминальные символы, которые представляют буквенный символ, будут записаны так, как они заключены в одинарные кавычки.
Чтобы быть полным, четыре нетерминальных символа этой грамматики должны иметь свои правила.
Строки в JSON будут находиться между двумя кавычками. Массивы будут представлять собой список разделенных запятыми любых значений JSON между двумя квадратными скобками. Объекты будут представлять собой разделенный запятыми список пар ключ/значение между фигурными скобками. Это расширяет грамматику до следующего:
JSON
: JSON_STRING
| number
| null
| JSON_BOOL
| JSON_ARRAY
| JSON_OBJECT
;
JSON_STRING
: '"' string '"'
;
JSON_BOOL
: true
| false
;
JSON_ARRAY
: '[' JSON_ARRAY_ELS ']'
;
JSON_ARRAY_ELS
: JSON_ARRAY_ELS ',' JSON
| JSON
| epsilon
;
JSON_OBJECT
: '{' JSON_OBJECT_KV_PAIRS '}'
;
JSON_OBJECT_KV_PAIRS
: JSON_OBJECT_KV_PAIRS ',' JSON_OBJECT_KV_PAIR
| JSON_OBJECT_KV_PAIR
| epsilon
;
JSON_OBJECT_KV_PAIR
: JSON_STRING ':' JSON
;
В этой грамматике есть пара интересных особенностей, на которые стоит обратить внимание.
Был введен специальный символ под названием epsilon. Этот символ представляет собой пустую строку и в этой грамматике используется для обозначения того, что массив или объект могут быть пустыми. Это позволит "[]" и "{}" быть допустимыми строками JSON.
Грамматика также рекурсивна. Это отражает рекурсивный характер самих значений JSON, поскольку нет ограничений на то, что может быть вложено в массивы и объекты. Это позволяет "[1,[true,[]]]" быть допустимой строкой JSON, которая будет разобрана на серию вложенных массивов. Кроме того, некоторые из этих рекурсивных правил являются лево рекурсивными, что означает, что производственное правило имеет себя в качестве начала правила:
JSON_ARRAY_ELS
: JSON_ARRAY_ELS ',' JSON
;
Для анализаторов, использующих определенные алгоритмы синтаксического анализа, это может привести к бесконечному зацикливанию, поскольку синтаксический анализатор для анализа JSON_ARRAY_ELS должен сначала проверить, соответствует ли оно JSON_ARRAY_ELS.. >до бесконечности. Поскольку в этой статье анализатор реализуется вручную, существует большая гибкость в отношении того, как анализатор обрабатывает левую рекурсию: его можно легко переписать как итерацию.
Токенизатор
Смысл токенизатора состоит в том, чтобы разбить текст, который нужно разобрать, на группы символов (даже если некоторые из этих групп содержат только один символ). Эти токены представляют собой терминальные символы в грамматике и часто определяются регулярными выражениями и имеют имя. Некоторые токены также могут быть признаны бессмысленными и полностью пропущены — этот подход часто используется для пробельных символов.
Грамматика, определенная выше, дает следующие токены:
const tokens = [
[/^\s+/, null], // skip whitespace
[/^\[/, '['],
[/^]/, ']'],
[/^\{/, '{'],
[/^}/, '}'],
[/^:/, ':'],
[/^,/, ','],
[/^"/, '"'],
[/^\d+/, 'number'],
[/^null\b/, 'null'], // Add word boundaries to ensure that
[/^true\b/, 'true'], // `null`, etc., is matched exactly.
[/^false\b/, 'false'],
[/^[^"]*/, 'string'], // Match anything not a quotation mark.
];
Каждый кортеж представляет пару шаблон/имя. Каждый шаблон привязывается к началу строки, чтобы токенизатор всегда генерировал следующий токен, который следует передать анализатору. Назначив пробелу имя null, это укажет токенизатору, что все пробелы следует игнорировать.
Логика токенизатора состоит в том, чтобы пройтись по списку токенов и найти первый, который соответствует началу строки. Это означает, что важно упорядочивать токены таким образом, чтобы более конкретные токены предшествовали более общим. Например, если в определенном языке программирования есть два ключевых слова def и define, define должно идти первым, чтобы токенизация строки define add(a, b) не совпадала сначала с def и, таким образом, не оставляла недопустимое ine add(a, b) для последующей обработки токенизатором.
Это дает в качестве скелета токенизатора следующую структуру
class Tokenizer {
constructor(tokens) {}
read(string) {}
next() {}
}
который можно конкретизировать
class Tokenizer {
// List of tokens recognized by the tokenizer
#tokens;
// Position in the input string from which it will
// read to get the next token
#cursor;
// String to turn into tokens
#string;
constructor(tokens) {
this.#tokens = tokens;
}
read(string) {
this.#cursor = 0;
this.#string = string;
}
next() {
// If at end of input, no more tokens to generate
if (this.#cursor === this.#string.length) {
return undefined;
}
// Find substring beginning at position of cursor
const str = this.#string.slice(this.#cursor);
for (const [pattern, type] of this.#tokens) {
const [match] = pattern.exec(str) || [];
if (!match) {
continue;
}
this.#cursor += match.length;
// Skip tokens with null types
if (type === null) {
return this.next();
}
return { token: match, type };
}
// Could not extract any tokens, so throw error
throw new Error(`Unrecognized input: ${str[0]}`);
}
}
Теперь, когда поток символов можно преобразовать в поток токенов, пришло время преобразовать эти токены в абстрактное синтаксическое дерево.
Анализатор
У анализатора немного больше работы, чем у токенизатора, поскольку он должен реализовать продукционные правила грамматики. Поскольку этот анализатор написан вручную, его размер и сложность прямо пропорциональны количеству правил, которые он должен реализовать.
Поскольку это разнообразие созданных вручную анализаторов (называемых рекурсивным спуском) напрямую реализует правила грамматики, хорошим скелетом для начала будет:
class Analyzer {
// Tokenizer class
#tokenizer;
// Current token being analyzed
#lookahead;
constructor(tokenizer) {}
#eat(tokenType) {}
read(string) {}
#JSON() {}
#JSON_STRING() {}
#JSON_number() {}
#JSON_null() {}
#JSON_BOOL() {}
#JSON_ARRAY() {}
#JSON_OBJECT() {}
#JSON_ARRAY_ELS() {}
#JSON_OBJECT_KV_PAIRS() {}
#JSON_OBJECT_KV_PAIR() {}
}
Большинство этих методов напрямую соответствуют грамматике; два новые. read — это общедоступный метод, который будет вызываться для строки, чтобы преобразовать ее в абстрактное синтаксическое дерево. #eat — это метод, обычно используемый анализаторами для проверки того, что текущий токен имеет требуемый тип. Если токен соответствует типу, он будет возвращен, и анализатор сможет продолжить свои выводы. В противном случае анализатор должен выдать ошибку. Использование #eat станет более очевидным позже в этой статье.
Также в анализаторе есть свойство #lookahead. Это один из наиболее важных аспектов синтаксического анализа: возможность проверить текущий токен перед его использованием. #lookahead хранит текущий токен, который позволяет анализатору определить, какой путь в грамматике он должен выбрать. Его существование будет иметь решающее значение для реализации метода #JSON. Как правило, любое количество токенов может использоваться для упреждения, хотя один токен является очень распространенным числом, и его достаточно для реализации синтаксического анализатора JSON.
Детализируя неграмматические методы, анализатор будет выглядеть так:
class Analyzer {
#tokenizer;
#lookahead;
constructor(tokenizer) {
this.#tokenizer = tokenizer;
}
read(string) {
this.#tokenizer.read(string);
// Set the first token as the lookahead
this.#lookahead = this.#tokenizer.next();
return this.#JSON();
}
#eat(tokenType) {
const token = this.#lookahead;
if (!token) {
throw new Error(
`Unexpected end of input; expected ${token.type}`
);
}
if (this.#lookahead.type !== tokenType) {
throw new Error(
`Expected ${tokenType} === ${token.type}`
);
}
// Set the next token as the lookahead
this.#lookahead = this.#tokenizer.next();
return token;
}
}
После реализации #eat и read можно реализовать методы построения AST.
class Analyzer {
// ... methods from above
#JSON() {
switch (this.#lookahead.type) {
case '"':
return this.#JSON_STRING();
case 'number':
return this.#JSON_number();
case 'null':
return this.#JSON_null();
case 'true':
case 'false':
return this.#JSON_BOOL();
case '[':
return this.#JSON_ARRAY();
case '{':
return this.#JSON_OBJECT();
default:
throw new Error(
`Received token which cannot be valid JSON`
);
}
}
}
Как видно из этого метода, упреждающий токен играет решающую роль, позволяя анализатору определить, какое значение JSON следует анализировать. Без этих знаний анализатор не смог бы продолжить работу. Поскольку только подмножество набора токенов грамматики может начинаться со значения JSON, если просмотр вперед не находится ни в одном из операторов case, то анализатор пытается прочитать искаженный JSON и выдает ошибку.
Остальные методы (некоторые из которых иллюстрируют использование #eat):
class Analyzer {
// ... previous methods
#JSON_STRING() {
// The quotation marks are necessary for the JSON grammar,
// but contribute nothing to the semantic content of the
// AST, so ensure they exist but do not use
this.#eat('"');
const string = this.#eat('string').token;
this.#eat('"');
return {
type: 'JSON_STRING',
value: string,
}
}
#JSON_number() {
const number = this.#eat('number').token;
return {
type: 'JSON_number',
value: +number,
}
}
#JSON_null() {
this.#eat('null');
return {
type: 'JSON_null',
value: null,
}
}
#JSON_BOOL() {
const bool = this.#lookahead.type === 'true'
? this.#eat('true')
: this.#eat('false');
return {
type: 'JSON_BOOL',
value: bool.token === 'true',
}
}
}
Это заботится о нерекурсивных правилах грамматики. Каждое правило возвращает объект, указывающий тип узла, который оно представляет в AST, а также интерпретируемое значение этого узла (это означает, что если анализатор считывает число, возвращаемый узел имеет значение , которое является числом вместо текстового маркера этого числа).
Эти конечные случаи значения JSON могут быть рекурсивно объединены в массивы и объекты, поэтому следующие правила каким-то образом будут включать рекурсию с помощью самого верхнего метода #JSON.
class Analyzer {
// ... previous rules
#JSON_ARRAY() {
this.#eat('[');
const elements = this.#JSON_ARRAY_ELS();
this.#eat(']');
return {
type: 'JSON_ARRAY',
elements,
}
}
#JSON_ARRAY_ELS() {
const elements = [];
while (this.#lookahead.type !== ']') {
elements.push(this.#JSON());
// The final element of an array will not have a comma
// following it, so conditionally consume any comma
// characters
this.#lookahead.type === ',' && this.#eat(',');
}
return elements;
}
}
Это первое производственное правило, которое использует другую форму для своего узла AST: все узлы, представляющие конечные узлы, имели свойства value, но здесь используется elements. Узлы AST могут иметь любую возможную форму без проблем, если формы используются последовательно. В этом случае более семантически имеет смысл использовать elements вместо value для узлов массива.
Правило грамматики для JSON_ARRAY_ELS является леворекурсивным, что, как сказано выше, может привести к бесконечной рекурсии для некоторых алгоритмических анализаторов. Однако ручной анализатор обходит это, анализируя элементы массива с помощью цикла while. Поскольку рекурсия и зацикливание являются тесно связанными понятиями, часто можно сделать такую замену, и в этом случае она предотвращает изменения в грамматике, но дает тот же результат.
Метод #JSON_ARRAY_ELS itself не возвращает узел AST, так как это вспомогательная функция, а не основной метод чтения JSON.
Методы чтения объектов очень похожи на те, что используются для чтения массивов:
class Analyzer {
// ... previous methods
#JSON_OBJECT() {
this.#eat('{');
const kvPairs = this.#JSON_OBJECT_KV_PAIRS();
this.#eat('}');
return {
type: 'JSON_OBJECT',
entries: kvPairs,
}
}
#JSON_OBJECT_KV_PAIRS() {
const entries = [];
while (this.#lookahead.type !== '}') {
entries.push(this.#JSON_OBJECT_KV_PAIR());
this.#lookahead.type === ',' && this.#eat(',');
}
return entries;
}
#JSON_OBJECT_KV_PAIR() {
// Get key
this.#eat('"');
const key = this.#eat('string').token;
this.#eat('"');
this.#eat(':');
// Get value
const value = this.#JSON();
return [key, value];
}
}
Пример вывода
Теперь, когда конвейер синтаксического анализа завершен, можно объединить токенизатор и анализатор, чтобы проиллюстрировать примеры выходных данных с учетом различных входных строк JSON.
const tokenizer = new Tokenizer(tokens);
const analyzer = new Analyzer(tokenizer);
const str1 = '"abc"';
const str2 = '145';
const str3 = '[true, { "k": null }, []]';
analyzer.read(str1);
// {
// type: 'JSON_STRING',
// value: 'abc',
// }
analyzer.read(str2);
// {
// type: 'JSON_number',
// value: 145,
// }
analyzer.read(str3);
// {
// type: 'JSON_ARRAY',
// elements: [
// { type: 'JSON_BOOL', value: true },
// { type: 'JSON_OBJECT', entries: [
// [ 'k', { type: 'JSON_null', value: null } ],
// },
// { type: 'JSON_ARRAY', elements: [] },
// }
Преобразование строки в значение JavaScript
Пока анализатор преобразует строку JSON в абстрактное синтаксическое дерево. Однако цель состоит в том, чтобы преобразовать указанную строку в значение JavaScript (тем самым имитируя фактический метод JSON.parse).
Хитрость в том, чтобы сделать это, требует использования того факта, что структура AST уже точно отражает структуру самого JSON: каждый метод, который возвращает узел AST, возвращает что-то, что имеет всю информацию, необходимую для создания фактического базового значения JSON. Это означает, что с минимальными изменениями анализатор может возвращать значения вместо AST.
Чтобы это произошло, необходим небольшой рефакторинг. Вместо того, чтобы методы анализатора всегда возвращали узлы AST, они будут вызывать фабричные функции, которые возвращают что-то, представляющее «тему» этой фабрики. В исходном случае темой были узлы AST; в следующем случае это будет JavaScript.
Рефакторинговая версия анализатора будет выглядеть так
const astFactory = {
JSON_STRING(token) {
return {
type: 'JSON_STRING',
value: token.token,
};
},
JSON_number(token) {
return {
type: 'JSON_number',
value: +token.token,
};
},
JSON_null() {
return {
type: 'JSON_null',
value: null,
};
},
JSON_BOOL(token) {
return {
type: 'JSON_BOOL',
value: token.token === 'true',
};
},
JSON_ARRAY(elements) {
return {
type: 'JSON_ARRAY',
elements,
};
},
JSON_OBJECT(entries) {
return {
type: 'JSON_OBJECT',
entries,
}
}
};
class Analyzer {
// ... non-refactored methods and properties
#factory;
constructor(tokenizer, factory) {
this.#tokenizer = tokenizer;
this.#factory = factory;
}
#JSON_STRING() {
this.#eat('"');
const string = this.#eat('string');
this.#eat('"');
return this.#factory.JSON_STRING(string);
}
#JSON_number() {
const number = this.#eat('number');
return this.#factory.JSON_number(number);
}
#JSON_null() {
this.#eat('null');
return this.#factory.JSON_null();
}
#JSON_BOOL() {
const bool = this.#lookahead.type === 'true'
? this.#eat('true')
: this.#eat('false');
return this.#factory.JSON_BOOL(bool);
}
#JSON_ARRAY() {
this.#eat('[');
const elements = this.#JSON_ARRAY_ELS();
this.#eat(']');
return this.#factory.JSON_ARRAY(elements);
}
#JSON_OBJECT() {
this.#eat('{');
const kvPairs = this.#JSON_OBJECT_KV_PAIRS();
this.#eat('}');
return this.#factory.JSON_OBJECT(kvPairs);
}
}
Теперь анализатор возвращает то, что возвращает соответствующая функция #factory. На данный момент все, что необходимо, — это написать фабрику JavaScript вместо фабрики AST.
const jsFactory = {
JSON_STRING(token) {
return token.token;
},
JSON_number(token) {
return +token.token;
},
JSON_null() {
return null;
},
JSON_BOOL(token) {
return token.token === 'true'
},
JSON_ARRAY(elements) {
return elements;
},
JSON_OBJECT(entries) {
return entries.reduce(
(obj, [k, v]) => {
obj[k] = v;
return obj;
},
{}
);
}
};
Используя те же строки, что и выше, фабрика JSON выдает на выходе действительно проанализированные значения JSON.
const tokenizer = new Tokenizer(tokens);
const analyzer = new Analyzer(tokenizer, jsFactory);
const str1 = '"abc"';
const str2 = '145';
const str3 = '[true, { "k": null }, []]';
analyzer.read(str1); // "abc"
analyzer.read(str2); // 145
analyzer.read(str3); // [true, { k: null }, []]
Заключение
Написание пользовательского токенизатора и анализатора вручную не такая сложная задача, как может показаться на первый взгляд, и открывает множество других возможностей для разработки, таких как создание механизма регулярных выражений, механизма CSS или даже собственного языка программирования. На самом деле, наиболее сложной частью часто является правильное моделирование грамматики. При четко определенной грамматике анализатор работает довольно быстро.
Хотя этот синтаксический анализатор не анализирует полную спецификацию JSON, он приближается к ней, и для всех, кто заинтересован в реализации полной грамматики, RFC Дугласа Крокфорда можно найти здесь. На самом деле, этот парсер можно расширить до грамматики JSON+, если кто-то заинтересован в расширении его возможностей. Такие значения, как Infinity, undefined и комментарии, не поддерживаются в спецификации, но их легко добавить в текущую грамматику.
Вот суть всего кода парсера в одном месте.
