Парсер выражений: как разобрать математическое выражение из строки

Парсер выражений превращает строку 2 + 3 * 4 в дерево, по которому программа получает 14, а не 20: парсер учитывает приоритет операций и круглые скобки ещё при разборе. Парсер ниже написан на JavaScript методом рекурсивного спуска и занимает меньше 200 строк. Для чужого ввода eval не подходит, в Python вместо него берут модуль ast.

Парсинг математических выражений нужен в калькуляторах, формулах из конфигов, фильтрах отчётов и правилах расчёта цены: пользователь вводит арифметическое выражение строкой, а программа должна вычислить его значение. Код ниже проверен на Node.js 24.14.1 и Python 3.14.3.

Из чего состоит разбор выражения

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

Для этой строки получается такое дерево:

+
├── 2
└── *
    ├── 3
    └── 4

Узел можно представить объектом: у бинарного узла есть оператор op и два потомка, left и right. Умножение оказалось глубже сложения, поэтому оно вычисляется первым: приоритет превратился в форму дерева, и вычислителю о нём знать не нужно. Такое же дерево строит интерпретатор Python, посмотреть его можно вызовом ast.dump(ast.parse("2 + 3 * 4", mode="eval")).

Дерево выражения имеет ещё одно преимущество: его можно вычислить много раз с разными значениями переменных, распечатать или упростить. Разбор «на лету», без дерева, короче, но в таком режиме результат нельзя использовать повторно.

Почему не eval и не регулярные выражения

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

# Python 3.14
user_input = "__import__('platform').system()"
print(eval(user_input))

Windows

На Windows программа печатает Windows, на Linux напечатает Linux. С таким же успехом на месте platform окажется os и команда, которая удаляет файлы в системе. В JavaScript тот же риск у eval и new Function.

Регулярные выражения подходят для лексера: с помощью одной строки запись режется на токены.

# Python 3.14
import re

print(re.findall(r"\d+\.?\d*|[-+*/()]", "2+(3*4)"))

['2', '+', '(', '3', '*', '4', ')']

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

Грамматика: приоритеты в пяти строках

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

expression = term { ("+" | "-") term }
term       = unary { ("*" | "/") unary }
unary      = "-" unary | power
power      = primary [ "^" unary ]
primary    = число | имя | имя "(" [ expression { "," expression } ] ")" | "(" expression ")"

Правило expression описывает бинарные операторы + и -, term бинарные операторы * и /, unary унарный оператор минус, power возведение в степень. Фигурные скобки в записи означают «ноль или больше повторений», квадратные «необязательно». Для построения дерева у каждого правила есть соответствующий метод класса: expression вызывает term, тот вызывает unary, и на самом дне primary разбирает число, имя или выражение в скобках. Открывающая скобка возвращает разбор к самому верхнему правилу, отсюда и рекурсия: выражение внутри скобок это снова полное выражение.

Парсер рекурсивного спуска на JavaScript

Файл parser.js состоит из трёх блоков, складывайте их подряд. Исходный код остальных примеров на JavaScript кладите в ту же папку. В первом блоке находятся класс ошибки и лексер:

// Node.js 24, запуск: node parser.js
class ParseError extends Error {
  constructor(message, pos) {
    super(`${message} (позиция ${pos})`);
    this.name = "ParseError";
  }
}
class CalcError extends Error {
  constructor(message, pos) {
    super(pos === undefined ? message : `${message} (позиция ${pos})`);
    this.name = "CalcError";
  }
}
const fail = (message, pos) => {
  throw new ParseError(message, pos);
};
const failCalc = (message, pos) => {
  throw new CalcError(message, pos);
};

// 1. Лексер: строка -> список токенов
function tokenize(expr) {
  const tokens = [];
  const re = /\s*(?:(\d+(?:\.\d+)?)|([A-Za-z_]\w*)|(.))/gy;
  const text = expr.trimEnd();
  let m;
  while ((m = re.exec(text)) !== null) {
    const [, num, name, sign] = m;
    const pos = m.index + m[0].length - (num ?? name ?? sign).length;
    if (num) tokens.push({ type: "num", value: Number(num), pos });
    else if (name) tokens.push({ type: "name", value: name, pos });
    else if ("+-*/^(),".includes(sign)) tokens.push({ type: sign, pos });
    else fail(`Неожиданный символ "${sign}"`, pos);
  }
  tokens.push({ type: "end", pos: expr.length });
  return tokens;
}

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

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

// 2. Парсер рекурсивного спуска: токены -> дерево
const MAX_DEPTH = 200;
const NAMES = { end: "конец выражения", num: "число", name: "имя" };
const show = (t) => NAMES[t.type] ?? t.type;

class Parser {
  constructor(expr) {
    this.tokens = tokenize(expr);
    this.index = 0;
    this.depth = 0;
  }
  peek() { return this.tokens[this.index]; }
  next() { return this.tokens[this.index++]; }
  // забирает следующий токен, если его тип есть в списке
  match(...types) {
    return types.includes(this.peek().type) ? this.next().type : null;
  }
  expect(type) {
    const t = this.next();
    if (t.type !== type) fail(`Ожидалось "${type}", найдено "${show(t)}"`, t.pos);
  }
  parse() {
    const tree = this.expression();
    const t = this.peek();
    if (t.type !== "end") fail(`Лишний токен "${show(t)}"`, t.pos);
    return tree;
  }
  expression() {
    let left = this.term();
    let op;
    while ((op = this.match("+", "-"))) {
      left = { type: "bin", op, left, right: this.term() };
    }
    return left;
  }
  term() {
    let left = this.unary();
    let op;
    while ((op = this.match("*", "/"))) {
      left = { type: "bin", op, left, right: this.unary() };
    }
    return left;
  }
  unary() {
    if (++this.depth > MAX_DEPTH) fail("Слишком глубокая вложенность", this.peek().pos);
    try {
      if (this.match("-")) return { type: "neg", arg: this.unary() };
      return this.power();
    } finally {
      this.depth--;
    }
  }
  power() {
    const base = this.primary();
    if (this.match("^")) return { type: "bin", op: "^", left: base, right: this.unary() };
    return base;
  }
  primary() {
    const t = this.next();
    if (t.type === "num") return { type: "num", value: t.value };
    if (t.type === "(") {
      const inner = this.expression();
      this.expect(")");
      return inner;
    }
    if (t.type === "name") {
      if (!this.match("(")) return { type: "var", name: t.value, pos: t.pos };
      const args = [];
      if (this.peek().type !== ")") {
        do {
          args.push(this.expression());
        } while (this.match(","));
      }
      this.expect(")");
      return { type: "call", name: t.value, args, pos: t.pos };
    }
    return fail(`Ожидалось число или "(", найдено "${show(t)}"`, t.pos);
  }
}

В методах expression и term работает цикл while: разбор происходит слева направо, и на каждом шаге прежнее дерево становится левым потомком нового узла, поэтому 10 - 3 - 2 превращается в (10 - 3) - 2. Если вместо цикла написать рекурсию, right: this.expression(), правая часть 3 - 2 разберётся отдельно, и разбор приведёт к 10 - (3 - 2). Выражение 2 - 1 такую ошибку не покажет, а 5 - 3 - 1 покажет: вместо 1 выйдет 3.

Третий блок вычисляет дерево: для каждого вида узла в switch есть свой case. Здесь же константа pi, функция isValid и запуск примеров:

// 3. Вычисление по дереву
const FUNCTIONS = { sqrt: Math.sqrt, sin: Math.sin, max: Math.max, min: Math.min };
const CONSTANTS = { pi: Math.PI };

function evaluate(n, vars = {}) {
  switch (n.type) {
    case "num":
      return n.value;
    case "var":
      if (Object.hasOwn(vars, n.name)) return vars[n.name];
      if (Object.hasOwn(CONSTANTS, n.name)) return CONSTANTS[n.name];
      return failCalc(`Неизвестная переменная "${n.name}"`, n.pos);
    case "neg":
      return -evaluate(n.arg, vars);
    case "call": {
      if (!Object.hasOwn(FUNCTIONS, n.name)) {
        return failCalc(`Неизвестная функция "${n.name}"`, n.pos);
      }
      return FUNCTIONS[n.name](...n.args.map((a) => evaluate(a, vars)));
    }
    case "bin": {
      const a = evaluate(n.left, vars);
      const b = evaluate(n.right, vars);
      switch (n.op) {
        case "+": return a + b;
        case "-": return a - b;
        case "*": return a * b;
        case "/":
          if (b === 0) failCalc("Деление на ноль");
          return a / b;
        case "^": return a ** b;
      }
    }
  }
  throw new Error(`Неизвестный узел: ${n.type}`);
}

function calc(expr, vars) {
  return evaluate(new Parser(expr).parse(), vars);
}

// Проверка ввода: true, если строка разбирается, false, если нет
function isValid(expr) {
  try {
    new Parser(expr).parse();
    return true;
  } catch (e) {
    if (e instanceof ParseError) return false;
    throw e;
  }
}

module.exports = { Parser, tokenize, evaluate, calc, isValid };

if (require.main === module) {
  const inputs = [
    "2 + 3 * 4",
    "(2 + 3) * 4",
    "10 - 3 - 2",
    "2 ^ 3 ^ 2",
    "-2 ^ 2",
    "sqrt(16) + max(1, 7, 3)",
    "x * 2 + pi",
  ];
  for (const expr of inputs) {
    console.log(`${expr} = ${calc(expr, { x: 5 })}`);
  }
  console.log(isValid("2 + 2"), isValid("2 +"), isValid("y + 1"));
}

Запуск node parser.js печатает:

2 + 3 * 4 = 14
(2 + 3) * 4 = 20
10 - 3 - 2 = 5
2 ^ 3 ^ 2 = 512
-2 ^ 2 = -4
sqrt(16) + max(1, 7, 3) = 11
x * 2 + pi = 13.141592653589793
true false true

Приоритет и ассоциативность: четыре выражения для проверки

Эти четыре выражения стоит прогнать через любой новый парсер выражений, свой или чужой:

За правую ассоциативность отвечает метод power: правый операнд он разбирает через unary, а тот через power, и цепочка 2 ^ 3 ^ 2 сворачивается справа. Значение выражения -2 ^ 2 определяет порядок правил: unary стоит выше power, значит, минус применится позже.

В математике и в Python выражение -2 ** 2 равно -4. В Excel формула =-2^2 возвращает 4: там унарный минус связывает сильнее степени. В JavaScript выражение -2 ** 2 вообще не запустится:

SyntaxError: Unary operator used immediately before exponentiation expression. Parenthesis must be used to disambiguate operator precedence

В JavaScript и Python ^ означает побитовое исключающее ИЛИ, поэтому выражение 2 ^ 3 там даёт 1. В калькуляторе ^ должен возвращать степень, иначе первый же тест 2^10 покажет 8 вместо 1024.

Функции и переменные

Вызов функции разбирается в методе primary. Если после имени стоит открывающая скобка, метод читает аргументы через запятую, и каждый аргумент это полное выражение. Поэтому вызовы функций вкладываются друг в друга: в max(sqrt(16), 2) первым аргументом служит вызов sqrt, а вторым число. Узел call содержит имя функции и список аргументов, узел var содержит имя переменной. Значения лежат в обычных объектах: FUNCTIONS для функций, CONSTANTS для констант вроде pi и vars для переменных, которые передаёт вызывающий код. Наличие имени проверяйте через Object.hasOwn: оператор in смотрит и в прототип. В JavaScript "toString" in {} возвращает true, потому что имя приходит оттуда. Пользователь напишет toString, а проверка через in вернёт ему функцию вместо сообщения. Благодаря Object.hasOwn получается Неизвестная переменная "toString".

Новые функции удобно добавлять строкой в FUNCTIONS. Неизвестная функция foo даёт CalcError с позицией имени, как и неизвестная переменная. Число аргументов функции здесь не проверяется: max принимает любое количество, а sqrt(1, 2) молча использует первый аргумент. Если нужен строгий контроль, храните в таблице рядом с функцией её арность и сравнивайте перед вызовом.

Как обрабатывать ошибки

Синтаксические ошибки бросает разбор (ParseError), ошибки вычисления бросает evaluate (CalcError). Десять выражений ниже показывают оба вида:

const { calc } = require("./parser");

const inputs = ["", "2 +", "(2 + 3", "2 3", "2 − 1", "2,5 * 2", "1 / 0", "y + 1", ".5", "(".repeat(300) + "1" + ")".repeat(300)];
for (const expr of inputs) {
  const shown = expr.length > 12 ? expr.slice(0, 8) + "..." : expr;
  try {
    console.log(JSON.stringify(shown), "=", calc(expr));
  } catch (e) {
    console.log(JSON.stringify(shown), "->", `${e.name}: ${e.message}`);
  }
}

"" -> ParseError: Ожидалось число или "(", найдено "конец выражения" (позиция 0)
"2 +" -> ParseError: Ожидалось число или "(", найдено "конец выражения" (позиция 3)
"(2 + 3" -> ParseError: Ожидалось ")", найдено "конец выражения" (позиция 6)
"2 3" -> ParseError: Лишний токен "число" (позиция 2)
"2 − 1" -> ParseError: Неожиданный символ "−" (позиция 2)
"2,5 * 2" -> ParseError: Лишний токен "," (позиция 1)
"1 / 0" -> CalcError: Деление на ноль
"y + 1" -> CalcError: Неизвестная переменная "y" (позиция 0)
".5" -> ParseError: Неожиданный символ "." (позиция 0)
"((((((((..." -> ParseError: Слишком глубокая вложенность (позиция 200)

Выражение 2 − 1 с юникодным минусом (U+2212) приходит при копировании из Word и с веб-страниц. Лексер называет незнакомый символ с позицией и не пропускает его молча.

Десятичная запятая в 2,5 * 2 даёт «Лишний токен «,»»: запятая в этой грамматике разделяет аргументы функции. Выхода два. Можно оставить точку единственным десятичным разделителем и сказать об этом пользователю, как здесь. Можно принять запятую в лексере, а аргументы функций разделять точкой с запятой, как в Excel с русской локалью.

В JavaScript выражение 1 / 0 равно Infinity, исключения нет, поэтому проверка делителя написана вручную. В Python то же деление бросает ZeroDivisionError: division by zero. Похожая тихая неприятность у sqrt(-1): JavaScript возвращает NaN, поэтому результат следует проверять на Number.isNaN.

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

Обёртка isValid из третьего блока пригодится для проверки выражения в форме. Она возвращает true, если строка разбирается, и false, если разбор бросил ParseError. Имена переменных и функций она не проверяет: isValid("y + 1") даёт true, а calc("y + 1") бросает CalcError. Любое другое исключение isValid пробрасывает дальше, чтобы не спрятать настоящую ошибку в коде.

Сумма 0.1 + 0.2 в JavaScript и в Python равна 0.30000000000000004. Так ведёт себя двоичное представление типа double, парсер тут ни при чём. Для денег в Python используется Decimal, в JavaScript считают в целых копейках.

Глубина вложенности

Каждая скобка в выражении уходит на пять вызовов вглубь: expression, term, unary, power, primary. Без ограничения парсер на Node.js 24.14.1 с настройками по умолчанию в свежем процессе падал примерно на 1700 вложенных скобках, а после прогрева держал несколько тысяч, так что заранее предел не угадать:

RangeError: Maximum call stack size exceeded

Такое выражение легко прислать нарочно: запрос закончится RangeError вместо понятной ошибки, а без try упадёт весь процесс. Чтобы сделать разбор устойчивым, в unary стоит счётчик depth с пределом MAX_DEPTH = 200, и вместо падения стека разбор заканчивается обычной ParseError. Двухсот уровней хватает для формул, которые пишут люди. Счётчик стоит именно в unary, потому что через него проходят и скобки, и цепочки минусов вроде ----1.

Модуль ast защищён от глубоких скобок сам: 200 вложенных скобок он разбирает, а на 201-й токенизатор останавливается с ошибкой SyntaxError: too many nested parentheses.

Парсер Пратта: приоритеты в таблице

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

const { Parser, evaluate } = require("./parser");

const RANK = { "+": 1, "-": 1, "*": 2, "/": 2, "^": 4 };
const NEG_RANK = 3; // унарный минус: выше * и /, ниже ^

class ClimbingParser extends Parser {
  expression(min = 1) {
    let left = this.prefix();
    for (;;) {
      const op = this.peek().type;
      const rank = RANK[op];
      if (rank === undefined || rank < min) return left;
      this.next();
      // "^" считается справа налево, остальные операторы слева направо
      const right = this.expression(op === "^" ? rank : rank + 1);
      left = { type: "bin", op, left, right };
    }
  }
  prefix() {
    if (this.match("-")) return { type: "neg", arg: this.expression(NEG_RANK) };
    return this.primary();
  }
}

module.exports = { ClimbingParser };

if (require.main === module) {
  for (const expr of ["2 + 3 * 4", "10 - 3 - 2", "2 ^ 3 ^ 2", "-2 ^ 2", "2 ^ -1", "-(1 + 2) * 3"]) {
    console.log(`${expr} = ${evaluate(new ClimbingParser(expr).parse())}`);
  }
}

Правый операнд у ^ разбирается с тем же числом, у остальных бинарных операторов с числом на единицу больше: так задаётся ассоциативность. Унарному оператору минус отведён ранг 3, между умножением и степенью, поэтому -2 ^ 2 по-прежнему даёт -4.

2 + 3 * 4 = 14
10 - 3 - 2 = 5
2 ^ 3 ^ 2 = 512
-2 ^ 2 = -4
2 ^ -1 = 0.5
-(1 + 2) * 3 = -9

Для сравнения двух парсеров мы сгенерировали 20 000 случайных выражений со скобками, минусами, степенями и функцией max, разобрали каждое обоими и сравнили деревья в JSON. Совпали все 20 000.

У ClimbingParser ограничение глубины придётся ставить отдельно: он обходит unary, и счётчик там не срабатывает.

Что добавить в парсер дальше

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

• Записи 2(3 + 1) и 2 pi многие пользователи считают нормальными. Такое неявное умножение можно реализовать в цикле метода term: если после операнда идёт число, имя или открывающая скобка, его умножают на следующий без знака. Проверка дала 2(3 + 1) = 8, но есть побочный эффект: строка 2 3 перестаёт быть ошибкой и даёт 6.
• Свёртка констант: в момент создания узла 2 * 3 можно сразу подставить число 6. Так поступают оптимизаторы компиляторов, и последующее вычисление обходит меньше узлов.
• Для пользовательских функций в таблице лежат дерево тела и список имён параметров, а при вызове evaluate получает новый набор переменных.

Безопасное вычисление через ast в Python

Если нужна только простая арифметика в Python, свой лексер не требуется. Модуль ast уже разбирает строку в дерево, остаётся обойти его и разрешить только нужные узлы:

# Python 3.14
import ast
import operator

BINARY = {
    ast.Add: operator.add,
    ast.Sub: operator.sub,
    ast.Mult: operator.mul,
    ast.Div: operator.truediv,
    ast.Pow: operator.pow,
}


def safe_eval(text):
    def walk(n):
        if isinstance(n, ast.Expression):
            return walk(n.body)
        if isinstance(n, ast.Constant) and type(n.value) in (int, float):
            return n.value
        if isinstance(n, ast.UnaryOp) and isinstance(n.op, ast.USub):
            return -walk(n.operand)
        if isinstance(n, ast.BinOp) and type(n.op) in BINARY:
            a, b = walk(n.left), walk(n.right)
            if isinstance(n.op, ast.Pow) and (abs(a) > 1e6 or abs(b) > 100):
                raise ValueError("Слишком большая степень")
            return BINARY[type(n.op)](a, b)
        name = type(getattr(n, "op", n)).__name__
        raise ValueError(f"Недопустимая конструкция: {name}")

    return walk(ast.parse(text, mode="eval"))


for src in ["2 + 3 * 4", "-2 ** 2", "2 ^ 3", "__import__('os').getcwd()",
            "9 ** 9 ** 9", "(((9 ** 100) ** 100) ** 100) ** 100", "2 +", "1 / 0",
            "-" * 999 + "1"]:
    try:
        print(repr(src[:40]), "=", safe_eval(src))
    except Exception as e:
        print(repr(src[:40]), "->", f"{type(e).__name__}: {e}")

Вывод программы:

'2 + 3 * 4' = 14
'-2 ** 2' = -4
'2 ^ 3' -> ValueError: Недопустимая конструкция: BitXor
"__import__('os').getcwd()" -> ValueError: Недопустимая конструкция: Call
'9 ** 9 ** 9' -> ValueError: Слишком большая степень
'(((9 ** 100) ** 100) ** 100) ** 100' -> ValueError: Слишком большая степень
'2 +' -> SyntaxError: invalid syntax (<unknown>, line 1)
'1 / 0' -> ZeroDivisionError: division by zero
'----------------------------------------' -> RecursionError: maximum recursion depth exceeded

Любой узел, которого нет в белом списке, приводит к исключению. Вызов __import__('os').getcwd() состоит из узла Call, поэтому он отклоняется на первом же шаге. Знак ^ в Python означает XOR, и в белом списке его нет, отсюда BitXor.

Проверка степени нужна, потому что 9 ** 9 ** 9 без неё не завершилось за 20 секунд. Одной проверки показателя мало: выражение (((9 ** 100) ** 100) ** 100) ** 100 проходит условие abs(b) > 100, но считается дольше 40 секунд. Поэтому в коде ограничены и основание (abs(a) > 1e6), и показатель. Цепочка из 999 минусов даёт RecursionError: walk упирается в лимит рекурсии Python, это обычное исключение, и except его ловит.

Какой способ выбрать

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

Алгоритм сортировочной станции не строит дерево: он преобразует выражение в обратную польскую запись, где 2 + 3 * 4 превращается в 2 3 4 * +, и считает её на стеке.

parse_expr из sympy внутри вызывает eval и для непроверенного ввода не годится. В sympy 1.14.0 вызов parse_expr("2^3") возвращает 1, потому что ^ там XOR, а sympify("2^3") возвращает 8. Библиотека math.js (версия 15.2.0) считает math.evaluate("2 + 3 * 4") как 14 без eval, но для чужого ввода в ней отключают функции import, createUnit и reviver, а при необходимости ещё evaluate, parse, simplify, derivative и resolve.

Мы бы выбирали так. Простая задача с арифметикой в Python: ast с белым списком. Калькулятор с переменными, функциями и понятными сообщениями: рекурсивный спуск. Больше десятка операторов или свой язык формул: лучше перейти на таблицу приоритетов, для языка программирования берут генератор парсеров вроде ANTLR, а для небольшого формата хватает pyparsing.

Частые вопросы

Как распарсить математическое выражение в Python?

Разобрать строку модулем ast: ast.parse(text, mode="eval") даёт дерево, которое обходят функцией с белым списком узлов, как в разделе выше. Вызов eval для пользовательского выражения использовать нельзя. Если в проекте нужны переменные и свои функции, лучше перенести парсер рекурсивного спуска: код на Python почти не отличается, методы и цикл while переписываются построчно.

Чем лексер отличается от парсера?

Лексер работает с символами и выдаёт токены, ему всё равно, стоит ли скобка на своём месте. Парсер работает с токенами и проверяет структуру выражения: закрыты ли скобки, есть ли операнд после знака. Ошибка «Неожиданный символ» приходит из лексера, а «Ожидалось число или «(«» из парсера.

Как добавить оператор, например остаток от деления?

В парсере рекурсивного спуска три правки: символ % в строку допустимых знаков лексера, условие this.match("*", "/", "%") в методе term и case "%": return a % b; в evaluate. В парсере Пратта метод term не нужен, вместо него строка "%": 2 в таблице RANK, а правки лексера и evaluate остаются: без case "%" вычисление упадёт с Error: Неизвестный узел: bin. Знак остатка в различных языках разный: в JavaScript -7 % 3 даёт -1 (знак делимого), в Python 2 (знак делителя).

Как посчитать одно выражение с разными значениями переменных?

Дерево даёт возможность разобрать выражение один раз, а вычислять много раз: оно хранит только структуру, значения переменных приходят в evaluate:

const { Parser, evaluate } = require("./parser");

const tree = new Parser("x * 2 + 1").parse(); // разбор один раз
console.log([1, 2, 3].map((x) => evaluate(tree, { x })));

[ 3, 5, 7 ]