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

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

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

• Часть 1. Токенизация (вы находитесь здесь)
• Часть 2. Вычисление выражения в обратной польской записи
• Часть 3. Алгоритм сортировочной станции
• Часть 4: Парсер рекурсивного спуска
• Часть 5: Парсер Пратта
• Часть 6. Перевод из постфиксной формы в инфиксную

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

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

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

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

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

• калькулятор выражений в обратной польской записи (Reverse Polish Notation);
• алгоритм сортировочной станции (Shunting Yard Algorithm);
• рекурсивный разбор (Recursive Descent Parser);
• парсер Пратта с динамическим управлением приоритетами.

В итоге каждый написанный парсер будет способен обрабатывать выражения, содержащие:

• целые и вещественные числа;
• базовые математические операции: сложение, вычитание, умножение, деление и возведение в степень;
• круглые скобки для изменения порядка действий – ( и );
• унарный минус (отличить вычитание от унарной операции не такая простая задача) – -(2+4) против 2-4;
• функции одного и двух аргументов: sin(x), cos(x), max(x, y), ...;
• математические константы: π, e;
• переменные: x, y, var123, ...;

Но начнём мы эту серию с этапа, без которого не обходится ни один парсер – с токенизации выражения.

Токенизация

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

2.57 * sin(x + pi) - ln(10)

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

["2.57", "*", "sin", "(", "x", "+", "pi", ")", "-", "ln", "(", "10", ")"]

Мы реализуем токенизатор как отдельный класс ExpressionTokenizer, который:

• позволяет управлять списком поддерживаемых функций и констант;
• игнорирует пробельные символы;
• сохраняет позиции токенов для информативности;
• проверяет выражение на наличие неподдерживаемых символов;
• использует регулярные выражения с именованными группами ((?<name>...));
• удобно интегрируется с будущими парсерами.

Какие токены нам нужны?

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

Нас будут интересовать следующие типы токенов:

• Числа – как целые, так и дробные (3, -2.5, 0.01);
• Константы – вроде pi, π, e, заранее заданные при инициализации;
• Функции – как sin, log, sqrt, передающиеся явно при создании токенизатора;
• Переменные – любые имена, например x, temperature, v_0;
• Операторы – такие как +, -, *, /, ^;
• Скобки – ( и ), определяющие приоритет операций;
• Разделители аргументов функции – , для функций, принимающих более одного аргумента;
• Любые другие символы – такие как ?, @, !, которые не должны присутствовать и будут выделены как ошибки.

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

-3 * ln(1 + x^2) / PI

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

Пишем токенизатор

Для преобразования строки выражения в список токенов мы создадим отдельный файл expression_tokenizer.js с классом ExpressionTokenizer. Конструктор токенизатора будет принимать два списка: имена допустимых функций (functions) и названия поддерживаемых констант (constants).

Сама токенизация будет происходить в методе tokenize, принимающим строку с выражением. При вызове будет возвращаться список токенов, каждый из которых будет содержать:

• type – тип токена (number, operator, function, ...);
• value – текстовое значение токена;
• start и end – индексы данного токена в исходной строке.

class ExpressionTokenizer {
    constructor({functions, constants}) {

    }

    tokenize(expression) {
        return ...
    }
}

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

constructor({functions, constants}) {
    this.regexp = new RegExp([
        `(?<left_parenthesis>\\()`, // открывающая скобка
        `(?<right_parenthesis>\\))`, // закрывающая скобка
        `(?<delimeter>,)`, // разделитель аргументов функции
        `(?<operator>[-+*/^])`, // операции
        `(?<function>${functions.join("|")})`, // функции
        `(?<constant>\\b(${constants.join("|")})\\b)`, // константы
        `(?<number>\\d+(\\.\\d+)?)`, // целые и вещественные числа
        `(?<variable>[a-z]\\w*)`, // переменные
        `(?<unknown>\\S)` // все остальные символы, кроме пробельных
    ].join("|"), "gi")
}

Чтобы разбить строку на токены, воспользуемся методом строки matchAll: он принимает регулярное выражение и возвращает итератор с обнаруженными совпадениями (matches). Нам нужно из этих совпадений сформировать токены, для чего напишем вспомогательный метод matchToToken. В нём нам нужно определить, к какой из именованных групп относится выделенная подстрока:

tokenize(expression) {
    const matches = expression.matchAll(this.regexp) // ищем все совпадения
    const tokens = [...matches.map(match => this.matchToToken(match))] // преобразуем в токены

    return tokens
}

// метод, преобразующий совпадение в токен
matchToToken(match) {
    for (const [type, value] of Object.entries(match.groups))
        if (value)
            return {type: type, value: value, start: match.index, end: match.index + value.length}

    return null
}

Теперь, нам нужно проверить, не было ли обнаружено в выражении недопустимых символов. Если среди токенов будет хотя бы один с типом unknown, то нам нужно сообщить об ошибке (в качестве ошибки мы будем кидать исключение Error):

class ExpressionTokenizer {
    ...

    tokenize(expression) {
        const matches = expression.matchAll(this.regexp)
        const tokens = [...matches.map(match => this.matchToToken(match))]

        const unknown = tokens.filter(token => token.type === "unknown")
        if (unknown.length > 0)
            throw new Error(`invalid tokens found: ${unknown.map(token => token.value).join(", ")}`)

        return tokens
    }
}

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

const tokenizer = new ExpressionTokenizer({functions: ["sin", "cos", "max"], constants: ["pi", "e"]})
const tokens = tokenizer.tokenize("-2e^-x * sin(x + pi)^2")

В результате в переменной tokens будет храниться такой массив:

[
    {"type": "operator", "value": "-", "start": 0, "end": 1},
    {"type": "number", "value": "2", "start": 1, "end": 2},
    {"type": "variable", "value": "e", "start": 2, "end": 3},
    {"type": "operator", "value": "^", "start": 3, "end": 4},
    {"type": "operator", "value": "-", "start": 4, "end": 5},
    {"type": "variable", "value": "x", "start": 5, "end": 6},
    {"type": "operator", "value": "*", "start": 7, "end": 8},
    {"type": "function", "value": "sin", "start": 9, "end": 12},
    {"type": "left_parenthesis", "value": "(", "start": 12, "end": 13},
    {"type": "variable", "value": "x", "start": 13, "end": 14},
    {"type": "operator", "value": "+", "start": 15, "end": 16},
    {"type": "constant", "value": "pi", "start": 17, "end": 19},
    {"type": "right_parenthesis", "value": ")", "start": 19, "end": 20},
    {"type": "operator", "value": "^", "start": 20, "end": 21},
    {"type": "number", "value": "2", "start": 21, "end": 22}
]

При этом попытка токенизировать некорректное выражение приведёт к ошибке:

tokenizer.tokenize("1 + 2 * !3 -> sin(x)") // Uncaught Error: invalid tokens found: !, >

Заключение

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

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

class ExpressionTokenizer {
    constructor({functions, constants}) {
        this.regexp = new RegExp([
            `(?<left_parenthesis>\\()`,
            `(?<right_parenthesis>\\))`,
            `(?<delimeter>,)`,
            `(?<operator>[-+*/^])`,
            `(?<function>${functions.join("|")})`,
            `(?<constant>\\b(${constants.join("|")})\\b)`,
            `(?<number>\\d+(\\.\\d+)?)`,
            `(?<variable>[a-z]\\w*)`,
            `(?<unknown>\\S)`
        ].join("|"), "gi")
    }

    tokenize(expression) {
        tokenize(expression) {
        const matches = expression.matchAll(this.regexp)
        const tokens = [...matches.map(match => this.matchToToken(match))]

        const unknown = tokens.filter(token => token.type === "unknown")
        if (unknown.length > 0)
            throw new Error(`invalid tokens found: ${unknown.map(token => token.value).join(", ")}`)

        return tokens
    }

    matchToToken(match) {
        for (const [type, value] of Object.entries(match.groups))
            if (value)
                return {type: type, value: value, start: match.index, end: match.index + value.length}

        return null
    }
}