Нотація Бекуса — Наура
Нота́ція Бе́куса — Нау́ра (англ. 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
На практиці для запису граматик можуть використовуватися не всі символи БНФ, а тільки " | " або "<>"," | ".
Це визначення спирається на принцип рекурсії та розглядає натуральне число як послідовність цифр.