Rozvinutá Backusova–Naurova forma
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.
- ↑ http://standards.iso.org/ittf/PubliclyAvailableStandards/s026153_ISO_IEC_14977_1996(E).zip ISO/IEC 14977
- ↑ – one EBNF. www.w3c.org [online]. [cit. 2010-05-06]. Dostupné v archivu pořízeném dne 2003-12-03.
Literatura editovat
- 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.
Související články editovat
Externí odkazy editovat
Obrázky, zvuky či videa k tématu Rozvinutá Backusova-Naurova forma na Wikimedia Commons
- EBNF: A Notation to Describe Syntax (PDF) autor Richard E. Pattis popisuje funkce a syntaxi EBNF
- BNF and EBNF: What are they and how do they work? autor Lars Marius Garshol
- The Naming of Parts autor John E. Simpson
- ISO/IEC 14977 : 1996(E)
- RFC 4234 – Augmented BNF for Syntax Specifications: ABNF
- BNF/EBNF variants autor Pete Jinks srovnává několik syntaxí.
- Create syntax diagrams from EBNF
- EBNF Parser & Renderer[nedostupný zdroj]