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

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

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

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

[ред.] Запис

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

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

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

Далі,

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

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

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

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

    <поштова-адреса> ::= <поштове-відділення> <вулична-адреса> <особа>
 
<поштове-відділення> ::= <індекс> "," <місце> <EOL>
 
             <місце> ::= <село> | <місто>
 
            <вулиця> ::= <вулиця> "," <будинок> <EOL>
 
             <особа> ::= <призвище> <ім'я> <EOL> | <призвище> <ім'я> <по-батькові> <EOL>

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

              <нуль> ::= 0
 
   <ненульова цифра> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
 
             <цифра> ::= <нуль> | <ненульова цифра>
 
<послідовність цифр> ::= <нуль> | <ненульова цифра> | <цифра><послідовність цифр>
 
  <натуральне число> ::= <цифра> | <ненульова цифра><послідовність цифр>

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

[ред.] Дивіться також

• Інформатика
• Розширена нотація Бекуса-Наура
• Формальні граматики
• Синтаксичний аналізатор

Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні джерела. Матеріал без джерел може бути підданний сумніву та вилучений.