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

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

Нота́ція Бе́куса — Нау́ра (англ. 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

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

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

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  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.
Мова програмування Це незавершена стаття про мови програмування.
Ви можете допомогти проєкту, виправивши або дописавши її.
Отримано з https://uk.wikipedia.org/w/index.php?title=Нотація_Бекуса_—_Наура&oldid=37705657