У этого термина существуют и другие значения, см. БНФ.
Форма Бэкуса—Наура (сокр. БНФ, Бэкуса—Наура форма) — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик.
Содержание
Применение
Используется для описания синтаксиса языков программирования, данных, протоколов (например, в документах RFC) и т. д. (причем как грамматики, так и регулярной лексики, поскольку регулярные грамматики являются подмножеством контекстно-свободных).
Описание
Терминология этой статьи может расходиться с традиционной.
БНФ-конструкция определяет конечное число символов (нетерминалов). Кроме того, она определяет правила замены символа на какую-то последовательность букв (терминалов) и символов. Процесс получения цепочки букв, можно определить поэтапно: изначально имеется один символ (символы обычно заключаются в угловые скобки, а их название не несёт никакой информации). Затем этот символ заменяется на некоторую последовательность букв и символов, согласно одному из правил. Затем процесс повторяется (на каждом шаге один из символов заменяется на последовательность, согласно правилу). В конце концов, получается цепочка, состоящая из букв (и не содержащая символов). Это означает, что полученная цепочка может быть выведена из начального символа.
БНФ-конструкция состоит из нескольких предложений вида
<определяемый символ> ::= <посл.1> | <посл.2> | . . . | <посл.n>
, описывающих правила. Такое правило означает, что символ <определяемый символ> может заменяться на одну из последовательностей посл.1. Знак определения обычно выглядит как ::=, но возможны и другие варианты.
Некоторые специальные символы, как например <пусто>, означают какую-то последовательность (в данном случае — пустую).
Примеры конструкций
- Вот пример БНФ-конструкции, описывающей правильные скобочные последо
вательности:
<правпосл>::=<пусто> | (<правпосл>) | <правпосл><правпосл>
Это простая конструкция, состоящая всего из одного правила, утверждающего, что символ <правпосл> может замениться либо на пустое место, либо на этот же символ <правпосл>, заключённый в скобки, либо на два символа <правпосл> идущих подряд.
Вот как получить с помощью этой конструкции цепочку ((())())() (ниже перечисляются все этапы, символы <пусто> опускаются):
<правпосл><правпосл><правпосл>(<правпосл>)<правпосл>(<правпосл>)(<правпосл>)(<правпосл>)(<пусто>)(<правпосл><правпосл>)()((<правпосл>)<правпосл>)()((<правпосл>)(<правпосл>))() ((<правпосл>)(<пусто>))() (((<правпосл>))())() (((<пусто>))())() ((())())()
См. также
| Это статья-заготовка о программировании. Помогите Википедии, дополнив эту статью, как и любую другую. |
