Нота́ція Бе́куса — Нау́ра (англ. 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
На практиці для запису граматик можуть використовуватися не всі символи БНФ, а тільки " | " або "<>"," | ".
Це визначення спирається на принцип рекурсії та розглядає натуральне число як послідовність цифр.
Див. також
Примітки
- 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 .
{{}}
: Перевірте значення|doi=
() - 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.
- 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.
Ця стаття потребує додаткових для поліпшення її . (листопад 2022) |
Це незавершена стаття про мови програмування. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Nota ciya Be kusa Nau ra angl Backus Naur form BNF ce sposib zapisu pravil kontekstno vilnoyi gramatiki sebto formoyu opisu formalnoyi movi Same yiyi tipovo vikoristovuyut dlya zapisu pravil mov programuvannya ta protokoliv komunikaciyi U 50 h rokah minulogo storichchya Dzhon Bekus stvoriv cyu notaciyu rozroblyayuchi movu ALGOL Na pershomu Vsesvitnomu Komp yuternomu Kongresi sho vidbuvsya u Parizhi 1959 go vin zrobiv dopovid na temu Sintaksis ta semantika proponovanoyi pershoyi mizhnarodnoyi algebrayichnoyi movi Piznishe Piter Naur sprostiv yiyi ta za poradoyu Donalda Knuta dodav do nazvi svoye im ya OpisBNF viznachaye skinchennu kilkist simvoliv neterminaliv Krim togo vona viznachaye pravila zamini simvolu na yakus poslidovnist bukv terminaliv i simvoliv Proces otrimannya lancyuzhka bukv mozhna viznachiti poetapno spochatku ye odin simvol simvoli zazvichaj znahodyatsya u kutovih duzhkah a yih nazva ne nese zhodnoyi informaciyi Potim cej simvol zaminyuyetsya na deyaku poslidovnist bukv i simvoliv vidpovidno do odnogo z pravil Potim proces povtoryuyetsya na kozhnomu kroci odin iz simvoliv zaminyuyetsya na poslidovnist zgidno z pravilom Zreshtoyu vihodit lancyuzhok sho skladayetsya z bukv i ne mistit simvoliv Ce oznachaye sho otrimanij lancyuzhok mozhe buti vivedenij z pochatkovogo simvolu ZapisNotaciya BNF ye naborom produkcij kozhna z yakih vidpovidaye zrazku lt simvol gt lt viraz sho mistit simvoli gt de viraz sho mistit simvoli ce poslidovnist simvoliv abo poslidovnosti simvoliv rozdilenih vertikalnoyu riskoyu sho povnistyu perelichuyut mozhlivij vibir simvol z livoyi chastini formuli Dali lt livij obmezhuvach virazu gt pravij obmezhuvach virazu viznachene yak abo Ci chotiri simvoli ye simvolami metamovi voni ne viznacheni u movi kotru opisuyut Reshta opisanih simvoliv nalezhat do abetki opisuvanoyi movi PrikladiDlya prikladu podivimos na mozhlivu notaciyu BNF dlya poshtovoyi adresi lt poshtova adresa gt lt poshtove viddilennya gt lt vulichna adresa gt lt osoba gt lt poshtove viddilennya gt lt indeks gt lt misce gt lt EOL gt lt misce gt lt selo gt lt misto gt lt vulichna adresa gt lt vulicya gt lt budinok gt lt EOL gt lt osoba gt lt prizvishe gt lt im ya gt lt EOL gt lt prizvishe gt lt im ya gt lt po batkovi gt lt EOL gt Drugij priklad tut navedenij odin zi sposobiv oznachiti naturalni chisla za dopomogoyu BNF lt nul gt 0 lt nenulova cifra gt 1 2 3 4 5 6 7 8 9 lt cifra gt lt nul gt lt nenulova cifra gt lt poslidovnist cifr gt lt nul gt lt nenulova cifra gt lt cifra gt lt poslidovnist cifr gt lt naturalne chislo gt lt cifra gt lt nenulova cifra gt lt poslidovnist cifr gt Rozglyanemo gramatiku G chislo G chislo Chislo Znak Cile chislo Drobova chastina Cifra S 0 9 P S de R skladayetsya z naboru produkcij Chislo Znak Cile chislo Drobova chastina Znak Znak Znak e Cile chislo Cifra Cile chislo Cifra Cile chislo Drobova chastina Cile chislo Drobova chastina e Cifra 0 Cifra 1 Cifra 2 Cifra 3 Cifra 4 Cifra 5 Cifra 6 Cifra 7 Cifra 8 Cifra 9 Zapishemo produkciyi ciyeyi gramatiki vidpovidno BNF lt Chislo gt lt Znak gt lt Cile chislo gt lt Drobova chastina gt lt Znak gt e lt Cile Chislo gt lt Cifra gt lt Cifra gt lt Cile chislo gt lt Drobova chastina gt lt Cile chislo gt e lt Cifra gt 0 1 2 3 4 5 6 7 8 9 Na praktici dlya zapisu gramatik mozhut vikoristovuvatisya ne vsi simvoli BNF a tilki abo lt gt Ce viznachennya spirayetsya na princip rekursiyi ta rozglyadaye naturalne chislo yak poslidovnist cifr Div takozhInformatika Rozshirena notaciya Bekusa Naura Formalni gramatiki Sintaksichnij analizatorPrimitkiMcCracken Daniel D Reilly Edwin D 1 sichnya 2003 Backus Naur form BNF Encyclopedia of Computer Science GBR John Wiley and Sons Ltd s 129 131 doi 10 5555 1074100 1074155 ISBN 978 0 470 86412 8 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite book title Shablon Cite book cite book a Perevirte znachennya doi dovidka Knuth Donald E 1964 12 backus normal form vs Backus Naur form Communications of the ACM angl T 7 12 s 735 736 doi 10 1145 355588 365140 ISSN 0001 0782 Procitovano 15 zhovtnya 2022 Farrel A 2009 04 Routing Backus Naur Form RBNF A Syntax Used to Form Encoding Rules in Various Routing Protocol Specifications angl doi 10 17487 RFC5511 ISSN 2070 1721 Procitovano 15 zhovtnya 2022 Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno listopad 2022 Ce nezavershena stattya pro movi programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi