Нотація Бекуса-Наура

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Нота́ція Бе́куса—Нау́ра (англ. Backus-Naur form, BNF) — це спосіб запису правил контекстно-вільної граматики, себто формою опису формальної мови.

Саме її типово використовують для запису правил мов програмування та протоколів комунікації. У 50-х роках минулого сторіччя Джон Бекус створив цю нотацію розробляючи мову ALGOL. На першому Всесвітньому Комп'ютерному Конгресі, що відбувся у Парижі 1959-го він зробив доповідь на тему «Синтаксис та семантика пропонованої першої міжнародної алгебраїчної мови». Пізніше Наур Пітер спростив її та (за порадою Дональда Кнута) додав до назви своє ім'я.

Запис[ред.ред. код]

Нотація БНФ є набором «продукцій», кожна з яких відповідає зразку:

<символ> ::= <вираз, що містить символи>

де вираз, що містить символи це послідовність символів або послідовності символів, розділених вертикальною рискою |, що повністю перелічують можливий вибір символ з лівої частини формули.

Далі,

  • < — лівий обмежувач виразу
  • > — правий обмежувач виразу
  • ::= — визначене як
  • | — або

Ці чотири символи є символами мета-мови, вони не визначені у мові, котру описують. Решта описаних символів належать до «абетки» описуваної мови.

Приклади[ред.ред. код]

Для прикладу подивимось на можливу нотацію BNF для поштової адреси:

    <поштова-адреса> ::= <поштове-відділення> <вулична-адреса> <особа>
 
<поштове-відділення> ::= <індекс> ", " <місце> <EOL>
 
             <місце> ::= <село> | <місто>
 
    <вулична-адреса> ::= <вулиця> "," <будинок> <EOL>
 
             <особа> ::= <прізвище> <ім’я> <EOL> | <прізвище> <ім’я> <по батькові> <EOL>

Другий приклад, тут наведений один зі способів означити натуральні числа за допомогою БНФ.

              <нуль> ::= 0
 
   <ненульова цифра> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
 
             <цифра> ::= <нуль> | <ненульова цифра>
 
<послідовність цифр> ::= <нуль> | <ненульова цифра> | <цифра><послідовність цифр>
 
  <натуральне число> ::= <цифра> | <ненульова цифра><послідовність цифр>

Це визначення спирається на принцип рекурсії та розглядає натуральне число як послідовність цифр.

Див. також[ред.ред. код]