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

Материал из Википедии — свободной энциклопедии

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

[править] Применение

Используется для описания синтаксиса языков программирования, данных, протоколов (например, в документах RFC) и т. д. (причем как грамматики, так и регулярной лексики, поскольку регулярные грамматики являются подмножеством контекстно-свободных).

[править] Описание

Терминология этой статьи может расходиться с традиционной.

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

БНФ-конструкция состоит из нескольких предложений вида

<определяемый символ> ::= <посл.1> | <посл.2> | . . . | <посл.n>

, описывающих правила. Такое правило, означает, что символ <определяемый символ> может заменятся на одну из последовательностей посл.i. Знак определения, обычно выглядит как ::=, но возможны и другие варианты.

Некоторые специальные символы, как например <пусто> означают какую-то последовательность (в данном случае — пустую).

[править] Примеры конструкций

Вот пример БНФ-конструкции, описывающей правильные скобочные последовательности:

<правпосл>::=<пусто> | (<правпосл>) | <правпосл><правпосл>

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

Вот, как получить с помощью этой конструкции цепочку ((())())() (ниже перечисляются все этапы, символы <пусто> опускаются):

<правпосл>
<правпосл><правпосл>
(<правпосл>)<правпосл>
(<правпосл>)(<правпосл>)
(<правпосл>)(<пусто>)
(<правпосл><правпосл>)()
((<правпосл>)<правпосл>)()
((<правпосл>)(<правпосл>))() 
((<правпосл>)(<пусто>))() 
(((<правпосл>))())() 
(((<пусто>))())() 
((())())()

Вот пример, взятый из книги Дональда Кнута Всё про T_EX (T_EXbook):

<simple assignment> ::= <variable assignment> | <arithmetic>
 | <code assignment> | <let assignment> | <shorthand definition>
 | <fontdef token> | <family assignment> | <shape assignment>
 | <readhnumber> to <optional spaces><control sequence>
 | <setboxh8-bit number><equals><filler><box>
 | <fonthcontrol sequence><equals><file name><at clause>
 | <global assignment>
 <variable assignment> ::= <integer variable><equals><number>
 | <dimen variable><equals><dimen>
 | <glue variable><equals><glue>
 | <muglue variable><equals><muglue>
 | <token variable><equals><general text>
 | <token variable><equals><filler><token variable>
 <arithmetic> ::= <advancehinteger variable><optional by><number>
 | <advancehdimen variable><optional by><dimen>
 | <advancehglue variable><optional by><glue>
 | <advancehmuglue variable><optional by><muglue>
 | <multiplyhnumeric variable><optional by><number>
 | <dividehnumeric variable><optional by><number>
 <optional by> ::= by | <optional spaces>
 <integer variable> ::= <integer parameter> | <countdef token>
 | <counth8-bit number>
 <dimen variable> ::= <dimen parameter> | <dimendef token>
 | <dimenh8-bit number>
 <glue variable> ::= <glue parameter> | <skipdef token>
 | <skiph8-bit number>
 <muglue variable> ::= <muglue parameter> | <muskipdef token>
 | <muskiph8-bit number>
 <token variable> ::= <token parameter> | <toksdef token>
 | <toksh8-bit number>
 <numeric variable> ::= <integer variable> | <dimen variable>
 | <glue variable> | <muglue variable>
 <code assignment> ::= <code name><8-bit number><equals><number> 
 <let assignment> ::= <futurelethcontrol sequence><token><token> 
 | <lethcontrol sequence><equals><one optional space><token> 
 <shorthand definition> ::= <chardefhcontrol sequence><equals><8-bit number> 
 | <mathchardefhcontrol sequence><equals><15-bit number> 
 | <registerdef><control sequence><equals><8-bit number> 
 <registerdef> ::= <countdef | <dimendef | <skipdef | <muskipdef | <toksdef 
 <family assignment> ::= <family member><equals><font> 
 <shape assignment> ::= <parshapehequals><number><shape dimensions>