Форма Бэкуса — Наура

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

История

Форма Бэкуса — Наура была разработана в конце 1950-х — начале 1960-х годов в контексте создания первого универсального языка программирования высокого уровня — Алгол. Основной вклад в её создание внесли американский учёный Джон Бэкус и датский информатик Петер Наур.

Предпосылки

До появления БНФ описание синтаксиса языков программирования было неформальным, часто приводило к неоднозначностям и затрудняло разработку компиляторов. В 1958 году на конференции в Цюрихе, посвящённой разработке Алгола, Бэкус предложил использовать формальные правила, основанные на идеях американского лингвиста Ноама Хомского (контекстно-свободные грамматики). Бэкус ввёл обозначения для записи правил, которые затем были доработаны Науром.

Развитие

Первая версия БНФ была опубликована в 1960 году в отчёте «Revised Report on the Algorithmic Language ALGOL 60». В этом документе БНФ использовалась для полного описания синтаксиса Алгола. Позднее, в 1963 году, американский учёный Дональд Кнут предложил расширение БНФ для более удобного описания синтаксических конструкций, которое получило название расширенная форма Бэкуса — Наура (РБНФ, от англ. Extended Backus–Naur form, EBNF). РБНФ добавила метасимволы для указания повторений (например, * для нуля или более повторений) и опциональных элементов (например, ? или [ ]), что упростило запись грамматик.

Современное состояние

БНФ и её варианты (РБНФ, ABNF, W3C EBNF) остаются стандартом де-факто для описания синтаксиса языков программирования, протоколов (например, HTTP, SMTP), форматов данных (JSON, XML) и других формальных систем. В 1996 году Международная организация по стандартизации (ISO) приняла стандарт ISO/IEC 14977:1996, определяющий синтаксис РБНФ.

Основные элементы

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

• Терминалы — конечные символы языка (например, ключевые слова, знаки операций, литералы). В БНФ обычно записываются в кавычках (например, "if", "+") или выделяются жирным шрифтом.
• Нетерминалы — синтаксические категории, которые определяются через правила (например, <выражение>, <оператор>). В БНФ часто заключаются в угловые скобки: < >.
• Метасимволы — символы, используемые для записи правил. В классической БНФ используются:
• ::= — означает «определяется как» (разделяет левую и правую части правила).
• | — означает «или» (альтернатива).
• < > — обозначение нетерминала.
• " " — обозначение терминала (иногда опускаются).
• Правило (продукция) — запись вида: <нетерминал> ::= <последовательность символов>.

Пример записи

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

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

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

Расширения и варианты

Расширенная форма Бэкуса — Наура (РБНФ, EBNF)

РБНФ добавляет метасимволы для сокращения записи:

• { } — повторение (ноль или более раз).
• [ ] — опциональный элемент (ноль или один раз).
• ( ) — группировка.
• * — повторение (в некоторых вариантах).
• + — одно или более повторений.

Пример записи целых чисел в РБНФ:

`` <цифра> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" <целое> ::= <цифра> { <цифра> } ``

Другие варианты

• ABNF (Augmented BNF) — расширенная версия, используемая в спецификациях интернет-протоколов (RFC 5234). Добавляет правила для бинарных данных и числовых значений.
• W3C EBNF — вариант, используемый Консорциумом Всемирной паутины (W3C) для описания синтаксиса XML, HTML и других стандартов.
• Стандарт ISO/IEC 14977 — международный стандарт для РБНФ, определяющий точный синтаксис и семантику.

Применение

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

Языки программирования

БНФ используется для формального описания синтаксиса большинства языков программирования: от ранних (Алгол, Паскаль) до современных (Python, Java, C++, Rust). Спецификации языков, такие как стандарты C (ANSI C) или Java (Java Language Specification), содержат грамматики в БНФ или её вариантах. Это позволяет разработчикам компиляторов и интерпретаторов однозначно понимать структуру языка.

Протоколы передачи данных

Многие интернет-протоколы, включая HTTP, SMTP, FTP, описаны с использованием БНФ или ABNF. Например, в RFC 7230 (HTTP/1.1) синтаксис запросов и ответов задан в ABNF.

Форматы данных

Синтаксис таких форматов, как JSON, XML, YAML, часто описывается с помощью БНФ. Например, спецификация JSON (RFC 8259) использует ABNF для определения допустимых структур.

Лингвистика и компьютерная лингвистика

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

Документация и обучение

БНФ широко применяется в учебной литературе по программированию и теории формальных языков для наглядного объяснения синтаксических конструкций. Многие учебники по компиляторам начинаются с введения в БНФ.

Преимущества и недостатки

Преимущества

• Однозначность: БНФ позволяет точно определить, какие последовательности символов являются допустимыми в языке.
• Простота: Базовый синтаксис БНФ легко изучается и понимается.
• Модульность: Правила можно комбинировать и переиспользовать.
• Автоматизация: На основе БНФ можно автоматически генерировать синтаксические анализаторы (парсеры) с помощью инструментов, таких как Yacc, Bison, ANTLR.

Недостатки

• Ограниченная выразительность: БНФ описывает только контекстно-свободные грамматики. Для языков, требующих контекстной зависимости (например, объявление переменных до их использования), необходимы дополнительные механизмы (семантические правила).
• Громоздкость: Для больших языков грамматика в БНФ может быть очень объёмной, что затрудняет её чтение.
• Отсутствие семантики: БНФ описывает только синтаксис, но не значение конструкций.

Критика и альтернативы

Основная критика БНФ связана с её ограниченностью при описании реальных языков программирования, которые часто содержат контекстно-зависимые элементы (например, правила области видимости, типизацию). Для преодоления этого недостатка используются атрибутные грамматики (например, грамматики ван Вейнгаардена) или семантические действия, добавляемые к правилам БНФ.

Альтернативными подходами к описанию синтаксиса являются:

• Синтаксические диаграммы (railroad diagrams) — графическое представление, более наглядное для человека, но менее формальное.
• Грамматики ван Вейнгаардена — двухуровневые грамматики, способные описывать контекстно-зависимые языки (использовались в языке Алгол 68).
• PEG (Parsing Expression Grammars) — альтернативная формальная система, основанная на синтаксическом анализе с возвратами, более простая для реализации, но менее мощная в некоторых аспектах.

Интересные факты

• Название «форма Бэкуса — Наура» возникло после того, как Петер Наур внёс значительные изменения в первоначальную нотацию Бэкуса, добавив угловые скобки для нетерминалов и символ ::= вместо стрелки.
• В 2005 году Джон Бэкус получил премию Тьюринга за вклад в разработку Алгола и создание БНФ.
• БНФ иногда называют «метаязыком», так как она используется для описания других языков.
• Стандарт ISO/IEC 14977 определяет РБНФ, но на практике используется множество неформальных вариантов.

Источники

• Revised Report on the Algorithmic Language ALGOL 60 (1960)
• ISO/IEC 14977:1996 — Information technology — Syntactic metalanguage — Extended BNF
• RFC 5234 — Augmented BNF for Syntax Specifications: ABNF
• Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. — Compilers: Principles, Techniques, and Tools (2nd edition)
• Knuth, D. E. — The Art of Computer Programming, Volume 1: Fundamental Algorithms