BNF и EBNF

BNF и EBNF — стандартные нотации, которыми в документации описывают синтаксис языков.

BNF (Backus–Naur Form) — нотация для записи контекстно-свободных грамматик через продукции с нетерминалами в угловых скобках.

BNF придумали в 1950-х для описания языка Algol. С тех пор почти каждая спецификация языка (Python, JSON, SQL) использует BNF или её расширение EBNF. Уметь читать эти нотации — базовый навык для понимания спецификаций.

Синтаксис BNF

В классической BNF нетерминалы заключают в угловые скобки, ::= означает «определяется как», | — «или». Терминалы пишут как есть или в кавычках.

<digit> ::= "0" | "1" | "2" | "3" | "4"
          | "5" | "6" | "7" | "8" | "9"
<sign>  ::= "+" | "-"
<int>   ::= <digit> | <digit> <int>

Здесь <int> — это либо одна цифра, либо цифра, за которой идёт ещё одно целое. Снова рекурсия, чтобы описать число из любого количества цифр.

EBNF: удобные расширения

EBNF (Extended BNF) — расширение BNF с операторами повторения {...}, необязательности [...] и группировки (...).

В чистой BNF повторения выражаются громоздкой рекурсией. EBNF добавляет краткие операторы. Сравните одно и то же правило «целое число — одна или несколько цифр».

Нотация	Запись
BNF	`<int> ::= <digit> \| <digit> <int>`
EBNF	`int = digit , { digit } ;`

Операторы EBNF:

{ X } — ноль или больше повторений X;
[ X ] — X необязателен (ноль или один раз);
( X | Y ) — группировка альтернатив;
, — последовательность, ; — конец правила.

Пример: число со знаком

number = [ sign ] , digit , { digit } ;
sign   = "+" | "-" ;
digit  = "0" | "1" | "2" | "3" | "4"
       | "5" | "6" | "7" | "8" | "9" ;

Читается так: число — это необязательный знак, затем хотя бы одна цифра, затем сколько угодно цифр. Куда компактнее рекурсивной BNF.

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

EBNF-операторы напрямую переводятся в код парсера. { X } становится циклом while, [ X ] — условием if, | — выбором ветки по текущему токену. Эта связь не случайна: EBNF и придумали так, чтобы по нему было легко писать рекурсивный спуск.

def matches_number_ebnf(text):
    # number = [ sign ] , digit , { digit }
    i = 0
    if i < len(text) and text[i] in "+-":  # [ sign ]
        i += 1
    if i >= len(text) or not text[i].isdigit():  # digit (обязательна)
        return False
    i += 1
    while i < len(text) and text[i].isdigit():  # { digit }
        i += 1
    return i == len(text)

print(matches_number_ebnf("-42"))
print(matches_number_ebnf("+"))

Вывод:

True
False

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

Путают { } (ноль или больше) и [ ] (ноль или один). Из-за этого, например, требуют ровно одну цифру там, где их может быть много.

Ещё ошибка — забыть, что в EBNF { X } допускает ноль повторений. Если нужна «хотя бы одна цифра», пишут digit , { digit } — одна обязательная плюс сколько угодно необязательных.

Итог

BNF описывает грамматику продукциями с нетерминалами в угловых скобках.
EBNF добавляет { } (повторение), [ ] (необязательность), ( ) (группировку).
EBNF-операторы прямо переводятся в циклы и условия парсера.
{ X } допускает ноль повторений — для «хотя бы одного» нужна явная первая X.