Backusova–Naurova forma

Backusova-Naurova forma (BNF) je metasyntaxe používaná k vyjádření bezkontextové gramatiky, která se používá pro popis formálních jazyků). John Backus a Peter Naur vytvořili bezkontextovou gramatiku, s jejíž pomocí definovali syntaxi programovacích jazyků využitím dvou typů pravidel: lexikálního a syntaktického.

BNF se často využívá k zápisu (notaci) gramatik počítačových programovacích jazyků, sad instrukcí a komunikačních protokolů, ale také jako notace zastupující části gramatik skutečných jazyků. Řada učebnic o teorii programovacích jazyků nebo sémantiky popisuje programovací jazyky pomocí BNF. Existuje řada rozšíření a jiných variant BNF.

Historie

John Backus vytvořil tuto notaci, aby vyjádřil gramatiku ALGOLu. Na prvním Světovém počítačovém kongresu konaném v Paříži v roce 1959 Backus přednesl příspěvek Syntaxe a sémantika navrhovaného mezinárodního algebraického jazyka z curyšské konference ACM-GAMM, v němž formálně popsal mezinárodní algebraický jazyk (IAL) později nazvaný ALGOL 58. Formální jazyk, který Backus představil, byl založen na produkčním systému Emila Posty. Generativní gramatiky se pak staly objektem intenzivních matematických studií, prováděných např. Noamem Chomskym, který je aplikoval na gramatiky skutečných jazyků.

Peter Naur označil Backusovu notaci za Backusovu normální formu (ALGOL 60, 1963) a zjednodušil ji, aby minimalizoval počet používaných znaků. Na návrh Donalda Knutha bylo Naurovo jméno přidáno do názvu jako uznání za jeho práci v oboru a nahradilo „N“ ve zkratce, neboť Knuth argumentoval tím, že BNF není v žádném případě normální. Backusova-Naurova forma, resp. gramatika BNF, je do značné míry podobná Paniniho pravidlům gramatiky, proto bývá někdy nazývána Paniniova-Backusova forma.

Úvod

BNF je sadou odvozených pravidel s následujícím zápisem:

<symbol> ::= <výraz se symboly>

kde symbol je neterminál a výraz se symboly sestává ze sekvence symbolů nebo sekvencí oddělených svislou čárou „|“, která indikuje možnost výběru. Celek představuje možnou náhradu za symbol vlevo. Symboly, které se na levé straně nikdy neobjeví, jsou terminály.

Příklad 1

Považujte následující řádky za příklad možné BNF pro americkou poštovní adresu:

<postal-address> ::= <name-part> <street-address> <zip-part>
<name-part> ::= <personal-part> <last-name> <opt-jr-part> <EOL> | <personal-part> <name-part> <EOL>
<personal-part> ::= <first-name> | <initial> "." 
<street-address> ::= <opt-apt-num> <house-num> <street-name> <EOL>
<zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>
<opt-jr-part> ::= "Sr." | "Jr." | <roman numeral>
<roman numeral> := "III" |  <five> | <tens>
<ones>  :: = "I"{1,3}
<five>   = "V"<ones>? | "IV"
<tens>   = X{1,3}<five>? | X{0,3}IX<five>

Přeloženo do češtiny:

Poštovní adresa se skládá z části Jméno, Adresa (ulice) a PSČ (Poštovní směrovací číslo).

• část Jméno se skládá z:
  • buď z Osobní části, po níž následuje příjmení a dále nepovinná tzv. Jr. část (obsahující zkratky typu Jr., Sr., nebo pořadové číslo v dynastii) a konec řádku
  • nebo z Osobní části následované částí Jméno (tato varianta ilustruje možnost rekurze v BNF, bude použita pro případy, kdy lidé používají mnohonásobná křestní nebo střední jména, resp. iniciály)
    • Osobní část se skládá buď z křestního jména, nebo z iniciály následované tečkou
• Adresa sestává z nepovinné části specifikující byt, následované číslem domu, jménem ulice a koncem řádku
• část PSČ se skládá z názvu města, následované čárkou, kódem státu a číslem, za nímž je opět konec řádku

Berme v úvahu, že řada položek by mohla být dále specifikována na levé straně (např. formát jména, PSČ apod.) pomocí dalších pravidel BNF.

Příklad 2

BNF sama o sobě se dá specifikovat pomocí pravidla BNF následujícím způsobem:

<syntax> ::= <rule> | <rule> <syntax>
<rule> ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""  
<expression> ::= <list> | <list> "|" <expression>
<line-end> ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list> ::= <term> | <term> <opt-whitespace> <list>
<term> ::= <literal> | "<" <rule-name> ">"
<literal> ::= '"' <text> '"' | "'" <text> "'"

V příkladu se předpokládá, že pro správnou interpretaci pravidla BNF nemusí toto pravidlo obsahovat žádné mezery. <EOL> představuje konec řádku (v ASCII návrat válce tiskárny, resp. nový řádek (line feed) v závislosti na operačním systému). <rule-name> a <text> lze nahradit za název a text deklarovaného pravidla.

Varianty

Existuje řada variant a rozšíření BNF, které vznikly z důvodu dosažení větší jednoduchosti nebo stručnosti, popřípadě za účelem adaptace BNF pro specifické účely. Jedním společným znakem řady variant BNF je použití opakovacích operátorů z regulárních výrazů, např. * a +.

Rozvinutá Backusova-Naurova forma (Extended Backus–Naur form, EBNF) je metasyntaktická notace používaná k vyjádření bezkontextové gramatiky. Původně byla vyvinuta Niklausem Wirthem, dnes je však většina proměnných EBNF standardizována a definována normami, zejm. ISO-14977 pod kódovým označením ISO/IEC 14977:1996(E).

Rozšířená Backusova-Naurova forma (Augmented Backus–Naur form, ABNF) vychází z BNF, má však svůj vlastní specifický syntax a pravidla odvozování. Základním principem tohoto meta-jazyka je popsat formální systém jazyka. ABNF je zanesen do RFC 4234 a je často používán jako definovací jazyk pro komunikační protokol IETF.

V tomto článku byl použit překlad textu z článku Backus-Naur form na anglické Wikipedii.