Разбор рекурсивным спуском: по функции на каждый нетерминал

Если ты напишешь по грамматике выражений три функции, объяснишь, почему правило E → E - T нельзя перенести в код как есть, и скажешь, чем цикл отличается от правой рекурсии, - листай до «Теперь сам».

Как думаешь, что сделает функция, которая начинается с вызова себя

Грамматика говорит: E → E - T. Перенесём дословно: функция E сначала вызывает функцию E, чтобы разобрать левую часть, потом читает минус, потом вызывает T.

Ответь себе до чтения: сколько токенов прочитает такая функция на строке 8 - 3 - 2? Ни одного. Первое, что она делает, - вызывает себя с той же позиции в строке; вызванная делает то же самое, и так до переполнения стека. Грамматика правильная и однозначная, язык тот, что нужен, а программа по ней не работает. Значит, годится не любая грамматика, и нужно понять, какая.

На что это похоже

Разбор адреса на конверте. «Адрес - это индекс, город, улица, дом». Читаешь индекс - для него своё правило, шесть цифр. Потом город - своё правило. Каждое правило знает, с чего оно начинается, съедает свою часть строки и возвращает управление тому, кто его вызвал.

Правило «список - это список и ещё один элемент» так прочитать нельзя: чтобы начать читать список, нужно сначала прочитать список. Человек читает иначе: «элемент, и дальше, пока идут запятые, ещё элементы». Это то же самое правило, переписанное так, чтобы у него было начало.

Механизм: грамматика как программа

Перед разбором текст режут на токены - числа, знаки, скобки; пробелы выбрасываются. Разборщик видит список токенов и позицию в нём.

На каждый нетерминал пишется функция. Договор у всех один: функция начинает с текущей позиции, читает ровно те токены, что составляют её нетерминал, сдвигает позицию за них и возвращает результат - значение или узел дерева. Правая часть правила читается слева направо: терминал - сверить токен и сдвинуться; нетерминал - вызвать его функцию.

Когда у нетерминала несколько правил, функция выбирает одно, глядя на очередной токен. Для множителя F → число | ( E ) выбор очевиден: скобка - второе правило, число - первое. Грамматики, в которых одного токена всегда достаточно для выбора, называют LL(1): чтение слева направо, вывод левый, один токен вперёд. Разборщик для такой грамматики не возвращается назад и читает каждый токен один раз.

Левая рекурсия. Правило вида E → E - T начинается с того же нетерминала, который определяет. Его нельзя выполнить как написано. Посмотрим, что порождает правило E → E - T | T: E ⇒ E - T ⇒ E - T - T ⇒ T - T - T. Каждое применение дописывает справа «минус и T», а последний шаг заменяет оставшееся E на T. Получается одно T, а за ним сколько угодно раз «минус и T». Это и записывают:

было                     стало
E → E + T | E - T | T    E → T { (+ | -) T }
T → T * F | F            T → F { * F }
F → число | ( E )        F → число | ( E ) | - F

фигурные скобки - повтор ноль или более раз

Круглые скобки в правиле E - группировка «плюс или минус» в записи правила, а в правиле F - символы языка. Повтор в фигурных скобках превращается в цикл while: пока очередной токен - плюс или минус, прочитать его и ещё одно T. Язык тот же с одной добавкой, которая к приёму не относится: в правило F дописан минус перед множителем, как в -5. Его называют унарным - у него один операнд.

Стек магазинного автомата никуда не делся: это стек вызовов. Каждая открытая скобка - это вызов функции выражения, который ещё не вернулся.

Правило

Рекурсивный спуск: одна функция на нетерминал; функция читает токены своего нетерминала и возвращает результат; выбор правила - по очередному токену. Леворекурсивное правило A → A x | y заменяется на A → y { x } и пишется циклом. Цикл, накапливающий результат слева, даёт группировку слева направо; рекурсивный вызов в правой части - справа налево. При выборе по одному токену разбор занимает время, пропорциональное числу токенов.

Разбор: калькулятор в три функции

Функция razbit режет текст на токены и дописывает в конец метку "конец", чтобы не проверять границу списка на каждом шаге. Дальше три функции по трём строкам грамматики; позиция хранится в списке из одного элемента poz. Число, переданное в функцию, она у вызвавшего изменить не может, а элемент списка - может, и так позицию двигают все три.

def razbit(tekst):
    tokeny = []
    i = 0
    while i < len(tekst):
        if tekst[i] == " ":
            i = i + 1
        elif tekst[i] in "0123456789":
            chislo = 0
            while i < len(tekst) and tekst[i] in "0123456789":
                chislo = chislo * 10 + int(tekst[i])
                i = i + 1
            tokeny.append(chislo)
        else:
            tokeny.append(tekst[i])
            i = i + 1
    tokeny.append("конец")
    return tokeny

def vyrazhenie(t, poz):
    # E → T { (+ | -) T }
    znachenie = slagaemoe(t, poz)
    while t[poz[0]] == "+" or t[poz[0]] == "-":
        znak = t[poz[0]]
        poz[0] = poz[0] + 1
        pravoe = slagaemoe(t, poz)
        if znak == "+":
            znachenie = znachenie + pravoe
        else:
            znachenie = znachenie - pravoe
    return znachenie

def slagaemoe(t, poz):
    # T → F { * F }
    znachenie = mnozhitel(t, poz)
    while t[poz[0]] == "*":
        poz[0] = poz[0] + 1
        znachenie = znachenie * mnozhitel(t, poz)
    return znachenie

def mnozhitel(t, poz):
    # F → число | ( E ) | - F
    tok = t[poz[0]]
    poz[0] = poz[0] + 1
    if tok == "(":
        znachenie = vyrazhenie(t, poz)
        poz[0] = poz[0] + 1
        return znachenie
    if tok == "-":
        return 0 - mnozhitel(t, poz)
    return tok

teksty = ["2 + 3 * 4", "(2 + 3) * 4", "8 - 3 - 2", "-(1 + 2) * 3"]
teksty = teksty + ["2 * (3 + 4) * (5 - 1)", "((((7))))"]
for tekst in teksty:
    t = razbit(tekst)
    poz = [0]
    print(vyrazhenie(t, poz), poz[0], len(t) - 1)

14 5 5
20 7 7
3 5 5
-9 8 8
56 13 13
7 9 9

В каждой строке - значение, позиция после разбора и число токенов без метки конца. Второе и третье числа совпадают: разбор дошёл ровно до конца. Назад он не возвращался: в программе позиция только растёт.

Приоритет получился сам собой из вложенности функций. В 2 + 3 * 4 функция выражения вызывает функцию слагаемого для правой части плюса, и та забирает 3 * 4 целиком, прежде чем вернуться. Скобки работают потому, что множитель, встретив (, вызывает выражение заново - это и есть рекурсия спуска. Унарный минус в -(1 + 2) * 3 относится к множителю (1 + 2), а не ко всему произведению; результат тот же, -9, но для степени разница была бы видна: -(2²) и (-2)² - разные числа.

Проверки ошибок в программе нет. На тексте 2 + функция множителя заберёт метку конца вместо числа, и следующее же обращение к токену выйдет за границу списка; на (2 метка конца будет перешагнута на месте закрывающей скобки, и кончится тем же; на 2 3 разбор остановится на первом токене и сочтёт дело сделанным. Настоящему разборщику нужны три проверки: что множитель начинается с допустимого токена, что на месте закрывающей скобки стоит она, и что после выражения текст кончился.

Разбор: три способа прочитать вычитание

Три функции для выражения из чисел и минусов. levaya - правило E → E - число | число как есть; чтобы программа не упала, она останавливается на глубине 50 и сообщает, сколько токенов прочитано. pravaya - правило E → число - E | число, рекурсия справа. ciklom - правило E → число { - число }.

def levaya(t, poz, glubina):
    if glubina == 50:
        return "глубина 50, прочитано токенов: " + str(poz[0])
    return levaya(t, poz, glubina + 1)

def pravaya(t, poz):
    levoe = t[poz[0]]
    poz[0] = poz[0] + 1
    if poz[0] < len(t) and t[poz[0]] == "-":
        poz[0] = poz[0] + 1
        return levoe - pravaya(t, poz)
    return levoe

def ciklom(t, poz):
    znachenie = t[poz[0]]
    poz[0] = poz[0] + 1
    while poz[0] < len(t) and t[poz[0]] == "-":
        znachenie = znachenie - t[poz[0] + 1]
        poz[0] = poz[0] + 2
    return znachenie

for t in [[8, "-", 3, "-", 2], [100, "-", 10, "-", 1, "-", 1]]:
    print(pravaya(t, [0]), ciklom(t, [0]))
print(levaya([8, "-", 3, "-", 2], [0], 0))

7 3
90 88
глубина 50, прочитано токенов: 0

Правая рекурсия разбирает строку без ошибок и даёт 7: она прочитала 8 - 3 - 2 как 8 - (3 - 2). Язык тот же, каждая строка разобрана, дерево у каждой одно - а ответ неверный, потому что дерево не то. Цикл даёт 3: он вычитает по мере чтения, слева направо. На четырёх числах расхождение 90 против 88.

Левая рекурсия за пятьдесят вложенных вызовов не прочитала ни одного токена: первое действие функции - вызов себя с той же позиции.

Правая рекурсия не всегда ошибка. Возведение в степень принято группировать справа: 2 ^ 3 ^ 2 - это 2 ^ 9, а не 8 ^ 2 (значок ^ здесь - степень, как в математической записи; в Python её пишут **). Для такой операции правило P → F ^ P | F и рекурсивный вызов в правой части - то, что нужно. Направление группировки - решение, которое принимает автор грамматики, и в коде оно видно сразу: цикл или рекурсия.

Что ломается без этого

Леворекурсивное правило перенесено в код дословно. Программа падает с переполнением стека на любом входе, включая пустой. Скрытая форма того же - левая рекурсия через два правила: A → B x, B → A y.

Левую рекурсию заменили правой, «чтобы работало». Работает, пока операции - сложение и умножение. Вычитание и деление начинают давать неверные ответы без единой ошибки разбора.

Два правила начинаются с одного токена. S → if E then S | if E then S else S: по токену if не выбрать. Общую часть выносят: прочитать if E then S, а потом посмотреть, идёт ли else. Для вложенных условий к этому добавляют правило привязки: else относится к ближайшему if.

После разбора не проверен конец. Текст 2 3 или (1 + 2)) принимается как правильный: разборщик прочитал начало, а хвост никто не посмотрел.

Глубокая вложенность. Стеком служит стек вызовов, поэтому тысяча открывающих скобок подряд - это тысячи вложенных вызовов. Разборщики, читающие чужой ввод, ограничивают глубину явно.

Зачем это в работе

Так пишут настоящие компиляторы. Разборщики GCC, Clang и компилятора Go - рекурсивный спуск, написанный руками: его легко читать, в нём удобно выдавать внятные сообщения об ошибках и восстанавливаться после них. Когда уровней приоритета много, функции уровней заменяют одной с таблицей приоритетов; идея та же.

Вторая школа - разбор снизу вверх: автомат со стеком читает токены и сворачивает их в нетерминалы, когда на верхушке стека собралась правая часть правила. Его строят по грамматике программой-генератором, левая рекурсия ему не мешает, а класс грамматик шире - это все детерминированные КС-языки. Плата - таблицы, которые не читаются глазами.

Свой маленький язык. Формулы в таблице, условия фильтра, шаблоны, конфигурационные файлы - задача «разобрать текст с вложенностью» встречается чаще, чем кажется, и решается парой сотен строк рекурсивного спуска.

Теперь сам

1. Перепиши правило L → L , x | x так, чтобы его можно было разобрать рекурсивным спуском.
2. Что вернёт функция pravaya на токенах 10 - 4 - 3 - 2? А ciklom?
3. По какому токену функция множителя выбирает правило F → ( E )?
4. Грамматика: S → a S | a b. Почему одного токена вперёд не хватает и как её переписать?
5. Сколько раз калькулятор из первого разбора прочитает каждый токен выражения из тысячи токенов?