Backus–Naur-Forma: Metaszintaxis

A BNF széles körben használatos a számítógépek programozási nyelveinek nyelvtanának leírására, ideértve az utasításkészleteket és a kommunikációs protokollokat, valamint egyes természetes nyelvek nyelvtanát is (pl. meter a szanszkrit költészetben). A legtöbb programozási nyelv elméleti leírása és/vagy szemantikai dokumentumai általában BNF-ben vannak leírva.

A BNF-nek több bővítése és változata létezik és van használatban.

A jelölési rendszert John Backus hozta létre az ALGOL nyelvtanának leírására. Az első, 1959-ben, Párizsban megtartott "World Computer Congress"-on mutatta be Backus a rendszerét a "The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference" – a zürichi ACM-GAMM konferencián javasolt a nemzetközi algebrai nyelv szintaxisa és szemantikája – előadásában. A nemzetközi algebrai nyelv leírása később ALGOL 58 néven vált ismertté. Az ismertetett formális nyelv Emil Post produkciós rendszerén alapul. A generatív nyelvtanokat már matematikai módszerekkel többen is tanulmányozták, közöttük Noam Chomsky, aki ezeket a formális leírásokat a természetes nyelvekre is alkalmazta.

Peter Naur később egyszerűsítette Backus jelöléseit, minimalizálta a használt karakterek számát, ezért Donald Knuth javaslatára, a hozzájárulásáért a neve megjelent a jelölési mód elnevezésében.

A Backus–Naur Forma vagy BNF nyelvtanok nagyon hasonlóak a Pánini nyelvtani szabályaihoz, ezért erre a jelölésre gyakran Panini–Backus-forma néven is hivatkoznak.

Egy BNF leírás valójában leszármaztatási szabályok halmaza, amelyeket a következő formában írnak fel:

 ::=  

ahol <szimbólum> egy nemterminális elem, a ::= jelölés (olvasd: négypont-egyenlő) választja el a szimbólumot a leszármaztatási szabálytól, ami egy kifejezés. Ez a kifejezés tartalmazza a szimbólumok sorozatát és/vagy egymástól a függőleges vonallal ('|') elválasztott sorozatokat (a '|' jel a választást jelenti – olvasd: vagy). A szabály bal oldala valójában azt mutatja, mivel/mikkel helyettesíthető a jobb oldalon álló szimbólum. Az a szimbólum, amely soha sem bukkan fel szabály bal oldalán, az úgynevezett terminális.

A fentiek illusztrálására nézzük meg egy (egyszerűsített) postai cím BNF leírását (pl. 1234 Pusztakotkodács, Kossuth Lajos u. 1):

 ::=  ", "  ", "   ::=  " "  |  " "   ::=  ". "  |   ::=      ::= "utca" | "tér" | "körút" | "lépcső" | "u." | "krt."  ::=  "-"  |   ::= " " 

magyarra fordítva:

• ez a bizonyos postai cím tartalmaz egy név részt, amit egy vessző-szóköz választ el az irányítószám résztől, amit még egy vessző-szóköz követ, majd a cím a „tényleges” címrésszel zárul.
• a név rész: egy vezetéknévi részből áll, amit egy keresztnév követ, vagy – és ez egyben a BNF rekurzív lehetőségeit mutatja – egy személyi rész, amit ismét egy keresztnév követ. Ez a megoldás biztosítja, hogy több keresztnév is megjeleníthető legyen.
• a vezetéknévi rész vagy egy titulusból (Dr, id, özv, ifj stb.), az azt követő pontból és egy vezetéknévből, vagy csak egy vezetéknévből állhat össze.
• a cím részt kerület, közterület neve, közterület típusa és házszám alkotja.
• a közterület típus egy egyszerű felsorolás, a lehetséges értékeket határozza meg. Ebben a példában ez lehet utca, vagy annak rövidítése, u. vagy tér, vagy körút, vagy ennek rövidítése krt., vagy lépcső.
• az irányítószám rész vagy egy országkód, amit kötőjel (-) követ és egy irányítószám és városnév, vagy csak egy irányítószám és városnév lehet.
• az irányítószám és a városnév egymástól egy szóközzel van elválasztva.

Meg kell jegyezni, hogy a fenti leírás nem teljes, hiszen nincsen pontosan definiálva, hogy mit is kell például ország_kód vagy akár irányítószám alatt érteni (annak ellenére, hogy tudjuk, mi is az irányítószám – esetünkben ez elég is). Egy programozási nyelv leírásakor viszont pontosan le kell írni mindent, ezért gyakran úgy kezdődnek a leírások, hogy megadják, mit kell betű alatt érteni, és mit kell szám alatt érteni, mik a fenntartott karakterek (ha vannak), szavak, stb., és csak ezután kezdődik a nyelv szintaxisának leírása.

A BNF szintaxis leírható a BNF saját jelölési módjával, a következők szerint:

 ::=  |    ::=  "<"  ">"  "::="     ::=  |  "|"   ::=  |     ::=  | "<"  ">"  ::= '"'  '"' | "'"  "'"  ::= " "  | ""  ::=   |    

Az "" az üres (azaz 0 karakterből álló) szöveg, tehát a 3. szabály azt jelenti, hogy az lehet üres is.

Megjegyzendő, hogy az eredeti BNF nem használt idézőjeleket.

Az megfelel a használt sorvégjelző karakternek (az ASCII kódban ez a kocsi-vissza és/vagy soremelés, de a konkrét megvalósítása operációs rendszertől függ).

A és a helyettesítendő az aktuális szabály nevével, címkéjével vagy leíró szövegével. Ezeket tovább lehetne bontani a felhasználható karakterek felsorolásával.

A BNF-nek több változata és kiterjesztése létezik, amelyeket vagy leírással kapcsolatos speciális igények, vagy pedig a további egyszerűsítésekre illetve hatékonyságra való törekvések hoztak létre. Közös ezekben a változatokban a reguláris kifejezések ismétlési műveleteinek, mint a * és a + használata. Az Extended Backus-Naur form (EBNF) a legismertebb ezek közül. A fenti példa sem felel meg pontosan az "ALGOL 60 report" jelölésmódjának. A [ ] zárójelek használata néhány évvel később, az IBM PL/I-es nyelvének meghatározásánál kezdődött, de azóta általánosan elfogadottá vált. Az ABNF a másik bővítés, amelyet az IETF használt protokollok leírására.

Parsing expression nyelvtanok is felépíthetők a BNF használatával, és a reguláris kifejezések jelölései is formalizálhatók, mint egy lehetséges osztálya a formális nyelvtanoknak. A BNF használata kevésbé jellemző az analitikus, mint a generatív nyelvtanok leírásánál.

Ma már számos BNF specifikáció található online, amelyek jól olvashatók és nem annyira formálisak. Ezeknél gyakran a következő szintaktikai szabályokat használják, bővítésként:

• Az opcionális elemeket szögletes zárójelek közé kell tenni, például [].
• A 0-szor vagy többször ismétlődő elemeket kapcsos zárójelek közé kell tenni, például  ::= { }.
• az 1-szer vagy többször ismétlődő elemeket plusz (+) követi.
• Egy elem ismétlődését az elem utáni csillag (*) karakterrel jelölik.
• Az alternatív lehetőségeket a | jelek választják el egymástól, például |.
• Ha az elemeket csoportba kell foglalni, akkor arra a normál zárójeleket használják.
• A terminális elemeket vastagon, a nemterminális elemeket normál szöveggel szedik.

• Reguláris kifejezés
• ANTLR

• Algol-60 BNF, az eredeti BNF.
• Példák nyelvtanokra: BNF Web club.
• [1] contains a posting on news:comp.compilers that explains some of the history of the two names (Backus-Naur form vs. Backus normal form).
• Article BNF and EBNF: What are they and how do they work? by Lars Marius Garshol.
• RFC 4234 Augmented BNF for Syntax Specifications: ABNF
• Comparision of different variants of BNF
• Syntax diagram of EBNF
• Generation of syntax diagrams from EBNF