Wikipedie

Rozvinutá Backusova–Naurova forma

Tento článek pojednává o EBNF. Možná hledáte: Rozšířená Backusova–Naurova forma (ABNF).

Rozvinutá Backusova–Naurova forma (anglicky Extended Backus–Naur Form), EBNF je v informatice rodina metasyntaktických notací využívaných pro zápis bezkontextových gramatik. EBNF se používá pro formální popis programovacích jazyků nebo jiných formálních jazyků. Různé formy EBFN jsou spíše modifikací než rozšířením Backusovy–Naurovy formy. EBNF navrhl Niklaus Wirth a později ji standardizovala Mezinárodní organizace pro normalizaci (ISO) jako standard ISO/IEC 14977.[1] Přestože je EBNF standardizovaná, existuje mnoho různých variací, které se mohou lišit v syntaktických konvencích. V příkladech v tomto článku je použita EBNF ISO specifikace.

Zápis pravidel

editovat

Slova formálního jazyka nebo zdrojový kód počítačového programu jsou tvořeny posloupností 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: 

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

Každý řádek definuje jedno přepisovací pravidlo. Na levé straně (před rovnítkem) je uveden neterminál (číslice, nenulová-číslice). 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 ukončuje pravidlo. Definice tedy říká, že číslice může být 0 nebo neterminál nenulová-číslice, přičemž nenulová-číslice může být libovolný terminál 1 nebo 2 nebo 3 nebo atd. nebo 9. V EBNF mohou být neterminály složené i z více slov (protože prvky posloupnosti se oddělují čarkami), takže místo nenulová-číslice lze psát nenulová číslice.

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, se uzavírá do složených závorek { ... }: 

přirozené číslo = nenulová číslice , { čí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 části, které mohou být použity pouze jednou nebo vůbec: 

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

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

EBNF také 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

editovat

Původní 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 EBNF: 

čí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 EBNF: 

čí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

editovat

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.[2]

Další příklad

editovat

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:

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

Vyjádření opakování

editovat

Následující syntaktická pravidla ukazují, jak lze v EBNF vyjádřit 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";

Těmito pravidly jsou generovány tyto terminální řetězce:

  • 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.

Konvence

editovat

1. EBNF používá následující konvence:

  • Každý meta-identifikátor EBNF se zapisuje jako jedno nebo několik slov spojených pomlčkami;
  • Meta-identifikátor zakončený „-symbol“, je název terminálního symbolu EBNF.

2. Operátory EBNF mají následující priority (od nejvyšší po nejnižší):

  • * pro opakování
  • - pro vynechání
  • , pro zřetězení
  • | pro oddělení jednotlivých definic
  • = pro definování neterminálu
  • ; konec pravidla
  • . konec pravidla

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

'  apostrof                                     apostrof  '
"  uvozovky                                     uvozovky  "
(* 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  ?

Apostrof definovaný v ASCII, tj. U+0027 ('), ale ve fontu použitém ve standardu ISO/IEC 14977:1996 (E) se velmi podobá znaku U+00B4 ('), takže může dojít k nedorozumění. Nicméně, ISO standard EBNF definuje ISO / IEC 646:1991, "ISO 7bitová kódovaná znaková sada pro výměnu informací" jako referenci a nezmiňuje žádné jiné znakové sady, takže by nemělo dojít k záměně s Unicode znaky mimo 7bitové ASCII.

Rozšiřitelnost EBNF

editovat

Standard ISO 14977 popisuje dva způsoby rozšiřování EBNF. Prvním, který je částí EBNF gramatiky, jsou speciální sekvence tvořené libovolným textem ohraničeným otazníky. Interpretace tohoto textu není ve standardním EBNF popsána. Například znak mezera lze definovat takto: 

mezera = ? US-ASCII character 32 ?;

Druhý způsob rozšiřování využívá skutečnosti, že za neterminály nemohou bezprostředně následovat závorky (musí být odděleny čárkou). Proto 

neco = foo ( bar );

není validní EBNF, ale je třeba psát: 

neco = foo, ( bar );

Rozšíření EBNF mohou využívat tuto notaci. Například aplikace funkce by v gramatice programovacího jazyka Lisp mohla být definována takto: 

aplikace funkce = seznam( symbol , { vyraz } );

Odkazy

editovat

Reference

editovat

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

  1. ↑ http://standards.iso.org/ittf/PubliclyAvailableStandards/s026153_ISO_IEC_14977_1996(E).zip ISO/IEC 14977
  2. ↑ Extensible Markup Language (XML) 1.0. Kapitola 6 Notation. www.w3.org [online]. [cit. 2024-06-05]. Dostupné online. (anglicky) 

Literatura

editovat

Související články

editovat

Externí odkazy

editovat
Citováno z „https://cs.wikipedia.org/w/index.php?title=Rozvinutá_Backusova–Naurova_forma&oldid=23978435“