Forma Backusa-Naura - Backus–Naur form

W informatyce , Notacja BNF ( / ˌ b ć k ə e n aʊər / ) lub Backus postaci normalnej ( BNF ) jest metasyntax zapisem bezkontekstowych gramatyk , często stosowane w celu opisania składnię z języków do wyliczenia, takie jak języki programowania komputerowego , formaty dokumentów , zestawy instrukcji i protokoły komunikacyjne. Stosuje się je wszędzie tam, gdzie potrzebne są dokładne opisy języków: na przykład w oficjalnych specyfikacjach językowych, w podręcznikach i podręcznikach teorii języków programowania.

Stosuje się wiele rozszerzeń i wariantów oryginalnej notacji Backus-Naur; niektóre są dokładnie zdefiniowane, w tym rozszerzona forma Backus-Naur (EBNF) i rozszerzona forma Backus-Naur (ABNF).

Historia

Pomysł opisujący strukturę języka, używając reguł nadpisywania sięgają co najmniej do pracy panini , starożytny indyjski gramatyka sanskrytu i szanowanego uczonego w hinduizmie, który żył kiedyś między 6 i 4 wieku pne . Jego notacja opisująca strukturę słów sanskrytu jest równoważna mocy Backusa i ma wiele podobnych właściwości.

W społeczeństwie zachodnim gramatyka była przez długi czas traktowana jako przedmiot nauczania, a nie nauka; opisy były nieformalne i ukierunkowane na praktyczne zastosowanie. W pierwszej połowie XX wieku językoznawcy, tacy jak Leonard Bloomfield i Zellig Harris, podjęli próby sformalizowania opisu języka, w tym struktury fraz.

W międzyczasie reguły przepisywania ciągów jako formalnych systemów logicznych zostały wprowadzone i zbadane przez matematyków, takich jak Axel Thue (w 1914), Emil Post (1920-40s) i Alan Turing (1936). Noam Chomsky , ucząc lingwistyki studentów teorii informacji na MIT , połączył lingwistykę i matematykę, przyjmując za podstawę opisu składni języka naturalnego to, co w istocie jest formalizmem Thue . Wprowadził również wyraźne rozróżnienie między regułami generatywnymi ( gramatykami bezkontekstowymi ) a regułami transformacji (1956).

John Backus , projektant języków programowania w IBM , zaproponował metajęzyk „formuł metajęzykowych” do opisu składni nowego języka programowania IAL, znanego dziś jako ALGOL 58 (1959). Jego notacja została po raz pierwszy użyta w raporcie ALGOL 60.

BNF to zapis gramatyk bezkontekstowych Chomsky'ego. Backus znał pracę Chomsky'ego.

Zgodnie z propozycją Backusa formuła określała „klasy”, których nazwy ujęto w nawiasy ostre. Na przykład <ab>. Każda z tych nazw oznacza klasę podstawowych symboli.

Dalszy rozwój ALGOL doprowadził do powstania ALGOL 60 . W raporcie komisji z 1963 r. Peter Naur nazwał notację Backusa formą normalną Backus . Donald Knuth przekonywał, że BNF należy raczej odczytywać jako formę Backusa–Naura , ponieważ nie jest to „ forma normalna w konwencjonalnym sensie”, w przeciwieństwie na przykład do formy normalnej Chomsky'ego . Nazwa formy Pāṇini Backus została również kiedyś zasugerowana ze względu na fakt, że rozwinięcie formy normalnej Backus może nie być dokładne i że Paṇini niezależnie opracowało wcześniej podobną notację.

BNF jest opisany przez Petera Naura w raporcie ALGOL 60 jako formuła metajęzykowa :

Ciągi znaków ujęte w nawiasy <> reprezentują zmienne metajęzykowe, których wartościami są ciągi symboli. Znaki „::=” i „|” (te ostatnie w znaczeniu „lub”) są spójnikami metajęzykowymi. Każdy znak we wzorze, który nie jest zmienną ani spójnikiem, oznacza sam siebie. Zestawienie znaków lub zmiennych w formule oznacza zestawienie oznaczonego ciągu.

Inny przykład z raportu ALGOL 60 ilustruje główną różnicę między metajęzykiem BNF a bezkontekstową gramatyką Chomsky'ego. Zmienne metajęzykowe nie wymagają reguły określającej ich powstawanie. Ich powstawanie można po prostu opisać językiem naturalnym w nawiasach <>. Poniższy raport ALGOL 60 sekcja 2.3 komentuje specyfikację, ilustruje, jak to działa:

W celu włączenia tekstu do symboli programu obowiązują następujące konwencje „komentarza”:

Sekwencja podstawowych symboli: jest równa
; komentarz <dowolna sekwencja niezawierająca ';'>; ;
początek komentarza <dowolna sekwencja niezawierająca ';'>; rozpocząć
end <dowolna sekwencja niezawierająca 'end' lub ';' lub 'inny'> kończyć się

Równoważność oznacza tutaj, że dowolna z trzech struktur pokazanych w lewej kolumnie może zostać zastąpiona w dowolnym wystąpieniu poza łańcuchami przez symbol pokazany w tym samym wierszu w prawej kolumnie bez żadnego wpływu na działanie programu.

Naur zmienił dwa symbole Backusa na powszechnie dostępne postacie. ::=Symbol był pierwotnie :≡. |Symbol był pierwotnie słowo „ lub ” (z paskiem nad nim). Pracując dla IBM, Backus miałby umowę o zachowaniu poufności i nie mógłby mówić o swoim źródle, gdyby pochodziło z zastrzeżonego projektu IBM.

BNF jest bardzo podobny do kanonicznych równań algebry logicznej, które są i były w tym czasie używane w projektowaniu układów logicznych. Backus był matematykiem i projektantem języka programowania FORTRAN. Nauka algebry Boole'a jest zwykle częścią programu nauczania matematyki. Wiemy, że ani Backus, ani Naur nie opisali imion zawartych w < >nieterminaliach. Terminologia Chomsky'ego nie była pierwotnie używana w opisie BNF. Naur opisał je później jako zajęcia w materiałach szkoleniowych ALGOL. W raporcie ALGOL 60 nazwano je zmiennymi metajęzykowymi. Wszystko inne niż zawarte w metasymbole ::=, |i nazwy klas < >są symbolami definiowanego języka. Metasymbole ::=należy interpretować jako „jest zdefiniowany jako”. |Służy do oddzielania alternatywne definicje i jest interpretowane jako „lub”. Metasymbole < >są ogranicznikami zawierającymi nazwę klasy. BNF jest opisywany jako metajęzyk do mówienia o ALGOL przez Petera Naura i Saula Rosena .

W 1947 Saul Rosen zaangażował się w działalność raczkującego Association for Computing Machinery , najpierw w komisji językowej, która przekształciła się w grupę IAL i ostatecznie doprowadziła do ALGOL. Był pierwszym redaktorem zarządzającym Communications of the ACM. Wiemy, że BNF został po raz pierwszy użyty jako metajęzyk do mówienia o języku ALGOL w raporcie ALGOL 60. W ten sposób wyjaśniono to w materiale kursu programowania ALGOL opracowanym przez Petera Naura w 1962 roku. Wczesne podręczniki ALGOL opracowane przez IBM, Honeywell, Burroughs i Digital Equipment Corporation podążały za raportem ALGOL 60, używając go jako metajęzyka. Saul Rosen w swojej książce opisuje BNF jako metajęzyk do mówienia o ALGOL. Przykładem jego zastosowania jako metajęzyka byłoby zdefiniowanie wyrażenia arytmetycznego:

<expr> ::= <term>|<expr><addop><term>

Pierwszym symbolem alternatywy może być definiowana klasa, powtórzenie, jak wyjaśnił Naur, ma funkcję określania, że ​​sekwencja alternatywy może rekurencyjnie zaczynać się od poprzedniej alternatywy i może być powtarzana dowolną liczbę razy. Na przykład, powyżej <expr>jest zdefiniowane jako a <term>po którym następuje dowolna liczba <addop> <term>.

W niektórych późniejszych metajęzykach, takich jak META II Schorre'a , konstrukcja powtarzania rekurencyjnego BNF jest zastępowana operatorem sekwencji i symbolami języka docelowego zdefiniowanymi przy użyciu ciągów w cudzysłowie. <I >wsporniki zostały usunięte. ()Dodano nawiasy do grupowania matematycznego. <expr>Reguła wydaje się w META II jako

EXPR = TERM $('+' TERM .OUT('ADD') | '-' TERM .OUT('SUB'));

Zmiany te umożliwiły META II i jego pochodnych językom programowania zdefiniowanie i rozszerzenie własnego metajęzyka, kosztem możliwości wykorzystania opisu w języku naturalnym, zmiennej metajęzykowej, opisu konstrukcji języka. Wiele metajęzyków spin-off było inspirowanych przez BNF. Zobacz META II , TREE-META i Metacompiler .

Klasa BNF opisuje formację konstrukcji języka, z formacją zdefiniowaną jako wzorzec lub akcję tworzenia wzorca. Nazwa klasy expr jest opisana w języku naturalnym jako a <term>po której następuje sekwencja <addop> <term>. Klasa jest abstrakcją; możemy o nim mówić niezależnie od jego powstania. Możemy mówić o terminie, niezależnie od jego definicji, jako dodawanym lub odejmowanym w wyraż. Możemy mówić o tym, że termin jest określonym typem danych i jak ma być oceniane wyrażenie przy określonych kombinacjach typów danych. Lub nawet zmienić kolejność wyrażenia, aby pogrupować typy danych i wyniki oceny typów mieszanych. Dodatek dotyczący języka naturalnego zawierał szczegółowe informacje na temat semantyki klas językowych, które mają być używane przez implementację kompilatora i programistę piszącego program ALGOL. Opis w języku naturalnym dodatkowo uzupełnił składnię. Reguła liczb całkowitych jest dobrym przykładem języka naturalnego i metajęzyka używanego do opisu składni:

<integer> ::= <digit>|<integer><digit>

Powyżej nie ma sprecyzowanych spacji. O ile reguła mówi, możemy mieć spację między cyframi. W języku naturalnym uzupełniamy metajęzyk BNF, wyjaśniając, że ciąg cyfr może nie zawierać spacji między cyframi. Angielski jest tylko jednym z możliwych języków naturalnych. Tłumaczenia raportów ALGOL były dostępne w wielu językach naturalnych.

Pochodzenie BNF nie jest tak ważne, jak jego wpływ na rozwój języka programowania. W okresie bezpośrednio po publikacji raportu ALGOL 60 BNF był podstawą wielu systemów kompilator-kompilator .

Niektóre, takie jak „A Syntax Directed Compiler for ALGOL 60” opracowany przez Edgara T. Ironsa i „A Compiler Building System” opracowany przez Brookera i Morrisa, wykorzystywały bezpośrednio BNF. Inne, takie jak Schorre Metacompilers , przekształciły go w język programowania z zaledwie kilkoma zmianami. <class name>stały się identyfikatorami symboli, porzucając otaczające <,> i używając łańcuchów w cudzysłowie dla symboli języka docelowego. Grupowanie podobne do arytmetyki zapewniło uproszczenie, które usunęło używanie klas, w których grupowanie było jedyną wartością. Reguła wyrażeń arytmetycznych META II pokazuje zastosowanie grupowania. Wyrażenia wyjściowe umieszczone w regule META II są używane do wyprowadzania kodu i etykiet w języku asemblerowym. Reguły w META II są równoważne z definicjami klas w BNF. Uniksowe narzędzie yacc jest oparte na BNF z tworzeniem kodu podobnego do META II. yacc jest najczęściej używany jako generator parserów , a jego korzenie to oczywiście BNF.

BNF jest dziś jednym z najstarszych języków związanych z komputerami, które są nadal używane.

Wstęp

Specyfikacja BNF to zbiór reguł wyprowadzania, zapisany jako

 <symbol> ::= __expression__

gdzie < symbol > jest nieterminalem , a __wyrażenie__ składa się z jednej lub więcej sekwencji symboli; kolejne sekwencje są oddzielone pionową kreską „|”, wskazującą na wybór , a całość jest możliwą substytucją symbolu po lewej stronie. Symbole, które nigdy nie pojawiają się po lewej stronie to terminale . Z drugiej strony, symbole pojawiające się po lewej stronie niekońcówkami i są zawsze zawarte między parą <>.

„::=” oznacza, że ​​symbol po lewej stronie należy zastąpić wyrażeniem po prawej stronie.

Przykład

Jako przykład rozważ ten możliwy BNF dla adresu pocztowego w USA :

 <postal-address> ::= <name-part> <street-address> <zip-part>

      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part>

  <personal-part> ::= <initial> "." | <first-name>

 <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>

       <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>

<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
    <opt-apt-num> ::= <apt-num> | ""

Przekłada się to na angielski jako:

  • Adres pocztowy składa się z części z nazwą, następnie z części dotyczącej ulicy i części z kodem pocztowym .
  • Część nazwy składa się z: części osobistej, po której następuje nazwisko, po której następuje opcjonalny przyrostek (Jr., Sr. lub liczba dynastyczna) i końcówka wiersza lub część osobista, po której następuje część z imieniem ( zasada ta ilustruje użycie rekurencji w BNF, obejmując przypadek osób, które używają wielu imion i drugich imion oraz inicjałów).
  • Część osobista składa się z imienia lub inicjału, po którym następuje kropka.
  • Ulica składa się z numeru domu, nazwy ulicy, opcjonalnego określenia mieszkania i końca linii.
  • Część zip składa się z nazwy miasta , przecinka, kodu stanu , kodu pocztowego i końca wiersza.
  • Część opt-suffix składa się z sufiksu, takiego jak „Sr.”, „Jr.” lub cyfra rzymska lub pusty ciąg (tzn. nic).
  • Opt-apt-num składa się z numeru mieszkania lub pustego ciągu (tj. niczego).

Zwróć uwagę, że wiele rzeczy (takich jak format imienia, numer mieszkania, kod pocztowy i cyfra rzymska) pozostaje tutaj nieokreślonych. W razie potrzeby można je opisać za pomocą dodatkowych zasad BNF.

Dalsze przykłady

Sama składnia BNF może być reprezentowana przez BNF w następujący sposób:

 <syntax>         ::= <rule> | <rule> <syntax>
 <rule>           ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= " " <opt-whitespace> | ""
 <expression>     ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
 <line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
 <list>           ::= <term> | <term> <opt-whitespace> <list>
 <term>           ::= <literal> | "<" <rule-name> ">"
 <literal>        ::= '"' <text1> '"' | "'" <text2> "'"
 <text1>          ::= "" | <character1> <text1>
 <text2>          ::= '' | <character2> <text2>
 <character>      ::= <letter> | <digit> | <symbol>
 <letter>         ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
 <digit>          ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
 <symbol>         ::=  "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"
 <character1>     ::= <character> | "'"
 <character2>     ::= <character> | '"'
 <rule-name>      ::= <letter> | <rule-name> <rule-char>
 <rule-char>      ::= <letter> | <digit> | "-"

Zauważ, że "" jest pustym ciągiem .

Pierwotny BNF nie używał cudzysłowów, jak pokazano w <literal>regule. Zakłada to, że do prawidłowej interpretacji reguły nie są potrzebne białe znaki .

<EOL>reprezentuje odpowiedni specyfikator końca wiersza (w ASCII , powrót karetki, wysuw wiersza lub oba w zależności od systemu operacyjnego ). <rule-name>i <text>należy je zastąpić odpowiednio nazwą/etykietą zadeklarowanej reguły lub dosłownym tekstem.

W powyższym przykładzie adresu pocztowego w USA cały cytat blokowy jest składnią. Każda linia lub nieprzerwana grupa linii jest regułą; na przykład jedna reguła zaczyna się od <name-part> ::=. Drugą częścią tej reguły (oprócz końca linii) jest wyrażenie, które składa się z dwóch list oddzielonych rurą |. Te dwie listy składają się z kilku terminów (odpowiednio trzech terminów i dwóch terminów). Każdy termin w tej konkretnej regule jest nazwą reguły.

Warianty

Istnieje wiele wariantów i rozszerzeń BNF, na ogół ze względu na prostotę i zwięzłość lub dostosowanie go do konkretnego zastosowania. Jedną wspólną cechą wielu wariantów jest użycie operatorów powtarzania wyrażeń regularnych , takich jak *i +. Notacja ebnf (EBNF) jest popularnym.

Innym powszechnym rozszerzeniem jest użycie nawiasów kwadratowych wokół opcjonalnych elementów. Chociaż nie występuje w oryginalnym ALGOL 60 raportu (zamiast wprowadzony kilka lat później w IBM „s PL / I definicja), notacja jest teraz powszechnie uznawana.

Rozszerzony formularz Backus-Naur (ABNF) i formularz Routing Backus-Naur (RBNF) to rozszerzenia powszechnie używane do opisywania protokołów Internet Engineering Task Force (IETF) .

Parsowanie gramatyki wyrażeń opiera się na notacjach BNF i wyrażeń regularnych, tworząc alternatywną klasę gramatyki formalnej , która ma zasadniczo charakter analityczny, a nie generatywny .

Wiele specyfikacji BNF znalezionych obecnie w Internecie ma być czytelnych dla człowieka i ma charakter nieformalny. Często zawierają one wiele z następujących reguł składni i rozszerzeń:

  • Elementy opcjonalne ujęte w nawiasy kwadratowe: [<item-x>].
  • Elementy istniejące 0 lub więcej razy są ujęte w nawiasy klamrowe lub z gwiazdką ( *), na przykład <word> ::= <letter> {<letter>}lub <word> ::= <letter> <letter>*odpowiednio.
  • Elementy, które istnieją co najmniej 1 raz, mają przyrostek z symbolem dodawania (plus) +, na przykład <word> ::= <letter>+.
  • Terminale mogą być pogrubione, a nie kursywą, a nieterminale w postaci zwykłego tekstu, a nie nawiasów ostrych.
  • W przypadku grupowania elementów są one ujęte w nawiasy proste.

Oprogramowanie wykorzystujące BNF

  • ANTLR , kolejny generator parserów napisany w Javie
  • Qlik Sense, narzędzie BI, wykorzystuje wariant BNF do tworzenia skryptów
  • Konwerter BNF (BNFC), działający na wariancie zwanym „formą Backus-Naur” (LBNF). W tym wariancie, każda produkcja dla danego nieterminala otrzymuje etykietę, która może być użyta jako konstruktor algebraicznego typu danych reprezentującego ten nieterminal. Konwerter jest w stanie tworzyć typy i parsery dla składni abstrakcyjnej w kilku językach, w tym w Haskell i Javie.
  • Coco/R , generator kompilatorów akceptujący przypisaną gramatykę w EBNF
  • DMS Software Reengineering Toolkit , system analizy i transformacji programów dla dowolnych języków
  • Parser GOLD BNF
  • GNU bizon , wersja GNU yacc
  • Parser RPA BNF. Parsowanie demonstracyjne online (PHP): JavaScript, XML
  • XACT X4MR System, oparty na regułach system ekspercki do tłumaczenia języka programowania
  • XPL Analyzer, narzędzie, które akceptuje uproszczony BNF dla języka i tworzy parser dla tego języka w XPL; może być zintegrowany z dostarczonym programem SKELETON, za pomocą którego można debugować język ( program wniesiony przez SHARE , poprzedzony przez A Compiler Generator )
  • Yacc , generator parserów (najczęściej używany z preprocesorem Lex )
  • bnfparser 2 , uniwersalne narzędzie do weryfikacji składni
  • bnf2xml, wprowadzanie znaczników ze znacznikami XML przy użyciu zaawansowanego dopasowywania BNF.
  • JavaCC, Java Compiler Compiler tm (JavaCC tm) - Generator parsera Java.
  • Narzędzia parsera Racketa, parsowanie w stylu lex i yacc (edycja Beautiful Racket)
  • Belr , Generator parserów napisany w C++11. Używa ABNF .

Zobacz też

Bibliografia

Zewnętrzne linki

  • Garshol, Lars Marius, BNF i EBNF: Czym są i jak działają? , NIE : Prywatne.
  • RFC  5234 — Rozszerzony BNF dla specyfikacji składni: ABNF.
  • RFC  5511 — Routing BNF: składnia używana w różnych specyfikacjach protokołów.
  • ISO / IEC 14977: 1996 (E) Technologia informacyjna - Syntaktyczny metajęzyk - Rozszerzony BNF , dostępny w „Publicznie dostępnym”, Normy , ISOlub z Kuhn, Marcus, Iso 14977 (PDF) , UK : CAM (ten ostatni nie ma okładki, ale poza tym jest znacznie czystszy)

Gramatyki językowe