Как использовать S-выражения в JavaScript
S-выражения являются основой семейства языков программирования Lisp. В этой статье я покажу вам, как шаг за шагом создать простой парсер S-выражений. Это может быть основой для парсера Lisp.
Lisp — самый простой в реализации язык, и создание парсера — первый шаг. Мы можем использовать для этого генератор парсера, но проще написать парсер самостоятельно. Мы будем использовать JavaScript.
Что такое S-выражения?
Если вы не знакомы с языком Lisp, S-выражения выглядят так:
(+ (second (list "xxx" 10)) 20)Это формат данных, в котором все создается из атомов или списков, заключенных в круглые скобки (где атомы других списков разделены пробелами).
S-выражения могут иметь разные типы данных, как и JSON:
- numbers
- strings
- symbols – похожие на строки, но без кавычек, их можно интерпретировать
как имена переменных из разных языков.
Кроме того, вы можете использовать специальный оператор точки, создающий пару.
(1 . b)Вы можете представить список в виде пар с точками (что указывает на то, что они фактически представляют собой структуру данных связанного списка).
Этот список:
(1 2 3 4)Можно записать как:
(1 . (2 . (3 . (4 . nil))))nil — специальный символ, обозначающий конец пустого списка. С помощью этого формата вы можете создать любое двоичное дерево. Но мы не будем использовать эту обожаемую нотацию в нашем парсере, чтобы не усложнять ситуацию.
Для чего используются S-выражения?
Код Lisp создается из S-выражений, но вы также можете использовать его для обмена форматами.
Они также являются частью текстового представления WebAssembly. Наверное, из-за простоты парсера и того, что не нужно придумывать свой формат. Вы можете использовать их для связи между сервером и браузером вместо JSON.
Tokenizer
Tokenizer — это часть синтаксического анализатора, который разбивает текст на токены, которые затем можно анализировать.
Обычно парсер сопровождается лексером или токенизатором, генерирующим токены.
Именно так работают некоторые генераторы парсеров (например, lex и Yacc или flex и bison. Второй — бесплатное программное обеспечение с открытым исходным кодом, часть проекта GNU).
Самый простой способ токенизации — использование регулярных выражений.
Это самый простой способ токенизации:
'(foo bar (baz))'.split(/(\(|\)|\n|\s+|\S+)/);Это объединение (с оператором канала) или разные случаи, которые нам нужно обработать. Круглые скобки — это специальные символы в Regex, поэтому их нужно экранировать косой чертой.
Это почти работает. Первая проблема заключается в том, что между совпадениями регулярных выражений есть пустые строки. Как это выражение:
'(('.split(/(\(|\)|\n|\s+|\S+)/);
// ==> [ '', '(', '', '(', '' ]У нас 5 токенов вместо 2. Эту проблему можно решить с помощью Array::filter.
'(('.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.length);
// ==> ["(", "("]Если токен пуст, длина вернет 0 и будет преобразована в false, что означает, что все пустые строки будут отфильтрованы.
Пробелы нам также не понадобятся, поэтому мы можем их отфильтровать:
'( ('.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.trim().length);
// ==> ["(", "("]Вторая большая проблема с baz)) в качестве последнего токена вот пример:
'(foo bar (baz))'.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.trim().length);
// ==> ["(", "foo", "bar", "(", "baz))"]Проблема в выражении \S+, которое является жадным и соответствует всему, кроме пробела. Чтобы решить эту проблему, мы можем использовать это выражение: [^\s()]+.
Он будет соответствовать всему, что не является пробелом и круглыми скобками (то же самое, что \S+, но в скобках).
(foo bar (baz))'.split(/(\(|\)|\n|\s+|[^\s()]+)/).filter(token => token.trim().length);
// ==> ["(", "foo", "bar", "(", "baz", ")", ")"]Как видите, вывод правильный. Давайте напишем этот токенизатор как функцию:
const tokens_re = /(\(|\)|\n|\s+|[^\s()]+)/;
function tokenize(string) {
string = string.trim();
if (!string.length) {
return [];
}
return string.split(tokens_re).filter(token => token.trim());
}Нам не нужно использовать длину после token.trim(), поскольку пустая строка также преобразуется в значение false, и фильтр удалит эти значения.
А как насчет строковых выражений (те, что в кавычках)? Посмотрим, что произойдет:
tokenize(`(define (square x)
"Function calculate square of a number"
(* x x))`);
// ==> ["(", "define", "(", "square", "x", ")", "\"Function", "calculate", "square",
// ==> "of", "a", "number\"", "(", "*", "x", "x", ")", ")"]ПРИМЕЧАНИЕ. Это функция на диалекте Scheme Lisp. Мы использовали литералы шаблонов, чтобы мы могли добавлять символы новой строки внутри кода Lisp.
Как видно из вывода, все отдельные строки разделены пробелами. Давайте это исправим:
Регулярные выражения для строк
Нам нужно добавить строковые литералы в качестве исключения в наш токенизатор. Лучшим является первый элемент объединения в нашем регулярном выражении.
Выражение, обрабатывающее строковые литералы, выглядит следующим образом:
/"[^"\\]*(?:\\[\S\s][^"\\]*)*"/Он обрабатывает экранированные кавычки внутри строки.
Вот как должно выглядеть полное регулярное выражение:
const tokens_re = /("[^"\\]*(?:\\[\S\s][^"\\]*)*"|\(|\)|\n|\s+|[^\s()]+)/;ПРИМЕЧАНИЕ. Мы также можем добавлять комментарии Lisp, но поскольку это не синтаксический анализатор Lisp, а S-выражение, мы не будем этого делать здесь. JSON также не поддерживает комментарии. Если вы хотите создать парсер Lisp, вы можете добавить их в качестве упражнения.
Наш токенайзер теперь работает корректно:
tokenize(`(define (square x)
"Function calculate square of a number"
(* x x))`);
// ==> ["(", "define", "(", "square", "x", ")",
// ==> "\"Function calculate square of a number\"",
// ==> "(", "*", "x", "x", ")", ")"]Парсер
Мы создадим наш парсер, используя структуру данных стека (LIFO — Last In First Out).
Чтобы полностью понять, как работает синтаксический анализатор, полезно знать о структурах данных, таких как связанные списки, двоичные деревья и стеки.
Вот первая версия нашего парсера:
function parse(string) {
const tokens = tokenize(string);
const result = []; // as normal array
const stack = []; // as stack
tokens.forEach(token => {
if (token == '(') {
stack.push([]); // add new list to stack
} else if (token == ')') {
if (stack.length) {
// top of the stack is already constructed list
const top = stack.pop();
if (stack.length) {
// add constructed list to previous list
var last = stack[stack.length - 1];
last.push(top);
} else {
result.push(top); // fully constructed list
}
} else {
throw new Error('Syntax Error - unmached closing paren');
}
} else {
// found atom add to the top of the stack
// top is used as an array we only add at the end
const top = stack[stack.length - 1];
top.push(token);
}
});
if (stack.length) {
throw new Error('Syntax Error - expecting closing paren');
}
return result;
}Функция возвращает массив наших структур в виде массивов. Если нам нужно для анализа более одного S-выражения у нас будет больше элементов в массиве:
parse(`(1 2 3) (1 2 3)`)
// ==> [["1", "2", "3"], ["1", "2", "3"]]Хотя нам не нужно обрабатывать точки, S-выражения могут иметь следующую форму:
((foo . 10) (bar . 20))Нам не нужно создавать специальную структуру для наших списков, чтобы иметь работающий анализатор. Но было бы неплохо иметь эту структуру с самого начала (чтобы вы могли использовать ее как основу для интерпретатора Лиспа). Мы будем использовать класс Pair, поэтому мы сможем создать любое двоичное дерево.
class Pair {
constructor(head, tail) {
this.head = head;
this.tail = tail;
}
}Нам также понадобится что-то, что будет обозначать конец списка (или пустой список). В языке Лисп оно обычно равно nil:
class Nil {}
const nil = new Nil();Мы можем создать статический метод, который преобразует массив в нашу структуру:
class Pair {
constructor(head, tail) {
this.head = head;
this.tail = tail;
}
static fromArray(array) {
if (!array.length) {
return nil;
}
let [head, ...rest] = array
if (head instanceof Array) {
head = Pair.fromArray(head);
}
return new Pair(head, Pair.fromArray(rest));
}
}Чтобы добавить это в наш парсер, все, что нам нужно сделать, это добавить его в конце:
result.map(Pair.fromArray);ПРИМЕЧАНИЕ. Если вы захотите добавить оператор точки позже, вам нужно будет создать пары вручную внутри синтаксического анализатора.
Мы не преобразовывали весь массив, поскольку он будет контейнером для наших S-выражений. Каждый элемент массива должен быть списком, поэтому мы использовали Array::map.
Давайте посмотрим, как это работает:
parse('(1 (1 2 3))')Результатом будет такая структура (это результат JSON.stringify со вставленным значением nil).
{
"head": "1",
"tail": {
"head": {
"head": "1",
"tail": {
"head": "2",
"tail": {
"head": "3",
"tail": nil
}
}
},
"tail": nil
}
}Последнее, что мы можем добавить, — это stringify список в строку, добавив метод toString в наш класс Pair:
class Pair {
constructor(head, tail) {
this.head = head;
this.tail = tail;
}
toString() {
const arr = ['('];
if (this.head) {
const value = this.head.toString();
arr.push(value);
if (this.tail instanceof Pair) {
// replace hack for the nested list
// because the structure is a tree
// and here tail is next element
const tail = this.tail.toString().replace(/^\(|\)$/g, '');
arr.push(' ');
arr.push(tail);
}
}
arr.push(')');
return arr.join('');
}
static fromArray(array) {
// ... same as before
}
}Давайте посмотрим, как это работает:
parse("(1 (1 2 (3)))")[0].toString()
// ==> "(1 (1 2 (3)))"Последняя проблема заключается в том, что в выходной структуре нет чисел. Все представляет собой строку.
Разбор атомов
Мы будем использовать регулярные выражения ниже:
const int_re = /^[-+]?[0-9]+([eE][-+]?[0-9]+)?$/;
const float_re = /^([-+]?((\.[0-9]+|[0-9]+\.[0-9]+)([eE][-+]?[0-9]+)?)|[0-9]+\.)$/;
if (atom.match(int_re) || atom.match(float_re)) {
// in javascript every number is float but if it's slow you can use parseInt for int_re
return parseFloat(atom);
}Далее мы можем анализировать строки. Наши строки почти такие же, как в JSON, с той лишь разницей, что они могут иметь символы новой строки (обычно именно так строки обрабатываются в диалектах Лиспа). Таким образом, мы можем использовать JSON.parse и заменять \n только на \\n (экранировать новую строку).
if (atom.match(/^".*"$/)) {
return JSON.parse(atom.replace(/\n/g, '\\n'));
}Таким образом, мы можем бесплатно использовать все escape-символы (то есть: \t или символы Юникода \u).
Следующим элементом S-выражений являются символы. Это любые последовательности символов, которые не являются числами или строками. Мы можем создать класс LSymbol, чтобы отличать Symbol от JavaScript.
class LSymbol {
constructor(name) {
this.name = name;
}
toString() {
return this.name;
}
}Функция разбора атомов может выглядеть так:
function parseAtom(atom) {
if (atom.match(int_re) || atom.match(float_re)) { // numbers
return parseFloat(atom);
} else if (atom.match(/^".*"$/)) {
return JSON.parse(atom.replace(/\n/g, '\\n')); // strings
} else {
return new LSymbol(atom); // symbols
}
}Наша функция парсера с добавлением parseAtom:
function parse(string) {
const tokens = tokenize(string);
const result = [];
const stack = [];
tokens.forEach(token => {
if (token == '(') {
stack.push([]);
} else if (token == ')') {
if (stack.length) {
const top = stack.pop();
if (stack.length) {
const last = stack[stack.length - 1];
last.push(top);
} else {
result.push(top);
}
} else {
throw new Error('Syntax Error - unmached closing paren');
}
} else {
const top = stack[stack.length - 1];
top.push(parseAtom(token)); // this line was added
}
});
if (stack.length) {
throw new Error('Syntax Error - expecting closing paren');
}
return result.map(Pair.fromArray);
}Мы также можем улучшить метод toString в Pair, чтобы использовать JSON.stringify для отличия строк от символов:
class Pair {
constructor(head, tail) {
this.head = head;
this.tail = tail;
}
toString() {
const arr = ['('];
if (this.head) {
let value;
if (typeof this.head === 'string') {
value = JSON.stringify(this.head).replace(/\\n/g, '\n');
} else {
// any object including Pair and LSymbol
value = this.head.toString();
}
arr.push(value);
if (this.tail instanceof Pair) {
// replace hack for the nested list because
// the structure is a tree and here tail
// is next element
const tail = this.tail.toString().replace(/^\(|\)$/g, '');
arr.push(' ');
arr.push(tail);
}
}
arr.push(')');
return arr.join('');
}
static fromArray(array) {
// ... same as before
}
}И это целый парсер. Остаются значения true и false (и, возможно, null), но они оставлены в качестве упражнения для читателя. Полный код можно найти на GitHub.
Различные подходы к парсеру Lisp в JavaScript
Приведенный выше код хорош для простой реализации на Lisp. Я использовал код, аналогичный исходной реализации схемы LIPS, которую до сих пор можно найти на CodePen.
Сейчас LIPS использует более продвинутый лексер (с использованием конечного автомата) вместо токенизатора. Лексер был переписан, поскольку подход со стеком было слишком сложно модифицировать.
