Формальные грамматики

Чтобы парсер знал, какие конструкции допустимы, синтаксис языка описывают строгой грамматикой.

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

Естественный язык расплывчат, а язык программирования обязан быть однозначным. Грамматика задаёт точные правила: что можно написать, а что — синтаксическая ошибка. Парсер — это, по сути, исполнитель грамматики.

Из чего состоит грамматика

Грамматика оперирует четырьмя сущностями:

• Терминалы — конкретные токены, дальше не раскрываются (число, +, ().
• Нетерминалы — абстрактные понятия, которые раскрываются через другие правила (выражение, слагаемое).
• Продукции — правила вида «нетерминал может быть тем-то».
• Стартовый символ — нетерминал, с которого начинается разбор.

Пример: грамматика сложения

Опишем простейший язык — суммы чисел. Стрелка ::= читается «определяется как», вертикальная черта — «или».

<expr>   ::= <number> "+" <expr>
           | <number>
<number> ::= "0" | "1" | "2" | ... | "9"

Прочитаем: выражение <expr> — это либо число плюс ещё одно выражение, либо просто число. Такое правило, ссылающееся на само себя, называется рекурсивным — именно рекурсия даёт грамматике возможность описывать сколь угодно длинные выражения конечным набором правил.

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

Разбор по грамматике — это поиск способа «вывести» входную строку из стартового символа, последовательно применяя продукции. Для строки 2+3 вывод выглядит так.

<expr>
=> <number> "+" <expr>     (первая продукция)
=> "2" "+" <expr>          (раскрыли число)
=> "2" "+" <number>        (вторая продукция)
=> "2" "+" "3"             (раскрыли число)

Если входную строку нельзя вывести ни одним способом — это синтаксическая ошибка. Например, 2 + + вывести не получится: после + грамматика требует выражение, а там опять +.

Проверим разбор кодом

Напишем игрушечный распознаватель именно для этой грамматики «число плюс число плюс...».

def is_valid_sum(text):
    text = text.replace(" ", "")
    # ожидаем: число (+ число)*
    expect_number = True
    for ch in text:
        if expect_number:
            if not ch.isdigit():
                return False
            expect_number = False
        else:
            if ch != "+":
                return False
            expect_number = True
    return not expect_number  # не должны кончиться на '+'

print(is_valid_sum("2+3+4"))
print(is_valid_sum("2++3"))

Вывод:

True
False

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

Путают терминалы и нетерминалы. Запомните: терминал — это то, что реально появляется во входе (токен), нетерминал — вспомогательное имя, которого во входе нет, оно лишь структурирует правила.

Ещё ошибка — забыть базовый случай в рекурсивном правиле. Если <expr> всегда раскрывается в <number> "+" <expr> без альтернативы «просто число», вывод никогда не завершится.

Итог

• Грамматика формально задаёт, какие строки корректны в языке.
• Терминалы — это токены, нетерминалы — абстрактные понятия из правил.
• Рекурсивные правила описывают сколь угодно длинные конструкции.
• Разбор — это вывод входной строки из стартового символа; невыводимость означает ошибку.