Rozšířená forma Backus - Naura

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. února 2015; kontroly vyžadují 12 úprav .

Extended Backus – Naur Form ( EBNF ) je formální systém definice syntaxe, ve kterém jsou některé syntaktické kategorie postupně definovány prostřednictvím jiných . Používá se k popisu bezkontextových formálních gramatik . Navrhl Niklaus Wirth . Jedná se o rozšířené zpracování forem Backus-Naur , od BNF se liší „prostornějšími“ konstrukcemi, které při stejné vyjadřovací schopnosti umožňují zjednodušit a zmenšit objem popisu.

Používá se však mnoho různých variant RBNF. Mezinárodní organizace pro normalizaci přijala normu RBNF: ISO/IEC 14977 [1] .

Popis

Terminály a neterminály

Stejně jako v BNF je popis gramatiky v RBNF soubor pravidel definujících vztahy mezi koncovými symboly (terminály) a neterminálními symboly (neterminály).

Terminálové symboly jsou minimální gramatické prvky, které nemají vlastní gramatickou strukturu. V RBNF jsou koncové znaky buď předdefinované identifikátory (jména, která jsou považována za daná pro daný popis gramatiky), nebo řetězce, sekvence znaků uzavřené v uvozovkách nebo apostrofech.
Neterminální symboly jsou gramatické prvky, které mají své vlastní názvy a strukturu. Každý nekoncový symbol se skládá z jednoho nebo více koncových a/nebo nekoncových symbolů, jejichž kombinace je určena gramatickými pravidly. V RBNF má každý nekoncový symbol jméno, což je řetězec znaků.

Pravidla

Pravidlo v RBNF je:

идентификатор = выражение.

kde identifikátor je název nekoncového symbolu a výraz je kombinací koncových a nekoncových symbolů a speciálních znaků, která je v souladu s pravidly RBNF. Tečka na konci je speciální znak, který označuje konec pravidla.

Sémantika pravidla RBNF spočívá v tom, že nekoncový znak určený identifikátorem nalevo od rovnítka je kombinací koncových a neterminálních znaků definovaných výrazem .

Úplný popis gramatiky je sada pravidel, která postupně definují všechny neterminální symboly gramatiky, takže každý neterminální symbol může být redukován na kombinaci koncových symbolů postupnou (rekurzivní) aplikací pravidel. V definici RBNF nejsou žádná zvláštní pravidla týkající se pořadí, ve kterém jsou pravidla napsána, i když takové předpisy mohou být zavedeny při používání RBNF softwarovými nástroji, které poskytují automatické generování analyzátorů z popisu gramatiky.

Výrazy

Sada možných konstrukcí RBNF je velmi malá. Jedná se o zřetězení, výběr, podmíněný výskyt a opakování.

Zřetězení. Definováno symbolem "," (čárka). Formové pravidlo A = B,C.znamená, že neterminál A se skládá ze dvou znaků – B a C. Prvky zřetězení se také nazývají syntaktické faktory nebo jednoduše faktory. V tomto příkladu jsou B a C syntaktické faktory.
Výběr. Označeno svislým pruhem. Formové pravidlo A = B|C|D.znamená, že neterminál A se může skládat buď z B, nebo C nebo D. Prvky výběru se také nazývají syntaktické termíny nebo jednoduše termíny. V tomto příkladu jsou B, C, D syntaktické termíny.
Podmíněný vstup. Hranaté závorky označují volitelný prvek výrazu, který může nebo nemusí být přítomen. Pravidlo tvaru A = [B].znamená, že neterminál A je buď prázdný, nebo se skládá ze znaku B.
Opakování. Složené závorky označují zřetězení libovolného počtu (včetně nuly) prvků v něm zapsaných. Formové pravidlo A = {B}.znamená, že A je buď prázdné, nebo je zřetězením libovolného počtu znaků B (tj. A je buď prázdný prvek, nebo B, nebo BB, nebo BBB atd.). Pokud chcete, aby A bylo buď B, nebo libovolné číslo B, ale nemůže být prázdné, použijte zápisA = B{B}.
Kromě základních operací může RBNF používat běžné závorky. Používají se k seskupování prvků při vytváření složitých výrazů. Například pravidlo A = (B|C)(D|E). označuje, že A se skládá ze dvou znaků, z nichž první je buď B nebo C, druhý je buď D nebo E, to znamená, že A může být jedním z řetězců BD, BE, CD, CE.
neobvyklé! Někdy má také smysl použít negaci. Například A = (B|D)!C znamená, že A může být B nebo D, ale ne BC nebo DC. Tato volba nám umožňuje jasně odlišit A od G = (B|D)C a zjednodušit proces analýzy.
neobvyklé! Definice číslice obsahuje 10 znaků - od '0' do '9'. Je celkem logické popsat pojem „číslice“ výčtem Digit = '0' | '1' | '2' | ... | '9':. Můžete také definovat pojem „symbol“.

Nebo vše výše uvedené ve zkratce:

lexém "::=" jeho popis (nebo "=")
'…' - textový prvek - znak nebo skupina znaků
A, B - prvek A následovaný prvkem B (zřetězení)
A | B - buď prvek A nebo B (výběr)
[A] — prvek A je zahrnut nebo není zahrnut (podmíněný výskyt)
{A} – žádný nebo více prvků z A (opakování)
(AB) - seskupení prvků

Možnosti syntaxe

V některých pracích existují upravené varianty syntaxe RBNF.

V pravidlech můžete najít použití symbolu „ ::=“ místo „ “ (analogicky s BNF).=
Někdy se zřetězení ve výrazech neoznačuje jednoduchou sekvencí znaků za sebou, ale čárkou. V tomto případě by několik slov oddělených mezerami mělo být chápáno jako jeden víceslovný název nekoncového symbolu. Například:

Podmíněný příkaz = "IF" , logický výraz , "THEN" , skupina příkazů , { "ELSIF" , logický výraz , " THEN" , skupina příkazů }, [ "ELSE" , skupina příkazů ], " ENDIF "

— pravidlo, které specifikuje gramatiku podmíněného operátoru jazyka Modula-2 , kde „Podmíněný operátor“ a „Skupina operátorů“ jsou neterminální symboly se složenými názvy.

standard BSI. Standard EBNF, přijatý v roce 1981 British Standards Institution (BSI), se liší od verze navržené Wirthem v následujících ohledech:
- zřetězení je označeno čárkou;
- konec definice pravidla je označen středníkem;
- mezery v pravidle, jiné než ty, které jsou uvedeny v uvozovkách, jsou považovány za nedůležité.

Příklady konstrukcí

Formální sebeurčení RBNF

Obecná forma popisné gramatiky EBNF může být popsána jako EBNF takto:

Syntaxe = { SynthOperator }. SynthOperator = Identifikátor "=" SynthExpression "." . SyntExpression = SynTerm { "|" SinTerm }. SynTerm = SyntFactor { SyntFactor }. SynthFactor = identifikátor | řetěz | "(" SynthExpression ")" | "[" SynthExpression "]" | "{" SynthExpression "}" .

Tento popis předpokládá, že identifikátor a řetězec jsou předdefinované termíny. V případě potřeby není obtížné zapsat jejich definici do RBNF, k tomu stačí zadat určitou abecedu a v případě potřeby další omezení typu identifikátoru.

Číslo a identifikátor v RBNF

Následující gramatiky definují zápis obecného desetinného čísla (s počátečním znaménkem, případnou zlomkovou částí a exponentem) a typickým identifikátorem programovacího jazyka (posloupnost písmen, čísel a podtržítek začínající písmenem).

Číslo = [ "+" | "-" ] NatNumber [ "." [ NatNumber ]][( "e" | "E" )[ "+" | "-" ] NatNumber ]. NatNumber = číslice { číslice }. Číslice = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" . Ident = písmeno { písmeno | Číslice | "_" }.

Definice nekoncového Písmena zde není uvedena z důvodu samozřejmosti a těžkopádnosti - představuje výběr z uznávané abecedy.

RBNF a další způsoby popisu formálních gramatik

RBNF a BNF

Podobnosti a rozdíly mezi BNF a RBNF jsou zřejmé z popisu. Rozdíl je celkově ve dvou hlavních bodech:

V RBNF byla syntaxe pro psaní pravidel zjednodušena: definiční znak „ ::=“ byl nahrazen „ =“ a bylo zrušeno použití lomených závorek pro rozlišení neterminálů. V důsledku toho zmizela možnost pojmenovávat neterminály verbálními identifikátory, ale záznam se zkrátil. V modifikaci syntaxe RBNF, která označuje zřetězení s čárkou, lze použít víceslovné identifikátory.
RBNF zavádí dva nové syntaktické prvky: podmíněný výskyt (výraz v hranatých závorkách) a opakování (výraz ve složených závorkách).

Na úspěch či neúspěch první změny mohou být různé názory, ale v žádném případě to nemá vliv na výrazové možnosti formy. Ale druhá inovace je velmi významná. Nepřidává také zásadně nové vyjadřovací možnosti (vše, co je napsáno v RBNF, lze adekvátně zapsat v běžném BNF), ale výrazně snižuje a zjednodušuje zápis.

Hlavní výhodou RBNF oproti BNF je schopnost popsat jednoduché opakující se konstrukce neurčité délky (seznamy, řetězce, sekvence atd.) bez rekurzivních pravidel. Absence konstrukce opakování v BNF vede k tomu, že každé opakování musí být definováno zavedením dalších přechodných neterminálních symbolů a rekurzivních pravidel, což činí definici příliš velkou a nejasnou. Popis opakování v EBNF se ukazuje jako kratší a vhodnější pro lidské vnímání.

Jako příklad zvažte pravidla, která definují neterminální „seznam“, což je sada od nuly do libovolného počtu identifikátorů oddělených čárkami (za předpokladu, že znaky „Pravá závorka“, „Levá závorka“, „Čárka“ a „Ident “ jsou již definovány).

Definice v RBNF obsahuje pouze jedno pravidlo:

Seznam = Levá závorka [ Ident { Ident čárky } ] Pravá závorka .

Definice v BNF vypadá takto:

Již z tohoto příkladu jsou vidět rozdíly mezi formuláři:

V BNF jsou v pravidle, které definuje Seznam, dvě možnosti – pro prázdný seznam a pro jakýkoli jiný. V RBNF díky konstrukci podmíněného výskytu zmizela potřeba explicitního popisu těchto dvou možností.
V BNF bylo požadováno zavést umělé rekurzivní pravidlo IdentList k popisu sekvence identifikátorů oddělených čárkami. V RBNF je kvůli konstrukci opakování tento fragment syntaxe zapsán přímo v hlavním pravidle a v jednodušší podobě.
Protože existuje pouze jedno pravidlo RBNF, jeho délka je kratší a neobsahuje varianty a rekurzi, je mnohem snazší ho pochopit. Pro obnovení podoby seznamu podle uvedených popisů stačí v případě popisu RBNF postupně zapsat hodnoty symbolů a pro popis BNF budete muset určit pořadí v která pravidla jsou aplikována a sestavují seznamy pro každou možnost (a v každém pravidle jsou dvě).

Cenou za výhody RBNF oproti BNF je přirozeně větší složitost automatické interpretace popisů RBNF. Generátory formálního analyzátoru gramatiky, které používají BNF, jsou jednodušší než ty, které používají RBNF.

RBNF a syntaktické diagramy

RBNF jsou ekvivalentní podtřídě syntaktických diagramů, které se široce používají k popisu gramatik. Jakákoli gramatika RBNF může být adekvátně reprezentována syntaktickým diagramem, ale obecně vám syntaktické diagramy umožňují vytvářet popisy, které nemohou být reprezentovány v RBNF (nebo v žádném případě nemohou být přeloženy do RBNF přímo bez předchozí konverze grafického popisu) .

Aplikace, výhody a nevýhody RBNF

RBNF, stejně jako jeho předchůdce, BNF, je extrémně široce používán jako prostředek k popisu umělých jazyků, především programovacích jazyků a souvisejících notačních systémů. Zejména vynálezce RBNF, Niklaus Wirth, použil tento formalismus ve svých knihách k popisu všech programovacích jazyků, o kterých se tam uvažovalo.

Vyšší komplexnost RBNF ve srovnání s BNF vede k tomu, že existuje podstatně méně generátorů analyzátorů založených na RBNF než generátorů založených na BNF. Nicméně existují a platí. RBNF je základem pro Spirit C++ Parser Framework, Coco/R, The SLK Parser Generator a některé další. Pro použití v takových systémech je syntaxe RBNF rozšířena stejným směrem jako syntaxe BNF při použití generátorů yacc nebo bison parser - kód, který ji zpracovává, je přímo vložen do popisu gramatiky a interakce s lexikálním analyzátorem je nějak organizována . Na strukturu pravidel mohou být také uložena další omezení – ne všechna pravidla, která lze v RBNF popsat, lze efektivně převést na kód.

Mezi absolutní přednosti RBNF patří jednoduchost (samotný jazyk RBNF obsahuje pouze 10 speciálních znaků - tři typy závorek, svislá čára, rovnítko a uvozovky, případně čárka; jeho syntaxe je určena pěti pravidly), dostatečný výkon a viditelnost, díky čemuž je vhodný pro vytváření popisů určených nejen pro automatický výklad, ale i pro čtení člověkem. Blízkost konstrukcí RBNF k syntaktickým diagramům umožňuje čerpat je přímo z popisu RBNF.

Nevýhody RBNF, stejně jako BNF, zahrnují skutečnost, že popisují gramatickou strukturu formálního jazyka bez zohlednění kontextových závislostí, což znamená, že v přítomnosti takových závislostí se popis RBNF ukáže jako neúplný. , a některá pravidla syntaxe popisovaného jazyka musí být uvedena v normální textové formě. To vede k tomu, že text, který přesně odpovídá gramatice RBNF, může být stále syntakticky nesprávný. Například v gramatice RBNF není možné přirozeně vyjádřit skutečnost, že operace vyžaduje operandy stejného typu. Tyto kontroly musí být prováděny ručně psaným kódem gramatického analyzátoru. Na druhou stranu systémy popisu gramatiky, které zahrnují definici kontextových závislostí, například van Wiingaardenova gramatika , se ukazují být mnohem komplikovanější a jejich použití pro automatické generování parserů se ukazuje jako obtížné.

Poznámky

↑ ISO/ IEC 14977 . ISO / IEC (15. prosince 1996). Získáno 20. února 2015. Archivováno z originálu 11. března 2007.

Odkazy

ISO/IEC 14977 (anglicky) . Počítačová laboratoř . University of Cambridge (15. prosince 1996). Staženo: 20. února 2015.
Andrew Bushman. ISO/IEC 14977 (neoficiální překlad) . Lokalizace ISO/IEC 14977:1996(E) (Extended BNF) . Skupiny Google (21. července 2013). Staženo: 20. února 2015. (neurčitý)