Нормальная форма Бэкуса — Наура

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

История

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

В 1959 году Джон Бэкус, работавший в компании IBM, предложил способ описания синтаксиса Алгола с использованием формальных правил, основанных на математических обозначениях. Его работа была представлена на конференции в Париже. В 1960 году на встрече в Копенгагене, где обсуждался проект Алгола, Питер Наур внёс в предложение Бэкуса ряд уточнений и упрощений, в частности, ввёл метасимволы < и > для обозначения нетерминалов, а также символ ::= для отделения левой части правила от правой. Полученный вариант был опубликован в отчёте «Revised Report on the Algorithmic Language ALGOL 60» (1963), и именно он стал известен как нормальная форма Бэкуса — Наура.

Первоначально БНФ называлась «формой Бэкуса» (Backus normal form), но по предложению Дональда Кнута (Donald Knuth) в 1964 году ей было присвоено имя обоих учёных, чтобы подчеркнуть вклад Наура. С тех пор БНФ стала стандартным инструментом в области формальных языков и компиляторов.

Основные понятия и синтаксис

БНФ оперирует двумя типами символов: терминалами и нетерминалами.

• Терминалы (терминальные символы) — это конкретные, неделимые элементы языка, такие как буквы, цифры, знаки препинания, ключевые слова (например, if, then, +, ;). В записи БНФ терминалы обычно заключаются в кавычки или пишутся без обрамления, если это однозначно.
• Нетерминалы (нетерминальные символы) — это абстрактные синтаксические категории, которые могут быть заменены на последовательность терминалов и других нетерминалов. В БНФ нетерминалы обычно заключаются в угловые скобки < и > (например, <выражение>, <число>).

Основной элемент БНФ — правило вывода (продукция). Каждое правило имеет вид:

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

Символ ::= означает «определяется как» или «может быть заменён на». Левая часть правила содержит один нетерминал, правая — последовательность терминалов и/или нетерминалов, которая описывает возможные варианты его замены.

Если нетерминал может быть заменён несколькими альтернативными последовательностями, они перечисляются через вертикальную черту | (символ «или»). Например:

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

Это правило означает, что нетерминал <цифра> может быть заменён на любой из десяти символов от 0 до 9.

Пример простой грамматики

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

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

Здесь <целое_число> определяется рекурсивно: оно может быть либо одной цифрой, либо целым числом, за которым следует ещё одна цифра. Это позволяет порождать числа любой длины (например, 123 выводится как <целое_число> → <целое_число> <цифра> → <целое_число> 3 → <цифра> 2 3 → 1 2 3).

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

Классическая БНФ имеет ограниченные выразительные возможности, поэтому со временем были разработаны её расширения, наиболее известное из которых — расширенная форма Бэкуса — Наура (Extended Backus–Naur Form, EBNF). EBNF добавляет дополнительные метасимволы для сокращения записи повторяющихся и необязательных конструкций:

• Квадратные скобки [ ] — обозначают необязательный элемент (может быть 0 или 1 раз).
• Фигурные скобки { } — обозначают повторение элемента 0 или более раз.
• Круглые скобки ( ) — используются для группировки альтернатив.
• Символ * (звёздочка) — обозначает повторение 0 или более раз (в некоторых вариантах).
• Символ + (плюс) — обозначает повторение 1 или более раз.

Пример EBNF для целых чисел:

`` целое_число = цифра { цифра }; цифра = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"; ``

В EBNF нетерминалы часто записываются без угловых скобок, а терминалы — в кавычках. Символ ::= может заменяться на =.

Существуют и другие диалекты, например, ABNF (Augmented BNF), используемый в протоколах интернета (RFC 5234), который добавляет числовые значения и правила для пробелов.

Применение

Нормальная форма Бэкуса — Наура и её расширения нашли широкое применение в различных областях информатики и лингвистики:

• Описание языков программирования: синтаксис большинства современных языков (C, Java, Python, Pascal, SQL, HTML, XML) формально определён с помощью БНФ или EBNF. Это позволяет разработчикам компиляторов и интерпретаторов однозначно понимать, какие конструкции являются допустимыми.
• Форматы данных: грамматики для JSON, YAML, протоколов передачи данных (HTTP, SMTP, FTP) часто описываются в ABNF или EBNF.
• Автоматическая генерация парсеров: инструменты вроде Yacc, Bison, ANTLR, JavaCC используют грамматики, близкие к БНФ, для автоматического создания синтаксических анализаторов (парсеров) по заданным правилам.
• Теория формальных языков: БНФ является стандартным способом задания контекстно-свободных грамматик, изучаемых в рамках курса теории автоматов и формальных языков.
• Документирование: спецификации языков и протоколов часто содержат синтаксические диаграммы, эквивалентные БНФ, для наглядного представления правил.

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

Несмотря на широкую распространённость, БНФ имеет ряд недостатков:

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

Связь с другими формализмами

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

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

Источники

• Revised Report on the Algorithmic Language ALGOL 60 (1963). Peter Naur et al.
• Donald E. Knuth. "Backus Normal Form vs. Backus Naur Form". Communications of the ACM, 1964.
• ISO/IEC 14977:1996. Information technology — Syntactic metalanguage — Extended BNF.
• RFC 5234. Augmented BNF for Syntax Specifications: ABNF. 2008.
• А. Ахо, М. Лам, Р. Сети, Д. Ульман. «Компиляторы: принципы, технологии и инструментарий». 2-е издание. — М.: Вильямс, 2008.
• В. А. Горбатов. «Теория автоматов и формальных языков». — М.: Высшая школа, 2009.