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

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

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

см. англ. Backus–Naur form

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<simple assignment> ::= <variable assignment> | <arithmetic>
|  | <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>
 ::= <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> 
<shape assignment> ::= \parshapehequals><number><shape dimensions> 

Этот пример не будет разбираться подробно в данной статье.