Backus Form - Naur

The Backus-Naur form (abbr. BNF , Backus-Naur form ) is a formal system for describing syntax in which certain syntactic categories are sequentially defined through other categories. BNF is used to describe context-free formal grammars. There is an extended Backus-Naur form, differing only in more capacious structures.

Used to describe the syntax of programming languages, data, protocols (for example, in RFC documents), etc. (both grammars and regular vocabulary, since regular grammars are a subset of context-free ones).

Description

The terminology of this article may differ from the traditional one.

BNF-design defines a finite number of characters (non-terminals). In addition, it defines the rules for replacing a symbol with a sequence of letters (terminals) and symbols. The process of obtaining a chain of letters can be determined in stages: initially there is one character (the characters are usually enclosed in angle brackets, and their name does not carry any information). Then this symbol is replaced with a certain sequence of letters and symbols, according to one of the rules. Then the process is repeated (at each step one of the characters is replaced with a sequence, according to the rule). In the end, it turns out a chain consisting of letters and not containing characters. This means that the resulting string can be inferred from the initial character.

BNF-construction consists of several sentences of the form

  <defined character> :: = <last.1> |  <last 2> |  .  .  .  |  <Last> n>

describing the rules. Such a rule means that the symbol <определяемый символ> symbol being <определяемый символ> can be replaced by one of the sequences <i>. The definition sign usually looks like ::= or → , but other options are possible.

Some special characters, such as <пусто> , mean some sequence (in this case, empty).

Design examples

• Here is an example of a BNF construct describing the correct bracket sequences:

  <right> :: = <empty> |  (<right>) |  <right> <right>

This is a simple construction consisting of just one rule, which states that the <правпосл> can be replaced either with an empty space, or with the same <right pos> character, enclosed in brackets, or with two <правпосл> characters <правпосл> in a row.

Description of the if in the BNF in PASCAL

  <conditional operator if> :: = if <boolean expression> then <operator> [else <operator>]
  <boolean expression> :: = <boolean expression> <boolean expression> |  <expression> <logical operator> <expression>
  <logical operator> :: = <|> |  =
  <expression> :: = <variable> |  <string> |  <character>
  ...