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

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

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

Саме її типово використовують для запису правил мов програмування та протоколів комунікації. У 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

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

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

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

Посилання[ред. | ред. код]