Расшифровка и предназначение
БНФ, Бэкуса-Наура форма. Специальная конструкция, описывающая множества последовательностей cимволов. Используется для описания синтаксиса языков программирования и не только. В чём-то БНФ похож на грамматики и регулярные выражения.
Описание
Я не знаю точной терминологии, поэтому буду использовать свою.
Объяснить, что порождает БНФ-конструкция, можно по аналогии с грамматиками. Не буду приводить скучных рассуждений про алфавит, терминальные и нетерминальные символы. БНФ-конструкцияопределяет конечное число символов (нетерминалов). Кроме того, она определяет правила замены символа на какую-то последовательность букв (терминалов) и символов. Процесс получения цепочки букв, можно представлять поэтапно: изначально имеется один символ (символы обычно заключаются в угловые скобки, а их название не несёт никакой информации). Затем этот символ заменяется на некоторую последовательность букв и символов, согласно одному из правил. Затем процесс повторяется (на каждом шаге один из символов заменяется на последовательность, согласно правилу). В конце концов, получается цепочка, состоящая из букв (и не содержащая символов). Это означает, что полученная цепочка моджет быть виведена из начального символа.
БНФ-конструкция состоит из нескольких предложений вида
<определяемый символ> :== посл.1 | посл.2 | . . . | посл.n
, описывающих правила. Такое правило, означает, что символ <определяемый символ> может заменятся на одну из последовательностей посл.i. Знак определения, обычно выглядит как :==, но возможны и другие варианты.
Некоторые специальные символы, как например <пусто> означают какую-то последовательность (в данном случае, как можно было догадаться пустую).
Примеры конструкций
- Вот пример БНФ-конструкции, описывающей правильные скобочные последовательности:
<правпосл>::=<пусто> | (<правпосл>) | <правпосл><правпосл>
Это простая конструкция, состоящая всего из одного правила, утверждающего, что символ <правпосл> может замениться либо на пустое место, либо на этот же символ <правпосл>, заключённый в скобки, либо на два символа <правпосл> идущих подряд.
Вот, как получить с помощью этой конструкции цепочку ((())())() (я перечисляю все этапы, символы <пусто> буду опускать):
<правпосл><правпосл><правпосл>(<правпосл>)<правпосл>(<правпосл>)(<правпосл>)(<правпосл>)(<пусто>)(<правпосл><правпосл>)()((<правпосл>)<правпосл>)()((<правпосл>)(<правпосл>))() ((<правпосл>)(<пусто>))() (((<правпосл>))())() (((<пусто>))())() ((())())()
- Вот пример, взятый из книги Дональда Кнута Всё про TEX (TEXbook):
<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> | <count
def 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>
Я не буду разбирать его подробно, скажу только, что таким образом описываются присваивания в системе TEX (например mydimen=10mm)
