Рекурсивный спуск

Рекурсивный спуск — самый понятный способ написать парсер вручную: по функции на каждое правило грамматики.

Рекурсивный спуск — метод нисходящего разбора, где каждому нетерминалу грамматики соответствует своя функция, а взаимные вызовы повторяют структуру правил.

Мы уже описали грамматику выражений уровнями expr → term → factor. Самое красивое в рекурсивном спуске: эта грамматика почти буквально превращается в код. Каждое правило становится функцией, а ссылки на другие нетерминалы — вызовами.

Поток токенов и текущий токен

Парсеру нужно читать токены по очереди и «подсматривать» текущий. Заведём небольшой класс с указателем.

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos]

    def eat(self, ttype):
        tok = self.tokens[self.pos]
        if tok[0] != ttype:
            raise SyntaxError("Ожидал " + ttype + ", получил " + tok[0])
        self.pos += 1
        return tok

p = Parser([("NUMBER", 7), ("EOF", None)])
print(p.peek())
print(p.eat("NUMBER"))
print(p.peek())

Вывод:

('NUMBER', 7)
('NUMBER', 7)
('EOF', None)

Метод peek смотрит на текущий токен, не сдвигая указатель. Метод eat требует токен ожидаемого типа: если он совпадает — съедает его и идёт дальше, если нет — это синтаксическая ошибка.

Функции на каждое правило

Теперь переведём грамматику в функции. Пока пусть они только проверяют синтаксис (значение посчитаем в следующих уроках).

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens; self.pos = 0
    def peek(self): return self.tokens[self.pos]
    def eat(self, t):
        tok = self.tokens[self.pos]
        if tok[0] != t: raise SyntaxError("Ждал " + t)
        self.pos += 1; return tok

    def expr(self):           # expr = term { (+|-) term }
        self.term()
        while self.peek()[0] in ("PLUS", "MINUS"):
            self.eat(self.peek()[0]); self.term()

    def term(self):           # term = factor { (*|/) factor }
        self.factor()
        while self.peek()[0] in ("STAR", "SLASH"):
            self.eat(self.peek()[0]); self.factor()

    def factor(self):         # factor = NUMBER | ( expr )
        if self.peek()[0] == "NUMBER":
            self.eat("NUMBER")
        else:
            self.eat("LPAREN"); self.expr(); self.eat("RPAREN")

toks = [("NUMBER",2),("PLUS","+"),("NUMBER",3),("STAR","*"),("NUMBER",4),("EOF",None)]
p = Parser(toks)
p.expr()
print("Синтаксис корректен, разобрано токенов:", p.pos)

Вывод:

Синтаксис корректен, разобрано токенов: 5

Как работает под капотом

«Нисходящий» означает, что разбор идёт от стартового символа вниз. Вызывая expr, мы спускаемся в term, оттуда в factor, а если встретили скобку — снова поднимаемся в expr через рекурсию. Цепочка вызовов на стеке буквально повторяет структуру выражения. Отсюда и название «рекурсивный спуск».

Частые ошибки

Самая частая — не съесть оператор в цикле. Если в expr вызвать term, но забыть eat для +, парсер зациклится на одном токене. Каждый распознанный токен обязан быть «съеден».

Вторая — забыть проверить EOF в конце. Если после expr остались лишние токены (например, 2 + 3 )), это ошибка, но без финальной проверки парсер её проглотит.

Итог

• Рекурсивный спуск даёт по функции на каждый нетерминал грамматики.
• peek смотрит на токен, eat требует и съедает ожидаемый тип.
• Циклы внутри функций реализуют EBNF-повторения { }.
• Структура вызовов на стеке повторяет структуру разбираемого выражения.