Я был еще школьником, когда мне в руки попала книжка «Начальный курс C и С++» от издательства Диалог МИФИ. Именно из этой книжки я узнал об основах объектно ориентированного программирования, и она же поставила передо мной проблему, которую я довольно долго не мог разрешить. В конце её было приложение с листингом программ одна из которых называлась рекурсивный калькулятор. Это и была моя первая встреча с разбором арифметических выражений методом рекурсивного спуска. До сих пор помню те долгие часы, которые были потрачены на попытки хоть что-то понять в этом коде.

Статья предназначена прежде всего для тех, кто первый раз сталкивается с задачей разбора выражений.

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

Для описания структуры воспользуемся формами Бекуса-Наура

E -> T + E | T - E | T
T -> F * T | F / T | F
F -> N     | (E)

Здесь вертикальная черта "|" означает логическую операцию «или», а E, T, F, N — различные виды подвыражений, на которое будет разбиваться исходное выражение при использовании данных предложений. N в данном случае обозначает число.

Первое предложение означает, что выражение типа E может состоять из выражения типа Т плюс выражение типа E, или из выражения типа Т минус выражение типа E или просто из выражения типа T.

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

Третье предложение означает, что выражение типа F это или число или выражение типа E, заключенное в скобки.

Давайте попробуем применить данные три предложения к примеру арифметического выражения

2 + 3 * ( 4 - 5 ) + 6 - 7

Применим первое предложение несколько раз

E(2+3*(4-5)+6-7) -> 
T(2) + E(3*(4-5)+6-7) -> 
T(2) + T(3*(4-5)) + E(6-7) -> 
T(2) + T(3*(4-5)) + T(6) - T(7)

Теперь наше выражение состоит только из подвыражений типа T, поэтому применяем второе предложение к каждому из них.

T(2) -> F(2)
T(3*(4-5)) -> F(3) * T((4-5)) -> F(3) * F((4-5))
T(6) -> F(6)
T(7) -> F(7)

Пришло время третьего предложения

F(2) -> N(2) -> 2
F(3) -> N(3) -> 3
F((4-5)) -> E(4-5)
F(6) -> N(6) -> 6
F(7) -> N(7) -> 7

Для выражения в скобках (4-5) мы тут рекурсивно перешли к первому предложению и должны будем повторить все действия по аналогии с тем, как это было для остальных частей выражения. Если бы выражение содержало вложенные скобки, то таких рекурсивных переходов было бы больше. Я бы рекомендовал вам самостоятельно попробовать применить все три предложения для выражения, которое содержало бы вложенные уровни скобок, например 2+2*(3+4*(5-6)), чтобы убедиться, что они работают и для него.

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

Если бесконечно подставлять первое предложение в само себя, то мы получим

E -> T±T±T±T± ... ±T

Второе предложение можно преобразовать аналогичным образом

T -> F*/F*/F*/*/ ... */F

Фактически это означает, что вместо рекурсии мы тут сможем использовать цикл. Из третьего предложения подобным образом рекурсию исключить не получиться.

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

String[] tokens = {"2", "+", "3", "*", "(", "4", "-", "5", ")", "+", "6", "-", "7"};

Создадим следующий класс парсера, который будет содержать методы

• parse() запускает разбор выражения
• expression() для обработки выражений типа E
• term() для обработки выражений типа T
• factor() для обработки выражений типа F и N

public class RecursiveDescentParser {

    private final List<String> tokens;
    private int pos = 0; // индекс текущего токена

    public RecursiveDescentParser(String[] tokens) {
        this.tokens = tokens;
    }

    public Double parse() {
        Double result = expression();
        if (pos != tokens.length) {
            throw new IllegalStateException("Error in expression at " + tokens[pos]));
        }
        return result;
    }

    // E -> T±T±T±T± ... ±T
    private Double expression() {
        // находим первое слагаемое
        Double first = term();

        while (pos < tokens.length) {
            String operator = tokens[pos];
            if (!operator.equals("+") && !operator.equals("-")) {
                break;
            } else {
                pos++;
            }

            // находим второе слагаемое (вычитаемое)
            Double second = term();
            if (operator.equals("+")) {
                first += second;
            } else {
                first -= second;
            }
        }
        return first;
    }

    // T -> F*/F*/F*/*/ ... */F
    private Double term() {
        // находим первый множитель
        Double first = factor();

        while (pos < tokens.length) {
            String operator = tokens[pos];
            if (!operator.equals("*") && !operator.equals("/")) {
                break;
            } else {
                pos++;
            }

            // находим второй множитель (делитель)
            Double second = factor();
            if (operator.equals("*")) {
                first *= second;
            } else {
                first /= second;
            }
        }
        return first;
    }
    
    // F -> N | (E)
    private Double factor() {
        String next = tokens[pos];
        Double result;
        if (next.equals("(")) {
            pos++;
            // если выражение в скобках, то рекурсивно переходим на обработку подвыражения типа Е
            result = expression();  
            String closingBracket = tokens[pos];
            if (pos < tokens.length && closingBracket.equals(")")) {
                pos++;
                return result;
            }
            throw new IllegalStateException("')' expected but " + closingBracket);
        }
        pos++;
        // в противном случае токен должен быть числом
        return Double.parseDouble(next);
    }
}

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