Forma Backusa-Naura

Nie mylić z formą normalną Boyce'a-Codda .

W informatyce forma Backusa – Naura ( / ˌ b ć k ə s ˈ n aʊər / ) lub postać normalna Backusa ( BNF ) to notacja metaskładni dla gramatyk bezkontekstowych , często używana do opisania składni języków używanych w informatyce, takie jak języki programowania komputerów , formaty dokumentów , zestawy instrukcji i protokoły komunikacyjne . Jest stosowany wszędzie tam, gdzie potrzebne są dokładne opisy języków: na przykład w oficjalnych specyfikacjach języków, w podręcznikach i podręcznikach z teorii języków programowania.

Używa się wielu rozszerzeń i wariantów oryginalnej notacji Backusa – Naura; niektóre są dokładnie zdefiniowane, w tym rozszerzona forma Backusa – Naura (EBNF) i rozszerzona forma Backusa – Naura (ABNF).

Przegląd

Specyfikacja BNF to zestaw reguł wyprowadzania, zapisanych jako

   <  symbol  >  ::=  __wyrażenie__

Gdzie:

  • < symbol > to nieterminal (zmienna), a __expression__ składa się z jednej lub więcej sekwencji symboli terminalnych lub nieterminalnych;
  • ::= oznacza, że ​​symbol po lewej stronie musi zostać zastąpiony wyrażeniem po prawej stronie.
  • kolejne sekwencje [symbolów] oddzielone są pionową kreską „|”, oznaczającą wybór , całość będąca możliwym zastąpieniem 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 są nieterminalami i zawsze są ujęte między parą <>.

Przykład

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

     

            

    

      

           

    <  adres pocztowy  >  ::=  <  część imienia  >  <  adres ulicy  >  <  część kodu pocztowego  >  <  część imienia  >  ::=  <  część osobista  >  <  nazwisko  >  <  część sufiksu opt  >  <  EOL  >  |  <  część-osobista  >  <  część-imienia  >  <  część-osobista  >  ::=  <  inicjał  >  "." |   <  imię  >  <  adres ulicy  >  ::=  <  numer domu  >  <  nazwa ulicy  >  <  numer mieszkania  >  <  EOL  >  < numer   pocztowy  >  ::=  <  nazwa miasta  >  ","  <  kod-stanu  >  <  kod pocztowy  >  <  EOL  >  <  część-sufiksu-opt  >  ::=  "Sr." |  "Jr."  |   <  cyfra rzymska  >  | ""   <  opt-numer-apt  >  ::=  <  apt-num  >  | ""

Przekłada się to na język angielski jako:

  • Adres pocztowy składa się z części nazwy, po której następuje część adresu , po której następuje część kodu pocztowego .
  • Część imienia składa się z: części osobowej, po której następuje nazwisko , po której następuje opcjonalny sufiks (Jr., Sr. lub numer dynastyczny) i końca wiersza lub część osobowa, po której następuje część imienia ( ta reguła ilustruje użycie rekurencji w BNF, obejmując przypadek osób, które używają wielu imion i imion oraz inicjałów).
  • Część osobista składa się z imienia lub inicjału, po którym następuje kropka.
  • Adres ulicy składa się z numeru domu, po którym następuje nazwa ulicy, po którym następuje opcjonalny specyfikator mieszkania , po którym następuje koniec wiersza.
  • Kod pocztowy składa się z nazwy miasta , po której następuje przecinek, po którym następuje kod stanu , po którym następuje kod pocztowy, po którym następuje koniec wiersza.
  • Część opt-sufiksu składa się z sufiksu, takiego jak „Sr.”, „Jr.” lub cyfrą rzymską lub pustym ciągiem znaków (tzn. nic).
  • Opt-apt-num składa się z numeru mieszkania lub pustego ciągu znaków (tzn. nic).

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 reguł BNF.

Historia

Pomysł opisania struktury języka za pomocą reguł przepisywania wywodzi się przynajmniej z prac Pāṇiniego , starożytnego indyjskiego gramatyka sanskrytu i szanowanego uczonego w hinduizmie, który żył między VI a IV wiekiem pne . Jego notacja opisująca sanskrytu jest równoważna mocy notacji Backusa i ma wiele podobnych właściwości.

W społeczeństwie zachodnim gramatyka była przez długi czas uważana za przedmiot nauczania, a nie badań naukowych; opisy były nieformalne i ukierunkowane na praktyczne zastosowanie. W pierwszej połowie XX wieku językoznawcy , tacy jak Leonard Bloomfield i Zellig Harris, rozpoczęli próby sformalizowania opisu języka, w tym struktury frazowej .

W międzyczasie reguły przepisywania ciągów jako formalne systemy logiczne zostały wprowadzone i zbadane przez matematyków, takich jak Axel Thue (w 1914 r.), Emil Post (1920–40) i Alan Turing (1936). Noam Chomsky , ucząc lingwistyki studentów teorii informacji na MIT , połączył językoznawstwo i matematykę, opierając się na formalizmie Thue jako podstawę opisu składni języka naturalnego . Wprowadził również wyraźne rozróżnienie między regułami generatywnymi (te z gramatyk bezkontekstowych ) a regułami transformacji (1956).

John Backus , projektant języka programowania w firmie IBM , zaproponował metajęzyk „formuł metajęzykowych” opisujących 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 notacja gramatyk bezkontekstowych Chomsky'ego. Backus znał prace Chomsky'ego.

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

Dalszy rozwój ALGOL doprowadził do ALGOL 60 . W raporcie komisji z 1963 roku Peter Naur nazwał notację Backusa postacią normalną Backusa . Donald Knuth argumentował, ż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 postaci normalnej Chomsky'ego . Nazwa forma Pāṇini Backus była również kiedyś sugerowana ze względu na fakt, że rozwinięcie postaci normalnej Backus może nie być dokładne, oraz że Pāṇini niezależnie opracował wcześniej podobny zapis.

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

Ciągi znaków w nawiasach <> reprezentują zmienne metajęzykowe, których wartościami są ciągi symboli. Znaki "::=" i "|" (to ostatnie w znaczeniu „lub”) to spójniki metajęzykowe. Każdy znak we wzorze, który nie jest zmienną ani łącznikiem, oznacza sam siebie. Zestawienie znaków lub zmiennych we wzorze oznacza zestawienie oznaczonej sekwencji.

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

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

Sekwencja podstawowych symboli: jest równa
; komentarz <dowolna sekwencja niezawierająca ';'>; ;
rozpocząć komentarz <dowolna sekwencja niezawierająca ';'>; zaczynać
end <dowolna sekwencja niezawierająca 'end' lub ';' lub „inaczej”> koniec

Równoważność oznacza tutaj, że dowolną z trzech struktur pokazanych w lewej kolumnie można zastąpić, w dowolnym przypadku poza łańcuchami, symbolem pokazanym w tym samym wierszu w prawej kolumnie bez żadnego wpływu na działanie programu.

Naur zmienił dwa symbole Backusa na powszechnie dostępne znaki. Pierwotnie symbolem ::= było :≡ . | _ symbolem było pierwotnie słowo „ lub ” (z kreską nad nim).

BNF jest bardzo podobny do kanonicznych równań algebry Boole'a , które są i były w tamtym czasie używane w projektowaniu obwodów logicznych. Backus był matematykiem i twórcą języka programowania FORTRAN. Badania nad algebrą Boole'a są zwykle częścią programu nauczania matematyki. Ani Backus, ani Naur nie opisali nazw zawartych w < > jako nieterminali. Terminologia Chomsky'ego nie była pierwotnie używana do opisu BNF. Naur opisał je później jako zajęcia w materiałach kursu ALGOL. W raporcie ALGOL 60 nazwano je zmiennymi metajęzykowymi. Wszystko inne niż metasymbole ::= , | , a nazwy klas ujęte w < > to symbole definiowanego języka. Metasymbol ::= należy interpretować jako „jest zdefiniowany jako”. | _ służy do oddzielania alternatywnych definicji i jest interpretowany jako „lub”. Metasymbole < > są ogranicznikami obejmującymi nazwę klasy. BNF jest opisany jako metajęzyk do mówienia o ALGOLu przez Petera Naura i Saula Rosena .

W 1947 Saul Rosen zaangażował się w działalność raczkującego Stowarzyszenia Maszyn Komputerowych , najpierw w komitecie językowym, który stał się grupą IAL i ostatecznie doprowadził do powstania ALGOL. Był pierwszym redaktorem naczelnym Communications of the ACM. [ wymagane wyjaśnienie ] BNF został po raz pierwszy użyty jako metajęzyk do omówienia języka ALGOL w raporcie ALGOL 60. Tak jest to wyjaśnione w kursie programowania ALGOL opracowanym przez Petera Naura w 1962 r. Wczesne podręczniki ALGOL firmy IBM, Honeywell, Burroughs i Digital Equipment Corporation były zgodne z 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 użycia jako metajęzyka byłoby zdefiniowanie wyrażenia arytmetycznego: 

   <  wyrażenie  >  ::=  <  termin  >  |  <  wyrażenie  ><  addop  ><  termin  >

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

META II Schorre'a , rekurencyjna konstrukcja powtórzeń BNF jest zastępowana operatorem sekwencji i symbolami języka docelowego zdefiniowanymi za pomocą ciągów znaków ujętych w cudzysłowy. Nawiasy < i > zostały usunięte. Dodano nawiasy ( ) dla grupowania matematycznego. Reguła <wyr> pojawiłaby się w META II jako 

WYRAŻ = TERMIN $('+' TERMIN .OUT('ADD') | '-' TERMIN .OUT('SUB'));

Zmiany te umożliwiły META II i pochodnym językom programowania zdefiniowanie i rozszerzenie własnego metajęzyka, kosztem możliwości użycia opisu w języku naturalnym, zmiennej metajęzykowej, opisu konstrukcji językowych. Wiele metajęzyków spin-off zostało zainspirowanych BNF. [ Potrzebne źródło ] Zobacz META II , TREE-META i Metacompiler .

Klasa BNF opisuje formację konstruktu językowego, z formacją zdefiniowaną jako wzorzec lub czynność tworzenia wzorca. Nazwa klasy expr jest opisana w języku naturalnym jako <term> , po którym następuje sekwencja <addop> <term> . Klasa jest abstrakcją; możemy o nim mówić niezależnie od jego powstania. Możemy mówić o wyrażeniu, niezależnie od jego definicji, jako dodawanym lub odejmowanym w wyrażeniu. Możemy mówić o tym, że termin jest określonym typem danych i o tym, jak należy oceniać wyrażenie, mając określone kombinacje typów danych, a nawet o zmianie kolejności wyrażenia w celu pogrupowania typów danych i wyników oceny typów mieszanych. Dodatek dotyczący języka naturalnego zawierał szczegółowe informacje na temat semantyki klas języka, które mają być używane przez implementację kompilatora i programistę piszącego program ALGOL. Opis w języku naturalnym również uzupełniał składnię. Reguła liczb całkowitych jest dobrym przykładem języka naturalnego i metajęzyka używanego do opisu składni: 

   <  liczba całkowita  >  ::=  <  cyfra  >  |  <  liczba całkowita  ><  cyfra  >

Powyżej nie ma żadnych szczegółów dotyczących białych znaków. Zgodnie z regułą, możemy mieć spację między cyframi. W języku naturalnym uzupełniamy metajęzyk BNF, wyjaśniając, że ciąg cyfr nie może zawierać białych odstępów 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. [ potrzebne źródło ] W okresie bezpośrednio po opublikowaniu raportu ALGOL 60 BNF był podstawą wielu systemów kompilator-kompilator .

Niektóre, jak „A Syntax Directed Compiler for ALGOL 60” opracowany przez Edgara T. Ironsa i „A Compiler Building System” opracowany przez Brookera i Morrisa, bezpośrednio używały BNF. Inne, takie jak Schorre Metacompilers, stały się językiem programowania z zaledwie kilkoma zmianami. <nazwa klasy> stała się identyfikatorami symboli, porzucając otaczające <,> i używając ciągów znaków w cudzysłowach dla symboli języka docelowego. Grupowanie podobne do arytmetycznego zapewniło uproszczenie, które wyeliminowało użycie klas, w których grupowanie było jedyną wartością. Reguła wyrażeń arytmetycznych META II pokazuje użycie grupowania. Wyrażenia wyjściowe umieszczone w regule META II są używane do wyprowadzania kodu i etykiet w asemblerze. Reguły w META II są odpowiednikami definicji klas w BNF. Uniksowe narzędzie yacc jest oparte na BNF z produkcją kodu podobną do META II. yacc jest najczęściej używany jako generator parsera , a jego korzenie są oczywiście BNF.

BNF jest dziś jednym z najstarszych wciąż używanych języków związanych z komputerami. [ potrzebne źródło ]

Dalsze przykłady

BNF syntax diagram
Diagram składni BNF

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

            
               
          
           
               
                                
            
        
                                                 
         <  składnia  >  ::=  <  reguła  >  |  <  reguła  >  <  składnia  >  <  reguła  >  ::=  <  opt-whitespace  >  "<"  <  nazwa-reguły  >  ">"  <  opt-whitespace  >  "  ::=  "  <  opt-whitespace  >  <  wyrażenie  >  <  koniec linii  >  <  opt-whitespace  >  ::=  " "  <  opt-whitespace  >  | ""   <  wyrażenie  >  ::=  <  lista  >  |  <  lista  >  <  opt-białe spacje  >  "|"  <  opt-whitespace  >  <  wyrażenie  >  <  line-end  >  ::=  <  opt-whitespace  >  <  EOL  >  |  <  koniec wiersza  >  <  koniec wiersza  >  <  lista  >  ::=  <  wyraz  >  |  <  term  >  <  opt-whitespace  >  <  lista  >  <  term  >  ::=  <  literał  >  | "<"   <  nazwa-reguły  >  ">"  <  literał  >  ::=  '"'  <  tekst1  >  '"' | "'"   <  tekst2  >  "'"  <  tekst1  >  ::=  "" |  <  znak1  >  <  tekst1  >  <  tekst2  >  ::=  "" |  <  znak2  >  <  tekst2  >  <  znak  >  ::=  <  litera  >  |  <  cyfra  >  |  <  symbol  >  <  litera  >  ::=  "A" | "B" |  "C" |  "D" |  "E" |  "F" |  "G" |  "H" |  "ja" |  "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" |  "ja" |  "j" |  "k" |  "l" |  "m" |  "n" |  "o" |  "p" |  "q" |  "r" |  "s" |  "t" |  "u" |  "w" |  "w" |  "x" |  "y" |  "z"   <  cyfra  >  ::=  "0" | "1" |  "2" |  "3" |  "4" |  "5" |  "6" |  "7" |  "8" |  "9"   <  symbol  >  ::=  "|" |  " " |  "!"  |  "#" |  "$" |  "%" |  "&" |  "(" | ")" |  "*" |  "+" |  "," |  "-" |  "."  |  "/" |  ":" |  ";"  |  ">" |  "=" |  "<" |  "?"  |  "@" |  "[" |  "\" |  "]" |  "^" |  "_" |  "`" |  "{" |  "}" |  "~"   <  znak1  >  ::=  <  znak  >  | "'"   <  znak2  >  ::=  <  znak  >  | '"'   <  nazwa-reguły  >  ::=  <  litera  >  |  <  nazwa-reguły  >  <  znak-reguły  >  <  znak-reguły  >  ::=  <  litera  >  |  <  cyfra  >  | "-"

Zauważ, że "" jest pustym łańcuchem .

Oryginalny BNF nie używał cudzysłowów, jak pokazano w regule <literal> . Zakłada się, że do prawidłowej interpretacji reguły nie są potrzebne żadne spacje .

<EOL> reprezentuje odpowiedni specyfikator końca linii (w ASCII , znak powrotu karetki, wysuw wiersza lub oba, w zależności od systemu operacyjnego ). <nazwa-reguły> i <tekst> należy zastąpić odpowiednio nazwą/etykietą zadeklarowanej reguły lub tekstem dosłownym.

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 <nazwa-część> ::= . Drugą częścią tej reguły (oprócz końca linii) jest wyrażenie, które składa się z dwóch list oddzielonych pionową kreską | . Te dwie listy składają się z pewnych terminów (odpowiednio trzech terminów i dwóch terminów). Każdy termin w tej konkretnej regule jest nazwą reguły.

Warianty

EBNF

Główny artykuł: Rozszerzony formularz Backus – Naur

Istnieje wiele wariantów i rozszerzeń BNF, na ogół albo ze względu na prostotę i zwięzłość, albo w celu dostosowania go do konkretnego zastosowania. Wspólną cechą wielu wariantów jest użycie wyrażeń regularnych, takich jak * i + . Rozszerzona forma Backusa – Naura (EBNF) jest powszechna.

Innym powszechnym rozszerzeniem jest użycie nawiasów kwadratowych wokół elementów opcjonalnych. Chociaż nie występuje w oryginalnym raporcie ALGOL 60 ( zamiast tego wprowadzono kilka lat później w definicji IBM PL/I ), notacja ta jest obecnie powszechnie uznawana.

ABNF

Główny artykuł: ABNF

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

Gramatyki analizujące wyrażenia opierają się na notacji BNF i wyrażeniach regularnych , tworząc alternatywną klasę gramatyki formalnej , która ma zasadniczo charakter raczej analityczny niż generatywny .

Inni

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

  • Elementy opcjonalne ujęte w nawiasy kwadratowe: [<item-x>] .
  • Elementy występujące 0 lub więcej razy są ujęte w nawiasy klamrowe lub zakończone gwiazdką ( * ), na przykład odpowiednio <słowo> ::= <litera> {<litera>} lub < słowo> ::= <litera> <litera>* .
  • Pozycje występujące 1 lub więcej razy są zakończone symbolem dodawania (plus), + , takim jak <słowo> ::= <litera>+ .
  • Terminale mogą być wyświetlane pogrubioną czcionką zamiast kursywą, a nieterminale zwykłym tekstem zamiast nawiasów ostrych.
  • Tam, gdzie elementy są pogrupowane, są one ujęte w nawiasy proste.

Oprogramowanie wykorzystujące BNF

  • ANTLR , kolejny generator parsera napisany w Javie
  • Qlik Sense, narzędzie BI, używa wariantu BNF do tworzenia skryptów
  • Konwerter BNF (BNFC), działający na wariancie zwanym „oznaczonym formularzem Backus – Naur” (LBNF). W tym wariancie każda produkcja dla danego nieterminala otrzymuje etykietę, która może służyć jako konstruktor algebraicznego typu danych reprezentującego ten nieterminal. Konwerter jest w stanie generować typy i parsery składni abstrakcyjnej w kilku językach, w tym Haskell i Java.
  • Coco/R , generator kompilatora akceptujący przypisaną gramatykę w EBNF
  • DMS Software Reengineering Toolkit , system analizy i transformacji programu dla dowolnych języków
  • ZŁOTY parser BNF
  • GNU bison , wersja GNU yacc
  • Parser RPA BNF. Analiza demo online (PHP): JavaScript, XML
  • XACT X4MR System, oparty na regułach system ekspercki do tłumaczenia języków 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 ( SHARE , który został poprzedzony przez A Compiler Generator )
  • Yacc , generator parsera (najczęściej używany z preprocesorem Lex )
  • bnfparser 2 , uniwersalne narzędzie do weryfikacji składni
  • bnf2xml, wprowadzanie znaczników za pomocą znaczników XML przy użyciu zaawansowanego dopasowywania BNF.
  • JavaCC, Java Compiler Compiler tm (JavaCC tm) — generator parsera języka Java.
  • Narzędzia parsera Racket , parsowanie w stylu lex i yacc (edycja Beautiful Racket)

Zobacz też

Linki zewnętrzne

Gramatyki językowe

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Backus–Naur_form&oldid=1141508412 ”