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

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

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

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

  1. Число → Знак ЦілеЧисло ДрібнаЧастина.
  2. Знак → +.
  3. Знак → -.
  4. Знак → ε.
  5. Ціле Число → Цифра.
  6. Ціле Число → Цифра ЦілеЧисло.
  7. Дрібна Частина → , ЦілеЧисло.
  8. Дрібна Частина → ε.
  9. Цифра → 0.
  10. Цифра →1.
  11. Цифра →2.
  12. Цифра →3.
  13. Цифра →4.
  14. Цифра →5.
  15. Цифра →6.
  16. Цифра →7.
  17. Цифра →8.
  18. Цифра →9.

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

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

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

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

<Дрібна Частина> ::= , <Ціле Число> І ε

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

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

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

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

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