Форма Бэкуса-Наура для описания языков¶

Форма Бэкуса — Наура (БНФ, от англ. Backus–Naur form, BNF) — это формальная нотация для описания синтаксиса контекстно-свободных грамматик, используемая преимущественно для задания грамматики языков программирования, форматов данных и протоколов. Предложенная в конце 1950-х годов, БНФ представляет собой метаязык, в котором левая часть правил определяет синтаксическую категорию, а правая — последовательность терминальных и нетерминальных символов, из которых она может состоять.

¶История

Нотация была разработана Джоном Бэкусом для описания синтаксиса языка Алгол-58 в докладе на конференции UNESCO в 1959 году. Позднее, в 1960 году, Питер Наур адаптировал и уточнил её в отчёте по Алголу-60, добавив более строгие обозначения (в частности, угловые скобки для нетерминалов и символ ::= вместо стрелки). В честь обоих исследователей нотация получила название «форма Бэкуса — Наура». Впоследствии она стала стандартом де-факто для описания синтаксиса большинства языков программирования, включая Паскаль, Си и их производные.

¶Синтаксис

Основу БНФ составляют правила вида:

`` <нетерминал> ::= последовательность символов ``

Символ ::= читается как «определяется как» или «состоит из». В левой части правила всегда находится нетерминальный символ, заключённый в угловые скобки (< и >). Правая часть содержит цепочку, состоящую из:

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

Пример классического описания целого числа:

`` <число> ::= <цифра> | <число> <цифра> <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ``

Здесь правило для <число> является рекурсивным, что позволяет описывать последовательности цифр произвольной длины.

¶Расширения

Базовая БНФ не содержит средств для компактного выражения повторений и необязательных элементов, что делает грамматики громоздкими. Для устранения этих недостатков были разработаны расширенные версии:

• Расширенная форма Бэкуса — Наура (РБНФ, EBNF) — добавляет операторы повторения (фигурные скобки { }), необязательности (квадратные скобки [ ]) и группировки (круглые скобки). Широко используется в стандартах ISO и IEC.
• Augmented BNF (ABNF) — модификация, применяемая в RFC (Request for Comments) для описания интернет-протоколов, отличается использованием числовых значений символов и специальных операторов.

Эти расширения не меняют выразительной мощности формализма, но значительно повышают читаемость и компактность описаний.

¶Применение

БНФ применяется в следующих областях:

• Проектирование языков программирования — для формального задания синтаксиса до написания компилятора.
• Документирование стандартов — в спецификациях языков (например, ISO 9899 для Си) и протоколов (RFC 5321 для SMTP).
• Генерация синтаксических анализаторов — грамматики в форме БНФ служат входными данными для генераторов парсеров (Yacc, Bison, ANTLR).
• Обучение и теория формальных языков — как наглядный инструмент для изучения контекстно-свободных грамматик.

¶Критика и ограничения

БНФ описывает только контекстно-свободную составляющую синтаксиса. Такие аспекты языков, как необходимость объявления переменных до использования, проверка типов или уникальность имён, не могут быть выражены в этой нотации и описываются отдельно в семантических правилах. Кроме того, рекурсивные определения без явных ограничений могут порождать неоднозначные грамматики, требующие дополнительных соглашений о приоритете операций.

¶Литература

• Бэкус Дж. «The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference» (1959).
• Наур П. «Revised report on the algorithmic language ALGOL 60» (1960).
• Вирт Н. «What can we do about the unnecessary diversity of notation for syntactic definitions?» (1977).