Парсим математические выражения на чистом Javascript. Часть 4: парсер рекурсивного спуска

javascript, math expression parsing, recursive descent parser
Парсим математические выражения на чистом Javascript. Часть 4: парсер рекурсивного спуска

Цикл статей о создании собственного парсера выражений: от токенизации до полноценного синтаксического разбора.

Оглавление цикла

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

Однако существует и другой, более выразительный способ синтаксического анализа – рекурсивный спуск. Этот метод лежит в основе множества настоящих парсеров, и его мощь в том, что он тесно связан с формальными грамматиками. В отличие от сортировочной станции, здесь правила синтаксиса можно выразить напрямую в виде вложенных функций, каждая из которых соответствует определённому уровню приоритета операций.

В этой части мы:

  • познакомимся с понятием грамматик;
  • поэтапно построим грамматику математических выражений;
  • реализуем класс RecursiveDescentParser, который будет на основе этой грамматики строить выражение в польской записи.

Что такое грамматика и рекурсивный спуск

Когда речь идёт о синтаксическом разборе, всё начинается с грамматики – формального описания допустимых конструкций языка. В контексте математических выражений грамматика определяет, в каком порядке и с какими правилами могут сочетаться числа, переменные, операции и скобки.

Простейший пример некоторого математического выражения, записанный на псевдо-BNF языке:

Грамматика некоторого математического выражения
expression ::= term (("+" | "-") term)*
term       ::= factor (("*" | "/") factor)*
factor     ::= number | "(" expression ")"

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

Предиктивный разбор

Когда грамматика достаточно проста, мы можем обрабатывать её предиктивно – то есть на каждом шаге решения у нас есть достаточно информации, чтобы понять, какой путь разбора выбрать. Такие грамматики называются LL(1) (один токен взгляда вперёд), и именно с ними отлично работает рекурсивный спуск.

Такой подход даёт нам:

  • простую отладку и поддержку;
  • отличную читаемость и контроль;
  • возможность построения польской записи прямо в процессе разбора.

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

Рекурсивный парсер чисел

В качестве отправной точки возьмём минимальную грамматику, которая поддерживает только числовые литералы:

Грамматика с поддержкой только чисел
Expression
  = Primary

Primary
  = NUMBER

Выражения, соответствующие такой грамматике максимально просты – 1, 3.141, 123.456, однако даже такой грамматики нам будет достаточно, чтобы погрузиться в мир рекурсивных парсеров. Давайте создадим файл recursive_descent_parser.js с классом RecursiveDescentParser:

Парсер чисел
class RecursiveDescentParser {
    parse(tokens) {
        this.tokens = tokens
        this.index = 0
        this.token = this.tokens[0]
        this.rpn = []

        this.parseExpression()

        if (this.index < this.tokens.length)
            throw new Error(`extra tokens after end of expression (${this.token.start})`)

        return this.rpn
    }

    consume(type) {
        const token = this.token

        if (token === null)
            throw new Error(`unexpected end of input, expected ${type}`)

        if (token.type !== type)
            throw new Error(`unexpected token: "${token.value}", expected ${type} (${token.start}:${token.end})`)

        this.token = ++this.index < this.tokens.length ? this.tokens[this.index] : null
        return token
    }

    /*
     * Expression
     *    = Primary
     */
    parseExpression() {
        this.parsePrimary()
    }

    /*
     * Primary
     *    = NUMBER
     */
    parsePrimary() {
        this.rpn.push(this.consume("number"))
    }
}

Давайте посмотрим, что здесь происходит:

  1. Метод parse(tokens):
    • Запоминает входной массив токенов.
    • Обнуляет текущую позицию (this.index) и сохраняет текущий токен (this.token).
    • Инициализирует выходной массив this.rpn, в котором будет формироваться результат в виде польской записи.
    • Вызывает parseExpression() – это точка входа для рекурсивного разбора всего выражения.
    • После завершения разбора проверяет, не остались ли необработанные токены. Если остались – значит в выражении синтаксическая ошибка.
  2. Метод consume(type):
    • Проверяет, соответствует ли текущий токен ожидаемому типу.
    • Если нет токенов или тип не совпадает – бросает исключение.
    • Иначе возвращает текущий токен и переходит на следующий.
    Обратите внимание: в качестве маркера конца ввода здесь используется null – то есть this.token становится null, когда выражение полностью прочитано.
  3. Метод parseExpression():
    • Просто вызывает parsePrimary().
  4. Метод parsePrimary():
    • Съедает базовый терминал – число.
    • Добавляет его в выходной массив RPN.

Обратите внимание на то, как мы добавили правила грамматики в виде комментариев непосредственно над методами parseExpression и parsePrimary. Такой приём помогает ясно представить, на каком этапе грамматического разбора мы находимся. По мере роста парсера это станет особенно полезным – ведь структура разбора будет прямо отражать структуру грамматики.

В данном случае Expression и Primary – это нетерминальные символы, а NUMBER – терминальный символ. Благодаря комментариям мы как бы накладываем текст грамматики поверх кода, превращая его в живую реализацию грамматических правил.

Мы последовательно вызываем методы, соответствующие нетерминальным символам грамматики, переходя от одного правила к другому – до тех пор, пока не будет обработано всё выражение. Именно такая структура, где разбор ведётся путём рекурсивных вызовов, и дала название подходу: анализатор рекурсивного спуска.

Хоть наша грамматика пока мала, но уже сейчас мы получили вполне работоспособный парсер. Давайте проверим его в деле:

Проверяем парсер, поддерживающий только числа
const tokenizer = new ExpressionTokenizer({
    functions: ["sin", "cos", "tan", "max"],
    constants: ["pi", "e"]
})

const parser = new RecursiveDescentParser()
const rpn = parser.parse(tokenizer.tokenize("42")) // 42

Добавляем сложение и вычитание

Пусть рекурсия продолжается! Пришло время обновить нашу грамматическую «схему», чтобы обработать сложение и вычитание.

Грамматика с поддержкой сложения и вычитания
Expression
  = Primary (("+" | "-") Primary)*

Primary
  = NUMBER

Синтаксис (expression)* означает, что допускается ноль или более вхождений выражения. А ("+" | "-") означает любой из перечисленных символов, в нашем случае символ сложения или вычитания.

При работе с бесконечными последовательностями мы можем использовать цикл while, проверяющий, есть ли ещё один нужный символ. Давайте добавим это в наш парсер:

Парсер с поддержкой сложения и вычитания
/*
 * Expression
 *    = Primary (("+" | "-") Primary)*
 */
parseExpression() {
    this.parsePrimary()

    while (this.token?.type === "operator" && (this.token.value === "+" || this.token.value === "-")) {
        const operator = this.consume("operator")
        this.parsePrimary()
        this.rpn.push(operator)
    }
}

Как видите, изменился только метод parseExpression. По мере расширения грамматики и добавления новых конструкций количество рекурсивных вызовов увеличивается – это естественное следствие роста сложности выражения. Важно, чтобы после завершения разбора не осталось необработанных токенов: метод parse должен завершаться успешно только в случае полного соответствия всей строки заданной грамматике.

Проверим наш обновлённый парсер:

Проверяем парсер, поддерживающий сложение и вычитание
parser.parse(tokenizer.tokenize("1 + 2")) // 1 2 +
parser.parse(tokenizer.tokenize("1 + 2 - 5 + 8")) // 1 2 + 5 - 8 +

Добавляем умножение и деление

Добавим в нашу грамматику правило Term для обработки умножения и деления:

Грамматика с поддержкой сложения, вычитания, умножения и деления
Expression
  = Term (("+" | "-") Term)*

Term
  = Primary (("*" | "/") Primary)*

Primary
  = NUMBER

В нашем рекурсивном синтаксическом анализаторе нужно будет создать новый метод с именем parseTerm. Внутри метода parseExpression теперь будет вызываться parseTerm вместо parsePrimary:

Парсер с поддержкой сложения, вычитания, умножения и деления
/*
 * Expression
 *   = Term (("+" | "-") Term)*
 */
parseExpression() {
    this.parseTerm()

    while (this.token?.type === "operator" && (this.token.value === "+" || this.token.value === "-")) {
        const operator = this.consume("operator")
        this.parseTerm()
        this.rpn.push(operator)
    }
}

/*
 * Term
 *   = Primary (("*" | "/") Primary)*
 */
parseTerm() {
    this.parsePrimary()

    while (this.token?.type === "operator" && (this.token.value === "*" || this.token.value === "/")) {
        const operator = this.consume("operator")
        this.parsePrimary()
        this.rpn.push(operator)
    }
}

Проверим наш обновлённый парсер:

Проверяем парсер, поддерживающий сложение, вычитание, умножение и деление
parser.parse(tokenizer.tokenize("1 + 2 * 3")) // 1 2 3 * +
parser.parse(tokenizer.tokenize("1 + 2 * 3 - 5 + 8 * 3 / 2.5")) // 1 2 3 * + 5 - 8 3 * 2.5 / +

Добавляем возведение в степень

Добавим в нашу грамматику правило Factor для обработки возведения в степень:

Грамматика с поддержкой сложения, вычитания, умножения, деления и возведения в степень
Expression
  = Term (("+" | "-") Term)*

Term
  = Factor (("*" | "/") Factor)*

Factor
  = Primary ("^" Factor)*

Primary
  = NUMBER

Обратите внимание, что второй "аргумент" в секции Factor не Primary, а Factor, поскольку возведение в степень – это правоассоциативная операция!

В нашем рекурсивном синтаксическом анализаторе нужно будет создать новый метод с именем parseFactor. Внутри метода parseTerm теперь будет вызываться parseFactor вместо parsePrimary:

Парсер с поддержкой сложения, вычитания, умножения, деления и возведения в степень
/*
 * Term
 *   = Factor (("*" | "/") Factor)*
 */
parseTerm() {
    this.parseFactor()

    while (this.token?.type === "operator" && (this.token.value === "*" || this.token.value === "/")) {
        const operator = this.consume("operator")
        this.parseFactor()
        this.rpn.push(operator)
    }
}

/*
 * Factor
 *   = Primary ("^" Factor)*
 */
parseFactor() {
    this.parsePrimary()

    while (this.token?.type === "operator" && this.token.value === "^") {
        const operator = this.consume("operator")
        this.parseFactor()
        this.rpn.push(operator)
    }
}

Проверим наш обновлённый парсер:

Проверяем парсер, поддерживающий сложение, вычитание, умножение, деление и возведение в степень
parser.parse(tokenizer.tokenize("1 + 2*3^4")) // 1 2 3 4 ^ * +
parser.parse(tokenizer.tokenize("2^2^3")) // 2 2 3 ^ ^

Небольшой рефакторинг

Нетрудно заметить, что внутри методов parseExpression, parseFactor и parseTerm дублируется код. Давайте исправим это, создав вспомогательный метод parseBinaryOperation:

Парсер после небольшого рефакторинга
parseBinaryExpresson(parseLeft, parseRight, values) {
    parseLeft()

    while (this.token?.type === "operator" && values.has(this.token.value)) {
        const operator = this.consume("operator")
        parseRight()
        this.rpn.push(operator)
    }
}

/*
 * Expression
 *   = Term (("+" | "-") Term)*
 */
parseExpression() {
    this.parseBinaryExpresson(() => this.parseTerm(), () => this.parseTerm(), new Set(["+", "-"]))
}

/*
 * Term
 *   = Factor (("*" | "/") Factor)*
 */
parseTerm() {
    this.parseBinaryExpresson(() => this.parseFactor(), () => this.parseFactor(), new Set(["*", "/"]))
}

/*
 * Factor
 *   = Primary ("^" Factor)*
 */
parseFactor() {
    this.parseBinaryExpresson(() => this.parsePrimary(), () => this.parseFactor(), new Set(["^"]))
}

Стало гораздо чище, не правда ли? Давайте проверим, как наш парсер обрабатывает различные выражения:

Проверяем парсер
parser.parse(tokenizer.tokenize("1 + 2 + 3")) // 1 2 3 + +
parser.parse(tokenizer.tokenize("7 - 4 - 2")) // 7 4 - 2 -
parser.parse(tokenizer.tokenize("1 * 2 * 3")) // 1 2 3 * *
parser.parse(tokenizer.tokenize("24 / 2 / 8")) // 24 2 / 8 /
parser.parse(tokenizer.tokenize("2^2")) // 2 2 ^
parser.parse(tokenizer.tokenize("1 + 2^3^4")) // 1 2 3 4 ^ ^ +

Добавляем обработку скобок

Теперь, когда мы немного привели наш код в порядок, давайте добавим в грамматику поддержку скобок:

Добавляем поддержку скобок
Expression
  = Term (("+" | "-") Term)*

Term
  = Factor (("*" | "/") Factor)*

Factor
  = Primary ("^" Factor)*

Primary
  = ParenthesizedExpression
  / NUMBER

ParenthesizedExpression
  = "(" expression ")"

Мы создадим новый метод parseParenthesizedExpression, который будет потреблять токены скобок ( и ) и парсить выражение между ними:

Парсер с поддержкой скобок
/*
 * Primary
 *    = ParenthesizedExpression
 *    / NUMBER
 */
parsePrimary() {
    if (this.token?.type === "left_parenthesis") {
        this.parseParenthesizedExpression()
        return
    }

    this.rpn.push(this.consume("number"))
}

/*
 * ParenthesizedExpression
 *   = "(" expression ")"
 */
parseParenthesizedExpression() {
    this.consume("left_parenthesis")
    this.parseExpression()
    this.consume("right_parenthesis")
}

И всё? И всё! В этом главная прелесть парсеров, использующих рекурсивный спуск. Давайте проверим обновлённый парсер:

Проверяем парсер
parser.parse(tokenizer.tokenize("((1 + 2) + (3))")) // 1 2 + 3 +
parser.parse(tokenizer.tokenize("7 - (4 - 2)")) // 7 4 2 - -
parser.parse(tokenizer.tokenize("24 / (2 / 8)")) // 24 2 8 / /
parser.parse(tokenizer.tokenize("1 + (2^3)^4")) // 1 2 3 ^ 4 ^ +

Добавляем унарный минус

Как думаете, сложно его будет добавить? Вообще нет! Буквально так же, как мы только что добавили выражение в круглых скобках, добавим правило UnaryExpression в нашу грамматику:

Добавляем поддержку унарного минуса
Expression
  = Term (("+" | "-") Term)*

Term
  = Factor (("*" | "/") Factor)*

Factor
  = Primary ("^" Factor)*

Primary
  = ParenthesizedExpression
  / UnaryExpression
  / NUMBER

ParenthesizedExpression
  = "(" expression ")"

UnaryExpression
  = "-" Factor

Мы хотим, чтобы унарное выражение раскрывалось, как "-" Factor вместо "-" Expression, поскольку мы хотим, чтобы возведение в степень имело более высокий приоритет, чем унарные операции, так как математическое выражение -2 ^ 2 должно давать значение -4.

Давайте же добавим метод parseUnaryExpression в наш рекурсивный парсер:

Парсер с поддержкой унарного минуса
/*
 * Primary
 *    = ParenthesizedExpression
 *    / UnaryExpression
 *    / NUMBER
 */
parsePrimary() {
    if (this.token?.type === "left_parenthesis") {
        this.parseParenthesizedExpression()
        return
    }

    if (this.token?.type === "operator" && this.token.value === "-") {
        this.parseUnaryExpression()
        return
    }

    this.rpn.push(this.consume("number"))
}

/*
 * UnaryExpression
 *   = "-" Factor
 */
parseUnaryExpression() {
    const token = this.consume("operator")
    token.value = "~" // заменяем на унарный минус
    this.parseFactor()
    this.rpn.push(token)
}

Мы обновили функцию Primary, включив в нее проверку, является ли текущий токен знаком -. Если да, то выполняем парсинг унарного выражения, не забывая при этом поменять - на ~.

Проверим же наш новый парсер в деле:

Проверяем парсер
parser.parse(tokenizer.tokenize("-5")) // 5 ~
parser.parse(tokenizer.tokenize("-(-(1 + 2) + -(-3))")) // 1 2 + ~ 3 ~ ~ + ~
parser.parse(tokenizer.tokenize("-----127")) // 127 ~ ~ ~ ~ ~
parser.parse(tokenizer.tokenize("-2^2")) // 2 2 ^ ~
parser.parse(tokenizer.tokenize("-2^-2^-3")) // 2 2 3 ~ ^ ~ ^ ~

Добавляем функции

Добавить поддержку функций будет не сложнее унарного минуса. Мы лишь ещё немного расширим наже правило Primary, добавив в него FunctionExpression:

Добавляем поддержку функций
Expression
  = Term (("+" | "-") Term)*

Term
  = Factor (("*" | "/") Factor)*

Factor
  = Primary ("^" Factor)*

Primary
  = ParenthesizedExpression
  / UnaryExpression
  / FunctionExpression
  / NUMBER

ParenthesizedExpression
  = "(" expression ")"

UnaryExpression
  = "-" Factor

FunctionExpression
  = FUNCTION "(" expression ("," expression)* ")"

Строго говоря, наше правило позволяет добавлять функции с произвольным числом аргументов. Но мы будем обрабатывать то количество аргументов, которое требуется функции. Поэтому нам потребуется передавать в наш парсер словарь с обрабатываемыми функциями, в котором хранится информация о требуемых аргументах.

Добавим в наш класс конструктор и реализуем метод parseFunctionExpression:

Парсер с поддержкой функций
constructor(functions) {
    this.functions = functions
}

/*
 * Primary
 *    = ParenthesizedExpression
 *    / UnaryExpression
 *    / FunctionExpression
 *    / NUMBER
 */
parsePrimary() {
    if (this.token?.type === "left_parenthesis") {
        this.parseParenthesizedExpression()
        return
    }

    if (this.token?.type === "operator" && this.token.value === "-") {
        this.parseUnaryExpression()
        return
    }

    if (this.token?.type === "function") {
        this.parseFunctionExpression()
        return
    }

    this.rpn.push(this.consume("number"))
}

/*
 * FunctionExpression
 *   = FUNCTION "(" expression ("," expression)* ")"
 */
parseFunctionExpression() {
    const token = this.consume("function")
    this.consume("left_parenthesis")
    this.parseExpression()

    // обрабатываем лишь необходимое количество аргументов
    for (let i = 1; i < this.functions[token.value].args; i++) {
        this.consume("delimeter")
        this.parseExpression()
    }

    this.consume("right_parenthesis")
    this.rpn.push(token)
}

Мы вновь расширили правило parsePrimary ещё одним условием – является ли текущий токен функцией. Если являестя, то запускаем парсинг функционального выражения.

Проверим, что парсер работает ожидаемым образом:

Проверяем парсер
parser.parse(tokenizer.tokenize("sin(1)")) // 1 sin
parser.parse(tokenizer.tokenize("tan(max(sin(1), cos(-1)))")) // 1 sin 1 ~ cos max tan 
parser.parse(tokenizer.tokenize("sin(1, 2, 3, 4)")) // Error: unexpected token: ",", expected right_parenthesis (5:6)

Парсер работает именно так, как от него ожидается – и особенно приятно то, что нам не пришлось вручную проверять количество переданных аргументов, чтобы отловить синтаксическую ошибку. Мы просто разбираем ровно столько аргументов, сколько требуется, а всё остальное обрабатывается естественным образом. Вспомните, насколько сложнее это выглядело в предыдущей статье!

Добавляем переменные и константы

Мы уже на финишной прямой. В парсер осталось добавить только поддержку констант и переменных и мы, конечно же, просто вновь расширим правило Primary:

Добавляем поддержку констант и переменных
Expression
  = Term (("+" | "-") Term)*

Term
  = Factor (("*" | "/") Factor)*

Factor
  = Primary ("^" Factor)*

Primary
  = ParenthesizedExpression
  / UnaryExpression
  / FunctionExpression
  / CONSTANT
  / VARIABLE
  / NUMBER

ParenthesizedExpression
  = "(" expression ")"

UnaryExpression
  = "-" Factor

FunctionExpression
  = FUNCTION "(" expression ("," expression)* ")"

Да, вот так просто. Давайте наконец доделаем наш парсер:

Парсер с поддержкой констант и переменных
/*
 * Primary
 *    = ParenthesizedExpression
 *    / UnaryExpression
 *    / FunctionExpression
 *    / CONSTANT
 *    / VARIABLE
 *    / NUMBER
 */
parsePrimary() {
    if (this.token?.type === "left_parenthesis") {
        this.parseParenthesizedExpression()
        return
    }

    if (this.token?.type === "operator" && this.token.value === "-") {
        this.parseUnaryExpression()
        return
    }

    if (this.token?.type === "function") {
        this.parseFunctionExpression()
        return
    }

    if (this.token?.type === "constant" || this.token?.type === "variable") {
        this.rpn.push(this.consume(this.token.type))
        return
    }

    this.rpn.push(this.consume("number"))
}

Мы вновь расширили метод parsePrimary, добавив в него проверку: он ожидает, что текущий токен окажется константой или переменной. Затем просто потребляем токен и добавляем его в rpn.

Давайте быстренько проверим, что наш парсер корректно работает после обновления:

Проверяем парсер
parser.parse(tokenizer.tokenize("sin(pi*x)")) // pi x * sin
parser.parse(tokenizer.tokenize("e^-pi")) // e pi ~ ^
parser.parse(tokenizer.tokenize("e*sin(x)^2 + pi*cos(y)^2")) // e x sin 2 ^ * pi y cos 2 ^ * +

Обновляем парсер математических выражений

Пришло время изменить самую главную строчку кода в файле expression_parser.js:

Заменяем парсер в ExpressionParser
 // было так
const parser = new ShuntingYardParser(functions)

// стало так
const parser = new RecursiveDescentParser(functions)

Запустим вновь тесты из прошлой статьи, чтобы убедиться, что парсер работает точно так же:

Тестируем парсер рекурсивного спуска
function TestParser(expression, expected, variables = {}, eps = 1e-15) {
    try {
        const parser = new ExpressionParser(expression)

        for (const [variable, value] of Object.entries(variables))
            parser.setVariable(variable, value)

        const result = parser.evaluate()

        if (Math.abs(result - expected) < eps)
            console.log(`%c${expression} = ${result}`, "color: green")
        else
            console.log(`%c${expression} = ${result}, but expected ${expected}`, "color: red")
    }
    catch (error) {
        console.log(`%c"${expression}" is invalid: ${error.message}`, expected === null ? "color: green" : "color: red")
    }
}

// проверяем корректные выражения
TestParser("1", 1) // 1 = 1
TestParser("1 + 2 * 3", 7) // 1 + 2 * 3 = 7
TestParser("-(1 + 2) * 3 - 4", -13) // -(1 + 2) * 3 - 4 = -13
TestParser("-2^2", -4) // -2^2 = -4
TestParser("(-2)^2", 4) // (-2)^2 = 4
TestParser("-2^-2", -0.25) // -2^-2 = -0.25
TestParser("(-2)^-2", 0.25) // (-2)^-2 = 0.25
TestParser("max(5 + 2^3, -7 * -9)", 63) // max(5 + 2^3, -7 * -9) = 63
TestParser("cos(7 - 5)^2 + sin(4^0.5)^2", 1) // cos(7 - 5)^2 + sin(4^0.5)^2 = 1
TestParser("sin(x) * (pi/-x - 5)^2", -9, {"x": -Math.PI / 2}) // sin(x) * (pi/-x - 5)^2 = -9

// проверяем некорректные выражения
TestParser("()", null) // "()" is invalid: unexpected token: ")", expected number (1:2)
TestParser("max(1)", null) // "max(1)" is invalid: unexpected token: ")", expected delimeter (5:6)
TestParser("sin(1, 5)", null) // "sin(1, 5)" is invalid: unexpected token: ",", expected right_parenthesis (5:6)
TestParser("sin cos 2 max 7", null) // "sin cos 2 max 7" is invalid: unexpected token: "cos", expected left_parenthesis (4:7)

Заключение

Рекурсивный спуск позволяет описывать парсер значительно яснее и выразительнее, чем алгоритм сортировочной станции. Такой подход не только обеспечивает большую гибкость в работе с синтаксисом выражений, но и позволяет гораздо элегантнее обрабатывать ошибки. Всего 103 строки кода (без учёта комментариев грамматики) против 167 – и это при той же функциональности! В следующей части мы сократим объём кода ещё больше, сохранив при этом полную поддержку всех выражений!

Куда же без исходников?

Итоговый файл recursive_descent_parser.js
class RecursiveDescentParser {
    constructor(functions) {
        this.functions = functions
    }

    parse(tokens) {
        this.tokens = tokens
        this.index = 0
        this.token = this.tokens[0]
        this.rpn = []

        this.parseExpression()

        if (this.index < this.tokens.length)
            throw new Error(`extra tokens after end of expression (${this.token.start})`)

        return this.rpn
    }

    consume(type) {
        const token = this.token

        if (token === null)
            throw new Error(`unexpected end of input, expected ${type}`)

        if (token.type !== type)
            throw new Error(`unexpected token: "${token.value}", expected ${type} (${token.start}:${token.end})`)

        this.token = ++this.index < this.tokens.length ? this.tokens[this.index] : null
        return token
    }

    parseBinaryExpresson(parseLeft, parseRight, values) {
        parseLeft()

        while (this.token?.type === "operator" && values.has(this.token.value)) {
            const operator = this.consume("operator")
            parseRight()
            this.rpn.push(operator)
        }
    }

    /*
     * Expression
     *   = Term (("+" | "-") Term)*
     */
    parseExpression() {
        this.parseBinaryExpresson(() => this.parseTerm(), () => this.parseTerm(), new Set(["+", "-"]))
    }

    /*
     * Term
     *   = Factor (("*" | "/") Factor)*
     */
    parseTerm() {
        this.parseBinaryExpresson(() => this.parseFactor(), () => this.parseFactor(), new Set(["*", "/"]))
    }

    /*
     * Factor
     *   = Primary ("^" Factor)*
     */
    parseFactor() {
        this.parseBinaryExpresson(() => this.parsePrimary(), () => this.parseFactor(), new Set(["^"]))
    }

    /*
     * Primary
     *    = ParenthesizedExpression
     *    / UnaryExpression
     *    / FunctionExpression
     *    / CONSTANT
     *    / VARIABLE
     *    / NUMBER
     */
    parsePrimary() {
        if (this.token?.type === "left_parenthesis") {
            this.parseParenthesizedExpression()
            return
        }

        if (this.token?.type === "operator" && this.token.value === "-") {
            this.parseUnaryExpression()
            return
        }

        if (this.token?.type === "function") {
            this.parseFunctionExpression()
            return
        }

        if (this.token?.type === "constant" || this.token?.type === "variable") {
            this.rpn.push(this.consume(this.token.type))
            return
        }

        this.rpn.push(this.consume("number"))
    }

    /*
     * ParenthesizedExpression
     *   = "(" expression ")"
     */
    parseParenthesizedExpression() {
        this.consume("left_parenthesis")
        this.parseExpression()
        this.consume("right_parenthesis")
    }

    /*
     * UnaryExpression
     *   = "-" Factor
     */
    parseUnaryExpression() {
        const token = this.consume("operator")
        token.value = "~" // заменяем на унарный минус
        this.parseFactor()
        this.rpn.push(token)
    }

    /*
     * FunctionExpression
     *   = FUNCTION "(" expression ("," expression)* ")"
     */
    parseFunctionExpression() {
        const token = this.consume("function")
        this.consume("left_parenthesis")
        this.parseExpression()

        for (let i = 1; i < this.functions[token.value].args; i++) {
            this.consume("delimeter")
            this.parseExpression()
        }

        this.consume("right_parenthesis")
        this.rpn.push(token)
    }
}

А так же

Часть 3. Алгоритм сортировочной станции

Часть 5. Парсер Пратта