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

Краткий обзор, позволяющий разобраться в вопросах: Что такое нотация Бэкуса — Наура? Чем отличается нормальная форма от расширенной? Каковы правила канонической семантики расширенной формы Бэкуса — Наура? Какие дополнительные элементы могут встречаться в различных модификациях РБНФ?

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

Из множества различных вариаций РБНФ каноничным принято считать вариант принятый международной организацией по стандартизации: ISO/IEC 14977.

Расширенная форма Бэкуса — Наура (как и нормальная форма) представляет собой набор правил, которые определяют отношения между терминальными и нетерминальными символами.

• Терминал или терминальный символ — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение.
• Нетерминал или нетерминальный символ — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

РБНФ-конструкция определяет конечное число нетерминалов (символов) и определяет правила замены символа на какую-то последовательность терминалов (букв) и символов.

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

Определяемый символ = выражение;

Слева от знака = (иногда по старинке используют ::=) стоит имя определяемого выражением нетерминала (символа), а справа — его описание в виде комбинации терминальных и нетерминальных символов и специальных знаков. ; в конце правила (иногда используют просто .) — специальный символ, указывающий на его завершение. Стоит обратить внимание на отсутствие угловых скобок вокруг нетерминалов. А также на тот факт, что в каноническом синтаксисе РБНФ и его модификациях, где для конкатенации применяется запятая, многословные идентификаторы использовать можно.

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

Явного требования порядка записи правил нет, однако такие предписания могут вводиться при использовании РБНФ в программах синтаксического анализа.

Пробелы в правиле считаются незначимыми (за исключением пробелов заключённых в кавычки).

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

• Конкатенация , (в ранних версиях использовали пробел). Правило A = B,C; говорит, что A состоит из двух символов – B и C. Элементы конкатенации принято называть синтаксическими факторами (или просто факторами).
  Использование запятой вместо пробела позволяет применять многословные идентификаторы, которые в нормальной форме обеспечивались угловыми скобками.
• Выбор |. Правило A = B|C|D; говорит, что A может быть одним из трех символов – или B, или C, или D. Элементы выбора принято называть синтаксическими термами (или просто термами).
• Условное вхождение [..]. В квадратных скобках указывается необязательный элемент. Правило вида A = [B]; говорит, что A либо является пустым, либо состоит из символа B.
• Повторение {..}. Фигурные скобки обозначают конкатенацию любого числа записанных в ней элементов (включая ноль). Правило вида A = {B}; говорит, что A — это либо пустой элемент, либо состоит из любого числа символов B. Правило вида A = B{B}; говорит, что A —состоит из либо числа символов B и не может быть пустым.
• Группировка элементов (..). Используется при формировании сложных выражений. Например из правила A = (B|C)(D|E); следует, что A может быть одной из пар символов: BD, BE, CD, CE.

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

Примеры:

Представление натурального и целого чисел:

цифра не ноль   = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
цифра           = "0" | цифра не ноль ;
натуральное     = цифра не ноль, { цифра } ;
целое           = "0" | [ "-" ], натуральное ;

Типичный идентификатор в языках программирования:

Идент = Буква{Буква|Цифра|"_"};

Буква представляет собой выбор из принятого алфавита.

Дополнительные элементы

В некоторых вариациях РБНФ можно встретить в дополнение следующие элементы:

• Косая черта / вместо вертикальной |для обозначения выбора.
• Префикс «*» с круглыми скобками для обозначения повторения вместо фигурных скобок. *(выражение) эквивалентно {выражение}.
• Префикс n* — повторение n или более раз.
• Префикс n*m — повторение от n до m раз.
• Постфикс * — повторение 0 или более раз.
• Постфикс + — повторение 1 или более раз.
• Постфикс ? — 0 или 1 раз.