роект: язык программирования
То, что проверяет и определяет смысл выражений в языке программирования, является в свою очередь просто программой.
Хэл Абельсон и Жеральд Сасман, «Структура и интерпретация компьютерных программ».
Когда ученик спросил учителя о природе цикла Данных и Контроля, Юань-Ма ответил: «Подумай о компиляторе, компилирующем самого себя».
Мастер Юань-Ма, «Книга программирования»
Создать свой язык программирования удивительно легко (пока вы не ставите запредельных целей) и довольно поучительно.
Главное, что я хочу продемонстрировать в этой главе – в построении языка нет никакой магии. Мне часто казалось, что некоторые человеческие изобретения настолько сложны и заумны, что мне их никогда не понять. Однако после небольшого самообразования и ковыряния такие штуки часто оказываются довольно обыденными.
Мы построим язык программирования Egg (Яйцо). Он будет небольшим, простым, но достаточно мощным для выражения любых расчётов. Он также будет осуществлять простые абстракции, основанные на функциях.
Разбор (parsing)
То, что лежит на поверхности языка – синтаксис, запись. Грамматический анализатор, или парсер – программа, читающая кусок текста и выдающая структуру данных, описывающую структуры программы, содержавшейся в тексте. Если текст не описывает корректную программу, парсер должен пожаловаться и указать на ошибку.
У нашего языка будет простой и однородный синтаксис. В Egg всё будет являться выражением. Выражение может быть переменной, число, строка или приложение. Приложения используются для вызова функций и конструкций типа if или while.
Для упрощения парсинга строки в Egg не будут поддерживать обратных слешей и подобных вещей. Строка – просто последовательность символов, не являющихся двойными кавычками, заключённая в двойные кавычки. Число – последовательность цифр. Имена переменных могут состоять из любых символов, не являющихся пробелами и не имеющих специального значения в синтаксисе.
Приложения записываются так же, как в JS — при помощи скобок после выражения и с любым количеством аргументов в скобках, разделённых запятыми.
do(define(x, 10),
if((x, 5),
print("много"),
print("мало")))
Однородность языка означает, что то, что в JS является операторами, применяется так же, как и остальные функции. Так как в синтаксисе нет концепции блоков, нам нужна конструкция do для обозначения нескольких вещей, выполняемых последовательно.
Структура данных, описывающая программу, будет состоять из объектов выражений, у каждого из которых будет свойство type, отражающее тип этого выражения и другие свойства, описывающие содержимое.
Выражения типа “value” представляют строки или числа. Их свойство value содержит строку или число, которое они представляют. Выражения типа “word” используются для идентификаторов (имён). У таких объектов есть свойство name, содержащее имя идентификатора в виде строки. И наконец, выражения “apply” представляют приложения. У них есть свойство “operator”, ссылающееся на применяемое выражение, и свойство “args” с массивом аргументов.
Часть (x, 5) будет представлена так:
{
type: "apply",
operator: {type: "word", name: ""},
args: [
{type: "word", name: "x"},
{type: "value", value: 5}
]
}
Такая структура данных называется синтаксическим деревом. Если вы представите объекты в виде точек, а связи между ними в виде линий, то получите древовидную структуру. То, что выражения содержат другие выражения, которые в свою очередь могут содержать свои выражения, сходно с тем, как разветвляются ветки.
Структура синтаксического дерева
Сравните это с парсером, написанным нами для файла настроек в главе 9, у которого была простая структура: он делил ввод на строки и обрабатывал их одну за другой. Там было всего несколько форм, которые разрешено принимать строке.
Здесь нам нужен другой подход. Выражения не разделяются на строчки, и их структура рекурсивна. Выражения-приложения содержат другие выражения. К счастью, эта задача элегантно решается применением рекурсивной функции, отражающей рекурсивность языка.
Мы определяем функцию parseExpression, принимающую строку на вход и возвращающую объект, содержащий структуру данных для выражения с начала строки, вместе с частью строки, оставшейся после парсинга. При разборе подвыражений (таких, как аргумент приложения), эта функция снова вызывается, возвращая выражение аргумента вместе с оставшимся текстом. Тот текст может, в свою очередь, содержать ещё аргументы, или же быть закрывающей скобкой, завершающей список аргументов.
Первая часть парсера:
function parseExpression(program) {
program = skipSpace(program);
var match, expr;
if (match = /^"([^"]*)"/.exec(program))
expr = {type: "value", value: match[1]};
else if (match = /^\d+\b/.exec(program))
expr = {type: "value", value: Number(match[0])};
else if (match = /^[^\s(),"]+/.exec(program))
expr = {type: "word", name: match[0]};
else
throw new SyntaxError("Неожиданный синтаксис: " + program);
return parseApply(expr, program.slice(match[0].length));
}
function skipSpace(string) {
var first = string.search(/\S/);
if (first == -1) return "";
return string.slice(first);
}
Поскольку Egg разрешает любое количество пробелов в элементах, нам надо постоянно вырезать пробелы с начала строки. С этим справляется skipSpace.
Пропустив начальные пробелы, parseExpression использует три регулярки для распознавания трёх простых (атомарных) элементов, поддерживаемых языком: строк, чисел и слов. Парсер создаёт разные структуры для разных типов. Если ввод не подходит ни под одну из форм, это не является допустимым выражением, и он выбрасывает ошибку. SyntaxError – стандартный объект для ошибок, который создаётся при попытке запуска некорректной программы JavaScript.
Мы можем отрезать обработанную часть программы, и передать его, вместе с объектом выражения, в parseApply, определяющая, не является ли выражение приложением. Если так и есть, он парсит список аргументов в скобках.
function parseApply(expr, program) {
program = skipSpace(program);
if (program[0] != "(")
return {expr: expr, rest: program};
program = skipSpace(program.slice(1));
expr = {type: "apply", operator: expr, args: []};
while (program[0] != ")") {
var arg = parseExpression(program);
expr.args.push(arg.expr);
program = skipSpace(arg.rest);
if (program[0] == ",")
program = skipSpace(program.slice(1));
else if (program[0] != ")")
throw new SyntaxError("Ожидается ',' or ')'");
}
return parseApply(expr, program.slice(1));
}
Если следующий символ программы – не открывающая скобка, то это не приложение, и parseApply просто возвращает данное ей выражение.
В ином случае, она пропускает открывающую скобку и создаёт объект синтаксического дерева для этого выражения. Затем она рекурсивно вызывает parseExpression для разбора каждого аргумента, пока не встретит закрывающую скобку. Рекурсия непрямая, parseApply и parseExpression вызывают друг друга.
Поскольку приложение само по себе может быть выражением (multiplier(2)(1)), parseApply должна, после разбора приложения, вызвать себя снова, проверив, не идёт ли далее другая пара скобок.
Вот и всё, что нам нужно для разбора Egg. Мы обернём это в удобную функцию parse, проверяющую, что она дошла до конца строки после разбора выражения (программа Egg – это одно выражение), и это даст нам структуру данных программы.
function parse(program) {
var result = parseExpression(program);
if (skipSpace(result.rest).length 0)
throw new SyntaxError("Неожиданный текст после программы");
return result.expr;
}
console.log(parse("+(a, 10)"));
// → {type: "apply",
// operator: {type: "word", name: "+"},
// args: [{type: "word", name: "a"},
// {type: "value", value: 10}]}
Работает! Она не выдаёт полезной информации при ошибке, и не хранит номера строки и столбца, с которых начинается каждое выражение, что могло бы пригодиться при разборе ошибок – но для нас и этого хватит.
Интерпретатор
А что нам делать с синтаксическим деревом программы? Запускать её! Этим занимается интерпретатор. Вы даёте ему синтаксическое дерево и объект окружения, который связывает имена со значениями, а он интерпретирует выражение, представляемое деревом, и возвращает результат.
function evaluate(expr, env) {
switch(expr.type) {
case "value":
return expr.value;
case "word":
if (expr.name in env)
return env[expr.name];
else
throw new ReferenceError("Неопределённая переменная: " +
expr.name);
case "apply":
if (expr.operator.type == "word" &&
expr.operator.name in specialForms)
return specialForms[expr.operator.name](expr.args,
env);
var op = evaluate(expr.operator, env);
if (typeof op != "function")
throw new TypeError("Приложение не является функцией.");
return op.apply(null, expr.args.map(function(arg) {
return evaluate(arg, env);
}));
}
}
var specialForms = Object.create(null);
У интерпретатора есть код для каждого из типов выражений. Для литералов он возвращает их значение. Например, выражение 100 интерпретируется в число 100. У переменной мы должны проверить, определена ли она в окружении, и если да – запросить её значение.
С приложениями сложнее. Если это особая форма типа if, мы ничего не интерпретируем, а просто передаём аргументы вместе с окружением в функцию, обрабатывающую форму. Если это простой вызов, мы интерпретируем оператор, проверяем, что это функция и вызываем его с результатом интерпретации аргументов.
Для представления значений функций Egg мы будем использовать простые значения функций JavaScript. Мы вернёмся к этому позже, когда определим специальную форму fun.
+
Рекурсивная структура интерпретатора напоминает парсер. Оба отражают структуру языка. Можно было бы интегрировать парсер в интерпретатор и интерпретировать во время разбора, но их разделение делает программу более читаемой.
Вот и всё, что нужно для интерпретации Egg. Вот так просто. Но без определения нескольких специальных форм и добавления полезных значений в окружение, вы с этим языком ничего не сможете сделать.
504
85 027 
