Определение
Форма Бэкуса — Наура (сокр. БНФ, Бэкуса — Наура форма) — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик. Существует расширенная форма Бэкуса — Наура, отличающаяся лишь более ёмкими конструкциями.
Используется для описания синтаксиса языков программирования, данных, протоколов (например, в документах RFC) и т. д. (причём как грамматики, так и регулярной лексики, поскольку регулярные грамматики являются подмножеством контекстно-свободных).
История
В 1960 году группа программистов из Цюриха, внеся некоторые изменения в спецификацию FORTRAN II, создала алгоритмический язык Algol-60. Джон Бэкус, создатель языка программирования Фортран, принял самое живое участие в обсуждении нового языка. Однако возникла проблема - английский язык, на котором изъяснялся Бэкус, был мало понятен швейцарским программистам. Для того чтобы исключить взаимное недопонимание, при описании конструкций языка были применены специальные диаграммы, которые Бэкус разработал совместно с Петером Науром (Peter Naur). С тех пор Форма Бэкуса-Наура (Backus-Naur Form - BNF) стала как бы эсперанто мирового программирования. Программисту, владеющему BNF, для знакомства с новым языком не нужно изучать толстенных фолиантов с описанием, достаточно изучить BNF этого языка.
Джон Бэкус
Петер Наур
Описание
БНФ-конструкция определяет конечное число символов (нетерминалов). Кроме того, она определяет правила замены символа на какую-то последовательность букв (терминалов) и символов. Процесс получения цепочки букв можно определить поэтапно: изначально имеется один символ (символы обычно заключаются в угловые скобки, а их название не несёт никакой информации). Затем этот символ заменяется на некоторую последовательность букв и символов, согласно одному из правил. Затем процесс повторяется (на каждом шаге один из символов заменяется на последовательность, согласно правилу). В конце концов, получается цепочка, состоящая из букв и не содержащая символов. Это означает, что полученная цепочка может быть выведена из начального символа.
БНФ-конструкция состоит из нескольких предложений вида
<определяемый символ> ::= <посл.1> | <посл.2> | . . . | <посл.n>
, описывающих правила. Такое правило означает, что символ <определяемый символ> может заменяться на одну из последовательностей
<посл.i>. Знак определения обычно выглядит как
::= или → , но возможны и другие варианты.
Некоторые специальные символы, как например
<пусто>, означают какую-то последовательность (в данном случае — пустую).
Примеры конструкций
Вот пример БНФ-конструкции, описывающей правильные скобочные последовательности:
<правпосл>::=<пусто> | (<правпосл>) | <правпосл><правпосл>
Это простая конструкция, состоящая всего из одного правила, утверждающего, что символ
<правпосл> может замениться либо на пустое место, либо на этот же символ
<правпосл>, заключённый в скобки, либо на два символа
<правпосл> идущих подряд.
Описание оператора
if языка PASCAL в БНФ:
<условный оператор if> ::= if <булево выражение> then <оператор> [else <оператор>]
<булево выражение> ::= "NOT" <булево выражение>
| <булево выражение> <логическая операция> <булево выражение>
| <выражение> <операция сравнения> <выражение>
<логическая операция> ::= "OR" | "AND"
<выражение> ::= <переменная> | <строка> | <символ>
<операция сравнения> ::= "=" | "<" | ">"
…
© greenmile
Источники:
www.peoples.ru
ru.wikipedia.org
В начало
