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

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

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

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

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

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

Что такое парсер Пратта?

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

Метод был предложен учёным Воном Праттом в 1973 году в статье «Top Down Operator Precedence». С тех пор он стал одним из любимых подходов разработчиков интерпретаторов и компиляторов, когда дело доходит до разбора математических выражений. Причина проста: он гибкий, простой и удивительно мощный.

Зачем использовать парсер Пратта?

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

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

Парсер Пратта для чисел

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

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

Prefix
  = NUMBER

Обратите внимание, мы используем Prefix вместо Primary, которое мы использовали в прошлой статье. Скоро увидим почему.

Давайте создадим файл pratt_parser.js с классом PrattParser:

Парсер Пратта для чисел
class PrattParser {
    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
     *    = Prefix
     */
    parseExpression() {
        this.parsePrefix()
    }

    /*
     * Prefix
     *    = NUMBER
     */
    parsePrefix() {
        this.rpn.push(this.consume("number"))
    }
}

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

Prefix против Infix и nud против led

Мы намеренно используем термин Prefix, а не Primary, потому что в парсерах Пратта поведение разбора зависит от того, встречается ли выражение в префиксной или инфиксной позиции.

В оригинальной работе Воана Пратта использовались термины nud и led, которые мы здесь заменим на более понятные Prefix и Infix.

  • nud расшифровывается как null denotation ("нулевое обозначение") и используется для токенов, которые могут быть распознаны без контекста слева. Примеры таких выражений: числа, скобки, унарные операторы (например, -x) и т.д. В нашем случае такие конструкции будут обрабатываться через метод parsePrefix.
  • led, или left denotation ("левое обозначение"), применяется к выражениям, которые зависят от левого контекста. Это, как правило, бинарные операторы (1 + 2, x * y). Их мы будем обрабатывать через метод parseInfix.

Почему это важно? Потому что одни и те же символы могут выполнять разные роли в зависимости от контекста. Например, как мы уже знаем, символ - может быть как унарным оператором (-2), так и бинарным (3 - 1). Когда - стоит в начале выражения, перед ним нет других токенов – это префиксная форма, и она будет обработана через parsePrefix. В случае 3 - 1 - появляется между токенами – это инфиксная форма, и она обрабатывается через parseInfix.

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

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

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

Грамматика с поддержкой сложения, вычитания, умножения и деления
Expression
  = Prefix (Infix)*

Prefix
  = NUMBER

Infix
  = ("+" | "-" | "*" | "/") Expression

Грамматика, представленная выше, определяет, что выражение Expression начинается с Prefix, за которым может следовать ноль или более Infix выражений. Каждое Infix выражение состоит из нуля или более операторов, за которыми идёт другое выражение.

Давайте рассмотрим несколько примеров того, как может быть сформировано математическое выражение. Начнем с числа 42:

Раскрываем грамматику для числа 42
Expression -> Prefix (Infix)*
    -> Prefix
    -> NUMBER
    -> 42

Теперь рассмотрим математическое выражение: 1 + 2:

Раскрываем грамматику для выражения 1 + 2
Expression -> Prefix (Infix)*
    -> Prefix Infix
    -> Prefix ("+" Expression)
    -> Prefix ("+" Prefix)
    -> Prefix + Prefix
    -> NUMBER + NUMBER
    -> 1 + 2

Теперь более сложное выражение: 1 + 2 * 3:

Раскрываем грамматику для выражения 1 + 2 * 3
Expression -> Prefix (Infix)*
    -> Prefix Infix Infix
    -> Prefix ("+" Expression) ("*" Expression)
    -> Prefix ("+" Prefix) ("*" Prefix)
    -> Prefix + Prefix * Prefix
    -> NUMBER + NUMBER * NUMBER
    -> 1 + 2 * 3

Давайте реализуем это в нашем парсере:

Парсер Пратта, поддерживающий сложение, вычитание, умножение и деление
class PrattParser {
    constructor() {
        this.operators = {
            "+": 1,
            "-": 1,
            "*": 2,
            "/": 2
        }
    }

    // получение приоритета токена
    getPrecedence(token) {
        if (token && token.type === "operator")
            return this.operators[token.value]

        return 0
    }

    /*
     * Expression
     *   = Prefix (Infix)*
     */
    parseExpression(precedence = 0) {
        this.parsePrefix()

        while (precedence < this.getPrecedence(this.token))
            this.parseInfix()
    }

    /*
     * Infix
     *   = ("+" | "-" | "*" | "/") (Expression)*
     */
    parseInfix() {
        const token = this.consume("operator")
        this.parseExpression(this.operators[token.value]) // парсим выражение с обновлённым приоритетом
        this.rpn.push(token)
    }

    /*
     * Prefix
     *   = Number
     */
    parsePrefix() {
        this.rpn.push(this.consume("number"))
    }
}

Разве может этот короткий код работать? Давайте проверим!

Проверяем парсер
const tokenizer = new ExpressionTokenizer({
    functions: ["sin", "cos", "tan", "max"],
    constants: ["pi", "e"]
})

const parser = new PrattParser()

parser.parse(tokenizer.tokenize("42")) // 42
parser.parse(tokenizer.tokenize("1 + 2")) // 1 2 +
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 / +

И правда работает. Но как? Давайте рассмотрим, что делает парсер при обработке выражения 1 + 2 * 3. На вход методу parse приходят токены следующего вида:

Входные токены выражения 1 + 2 * 3
[
    {"type": "number", "value": "1", "start": 0, "end": 1},
    {"type": "operator", "value": "+"," start": 2, "end": 3},
    {"type": "number", "value": "2", "start": 4, "end": 5},
    {"type": "operator", "value": "*"," start": 6, "end": 7},
    {"type": "number", "value": "3", "start": 8, "end": 9}
]

Метод parse внутри себя вызывает parseExpression(), что запускает рекурсивный спуск по методам parsePrefix и parseInfix.

parsePrefix обрабатывает токен 1 и переходит к следующему коду внутри метода parseExpression:

Главный цикл parseExpression
while (precedence < this.getPrecedence(this.token))
    this.parseInfix()

Именно здесь начинается магия парсера Пратта. Изначально текущий приоритет (precedence) установлен в ноль. Далее мы сравниваем его с приоритетом следующего токена +. Для получения численного значения приоритета используется вспомогательный метод getPrecedence, использующий предварительно добавленный словарь приоритетов в конструкторе класса.

Приоритеты операций
this.operators = {
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2
}

Мы входим в цикл while, потому что текущий приоритет (0) меньше приоритета следующего токена (+), который равен 1 (это значение возвращается методом getPrecedence). Далее вызывается метод parseInfix, который выполняет операцию сложения и рекурсивно вызывает parseExpression – но уже с новым приоритетом – 1.

Цикл while запускается снова для умножения, ведь приоритет * равен 2, а 1 < 2. В какой-то момент мы доходим до конца выражения, и текущий токен становится равен null.

Когда текущий токен становится null, метод getPrecedence возвращает 0, что завершает цикл while внутри метода parseExpression. Именно поэтому мы используем getPrecedence, а не обращаемся напрямую к словарю операторов.

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

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

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

Грамматика с поддержкой сложения, вычитания, умножения и деления
Expression
  = Prefix (Infix)*

Prefix
  = NUMBER

Infix
  = ("+" | "-" | "*" | "/" | "^") Expression

В конструкторе парсера добавим оператор ^ в operators. Возведение в степень должно иметь наивысший приоритет среди всех операций:

Обновлённые операции
this.operators = {
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2,
    "^": 3
}

А вот и самое интересное! Возведение в степень – это оператор, который имеет правую ассоциативность вместо левой. Это означает, что выражение 2 ^ 2 ^ 3 должно возвращать значение 256, а не 64.

Для корректной обработки правоассоциативных операций достаточно просто вычесть единицу из приоритета, который передаётся в метод parseExpression внутри parseInfix. Да, всё действительно так просто! Никакой громоздкой перестройки грамматики, никаких ухищрений, чтобы заставить всё работать:

Изменённый parseInfix
/*
 * Infix
 *   = ("+" | "-" | "*" | "/" | "^") (Expression)*
 */
parseInfix() {
    const token = this.consume("operator")
    this.parseExpression(this.operators[token.value] - (token.value === "^" ? 1 : 0))
    this.rpn.push(token)
}

Немного отойдя от шока, давайте проверим эту версию парсера на примерах:

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

Обработка скобок

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

Добавляем круглые скобки
Expression
  = Prefix (Infix)*

Prefix
  = ParenthesizedExpression
  / NUMBER

Infix
  = ("+" | "-" | "*" | "/" | "^") Expression

ParenthesizedExpression
  = "(" Expression ")"

Добавим в наш метод parsePrefix проверку, что текущий токен является открывающей скобкой (. Если это так, то будем запускать метод parseParenthesizedExpression, который потребит скобки и распарсит выражение внутри них через вызов parseExpression:

Добавляем скобки
/*
 * Prefix
 *   = ParenthesizedExpression
 *   / NUMBER
 */
parsePrefix() {
    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 и дополним правило Prefix:

Добавляем унарный минус
Expression
  = Prefix (Infix)*

Prefix
  = ParenthesizedExpression
  / UnaryExpression
  / NUMBER

Infix
  = ("+" | "-" | "*" | "/" | "^") Expression

ParenthesizedExpression
  = "(" Expression ")"

UnaryExpression
  = "-" Expression

Обратите внимание, что в нашем правиле грамматики для UnaryExpression теперь используется "-" Expression. В прошлой статье мы использовали "-" Factor. Поскольку метод parseExpression в нашем парсере Пратта уже автоматически учитывает приоритеты операторов, мы можем безопасно применять "-" Expression в грамматике.

Как уже упоминалось ранее, унарный оператор использует тот же символ, -, что и операция вычитания. Однако технически унарная операция имеет более высокий приоритет, чем умножение и деление, но ниже, чем возведение в степень. Поэтому нам нужно обновить наш словарь operators, чтобы корректно обрабатывать унарный оператор ~:

Добавляем унарные операции
constructor() {
    this.operators = {
        "+": 1,
        "-": 1,
        "*": 2,
        "/": 2,
        "~": 3, // добавили унарный минус
        "^": 4 // обновили приоритет
    }
}

/*
 * Prefix
 *   = ParenthesizedExpression
 *   / UnaryExpression
 *   / NUMBER
 */
parsePrefix() {
    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
 *   = "-" Expression
 */
parseUnaryExpression() {
    const token = this.consume("operator")
    token.value = "~" // заменяем на унарный минус
    this.parseExpression(this.operators[token.value])
    this.rpn.push(token)
}

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

Проверяем парсер
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 ~ ^ ~ ^ ~

Обратите внимание, унарная операция должна иметь более низкий приоритет, чем возведение в степень, и мы можем использовать несколько - символов унарных операций подряд.

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

Вновь расширим нашу грамматику, добавив в неё правило FunctionExpression и расширив при этом правило Prefix:

Добавляем функции
Expression
  = Prefix (Infix)*

Prefix
  = ParenthesizedExpression
  / UnaryExpression
  / FunctionExpression
  / NUMBER

Infix
  = ("+" | "-" | "*" | "/" | "^") Expression

ParenthesizedExpression
  = "(" Expression ")"

UnaryExpression
  = "-" Expression

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

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

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

Парсер с поддержкой функций
constructor(functions) {
    this.functions = functions
    this.operators = {
        "+": 1,
        "-": 1,
        "*": 2,
        "/": 2,
        "~": 3,
        "^": 4
    }
}

/*
 * Prefix
 *   = ParenthesizedExpression
 *   / UnaryExpression
 *   / FunctionExpression
 *   / NUMBER
 */
parsePrefix() {
    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)
}

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

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

Проверяем парсер
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)

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

Наконец добавим поддержку констант и переменных в нашу грамматику:

Добавляем функции
Expression
  = Prefix (Infix)*

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

Infix
  = ("+" | "-" | "*" | "/" | "^") Expression

ParenthesizedExpression
  = "(" Expression ")"

UnaryExpression
  = "-" Expression

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

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

Парсер с поддержкой констант и переменных
/*
 * Prefix
 *   = ParenthesizedExpression
 *   / UnaryExpression
 *   / FunctionExpression
 *   / CONSTANT
 *   / VARIABLE
 *   / NUMBER
 */
parsePrefix() {
    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"))
}

Проверим, что наш парсер корректно работает после последнего обновления:

Проверяем парсер
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 RecursiveDescentParser(functions)

// стало так
const parser = new PrattParser(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)

Заключение

Поздравляю – вы дошли до конца! Теперь вам под силу разбирать любые математические выражения.

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

Надеюсь, вам было интересно!

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

Итоговый файл pratt_parser.js
class PrattParser {
    constructor(functions) {
        this.functions = functions
        this.operators = {
            "+": 1,
            "-": 1,
            "*": 2,
            "/": 2,
            "~": 3,
            "^": 4
        }
    }

    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
    }

    getPrecedence(token) {
        if (token && token.type === "operator")
            return this.operators[token.value]

        return 0
    }

    /*
     * Expression
     *   = Prefix (Infix)*
     */
    parseExpression(precedence = 0) {
        this.parsePrefix()

        while (precedence < this.getPrecedence(this.token))
            this.parseInfix()
    }

    /*
     * Infix
     *   = ("+" | "-" | "*" | "/" | "^") (Expression)*
     */
    parseInfix() {
        const token = this.consume("operator")
        this.parseExpression(this.operators[token.value] - (token.value === "^" ? 1 : 0))
        this.rpn.push(token)
    }

    /*
     * Prefix
     *   = ParenthesizedExpression
     *   / UnaryExpression
     *   / FunctionExpression
     *   / CONSTANT
     *   / VARIABLE
     *   / NUMBER
     */
    parsePrefix() {
        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
     *   = "-" Expression
     */
    parseUnaryExpression() {
        const token = this.consume("operator")
        token.value = "~" // заменяем на унарный минус
        this.parseExpression(this.operators[token.value])
        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)
    }
}

А так же

Часть 4. Парсер рекурсивного спуска

Часть 6. Перевод из постфиксной формы в инфиксную