Простая форма Бэкуса — Наура (БНФ)

Краткий обзор, отвечающий на вопросы: Что это? Где используется? Правила написания и примеры использования.

 

Backus–Naur form или Backus normal form (BNF) это формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик, обычно используется для описания синтаксиса языков программирования, форматов документов, наборов инструкций и протоколов связи. Применяются везде, где необходимо точное описание синтаксиса: например, в официальных спецификациях, руководствах и учебниках.

Так же существует ещё и расширенная форма Бэкуса — Наура, отличающаяся более ёмкими конструкциями.

Термины:

  • Терминал или терминальный символ — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение.
  • Нетерминал или нетерминальный символ — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

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

За процесс построения цепочки букв можно проследить поэтапно:

  • Изначально имеется только один символ. Обычно символы представляются в виде некого названия заключенного в угловые скобки.
  • Затем этот символ заменяется некоторой последовательностью букв и символов, согласно одному из описанных правил.
  • Затем процесс повторяется (на каждом шаге один из символов заменяется на последовательность, согласно правилу).

В конце концов, получается цепочка, состоящая из букв и не содержащая символов.

Запись правила разбита на две части разделенных символом определения ::= или иногда вместо него используют ->. В левой части содержится определяемый символ, а справа последовательность из букв и символов. В описании правила в правой части может использоваться оператор выбора “|” обеспечивающий логическое ИЛИ. В описании правила может применяться рекурсия.

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

Примеры конструкций БНФ.

Общий вид конструкции.

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

 

БНФ-конструкция правильной скобочной последовательности.

<правпосл> ::= “” | (<правпосл>) | <правпосл><правпосл>

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

Синтаксис БНФ представленный БНФ-конструкцией (используется латиница)

<syntax>         ::= <rule> | <rule> <syntax>
<rule>           ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""
<expression>     ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
<line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list>           ::= <term> | <term> <opt-whitespace> <list>
<term>           ::= <literal> | "<" <rule-name> ">"
<literal>        ::= '"' <text1> '"' | "'" <text2> "'"
<text1>          ::= "" | <character1> <text1>
<text2>          ::= "" | <character2> <text2>
<character>      ::= <letter> | <digit> | <symbol>
<letter>         ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
<digit>          ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<symbol>         ::=  "|" | " " | "-" | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | "<" | "=" | ">" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "|" | "}" | "~"
<character1>     ::= <character> | "'"
<character2>     ::= <character> | '"'
<rule-name>      ::= <letter> | <rule-name> <rule-char>
<rule-char>      ::= <letter> | <digit> | "-"

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *