usharik.dev

← Все статьи

Разбор выражений рекурсивным спуском: новая версия на Java 21

Опубликовано · Алексей Ушаровский

Впервые опубликовано на Хабре 24 февраля 2020; здесь переработанная и обновлённая версия.

Я ещё учился в школе, когда мне попалась книжка «Начальный курс C и C++». В конце был листинг «рекурсивный калькулятор», и я много вечеров не мог понять, как несколько коротких функций вычисляют 2 + 3 * (4 - 5). В 2020 году я написал об этом статью на Хабре. Здесь та же идея шесть лет спустя: с тем, что я теперь объяснил бы студенту в первую очередь, и на современной Java.

Вся программа — один файл: Calc.java. Запуск — java Calc.java, Java 21 компилирует его сама.

Сначала грамматика

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

expression -> term   (('+' | '-') term)*
term       -> factor (('*' | '/') factor)*
factor     -> NUMBER | '(' expression ')'

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

Приоритет получается из уровней. * связывает сильнее +, потому что умножение разбирается на уровень глубже: когда expression видит +, метод term уже забрал 3 * (4 - 5) целиком.

Ловушка в версии 2020 года

В старой статье правила были записаны рекурсивно:

E -> T + E | T - E | T

Выглядит так же, но это не так. Если реализовать дословно, 10 - 4 - 3 превратится в 10 - (4 - 3) = 9: рекурсия группирует справа. А вычитание и деление левоассоциативны и группируются слева: (10 - 4) - 3 = 3.

Код в 2020 году всё равно давал верный ответ, потому что рекурсию я заменил циклом и накапливал результат слева направо. Грамматика и код расходились, и в тексте об этом не было ни слова. В правилах выше вместо правой рекурсии повторение (*), и грамматика говорит ровно то, что делает цикл.

Сначала токены

Старая статья пропускала разбиение на токены и начинала с готового массива строк. Токенизатор короткий, и именно в нём удобнее всего сообщать об ошибках вроде 1 # 2, так что он здесь есть. Токены — records за sealed-интерфейсом:

sealed interface Token permits Num, Name, Sym {}
record Num(double value) implements Token {}
record Name(String text) implements Token {}
record Sym(char c) implements Token {}

Токенизатор проходит строку один раз: цифры и точки становятся Num, буквы с цифрами — Name, любой из символов +-*/^(), — Sym, пробелы пропускаются, всё остальное — ошибка с позицией.

Строим дерево, потом вычисляем

В 2020 году парсер вычислял результат прямо по ходу разбора. Для калькулятора это нормально, но дерево полезнее: его можно напечатать, упростить, вычислить для многих значений x или скомпилировать. С records дерево почти ничего не стоит:

sealed interface Expr permits Number, Var, Unary, Binary, Call {}
record Number(double value) implements Expr {}
record Var(String name) implements Expr {}
record Unary(char op, Expr operand) implements Expr {}
record Binary(char op, Expr left, Expr right) implements Expr {}
record Call(String function, List<Expr> args) implements Expr {}

Расширяем грамматику

Добавим то, что нужно настоящему калькулятору: унарный минус, степень, переменные и функции вроде max(1, x * 2, sqrt(16)).

expression -> term (('+' | '-') term)*
term       -> unary (('*' | '/') unary)*
unary      -> '-' unary | power
power      -> primary ('^' unary)?
primary    -> NUMBER | NAME | NAME '(' args ')' | '(' expression ')'

Здесь спрятаны два решения.

Каждое правило — один метод. Два цикла — это левоассоциативные правила:

private Expr expression() {
    Expr left = term();
    while (peek('+') || peek('-')) {
        char op = next();
        left = new Binary(op, left, term());
    }
    return left;
}

private Expr term() {
    Expr left = unary();
    while (peek('*') || peek('/')) {
        char op = next();
        left = new Binary(op, left, unary());
    }
    return left;
}

private Expr unary() {
    if (peek('-')) {
        next();
        return new Unary('-', unary());
    }
    return power();
}

private Expr power() {
    Expr base = primary();
    if (peek('^')) {
        next();
        return new Binary('^', base, unary()); // правая ассоциативность: 2^3^2 = 2^9
    }
    return base;
}

В primary окупается сопоставление с образцом из Java 21. Один switch по sealed-типу токена выбирает между числом, вызовом функции, переменной и скобкой, а компилятор проверяет, что ни один случай не забыт:

private Expr primary() {
    if (pos >= tokens.size()) throw error("unexpected end of expression");
    Token t = tokens.get(pos++);
    return switch (t) {
        case Num n -> new Number(n.value());
        case Name n when peek('(') -> call(n.text());
        case Name n -> new Var(n.text());
        case Sym s when s.c() == '(' -> {
            Expr inner = expression();
            expect(')');
            yield inner;
        }
        case Sym s -> throw error("unexpected '" + s.c() + "'");
    };
}

Вычисление — ещё один switch, теперь по дереву:

static double eval(Expr e, Map<String, Double> vars) {
    return switch (e) {
        case Number n -> n.value();
        case Var v -> { /* значение переменной из vars */ }
        case Unary u -> -eval(u.operand(), vars);
        case Binary b -> { /* +, -, *, /, ^ над двумя сторонами */ }
        case Call c -> { /* sqrt, sin, max */ }
    };
}

Проверяем

Метод main из файла печатает:

2 + 3 * (4 - 5) + 6 - 7      = -2.0   ok
2 + 2 * (3 + 4 * (5 - 6))    = 0.0    ok
10 - 4 - 3                   = 3.0    ok
-2 ^ 2                       = -4.0   ok
2 ^ 3 ^ 2                    = 512.0  ok
2 * -x                       = -6.0   ok
max(1, x * 2, sqrt(16))      = 6.0    ok
-(1 + 2) * 3                 = -9.0   ok
2 +                          -> unexpected end of expression at token 2
(1 + 2                       -> ')' expected at token 4
2 3                          -> unexpected Num[value=3.0] at token 1
1 # 2                        -> Unexpected character '#' at 2

Дерево для 2 + 3 * x печатают сами records:

Binary[op=+, left=Number[value=2.0], right=Binary[op=*, left=Number[value=3.0], right=Var[name=x]]]

Что вынести из статьи

Хорошее упражнение: добавьте сравнения новым верхним правилом comparison -> expression (('<' | '==') expression)? и начинайте разбор с него, а поверх — тернарный оператор a ? b : c. Если грамматика верна, код пишется почти механически.

Исходные файлы