Kiterjesztett Backus Forma - Naura

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2015. február 20-án áttekintett verziótól ; az ellenőrzések 12 szerkesztést igényelnek .

Az Extended Backus – Naur Form ( EBNF ) egy formális szintaktikai definíciós rendszer, amelyben egyes szintaktikai kategóriák szekvenciálisan vannak meghatározva másokon keresztül . Kontextusmentes formális nyelvtan leírására szolgál . Javasolta : Niklaus Wirth . Ez a Backus-Naur formák kiterjesztett feldolgozása , a BNF-től "terjedtebb" konstrukciókban különbözik, amelyek ugyanazzal a kifejezőképességgel teszik lehetővé a leírás egyszerűsítését és mennyiségi csökkentését.

Az RBNF számos változatát azonban használják. A Nemzetközi Szabványügyi Szervezet elfogadta az RBNF szabványt: ISO/IEC 14977 [1] .

Leírás

Terminálok és nem terminálok

A BNF-hez hasonlóan a nyelvtani leírás az RBNF-ben is a terminális szimbólumok (terminálok) és a nem terminális szimbólumok (nem terminálok) közötti kapcsolatokat meghatározó szabályok halmaza.

A terminálszimbólumok minimális nyelvtani elemek, amelyeknek nincs saját nyelvtani szerkezetük. Az RBNF-ben a terminálkarakterek vagy előre meghatározott azonosítók (egy adott nyelvtani leíráshoz megadott nevek), vagy karakterláncok, idézőjelekbe vagy aposztrófokba zárt karaktersorozatok.
A nem terminális szimbólumok nyelvtani elemek, amelyeknek saját neve és szerkezete van. Minden nem terminális szimbólum egy vagy több terminális és/vagy nem terminális szimbólumból áll, amelyek kombinációját a nyelvtani szabályok határozzák meg. Az RBNF-ben minden nem terminális szimbólumnak van neve, amely egy karaktersorozat.

Szabályok

Az RBNF szabálya a következő:

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

ahol az azonosító egy nem terminális szimbólum neve, a kifejezés pedig terminális és nem terminális szimbólumok és speciális karakterek kombinációja, amely megfelel az RBNF szabályoknak. A végén lévő pont egy speciális karakter, amely a szabály végét jelzi.

Az RBNF szabály szemantikája az, hogy az egyenlőségjeltől balra lévő azonosító által megadott nem terminális karakter terminális és nem terminális karakterek kombinációja, amelyeket egy kifejezés határoz meg.

A teljes nyelvtani leírás olyan szabálykészlet, amely szekvenciálisan határozza meg a nyelvtan összes nem terminális szimbólumát, így minden nem terminális szimbólum terminális szimbólumok kombinációjára redukálható a szabályok egymást követő (rekurzív) alkalmazásával. Az RBNF definíciójában nincsenek speciális szabályok a szabályok írási sorrendjére vonatkozóan, bár az RBNF használatakor ilyen előírásokat bevezethetnek olyan szoftvereszközök, amelyek az elemzők automatikus generálását biztosítják a nyelvtani leírásból.

Kifejezések

A lehetséges RBNF konstrukciók halmaza nagyon kicsi. Ezek az összefűzés, a kiválasztás, a feltételes előfordulás és az ismétlés.

Összefűzés. A "," (vessző) szimbólum határozza meg. Az űrlapszabály A = B,C.azt jelenti, hogy a nem terminális A két karakterből áll - B-ből és C-ből. Az összefűzési elemeket szintaktikai tényezőknek vagy egyszerűen tényezőknek is nevezik. Ebben a példában B és C szintaktikai tényezők.
Választás. Függőleges sáv jelzi. Az A = B|C|D.űrlapszabály azt jelenti, hogy a nem terminális A állhat B-ből, C-ből vagy D-ből. A választási elemeket szintaktikai kifejezéseknek vagy egyszerűen kifejezéseknek is nevezik. Ebben a példában a B, C, D szintaktikai kifejezések.
Feltételes belépés. A szögletes zárójelek a kifejezés egy opcionális elemét jelölik, amely előfordulhat, de előfordulhat, hogy nincs. Az űrlapszabály A = [B].azt jelenti, hogy a nem terminál A vagy üres, vagy B karakterből áll.
Ismétlés. A göndör zárójelek a benne írt elemek tetszőleges számú (nullát is beleértve) összefűzését jelölik . Az űrlapszabály A = {B}.azt jelenti, hogy A vagy üres, vagy tetszőleges számú B karakter összefűzése (vagyis A vagy üres elem, vagy B, vagy BB, vagy BBB stb.). Ha azt szeretné, hogy A vagy B legyen, vagy tetszőleges B szám, de nem lehet üres, használja a jelöléstA = B{B}.
Az alapműveletek mellett az RBNF használhat szabályos zárójeleket is. Összetett kifejezések alkotásakor elemek csoportosítására szolgálnak. Például az A = (B|C)(D|E) szabály. azt jelöli, hogy A két karakterből áll, amelyek közül az első vagy B vagy C, a második pedig D vagy E, azaz A a BD, BE, CD, CE karakterláncok egyike lehet.
nem gyakori! Néha van értelme a tagadás használatának is. Például A = (B|D)!C azt jelenti, hogy A lehet B vagy D, de nem BC vagy DC. Ez az opció lehetővé teszi számunkra, hogy egyértelműen megkülönböztessük A-t a G = (B|D)C-től, és egyszerűsítsük az elemzési eljárást.
nem gyakori! A számjegy definíciója 10 karakterből áll – '0'-tól '9'-ig. Teljesen logikus, hogy a "számjegy" fogalmát felsorolással írjuk le Digit = '0' | '1' | '2' | ... | '9':. Meghatározhatja a "szimbólum" fogalmát is.

Vagy röviden a fentiek mindegyike:

lexéma "::=" a leírása (vagy "=")
„…” – szövegelem – karakter vagy karaktercsoport
A, B - A elem, majd B elem (összefűzés)
A | B – A vagy B elem (választható)
[A] – az A elem benne van vagy nincs benne (feltételes előfordulás)
{A} – A nulla vagy több eleme (ismétlődő)
(AB) - elemek csoportosítása

Szintaxis beállítások

Egyes művek az RBNF szintaxis módosított változatait tartalmazzák.

A szabályokban megtalálhatja a „ ” szimbólum használatát a „ ::=” helyett =(a BNF-hez hasonlóan).
Néha a kifejezésekben az összefűzést nem egy egyszerű karaktersorozat jelzi egymás után, hanem vessző. Ebben az esetben több szóközzel elválasztott szót egy nem terminális szimbólum egy többszavas neveként kell érteni. Például:

Feltételes utasítás = "IF" , logikai kifejezés , "THEN" , utasításcsoport , { "ELSIF" , logikai kifejezés , " THEN " , utasításcsoport }, [ " ELSE" , utasításcsoport ], " ENDIF "

— egy szabály, amely meghatározza a Modula-2 nyelv feltételes operátorának nyelvtanát , ahol a "Feltételes operátor" és az "Üzemeltetők csoportja" összetett nevekkel rendelkező, nem terminális szimbólumok.

BSI szabvány. A Brit Szabványügyi Intézet (BSI) által 1981-ben elfogadott EBNF szabvány a következő módokon különbözik a Wirth által javasolt változattól:
- az összefűzést vessző jelzi;
- a szabálydefiníció végét pontosvessző jelzi;
- a szabályban az idézőjelbe tett szóközök nem számítanak fontosnak.

Építési példák

Az RBNF formális önrendelkezése

Az EBNF-leíró nyelvtan általános formája a következőképpen írható le EBNF-ként:

Szintaxis = { SynthOperator }. SynthOperator = Azonosító "=" SynthExpression "." . SyntExpression = SynTerm { "|" SinTerm }. SynTerm = SyntFactor { SyntFactor }. SynthFactor = azonosító | lánc | "(" SynthExpression ")" | "[" SynthExpression "]" | "{" SynthExpression "}" .

Ez a leírás feltételezi, hogy az azonosító és a karakterlánc előre meghatározott kifejezések. Ha szükséges, nem nehéz megírni a definíciójukat az RBNF-ben, ehhez csak egy bizonyos ábécét kell megadni, és ha szükséges, további korlátozásokat kell megadni az azonosító típusára vonatkozóan.

Szám és azonosító az RBNF-ben

A következő nyelvtanok egy általános tizedes szám jelölését határozzák meg (vezető jellel, lehetséges törtrésszel és kitevővel) és egy tipikus programozási nyelv azonosítóját (betűvel kezdődő betűk, számok és aláhúzásjelek sorozata).

Szám = [ "+" | "-" ] NatNumber [ "." [ NatNumber ]][( "e" | "E" )[ "+" | "-" ] NatNumber ]. NatNumber = számjegy { számjegy }. Számjegy = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" . Ident = Letter { Letter | Számjegy | "_" }.

A nem terminális betű definícióját itt a nyilvánvalóság és a nehézkesség miatt nem adjuk meg - az elfogadott ábécé közül való választást jelenti.

RBNF és más formális nyelvtanok leírásának módjai

RBNF és BNF

A leírásból nyilvánvalóak a hasonlóságok és különbségek a BNF és az RBNF között. A különbség nagyjából két fő pontból áll:

Az RBNF-ben egyszerűsítették a szabályok írási szintaxisát: a „ ” definíciós jelet „ ::=”-re cserélték =, és megszűnt a szögletes zárójelek használata a nem terminálok megkülönböztetésére. Ennek eredményeként megszűnt a nem terminálok bőbeszédű azonosítókkal történő elnevezésének lehetősége, de a rekord rövidebb lett. Az RBNF szintaxis egy olyan módosításában, amely a vesszővel való összefűzést jelöli, többszavas azonosítók használhatók.
Az RBNF két új szintaktikai elemet vezet be: a feltételes előfordulást (a kifejezés szögletes zárójelben) és az ismétlést (a kifejezés szögletes zárójelben).

Az első változtatás sikerességéről vagy kudarcáról eltérő vélemények születhetnek, de mindenesetre ez nem befolyásolja a forma kifejező lehetőségeit. De a második újítás nagyon jelentős. Szintén nem ad hozzá alapvetően új kifejezési lehetőségeket (minden, ami RBNF-ben le van írva, megfelelően írható a közönséges BNF-ben), de jelentősen csökkenti és egyszerűsíti a jelölést.

Az RBNF fő előnye a BNF-fel szemben, hogy képes meghatározatlan hosszúságú egyszerű ismétlődő konstrukciókat (listák, karakterláncok, sorozatok stb.) leírni rekurzív szabályok nélkül. Az ismétlési konstrukció hiánya a BNF-ben ahhoz a tényhez vezet, hogy minden ismétlést további köztes, nem terminális szimbólumok és rekurzív szabályok bevezetésével kell meghatározni, ami túl nagy és homályossá teszi a definíciót. Az ismétlések leírása az EBNF-ben rövidebbnek és kényelmesebbnek bizonyul az emberi észlelés számára.

Példaként tekintsük a nem terminális "listát" meghatározó szabályokat, amelyek nullától tetszőleges számú azonosítóból állnak, vesszővel elválasztva (feltételezve, hogy a "RightBracket", "LeftBracket", "Comma" és "Ident" karakterek " már definiáltak).

Az RBNF definíciója csak egy szabályt tartalmaz:

Lista = LeftBracket [ Ident { Comma Ident }] RightBracket .

A BNF definíciója így néz ki:

Már ebből a példából is láthatóak az űrlapok közötti különbségek:

A BNF-ben a listát meghatározó szabályban két lehetőség van - üres listára és bármely másra. Az RBNF-ben a feltételes előfordulás konstrukciója miatt megszűnt a két lehetőség explicit leírásának igénye.
A BNF-ben szükség volt egy mesterséges rekurzív IdentList szabály bevezetésére, amely vesszővel elválasztott azonosítók sorozatát írja le. Az RBNF-ben az ismétlés felépítése miatt ez a szintaxistöredék közvetlenül a főszabályba van írva, és egyszerűbb formában.
Mivel csak egy RBNF-szabály létezik, ennek hossza rövidebb, és nem tartalmaz változatokat és rekurziót, így sokkal könnyebben érthető. A lista adott leírások szerinti formájának visszaállításához RBNF leírás esetén elegendő a szimbólumok értékeit egymás után felírni, a BNF leíráshoz pedig a sorrendet kell meghatározni a amelyekre a szabályok vonatkoznak, és készítsen listákat az egyes opciókhoz (és mindegyik szabályban kettő van).

Természetesen az RBNF BNF-fel szembeni előnyeinek ára az RBNF leírások automatikus értelmezésének bonyolultabbá tétele. A BNF-et használó formális nyelvtani elemző generátorok egyszerűbbek, mint az RBNF-et használók.

RBNF és szintaktikai diagramok

Az RBNF egyenértékű a szintaktikai diagramok alosztályával, amelyeket széles körben használnak a nyelvtan leírására. Bármely RBNF nyelvtan megfelelően ábrázolható szintaktikai diagrammal, de általában a szintaktikai diagramok lehetővé teszik olyan leírások létrehozását, amelyek nem ábrázolhatók RBNF-ben (vagy egyébként nem fordíthatók le közvetlenül RBNF-re a grafikus leírás előzetes konvertálása nélkül). .

Az RBNF alkalmazásai, előnyei és hátrányai

Az RBNF-t, akárcsak elődjét, a BNF-et, rendkívül széles körben használják mesterséges nyelvek, elsősorban programozási nyelvek és kapcsolódó jelölési rendszerek leírására. Különösen az RBNF feltalálója, Niklaus Wirth használta ezt a formalizmust könyveiben az összes ott tárgyalt programozási nyelv leírására.

Az RBNF nagyobb bonyolultsága a BNF-hez képest azt a tényt eredményezi, hogy lényegesen kevesebb az RBNF alapú elemző generátor, mint a BNF alapú. Ezek azonban léteznek és érvényesek. Az RBNF a Spirit C++ Parser Framework, a Coco/R, az SLK Parser Generator és néhány más alapja. Az ilyen rendszerekben való használathoz az RBNF szintaxist a BNF szintaxissal megegyező irányban kiterjesztik a yacc vagy bison értelmező generátorok használatakor - az azt feldolgozó kód közvetlenül bekerül a nyelvtani leírásba, és a lexikális elemzővel való interakció valamilyen módon meg van szervezve. . A szabályok szerkezetére további korlátozások is vonatkozhatnak – nem minden RBNF-ben leírható szabály konvertálható hatékonyan kóddá.

Az RBNF abszolút előnyei közé tartozik az egyszerűség (maga az RBNF nyelv mindössze 10 speciális karaktert tartalmaz - háromféle zárójelet, függőleges sávot, egyenlőségjelet és idézőjeleket, esetleg vesszőt; szintaxisát öt szabály határozza meg), elegendő teljesítmény, ill. láthatóság, ami kényelmessé teszi nemcsak automatikus értelmezésre, hanem emberi olvasásra is alkalmas leírások készítését. Az RBNF konstrukcióknak a szintaktikai diagramokhoz való közelsége lehetővé teszi, hogy az utóbbiakat közvetlenül az RBNF leírásából levonjuk.

Az RBNF – akárcsak a BNF – hátrányai közé tartozik, hogy a formális nyelv grammatikai szerkezetét a kontextuális függőségek figyelembevétele nélkül írják le, ami azt jelenti, hogy ilyen függőségek jelenlétében az RBNF leírása hiányosnak bizonyul. , és a leírt nyelv egyes szintaktikai szabályait normál szöveges formában kell megadni. Ez ahhoz a tényhez vezet, hogy az RBNF nyelvtannak pontosan megfelelő szöveg szintaktikailag továbbra is hibás lehet. Például egy RBNF nyelvtanban nem lehet természetesen ábrázolni azt a tényt, hogy egy művelethez azonos típusú operandusok szükségesek. Az ilyen ellenőrzéseket kézzel írt nyelvtani elemző kóddal kell elvégezni. Másrészt a kontextusfüggőségek meghatározását tartalmazó nyelvtani leíró rendszerek, például van Wiingaarden nyelvtana , sokkal bonyolultabbnak bizonyulnak, és az értelmezők automatikus generálására való felhasználásuk is bonyolultnak bizonyul.

Jegyzetek

↑ ISO/ IEC 14977 . ISO / IEC (1996. december 15.). Letöltve: 2015. február 20. Az eredetiből archiválva : 2007. március 11..

Linkek

ISO/IEC 14977 (angol) . Computer Laboratory . Cambridge -i Egyetem (1996. december 15.). Letöltve: 2015. február 20.
Andrew Bushman. ISO/IEC 14977 (nem hivatalos fordítás) . Az ISO/IEC 14977:1996(E) (kiterjesztett BNF) lokalizációja . Google Csoportok (2013. július 21.). Letöltve: 2015. február 20. (határozatlan)