Структура синтаксического дерева

Сравните это с парсером, написанным нами для файла настроек в главе 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+/.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}]}

Работает! Она не выдаёт полезной информации при ошибке, и не хранит номера строки и столбца, с которых начинается каждое выражение, что могло бы пригодиться при разборе ошибок – но для нас и этого хватит.