Что такое Метод рекурсивного спуска: простой способ написать парсер

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

Что такое рекурсивный спуск?

Метод рекурсивного спуска строится на базе контекстно-свободной грамматики. Каждое правило грамматики реализуется в виде функции, которая вызывает другие функции по мере необходимости — тем самым «спускаясь» по дереву разбора.

Например, для грамматики простого арифметического выражения:

Expr   → Term (('+' | '-') Term)*
Term   → Factor (('*' | '/') Factor)*
Factor → NUMBER | '(' Expr ')'

мы можем написать три функции: parseExpr(), parseTerm() и parseFactor().

sealed class Expr {
    data class Num(val value: Double) : Expr()
    data class BinOp(val left: Expr, val op: Char, val right: Expr) : Expr()
}

class Parser(private val tokens: List<String>) {
    private var pos = 0

    private fun current(): String? = tokens.getOrNull(pos)
    private fun eat(expected: String): Boolean {
        if (current() == expected) {
            pos++
            return true
        }
        return false
    }

    fun parseExpr(): Expr {
        var expr = parseTerm()
        while (current() == "+" || current() == "-") {
            val op = current()!![0]
            pos++
            val right = parseTerm()
            expr = Expr.BinOp(expr, op, right)
        }
        return expr
    }

    private fun parseTerm(): Expr {
        var term = parseFactor()
        while (current() == "*" || current() == "/") {
            val op = current()!![0]
            pos++
            val right = parseFactor()
            term = Expr.BinOp(term, op, right)
        }
        return term
    }

    private fun parseFactor(): Expr {
        val token = current()
        return when {
            token == "(" -> {
                pos++
                val expr = parseExpr()
                if (!eat(")")) error("Expected ')'")
                expr
            }
            token?.toDoubleOrNull() != null -> {
                pos++
                Expr.Num(token.toDouble())
            }
            else -> error("Unexpected token: $token")
        }
    }
}

Пример использования:

fun main() {
    val input = "(2 + 3) * 4"
    val tokens = input.replace("(", " ( ").replace(")", " ) ")
        .split("\\s+".toRegex()).filter { it.isNotBlank() }

    val parser = Parser(tokens)
    val result = parser.parseExpr()
    println(result)
}

Простыми словами

Метод рекурсивного спуска — это способ написать парсер, то есть программу, которая читает и разбирает текст по правилам, например, математическое выражение вроде 2 + 3 * 4.

Простыми словами:

1. У тебя есть набор правил, как должно выглядеть выражение:
   • Выражение (Expr) состоит из слагаемых и плюсов/минусов.
   • Слагаемое (Term) состоит из множителей и знаков умножения/деления.
   • Множитель (Factor) — это число или выражение в скобках.
2. На каждое правило ты пишешь функцию.
   • parseExpr() — ищет плюсы/минусы.
   • parseTerm() — ищет умножение/деление.
   • parseFactor() — ищет число или выражение в скобках.
3. Каждая функция вызывает другую — рекурсивно. Это и называется “спуск” — сверху вниз, от выражения к самому простому элементу.

Пример:

Чтобы разобрать "2 + 3 * 4", твой код сначала:

• увидит 2 → это Factor,
• потом + → значит, это Expr,
• потом 3 * 4 → тоже разберёт как Term с Factor-ами.

В итоге ты получаешь дерево, где видно, что 3 * 4 нужно считать раньше, чем складывать с 2.

Это как инструкция:

• сначала прочитай часть, которая в скобках (или число),
• потом проверь, есть ли умножение,
• потом проверь, есть ли сложение.

Метод работает пошагово и вызывает сам себя по мере необходимости.

Схема работы рекурсивного спуска

Вот как выглядит схема вызовов функций при разборе выражения 2 + 3 * 4:

parseExpr
 └── parseTerm
     └── parseFactor -> 2
 └── '+'
 └── parseTerm
     └── parseFactor -> 3
     └── '*'
     └── parseFactor -> 4

Преимущества

• Простота реализации.
• Хорошо подходит для небольших языков и DSL.
• Код читаемый и расширяемый.

Недостатки

• Не поддерживает леворекурсивные грамматики напрямую.
• Подходит только для LL(1) грамматик (анализ слева направо, один символ вперёд).
• Может потребовать много кода при сложной грамматике.

Заключение

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