Как реализовать язык программирования на JavaScript. Часть 1: Парсер14.03.2019 15:34

Здравствуйте! Представляю вам любительский перевод руководства реализации своего языка программирования на JavaScript — PL Tutorial.

Мы создадим свой язык программирования — λзык (в оригинале — λanguage). В процессе создания мы будем использовать достаточно много интересных техник, таких как рекурсивный спуск, стиль передачи управления, базовые техники оптимизации. Будет создано две версии интерпретатора — обычный и CPS-интерпретатор, транс-компилятор в JavaScript.

Автор оригинала — Mihai Bazon, автор известной библиотеки UglifyJS (инструмент для минимизации и форматирования JS-кода).

Если вы когда-нибудь писали свой компилятор или интерпретатор, то здесь не будет ничего нового для вас. Но если вы используете регулярные выражения, чтобы «распарсить» что-либо, что выглядит как язык программирования, то прочитайте секцию про парсинг. Давайте писать код, в котором меньше багов!

Статья разделена на части в порядке «от простого к сложному». Я не рекомендую вам пропускать части статьи, кроме случая, когда вы хорошо понимаете тему. Вы всегда можете вернуться назад, если вы не понимаете что-то.

Что мы собираемся выучить:

• Что такое парсер, и как его написать.
• Как написать интерпретатор.
• Передача продолжения, и почему это важно.
• Написание (транс-)компилятора.
• Стиль передачи продолжения.
• Несколько базовых техник оптимизации кода.
• Примеры, что в нашем λзыке нового по сравнению с JavaScript.

Вместе с этим я покажу, почему Lisp — великий язык программирования. Тем не менее, язык, над которым мы работаем не является Lisp. У него богаче синтаксис (классическая инфиксная нотация, которую все знают), примерно такой, как Scheme (кроме макросов). Хорошо, или нет, но макросы это главная фича Lisp — то, чего другие языки (кроме диалектов Lisp) не могут сделать так хорошо, как он. (Да, я знаю про SweetJS… близко, но не то.)

Но сначала давайте представим наш язык программирования.

Перед тем, как что-то делать, у нас должна быть четкая картина того, что мы хотим сделать. Неплохо было бы написать описание грамматики языка, но я собираюсь сделать проще — написать пример простой программы, так что вот примеры λзыка:

# это комментарий

println("Hello World!");

println(2 + 3 * 4);

# функции создаются с помощью ключевых слов `lambda` или `λ`
fib = lambda (n) if n < 2 then n else fib(n - 1) + fib(n - 2);

println(fib(15));

print-range = λ(a, b)             # `λ` это одно и то же, что и `lambda`
                if a <= b then {  # `then` здесь опционален, как вы можете увидеть ниже
                  print(a);
                  if a + 1 <= b {
                    print(", ");
                    print-range(a + 1, b);
                  } else println("");        # новая строка
                };
print-range(1, 5);

Вывод:

Hello World!
14
610
1, 2, 3, 4, 5

λзык выглядит похожим на JavaScript, но в целом это не так. Во-первых, здесь нет инструкций (statements), только выражения. Выражение должно возвращать значение и может быть использовано в любом месте другого выражения. Точки с запятой нужны, чтобы разделить выражения в «последовательности» выражений. Фигурные скобки { и } создают такую последовательность, которая сама является выражением, а её значение — последнее значение из последовательности. Следующая программа правильная:

a = {
  fib(10);  # не имеет побочных эффектов, но вызывается в любом случае
  fib(15)   # последняя точка с запятой не является обязательной
};
print(a); # выводит 610

Функции создаются с помощью ключевых слов lambda или λ. После этого в скобках идет (возможно пустой) список названий аргументов, разделенных запятой. Тело функции — одно выражение, но может быть заключено в последовательность {...}. Также стоит заметить, что нет ключевого слова return. Функция возвращает значение последнего выражения.

Также, нет var. Для того, чтобы добавить переменную вы можете использовать то, что JavaScript-программисты называют IIFE. Используйте lambda, объявите переменные как аргументы. У переменных область видимости — функция, а функции — замыкания, как в JavaScript [прим. перевод.: до ES6.].

Даже if является выражением. В JavaScript для этого используется тернарный оператор:

a = foo() ? bar() : baz();           // JavaScript
a = if foo() then bar() else baz();  # λзык

Ключевое слово this не обязательное, если ветка является последовательностью ({...}), как вы могли видеть выше. В другом случае оно необходимо. else используется в случае, если присутствует альтернативная ветка. И снова, then и else принимают выражение, как тело, но вы можете объединить несколько выражений в одно, используя {...}. Если else отсутствует, и условие равно false, то и результат всего if является false. Стоит заметить, что false это ключевое слово, представляющее значение, которое является единственным ложным значением в λзыке:

if foo() then print("OK");

выведет OK тогда, и только тогда, когда результат foo() не является false. Также, есть ключевое слово true, но абсолютно все, что не является false (в рамках JavaScript, оператор ===) будет считаться как true в ветвлениях (включая число 0 и пустую строку "").

Заметьте, что нет нужды в скобках вокруг выражения в if. Если вы добавите их, это не будет ошибкой, потому, что ( начинает выражение, но они просто лишние.

Вся программа может быть распарсена даже, если её окружить круглыми скобками, поэтому вы должны добавлять ; после каждого выражения. Последнее выражения является исключением.

Отлично, это наш маленький λзык. Он не является идеальным. Синтаксис выглядит красивым, но в нём есть недостатки. Есть много отсутствующих возможностей, таких, как объекты и массивы. Мы на них не обращаем внимание, так как они не являются основными для нашего просто языка программирования.

Дальше, мы напишем парсер для нашего языка.

Создание парсера это сложная задача. По сути, он должен брать кусок кода и превращать его в AST (абстрактное синтаксическое дерево). AST — структурированное представление программы в памяти, абстрактное — потому, что оно не содержит полной информации о коде, только семантику. Описание AST находится в отдельной части.

Например, у нас есть следующий код:

sum = lambda(a, b) {
  a + b;
};
print(sum(1, 2));

Наш парсер будет генерировать дерево, как JavaScript объект:

{
  type: "prog",
  prog: [
    // первая строка:
    {
      type: "assign",
      operator: "=",
      left: { type: "var", value: "sum" },
      right: {
        type: "lambda",
        vars: [ "a", "b" ],
        body: {
          // тело должно было быть "prog", но потому, что
          // оно содержит только одно выражение, парсер
          // превратил его в само выражение.
          type: "binary",
          operator: "+",
          left: { type: "var", value: "a" },
          right: { type: "var", value: "b" }
        }
      }
    },
    // вторая строка:
    {
      type: "call",
      func: { type: "var", value: "print" },
      args: [{
        type: "call",
        func: { type: "var", value: "sum" },
        args: [ { type: "num", value: 1 },
                { type: "num", value: 2 } ]
      }]
    }
  ]
}

Основная сложность в создании парсера состоит в сложности правильно организовать код. Парсер должен работать на более высоком уровне, чем чтение символов из строки. Несколько рекомендаций, чтобы уменьшить сложность кода:

• Писать много небольших функций. В каждой функции делать одну вещь и делать её хорошо.
• Не пробовать использовать регулярных выражений для парсинга. Они просто не работают. Они могут быть полезными в лексическом анализаторе, но, для простоты, мы их использовать не будем.
• Не пробовать угадывать. Когда не уверены, как распарсить что-то, бросать исключение, содержащее местоположение ошибки (строка и колонка).

Чтобы оставлять код проще, мы его разделим на три части, которые в свою очередь разделены на много маленьких функций:

Это самая простая часть. Мы создадим объект «потока», который будет представлять операции последовательного чтения символов из строки. Он содержит четыре функции:

• peek() — возвращает следующий символ, не извлекая его из потока.
• next() — возвращает следующий символ, извлекая его из потока.
• eof() — возвращает true, если больше нет символов в потоке.
• croak(msg) — бросает исключение, содержащее сообщение (msg) и текущее положение в потоке.

Последняя функция нужна для того, чтобы можно было просто бросать исключение, содержащее местоположение ошибки.

Вот весь код этого объекта (назовем его InputStream). Он достаточно мал, так что у вас не должно быть проблем с ним:

function InputStream(input) {
    var pos = 0, line = 1, col = 0;
    return {
        next  : next,
        peek  : peek,
        eof   : eof,
        croak : croak,
    };
    function next() {
        var ch = input.charAt(pos++);
        if (ch == "\n") line++, col = 0; else col++;
        return ch;
    }
    function peek() {
        return input.charAt(pos);
    }
    function eof() {
        return peek() == "";
    }
    function croak(msg) {
        throw new Error(msg + " (" + line + ":" + col + ")");
    }
}

Обратите внимание, что это не обычный объект (который создается через new). Чтобы получить этот объект, нужно: var stream = InputStream(string).

Дальше мы напишем следующий уровень абстракции: Поток токенов (лексем).

Токенизатор (лексер) использует поток символов и возвращает объект с таким же интерфейсом, но возвращаемые значения функций peek()/next() будут токенами. Токен — тип с двумя свойствами: type, value. Вот несколько примеров токенов:

{ type: "punc", value: "(" }           // спец. символы: скобки, комма, точка с запятой и т. д.
{ type: "num", value: 5 }              // числа
{ type: "str", value: "Hello World!" } // строки
{ type: "kw", value: "lambda" }        // ключевые слова
{ type: "var", value: "a" }            // идентификаторы
{ type: "op", value: "!=" }            // операторы

Пробельные символы (пробел, табуляция, переносы строк) и комментарии просто пропускаются.

Чтобы написать токенизатор, нам нужно внимательнее посмотрать на наш язык. Идея в том, чтобы заметить, что в зависимости от текущего символа (input.peek()) мы можем решить, какой токен нужно читать:

• Во первых, пропускать пробельные символы.
• Если input.eof(), то возвращать null.
• Если это символ #, то пропускать все символы до конца строки (и возвратить следующий токен).
• Если это кавычка, то считываем строку.
• Если это цифра, то считываем число.
• Если это буква, то считываем слово, и возвращаем либо идентификатор, либо ключевое слово.
• Если это один из специальных символов, то возвращаем соответствующий токен.
• Если это один из символов операторов, то возвращаем соответствующий токен.
• Если ничего из выше сказанного не подходит, то бросаем исключение, используя input.croak().

У нас будет функция read_next, основная функция токенизатора:

function read_next() {
    read_while(is_whitespace);
    if (input.eof()) return null;
    var ch = input.peek();
    if (ch == "#") {
        skip_comment();
        return read_next();
    }
    if (ch == '"') return read_string();
    if (is_digit(ch)) return read_number();
    if (is_id_start(ch)) return read_ident();
    if (is_punc(ch)) return {
        type  : "punc",
        value : input.next()
    };
    if (is_op_char(ch)) return {
        type  : "op",
        value : read_while(is_op_char)
    };
    input.croak("Can't handle character: " + ch);
}

Здесь можно заметить много дополнительных функций, которые возвращают разные типы токенов, такие, как read_string(), read_number() и т. д… Они вынесены в отдельные функции, так что код выглядит проще и красивее.

Также, интересно то, что мы не забираем все символы сразу: каждый раз, когда парсер будет просить следующий токен, мы будем читать один токен. Если случиться какая-то ошибка, мы даже не прочитаем все символы.

read_ident() прочитает все символы подряд, которые могут быть частью идентификатора (is_id()). Идентификатор должен начинаться с буквы, λ, или _, и могут содержать эти же символы, числа, или любые из: ?!-<>=. Из этого следует, что foo-bar не будет прочитан, как три токена, а как один (var-токен). Это нужно для того, чтобы можно было определять функции с такими названиями, как is-pair? или string>= (извините, это Лиспер во мне).

Также, read_ident() будет проверять, есть ли идентификатор в списке известных ключевых слов, и если он там есть, будет возвращен kw-токен, вместо var-токена.

Я думаю, код говорит сам за себя, так что вот готовый токенизатор для нашего языка:

function TokenStream(input) {
    var current = null;
    var keywords = " if then else lambda λ true false ";
    return {
        next  : next,
        peek  : peek,
        eof   : eof,
        croak : input.croak
    };
    function is_keyword(x) {
        return keywords.indexOf(" " + x + " ") >= 0;
    }
    function is_digit(ch) {
        return /[0-9]/i.test(ch);
    }
    function is_id_start(ch) {
        return /[a-zλ_]/i.test(ch);
    }
    function is_id(ch) {
        return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch) >= 0;
    }
    function is_op_char(ch) {
        return "+-*/%=&|<>!".indexOf(ch) >= 0;
    }
    function is_punc(ch) {
        return ",;(){}[]".indexOf(ch) >= 0;
    }
    function is_whitespace(ch) {
        return " \t\n".indexOf(ch) >= 0;
    }
    function read_while(predicate) {
        var str = "";
        while (!input.eof() && predicate(input.peek()))
            str += input.next();
        return str;
    }
    function read_number() {
        var has_dot = false;
        var number = read_while(function(ch){
            if (ch == ".") {
                if (has_dot) return false;
                has_dot = true;
                return true;
            }
            return is_digit(ch);
        });
        return { type: "num", value: parseFloat(number) };
    }
    function read_ident() {
        var id = read_while(is_id);
        return {
            type  : is_keyword(id) ? "kw" : "var",
            value : id
        };
    }
    function read_escaped(end) {
        var escaped = false, str = "";
        input.next();
        while (!input.eof()) {
            var ch = input.next();
            if (escaped) {
                str += ch;
                escaped = false;
            } else if (ch == "\\") {
                escaped = true;
            } else if (ch == end) {
                break;
            } else {
                str += ch;
            }
        }
        return str;
    }
    function read_string() {
        return { type: "str", value: read_escaped('"') };
    }
    function skip_comment() {
        read_while(function(ch){ return ch != "\n" });
        input.next();
    }
    function read_next() {
        read_while(is_whitespace);
        if (input.eof()) return null;
        var ch = input.peek();
        if (ch == "#") {
            skip_comment();
            return read_next();
        }
        if (ch == '"') return read_string();
        if (is_digit(ch)) return read_number();
        if (is_id_start(ch)) return read_ident();
        if (is_punc(ch)) return {
            type  : "punc",
            value : input.next()
        };
        if (is_op_char(ch)) return {
            type  : "op",
            value : read_while(is_op_char)
        };
        input.croak("Can't handle character: " + ch);
    }
    function peek() {
        return current || (current = read_next());
    }
    function next() {
        var tok = current;
        current = null;
        return tok || read_next();
    }
    function eof() {
        return peek() == null;
    }
}

• Функция next() не всегда вызывает read_next(), потому, что может быть токен, который был считан раньше (с помощью функции peek()). Для этого у нас есть переменная current, которая содержит текущий токен.
• Поддерживаются только десятичные числа в обычной нотации (не поддерживаются 1E5, 0x и т. д.). Но если бы мы хотели добавить их поддержку, мы бы изменили только read_number().
• В отличие от JavaScript, единственные символы, которые не могут быть не экранированными в строке — кавычка и обратный слэш. Строки могут содержать переводы строк, символы табуляции и что-либо. Мы не интерпретируем стандартные комбинации, как \n, \t и т. д… Это очень просто переделать (read_string()).

Теперь у нас есть мощные инструменты, чтобы легко написать парсер, но сначала я б рекомендовал посмотреть описание AST.

Как указано выше, парсер буде строить структуру, которая показывает семантику программы. AST состоит из узлов (nodes). Каждый узел — обычный JavaScript объект, у которого есть свойство type, которое определяет тип узла, а также дополнительная информация, которая зависит от типа.

123.5

{ type: "num", value: 123.5 }

"Hello World"

{ type: "str", value: "Hello World!" }

true
false

{ type: "bool", value: true }
{ type: "bool", value: false }

foo

{ type: "var", value: "foo" }

lambda (x) 10   # или
λ (x) 10

{
  type: "lambda",
  vars: [ "x" ],
  body: { type: "num", value: 10 }
}

foo(a, 1)

{
  "type": "call",
  "func": { "type": "var", "value": "foo" },
  "args": [
    { "type": "var", "value": "a" },
    { "type": "num", "value": 1 }
  ]
}

if foo then bar else baz

{
  "type": "if",
  "cond": { "type": "var", "value": "foo" },
  "then": { "type": "var", "value": "bar" },
  "else": { "type": "var", "value": "baz" }
}

if foo then bar

{
  "type": "if",
  "cond": { "type": "var", "value": "foo" },
  "then": { "type": "var", "value": "bar" }
}

a = 10

{
  "type": "assign",
  "operator": "=",
  "left": { "type": "var", "value": "a" },
  "right": { "type": "num", "value": 10 }
}

x + y * z

{
  "type": "binary",
  "operator": "+",
  "left": { "type": "var", "value": "x" },
  "right": {
    "type": "binary",
    "operator": "*",
    "left": { "type": "var", "value": "y" },
    "right": { "type": "var", "value": "z" }
  }
}

{
  a = 5;
  b = a * 2;
  a + b;
}

{
  "type": "prog",
  "prog": [
    {
      "type": "assign",
      "operator": "=",
      "left": { "type": "var", "value": "a" },
      "right": { "type": "num", "value": 5 }
    },
    {
      "type": "assign",
      "operator": "=",
      "left": { "type": "var", "value": "b" },
      "right": {
        "type": "binary",
        "operator": "*",
        "left": { "type": "var", "value": "a" },
        "right": { "type": "num", "value": 2 }
      }
    },
    {
      "type": "binary",
      "operator": "+",
      "left": { "type": "var", "value": "a" },
      "right": { "type": "var", "value": "b" }
    }
  ]
}

let (a = 10, b = a * 10) {
  a + b;
}

{
  "type": "let",
  "vars": [
    {
      "name": "a",
      "def": { "type": "num", "value": 10 }
    },
    {
      "name": "b",
      "def": {
        "type": "binary",
        "operator": "*",
        "left": { "type": "var", "value": "a" },
        "right": { "type": "num", "value": 10 }
      }
    }
  ],
  "body": {
    "type": "binary",
    "operator": "+",
    "left": { "type": "var", "value": "a" },
    "right": { "type": "var", "value": "b" }
  }
}

Парсер будет строить дерево, которое описано выше.

Благодаря работе, которую мы проделали в токенизаторе, парсер работает с потоком токенов, вместо потока символов. Здесь все ещё есть много дополнительных функций, чтобы упростить структуру. Мы поговорим про основные из них. Давайте начнем с высокоуровневых, парсер функции:

function parse_lambda() {
    return {
        type: "lambda",
        vars: delimited("(", ")", ",", parse_varname),
        body: parse_expression()
    };
}

Эта функция будет вызвана, когда ключевое слово lambda уже было взято из потока токенов, так что нам осталось только взять названия аргументов. Но так, как они находятся в скобках и разделены запятыми, мы сделаем это с помощью функции delimited, которая принимает следующие аргументы: start, stop, separator, функция parser, которая парсит каждый элемент отдельно. В данном случае, мы используем функцию parse_varname, которая бросает ошибку, если заметит что-то, что выглядит не как переменная. Тело функции — выражение, так что мы его получаем с помощью parse_expression.

Функция delimited более низкоуровневая:

function delimited(start, stop, separator, parser) {
    var a = [], first = true;
    skip_punc(start);
    while (!input.eof()) {
        if (is_punc(stop)) break;
        if (first) first = false; else skip_punc(separator);
        if (is_punc(stop)) break; // последний разделитель может быть пропущен
        a.push(parser());
    }
    skip_punc(stop);
    return a;
}

Как вы можете заметить, она использует ещё больше функций: is_punc и skip_punc. Первая возвращает true, если текущий токен является заданным знаком пунктуации (не извлекая его), тогда как skip_punc проверит, является ли текущий токен заданным знаком и извлекает его (или бросает исключение в противном случае).

Функция, которая парсит целую программу, похоже, самая простая:

function parse_toplevel() {
    var prog = [];
    while (!input.eof()) {
        prog.push(parse_expression());
        if (!input.eof()) skip_punc(";");
    }
    return { type: "prog", prog: prog };
}

Так как у нас только выражения, мы просто вызываем parse_expression() и читаем выражения, пока не прочитаем все. Используя skip_punc(";"), мы делаем ; обязательной после каждого выражения.

Ещё один простой пример — parse_if():

function parse_if() {
    skip_kw("if");
    var cond = parse_expression();
    if (!is_punc("{")) skip_kw("then");
    var then = parse_expression();
    var ret = { type: "if", cond: cond, then: then };
    if (is_kw("else")) {
        input.next();
        ret.else = parse_expression();
    }
    return ret;
}

Она пропускает ключевое слово if (бросает исключение, если текущий токен — не ключевое слово if), читает условие используя parse_expression(). Если дальше не идет символ {, то требуется ключевое слово then (синтаксис выглядит не очень без этого). Ветки — просто выражения, поэтому мы просто снова используем parse_expression() для них. Ветка else не обязательная, поэтому мы сначала проверяем присутствие ключевого слово, перед тем, как парсить её.

Имея много маленьких функций, мы можем сделать код простым. Мы написали парсер почти так, как было б если использовали для этого высокоуровненый язык специально для разбора синтаксиса. Все эти функции «взаимо-рекурсивные», то-есть у нас есть parse_atom(), который в зависимости от текущего токена, вызывает другие функции. Одна из них — parse_if() (вызывается, когда текущий токен — if) и она в свою очередь вызывает parse_expression(). Но parse_expression() вызывает parse_atom(). Здесь нет бесконечной рекурсии потому, что одна из функций всегда извлекает хотя-бы один токен.

Этот вид метод парсинга называется Методом рекурсивного спуска, и по сути, самый простой в написании.

Более низкий уровень: parse_atom() и parse_expression().

Функция parse_atom() вызывает другую функцию, в зависимости от текущего токена:

function parse_atom() {
    return maybe_call(function(){
        if (is_punc("(")) {
            input.next();
            var exp = parse_expression();
            skip_punc(")");
            return exp;
        }
        if (is_punc("{")) return parse_prog();
        if (is_kw("if")) return parse_if();
        if (is_kw("true") || is_kw("false")) return parse_bool();
        if (is_kw("lambda") || is_kw("λ")) {
            input.next();
            return parse_lambda();
        }
        var tok = input.next();
        if (tok.type == "var" || tok.type == "num" || tok.type == "str")
            return tok;
        unexpected();
    });
}

Когда она видит открывающую скобку, тогда должно идти скобочное выражение, поэтому, пропуская скобку, функция вызывает parse_expression() и ожидает после этого пропустить закрывающую скобку. Если она видит какое-то ключевое слово, то она вызывает соответствующую функцию. Если она видит константу или идентификатор, то возвращает её как есть. И если ничего не подходит, то вызывает unexpected(), который бросает исключение.

Когда она видит {, то вызывает parse_prog, чтобы разобрать последовательность выражений. Также, parse_prog делает простую оптимизацию: если между { и } нет выражений, то она возвращает false, если только одно выражение, то возвращает только его. В противном случае возвращается узел prog с массивом выражений.

// мы собираемся использовать узел FALSE в нескольких местах,
// поэтому я делаю его глобальным.
var FALSE = { type: "bool", value: false };

function parse_prog() {
    var prog = delimited("{", "}", ";", parse_expression);
    if (prog.length == 0) return FALSE;
    if (prog.length == 1) return prog[0];
    return { type: "prog", prog: prog };
}

А вот и функция parse_expression(). В отличие от parse_atom(), она будет парсить как можно больше выражений, используя maybe_binary():

function parse_expression() {
    return maybe_call(function(){
        return maybe_binary(parse_atom(), 0);
    });
}

Функции maybe_*.

Эти функции проверяют, что идет после выражения и решают, обернуть выражение в свой узел, или вернуть его как есть.

Функция maybe_call() очень простая: она получает функция, которая парсит текущее выражение, и, если после выражения встречается (, то оно оборачивается в узер call. Заметьте, как delimited() подходит для парсинга списка аргументов:

function maybe_call(expr) {
    expr = expr();
    return is_punc("(") ? parse_call(expr) : expr;
}

function parse_call(func) {
    return {
        type: "call",
        func: func,
        args: delimited("(", ")", ",", parse_expression)
    };
}

Приоритет операторов.

Функция maybe_binary(left, my_prec) используется, чтобы объединять такие выражения, как 1 + 2 * 3. Суть в том, что, чтобы разобрать их правильно, нужно правильно определить приоритет операторов:

var PRECEDENCE = {
    "=": 1,
    "||": 2,
    "&&": 3,
    "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7,
    "+": 10, "-": 10,
    "*": 20, "/": 20, "%": 20,
};

Этот код значит, что * «сильнее», чем +, поэтому, выражение 1 + 2 * 3 будет прочитано как (1 + (2 * 3)) вместо ((1 + 2) * 3).

Суть в том, что прочитать только одно выражение (read_atom) и передать его в maybe_binary() (левое выражение), и приоритет текущего оператора (my_prec). Функция maybe_binary будет смотреть, что следует дальше. Если она не видит оператор, или у него приоритет ниже, тогда левое выражение просто возвращается.

Если это оператор, у которого приоритет выше, чем у текущего, тогда он оборачивается в новый узел с типом binary, левым выражением, и для правого выражения повторяется то же, но с новым приоритетом оператора (*):

function maybe_binary(left, my_prec) {
    var tok = is_op();
    if (tok) {
        var his_prec = PRECEDENCE[tok.value];
        if (his_prec > my_prec) {
            input.next();
            var right = maybe_binary(parse_atom(), his_prec) // (*);
            var binary = {
                type     : tok.value == "=" ? "assign" : "binary",
                operator : tok.value,
                left     : left,
                right    : right
            };
            return maybe_binary(binary, my_prec);
        }
    }
    return left;
}

Обратите внимание, перед тем, как мы возвращаем новый узел, мы также вызываем maybe_binary, передавая старый приоритет (my_prec), для того, чтобы обернуть выражение в ещё одно, если дальше идут ещё операторы. Если что-то непонятно, прочитайте код снова (возможно, попробуйте выполнить код в голове для некоторых выражений), пока он не станет понятным.

Также, следуя из того, что my_prec сразу равен 0, любой оператор будет пробовать создавать узел с типом binary (или assign для оператора =).

В парсере есть ещё несколько функций, которые я покажу ниже.

var FALSE = { type: "bool", value: false };
function parse(input) {
    var PRECEDENCE = {
        "=": 1,
        "||": 2,
        "&&": 3,
        "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7,
        "+": 10, "-": 10,
        "*": 20, "/": 20, "%": 20,
    };
    return parse_toplevel();
    function is_punc(ch) {
        var tok = input.peek();
        return tok && tok.type == "punc" && (!ch || tok.value == ch) && tok;
    }
    function is_kw(kw) {
        var tok = input.peek();
        return tok && tok.type == "kw" && (!kw || tok.value == kw) && tok;
    }
    function is_op(op) {
        var tok = input.peek();
        return tok && tok.type == "op" && (!op || tok.value == op) && tok;
    }
    function skip_punc(ch) {
        if (is_punc(ch)) input.next();
        else input.croak("Expecting punctuation: \"" + ch + "\"");
    }
    function skip_kw(kw) {
        if (is_kw(kw)) input.next();
        else input.croak("Expecting keyword: \"" + kw + "\"");
    }
    function skip_op(op) {
        if (is_op(op)) input.next();
        else input.croak("Expecting operator: \"" + op + "\"");
    }
    function unexpected() {
        input.croak("Unexpected token: " + JSON.stringify(input.peek()));
    }
    function maybe_binary(left, my_prec) {
        var tok = is_op();
        if (tok) {
            var his_prec = PRECEDENCE[tok.value];
            if (his_prec > my_prec) {
                input.next();
                return maybe_binary({
                    type     : tok.value == "=" ? "assign" : "binary",
                    operator : tok.value,
                    left     : left,
                    right    : maybe_binary(parse_atom(), his_prec)
                }, my_prec);
            }
        }
        return left;
    }
    function delimited(start, stop, separator, parser) {
        var a = [], first = true;
        skip_punc(start);
        while (!input.eof()) {
            if (is_punc(stop)) break;
            if (first) first = false; else skip_punc(separator);
            if (is_punc(stop)) break;
            a.push(parser());
        }
        skip_punc(stop);
        return a;
    }
    function parse_call(func) {
        return {
            type: "call",
            func: func,
            args: delimited("(", ")", ",", parse_expression),
        };
    }
    function parse_varname() {
        var name = input.next();
        if (name.type != "var") input.croak("Expecting variable name");
        return name.value;
    }
    function parse_if() {
        skip_kw("if");
        var cond = parse_expression();
        if (!is_punc("{")) skip_kw("then");
        var then = parse_expression();
        var ret = {
            type: "if",
            cond: cond,
            then: then,
        };
        if (is_kw("else")) {
            input.next();
            ret.else = parse_expression();
        }
        return ret;
    }
    function parse_lambda() {
        return {
            type: "lambda",
            vars: delimited("(", ")", ",", parse_varname),
            body: parse_expression()
        };
    }
    function parse_bool() {
        return {
            type  : "bool",
            value : input.next().value == "true"
        };
    }
    function maybe_call(expr) {
        expr = expr();
        return is_punc("(") ? parse_call(expr) : expr;
    }
    function parse_atom() {
        return maybe_call(function(){
            if (is_punc("(")) {
                input.next();
                var exp = parse_expression();
                skip_punc(")");
                return exp;
            }
            if (is_punc("{")) return parse_prog();
            if (is_kw("if")) return parse_if();
            if (is_kw("true") || is_kw("false")) return parse_bool();
            if (is_kw("lambda") || is_kw("λ")) {
                input.next();
                return parse_lambda();
            }
            var tok = input.next();
            if (tok.type == "var" || tok.type == "num" || tok.type == "str")
                return tok;
            unexpected();
        });
    }
    function parse_toplevel() {
        var prog = [];
        while (!input.eof()) {
            prog.push(parse_expression());
            if (!input.eof()) skip_punc(";");
        }
        return { type: "prog", prog: prog };
    }
    function parse_prog() {
        var prog = delimited("{", "}", ";", parse_expression);
        if (prog.length == 0) return FALSE;
        if (prog.length == 1) return prog[0];
        return { type: "prog", prog: prog };
    }
    function parse_expression() {
        return maybe_call(function(){
            return maybe_binary(parse_atom(), 0);
        });
    }
}

Благодарности

Очень благодарен Marijn Haverbeke, автору библиотеки parse-js (Common Lisp), благодаря которой я понял, как писать парсеры. Парсер, описанный выше предназначен для намного более простого языка, чем JS, но идеи взяты именно из него.

© Habrahabr.ru