Пропустив начальные пробелы, 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. Вот так просто. Но без определения нескольких специальных форм и добавления полезных значений в окружение, вы с этим языком ничего не сможете сделать.
Специальные формы
Объект specialForms используется для определения особого синтаксиса Egg. Он сопоставляет слова с функциями, интерпретирующими эти специальные формы. Пока он пуст. Давайте добавим несколько форм.
specialForms["if"] = function(args, env) {
if (args.length != 3)
throw new SyntaxError("Неправильное количество аргументов для if");
if (evaluate(args[0], env) !== false)
return evaluate(args[1], env);
else
return evaluate(args[2], env);
};
Конструкция if языка Egg ждёт три аргумента. Она вычисляет первый, и если результат не false, вычисляет второй. В ином случае вычисляет третий. Этот if больше похож на тернарный оператор ?:. Это выражение, а не инструкция, и она выдаёт значение, а именно, результат второго или третьего выражения.
Egg отличается от JavaScript тем, как он обрабатывает условие if. Он не будет считать ноль или пустую строку за false.
if представлено в виде особой формы а не обычной функции, потому что аргументы функций вычисляются перед вызовом, а if должен интерпретировать один из двух аргументов – второй или третий, в зависимости от значения первого.
Форма для while схожая.
specialForms["while"] = function(args, env) {
if (args.length != 2)
throw new SyntaxError("Неправильное количество аргументов для while");
while (evaluate(args[0], env) !== false)
evaluate(args[1], env);
// Поскольку undefined не задано в Egg,
// за отсутствием осмысленного результата возвращаем false
return false;
};
Ещё одна основная часть языка – do, выполняющий все аргументы сверху вниз. Его значение – это значение, выдаваемое последним аргументом.
specialForms["do"] = function(args, env) {
var value = false;
args.forEach(function(arg) {
value = evaluate(arg, env);
});
return value;
};
Чтобы создавать переменные и давать им значения, мы создаём форму define. Она ожидает word в качестве первого аргумента, и выражение, производящее значение, которое надо присвоить этому слову в качестве второго. define, как и всё, является выражением, поэтому оно должно возвращать значение. Пусть оно возвращает присвоенное значение (прямо как оператор = в JavaScript).
specialForms["define"] = function(args, env) {
if (args.length != 2 || args[0].type != "word")
throw new SyntaxError("Bad use of define");
var value = evaluate(args[1], env);
env[args[0].name] = value;
return value;
};
Окружение
Окружение, принимаемое интерпретатором — это объект со свойствами, чьи имена соответствуют именам переменных, а значения – значениям этих переменных. Давайте определим объект окружения, представляющий глобальную область видимости.
Для использования конструкции if мы должны создать булевские значения. Так как их всего два, особый синтаксис для них не нужен. Мы просто делаем две переменные со значениями true и false.
var topEnv = Object.create(null);
topEnv["true"] = true;
topEnv["false"] = false;
Теперь мы можем вычислить простое выражение, меняющее булевское значение на обратное.
var prog = parse("if(true, false, true)");
console.log(evaluate(prog, topEnv)); // → false
Для поддержки простых арифметических операторов и сравнения мы добавим несколько функций в окружение. Для упрощения кода мы будем использовать new Function для создания набора функций-операторов в цикле, а не определять их все по отдельности.
