Backusova–Naurova forma

Backusova–Naurova forma (BNF) je způsob zápisu bezkontextových gramatik používaných pro popis formálních jazyků. BNF vytvořil John Backus pro popis syntaxe programovacího jazyka ALGOL a zdokonalil Peter Naur. BNF používá dva typy pravidel: lexikální a syntaktická.

BNF a její varianty EBNF (rozvinutá Backusova–Naurova forma) a ABNF (rozšířená Backusova–Naurova forma) se používají i k zápisu (notaci) instrukčních sad a komunikačních protokolů, ale také jako notace pro popis částí gramatik přirozených jazyků.

Historie

BNF vytvořil John Backus pro popis syntaxe jazyka ALGOL. 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 Posta. Generativní gramatiky se pak staly objektem intenzivních matematických studií, prováděných např. Noamem Chomskym, který je aplikoval na gramatiky přirozený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 do názvu přidáno Naurovo jméno 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 gramatickým pravidlům, proto bývá někdy nazývána Paniniova–Backusova forma.

Úvod

BNF je sadou odvozovacích pravidel tvaru

<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> ::= <ones> | <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.

Reference

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

Externí odkazy

• Obrázky, zvuky či videa k tématu Backusova-Naurova forma na Wikimedia Commons