Rozvinutá Backusova-Naurova forma

Faktická přesnost tohoto článku byla zpochybněna.

Podrobnější zdůvodnění najdete v diskusi. Neodstraňujte, prosíme, tuto zprávu, dokud nebudou pochybnosti vyřešeny.

---

Pro vkladatele šablony: Na diskusní stránce zdůvodněte vložení šablony.

Rozvinutá Backusova–Naurova forma (EBNF) je v informatice součástí rodiny metasyntaktických notací využívaných pro vyjádření bezkontextových gramatik používaných pro formální popis programovacích jazyků nebo jiných formálních jazyků. EBFN je rozšířením základní metasyntaktické notace Backus-Naurovy formy. EBNF vyvinul Niklaus Wirth, i když v dnešní době existuje mnoho dalších variací. Mezinárodní organizace pro normalizaci (ISO) přijala EBNF jako standard ISO/IEC 14977. V tomto článku je pro příklady používána EBNF ISO specifikace. Ostatní verze EBNF se mohou lišit v syntaktických konvencích.

Zápis pravidel

Formální jazyk nebo zdrojový kód počítačového programu se skládá z terminálů, což jsou tisknutelné znaky, čísla, interpunkční znaménka, bílé znaky (mezery tabelátory, konce řádků) atd.

EBNF definuje přepisovací pravidla, kde jsou sekvence symbolů přiřazeny neterminálům:

číslice-bez-nuly = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
číslice = "0" | číslice bez nuly ;

Ve výše uvedeného příkladu jsou zapsány dva řádky přepisovacích pravidel, které mají na levé straně uvedeny neterminály (číslice, číslice-bez-nuly). Na pravé straně jsou uvedeny různé varianty terminálních a neterminálních symbolů, které jsou vzájemně odděleny znakem svislá čára. Terminální symboly jsou uzavřeny do uvozovek, středník je ukončovacím symbolem. Definice tedy říká, že číslice může být 0 nebo neterminál číslice bez nuly, přičemž číslice bez nuly může obsahovat terminály 1, 2, 3 atd. až 9.

Přepisovací pravidla mohou též obsahovat sekvence terminálů a neterminálů oddělených čárkou:

dvanáct = "1" , "2" ;
dvě-stě-jedna = "2" , "0" , "1" ;
tři-sta-dvanáct = "3" , dvanáct ;
dvanáct-tisíc-dvě-stě-jedna = dvanáct , dvě-stě-jedna ;

Výraz, který může být vynechán nebo opakován je uzavírán do složených závorek { ... }:

přirozené číslo = číslice bez nuly , { číslice } ;

V tomto případě jsou řetězce 1, 2,... 10,... 12345,... správným výrazem. Ve výsledku může být vše, co je uvedeno ve složených závorkách, libovolně opakováno nebo to tam nemusí být vůbec.

V hranatých závorkách [ ... ] jsou uvedeny možnosti, které mohou být použity pouze jednou nebo vůbec:

celé číslo = "0" | [ "-" ] , přirozené číslo ;

Podle tohoto pravidla může být celé číslo nula (0) nebo přirozené číslo, před kterým může být znaménko mínus.

EBNF mimo jiné definuje syntaxi pro popis určitého počtu opakování, vynechání určitých částí nebo vložení komentářů do EBNF gramatiky.

Rozšířená BNF

Backusova-Naurova forma neumožňuje vyjádřit volitelné a opakující se výrazy. Místo toho je nutné využít mezipravidlo nebo alternativní definici pro vynechání či volitelnou existenci prvku, případně rekurzivně pro opakování. Tyto konstrukce je možné využít i v EBNF.

Volitelná část v EBFN:

číslo-se-znaménkem = [ znaménko ] , celé-číslo ;

v BNF vypadá definice takto:

<číslo-se-znaménkem> ::= <znaménko> <celé-číslo> | <celé-číslo> ;

nebo

<číslo-se-znaménkem> ::= <nepovinné znaménko> <číslo> ;
<nepovinné-znaménko> ::= ε | <znaménko> ; (* epsilon ("ε") se využívá pro vyjádření prázdných pravidel *)

Opakování v EBFN:

číslo = { číslice } ;

v BNF vypadá definice takto:

<číslo> ::= ε | <číslo> <číslice> ;

Poznámka: EBNF (ISO) využívá pro zřetězení čárku ','. BNF takovou možnost nemá.

Další dodatky a úpravy

EBNF odstraňuje některé další vady BNF:

• BNF využívá symboly (<, >, |, ::=). Pokud jsou obsaženy v jazyce bez dalších úprav a vysvětlení, BNF je nedokáže využít.
• Syntaxe BNF může mít pravidla zapsána pouze na jednom řádku.

EBNF řeší následující problémy:

• Terminální symboly musí být uzavřeny do uvozovek ("..." nebo '...'). Špičaté závorky ("<...>") mohou být pro terminály a neterminály vynechány.
• Ukončovací znak, středník, značí konec pravidla.

Kromě toho existují mechanismy pro vylepšení, definice počtu opakování, vynechání kromě některých možností (např. všechny znaky, kromě uvozovek), komentáře, atd.

I přes všechna tato vylepšení není EBNF silnější, než BNF a to ve smyslu toho, jak jazyk definovat. De fakto lze říci, že všechny formální gramatiky, které lze definovat v EBNF, mohou být vytvořeny i v BNF. Nicméně to ve výsledku vede k mnohem obsáhlejšímu množství definičních pravidel.

EBNF je standardizována ISO pod označením ISO/IEC 14977:1996(E).

Za určitých okolností je jakákoliv rozšířená BNF jen EBNF. Například W3C využívá one EBNF pro specifikování XML.

Další příklad

Programovací jazyky podobné Pascalu umožňují pouze přiřazení, která jsou v EBNF definována následovně:

(* jednoduchý program v EBNF − Wikipedia *)
program = 'PROGRAM' , mezera , identifikátor , mezera ,
           'BEGIN' , mezera ,
           { přiřazení , ";" , mezera } ,
           'END.' ;
identifikátor = znak-abecedy , { znak-abecedy | číslice } ;
číslo = [ "-" ] , číslice , { číslice } ;
řetězec = '"' , { všechny-znaky − '"' } , '"' ;
přiřazení = identifikátor , ":=" , ( číslo | identifikátor | řetězec ) ;
znak-abecedy = "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" ;
číslice = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
mezera = ? znak prázdného místa ? ;
všechny-znaky = ? všechny tisknutelné znaky ? ;

Syntakticky správný program vypadá následovně:

PROGRAM DEMO1
BEGIN
  A0:=3;
  B:=45;
  H:=-100023;
  C:=A;
  D123:=B34A;
  BABOON:=GIRAFFE;
  TEXT:="Hello world!";
END.

Jazyk může byt jednoduše rozšířen o řídicí struktury, aritmetické výrazy a instrukce pro vstup/výstup.

Následující znaky jsou navrženy jako standard klasické prezentace:

Usage	Notation
definice	=
zřetězení	,
ukončení	;
oddělení	|
nepovinné	[ ... ]
opakování	{ ... }
seskupení	( ... )
dvojité uvozovky	" ... "
jednoduché uvozovky	' ... '
komentář	(* ... *)
speciální část	? ... ?
výjimka	-

Konvence

1. Využívají se následující konvence:

• Každý meta-identifikátor rozšířeného BNF je zapsán jako jedno nebo více slov spojených dohromady pomlčkou;
• Meta-identifikátor je ukončen “-symbol”, což je název ukončujícího symbolu v BNF.

2. Znaky reprezentující jednotlivé operátory rozšířené BNF a jejich pořadí (svrchu):

* pro opakování
- pro vynechání
, pro zřetězení
| pro oddělení jednotlivých definic
= pro přiřazení definice
; pro ukončení

3. Toto pořadí může být změněno pomocí následujících závorek:

'  první-uvozovka                         první-uvozovka  '
"  druhá-uvozovka                         druhá-uvozovka  "
(* začátek-komentáře                     konec-komentáře *)
(  začátek-skupiny                         konec-skupiny  )
[  začátek-nepovinné části         konec-nepovinné-části  ]
{  začátek-opakující-se-části   konec-opakující-se-části  }
?  speciální-část                         speciální-část  ?

První-uvozovka je apostrof, tak jak je definován v ISO / IEC 646:1991, tedy Unicode 0x0027 ('), ale písmo využité v ISO / IEC 14977:1996 (E) ho vykresluje velmi podobně znaku Unicode 0x00B4 ('), takže může dojít k nedorozumění. Nicméně, ISO rozšířeného BNF standardu ho definuje jako ISO / IEC 646:1991, "ISO 7-bit kódované znakové sady pro výměnu informací", jako referenci a nezmiňuje žádné jiné znakové sady, aby zde nedošlo k nedorozumění se znaky s Unicode mimo 7-bit ASCII.

Příklad, následující syntaktická pravidla ukazují možnosti pro vyjádření opakování:

aa = "A";
bb = 3 * aa, "B";
cc = 3 * [aa], "C";
dd = {aa}, "D";
ee = aa, {aa}, "E";
ff = 3 * aa, 3 * [aa], "F";
gg = {3 * aa}, "G";

Terminální řetězce jsou definovány následujícími pravidly:

aa: A
bb: AAAB
cc: C AC AAC AAAC
dd: D AD AAD AAAD AAAAD atd.
ee: AE AAE AAAE AAAAE AAAAAE atd.
ff: AAAF AAAAF AAAAAF AAAAAAF
gg: G AAAG AAAAAAG atd.

EBNF rozšířitelnost

Na základě ISO 14977 standardu EBNF je možnost rozšířitelnosti, pomocí dvou prostředků. První je část gramatiky EBNF, speciální sekvence, která může obsahovat libovolný text ohraničený otazníky. Interpretace tohoto textu je nad rámec standardního EBNF. Například mezera by mohla být definována jako následující pravidlo:

mezera = ? US-ASCII character 32 ?;

Druhým prostředkem je skutečnost, že závorky nemohou být umístěny přímo za identifikátory (musí být zřetězeny). Zde je ukázka validní EBNF:

neco = foo, ( bar );

Následující není validní EBNF:

neco = foo ( bar );

Proto by rozšíření EBNF měli využívat notace. Například v gramatice jazyku List by 'function application' definuje následující pravidlo:

function application = list( symbol , { expression } );

Literatura

• Niklaus Wirth: What can we do about the unnecessary diversity of notation for syntactic definitions? CACM, Vol. 20, Issue 11, November 1977, pp. 822–823.
• Roger S. Scowen: Extended BNF — A generic base standard. Software Engineering Standards Symposium 1993.
• The International standard (ISO 14977) that defines the EBNF is now freely available as Zip-compressed PDF file.
• The W3C used a different EBNF to specify the XML syntax.
• The British Standards Institution published a standard for an EBNF: BS 6154 in 1981.
• The IETF uses Augmented BNF (ABNF), specified in RFC 5234.

Externí odkazy

• Článek "EBNF: A Notation to Describe Syntax (PDF)" by Richard E. Pattis describing the functions and syntax of EBNF
• Článek "BNF and EBNF: What are they and how do they work?" by Lars Marius Garshol
• Článek "The Naming of Parts" by John E. Simpson
• ISO/IEC 14977 : 1996(E)
• RFC 4234 – Augmented BNF for Syntax Specifications: ABNF
• BNF/EBNF variants – a table by Pete Jinks comparing several syntaxes.
• Create syntax diagrams from EBNF
• EBNF Parser & Renderer

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