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

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

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

Опис ред.

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

Запис ред.

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

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

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

Далі,

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

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

Приклади ред.

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

    <поштова-адреса> ::= <поштове-відділення> <вулична-адреса> <особа>

<поштове-відділення> ::= <індекс> ", " <місце> <EOL>

             <місце> ::= <село> | <місто>

    <вулична-адреса> ::= <вулиця> "," <будинок> <EOL>

             <особа> ::= <прізвище> <ім’я> <EOL> | <прізвище> <ім’я> <по батькові> <EOL>

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

              <нуль> ::= 0

   <ненульова цифра> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

             <цифра> ::= <нуль> | <ненульова цифра>

<послідовність цифр> ::= <нуль> | <ненульова цифра> | <цифра><послідовність цифр>

  <натуральне число> ::= <цифра> | <ненульова цифра><послідовність цифр>

Розглянемо граматику G(число):

G(число)=({Число, Знак, Ціле число, Дробова частина, Цифра, S}), {+,-,0,...,9,,},P,S),

де Р складається з набору продукцій:

# Число → Знак Ціле число Дробова частина.
# Знак → +.
# Знак → -.
# Знак → ε.
# Ціле число → Цифра.
# Ціле число → Цифра Ціле число.
# Дробова частина → ,  Ціле число.
# Дробова частина → ε.
# Цифра → 0.
# Цифра → 1.
# Цифра → 2.
# Цифра → 3.
# Цифра → 4.
# Цифра → 5.
# Цифра → 6.
# Цифра → 7.
# Цифра → 8.
# Цифра → 9.

Запишемо продукції цієї граматики відповідно БНФ:

<Число> ::= <Знак> <Ціле число> <Дробова частина>

<Знак> ::= + | - | ε

<Ціле Число> ::= <Цифра> | <Цифра> <Ціле число> 

<Дробова частина> ::= , <Ціле число> | ε

<Цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

На практиці для запису граматик можуть використовуватися не всі символи БНФ, а тільки " | " або "<>"," | ".

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

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

Примітки ред.

↑ McCracken, Daniel D.; Reilly, Edwin D. (1 січня 2003). Backus-Naur form (BNF). Encyclopedia of Computer Science. GBR: John Wiley and Sons Ltd. с. 129—131. doi:10.5555/1074100.1074155. ISBN 978-0-470-86412-8. {{cite book}}: Перевірте значення |doi= (довідка)
↑ Knuth, Donald E. (1964-12). backus normal form vs. Backus Naur form. Communications of the ACM (англ.). Т. 7, № 12. с. 735—736. doi:10.1145/355588.365140. ISSN 0001-0782. Процитовано 15 жовтня 2022.
↑ Farrel, A. (2009-04). Routing Backus-Naur Form (RBNF): A Syntax Used to Form Encoding Rules in Various Routing Protocol Specifications (англ.). doi:10.17487/RFC5511. ISSN 2070-1721. Процитовано 15 жовтня 2022.

Це незавершена стаття про мови програмування.
Ви можете допомогти проєкту, виправивши або дописавши її.

[1] McCracken, Daniel D.; Reilly, Edwin D. (1 січня 2003). Backus-Naur form (BNF). Encyclopedia of Computer Science. GBR: John Wiley and Sons Ltd. с. 129—131. doi:10.5555/1074100.1074155. ISBN 978-0-470-86412-8. {{cite book}}: Перевірте значення |doi= (довідка)

[2] Knuth, Donald E. (1964-12). backus normal form vs. Backus Naur form. Communications of the ACM (англ.). Т. 7, № 12. с. 735—736. doi:10.1145/355588.365140. ISSN 0001-0782. Процитовано 15 жовтня 2022.

[3] Farrel, A. (2009-04). Routing Backus-Naur Form (RBNF): A Syntax Used to Form Encoding Rules in Various Routing Protocol Specifications (англ.). doi:10.17487/RFC5511. ISSN 2070-1721. Процитовано 15 жовтня 2022.

[1]

[2]

[3]