Formular Backus extins - Naura

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 20 februarie 2015; verificările necesită 12 modificări .

Extended Backus – Naur Form ( EBNF ) este un sistem formal de definire a sintaxelor în care unele categorii sintactice sunt definite secvenţial prin altele . Folosit pentru a descrie gramatici formale fără context . Propus de Niklaus Wirth . Este o prelucrare extinsă a formelor Backus-Naur , se deosebește de BNF prin construcții mai „capabile”, care, cu aceeași capacitate expresivă, fac posibilă simplificarea și reducerea volumului descrierii.

Cu toate acestea, sunt utilizate multe variante diferite de RBNF. Organizația Internațională de Standardizare a adoptat standardul RBNF: ISO/IEC 14977 [1] .

Descriere

Terminale și non-terminale

Ca și în BNF, o descriere gramaticală în RBNF este un set de reguli care definesc relațiile dintre simbolurile terminale (terminale) și simbolurile non-terminale (non-terminale).

Simbolurile terminale sunt elemente gramaticale minime care nu au propria lor structură gramaticală. În RBNF, caracterele terminale sunt fie identificatori predefiniti (nume considerate a fi date pentru o anumită descriere gramaticală), fie șiruri de caractere, secvențe de caractere cuprinse între ghilimele sau apostrofe.
Simbolurile non-terminale sunt elemente gramaticale care au propriile nume și structură. Fiecare simbol non-terminal este format din unul sau mai multe simboluri terminale și/sau non-terminale, a căror combinație este determinată de regulile gramaticale. În RBNF, fiecare simbol non-terminal are un nume, care este un șir de caractere.

Reguli

Regula în RBNF este:

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

unde identificatorul este numele unui simbol non-terminal, iar expresia este o combinație de simboluri terminale și non-terminale și caractere speciale care respectă regulile RBNF. Punctul de la sfârșit este un caracter special care indică sfârșitul regulii.

Semantica regulii RBNF este că caracterul non-terminal specificat de identificatorul din stânga semnului egal este o combinație de caractere terminale și non-terminale definite de o expresie .

O descriere gramaticală completă este un set de reguli care definește secvențial toate simbolurile non-terminale ale gramaticii, astfel încât fiecare simbol non-terminal să poată fi redus la o combinație de simboluri terminale prin aplicarea succesivă (recursivă) a regulilor. Nu există reguli speciale în definiția RBNF cu privire la ordinea în care sunt scrise regulile, deși astfel de prescripții pot fi introduse atunci când se utilizează RBNF de către instrumente software care asigură generarea automată de parseri dintr-o descriere gramaticală.

Expresii

Setul de posibile construcții RBNF este foarte mic. Acestea sunt concatenarea, selecția, apariția condiționată și repetiția.

Concatenare. Definit de simbolul "," (virgulă). Regula de formă A = B,C.înseamnă că non-terminalul A este format din două caractere - B și C. Elementele de concatenare sunt numite și factori sintactici, sau pur și simplu factori. În acest exemplu, B și C sunt factori sintactici.
Alegere. Indicat de o bară verticală. Regula de formă A = B|C|D.înseamnă că neterminalul A poate consta fie din B, fie din C, fie din D. Elementele de alegere sunt numite și termeni sintactici sau pur și simplu termeni. În acest exemplu, B, C, D sunt termeni sintactici.
Intrare condiționată. Parantezele pătrate marchează un element opțional al expresiei, care poate fi prezent sau nu. Regula de formă A = [B].înseamnă că non-terminalul A este fie gol, fie este format din caracterul B.
Repetiţie. Parantezele denotă concatenarea oricărui număr (inclusiv zero) de elemente scrise în el. Regula de formă A = {B}.înseamnă că A este fie gol, fie este o concatenare a oricărui număr de caractere B (adică A este fie un element gol, fie B, fie BB, fie BBB și așa mai departe). Dacă doriți ca A să fie fie B, fie un număr arbitrar B, dar nu poate fi gol, utilizați notațiaA = B{B}.
Pe lângă operațiunile de bază, RBNF poate folosi paranteze obișnuite. Sunt folosite pentru gruparea elementelor atunci când formează expresii complexe. De exemplu, regula A = (B|C)(D|E). denotă faptul că A este format din două caractere, primul dintre care este fie B sau C, al doilea este fie D, fie E, adică A poate fi unul dintre șirurile BD, BE, CD, CE.
nu este comun! De asemenea, uneori are sens să folosești negația. De exemplu, A = (B|D)!C înseamnă că A poate fi B sau D, dar nu BC sau DC. Această opțiune ne permite să distingem clar A de G = (B|D)C și să simplificăm procedura de analizare.
nu este comun! Definiția unei cifre include 10 caractere - de la „0” la „9”. Este destul de logic să descriem conceptul de „cifră” prin enumerare Digit = '0' | '1' | '2' | ... | '9':. De asemenea, puteți defini conceptul de „simbol”.

Sau toate cele de mai sus pe scurt:

lexemul "::=" descrierea acestuia (sau "=")
„…” - element text - caracter sau grup de caractere
A, B - elementul A urmat de elementul B (concatenare)
A | B - fie elementul A, fie B (alegere)
[A] — elementul A este inclus sau nu (apariție condiționată)
{A} - zero sau mai multe elemente ale lui A (se repetă)
(AB) - grupare de elemente

Opțiuni de sintaxă

Unele lucrări conțin variante modificate ale sintaxei RBNF.

Puteți găsi utilizarea simbolului „ ::=” în loc de „ =” în reguli (prin analogie cu BNF).
Uneori, concatenarea în expresii este indicată nu printr-o simplă succesiune de caractere una după alta, ci printr-o virgulă. În acest caz, mai multe cuvinte separate prin spații ar trebui să fie înțelese ca un nume cu mai multe cuvinte a unui simbol non-terminal. De exemplu:

Declarație condiționată = „IF” , expresie booleană , „THEN” , grup de instrucțiuni , { „ELSIF” , expresie booleană , „ THN ” , grup de instrucțiuni }, [ „ELSE” , grup de instrucțiuni ], „ ENDIF ”

— o regulă care specifică gramatica operatorului condiționat al limbajului Modula-2 , unde „Operatorul condiționat” și „Grupul de operatori” sunt simboluri non-terminale cu nume compuse.

Standardul BSI. Adoptat în 1981 de British Standards Institution (BSI), standardul EBNF diferă de versiunea propusă de Wirth în următoarele moduri:
- concatenarea este indicată prin virgulă;
- sfârșitul definiției regulii este indicat prin punct și virgulă;
- spațiile dintr-o regulă, altele decât cele cuprinse între ghilimele, sunt considerate neimportante.

Exemple de construcție

Autodeterminarea formală a RBNF

Forma generală a unei gramatici de descriere EBNF poate fi descrisă ca EBNF după cum urmează:

Sintaxă = { SynthOperator }. SynthOperator = Identificator "=" SynthExpression "." . SyntExpression = SynTerm { "|" SinTerm }. SynTerm = SyntFactor { SyntFactor }. SynthFactor = identificator | lanț | „(” SynthExpression „)” | „[” SynthExpression „]” | „{” SynthExpression „}” .

Această descriere presupune că identificatorul și șirul sunt termeni predefiniti. Dacă doriți, nu este dificil să scrieți definiția lor în RBNF, pentru aceasta trebuie doar să specificați un anumit alfabet și, dacă este necesar, restricții suplimentare privind tipul de identificator.

Numărul și identificatorul în RBNF

Următoarele gramatici definesc notația unui număr zecimal general (cu un semn de început, o posibilă parte fracțională și un exponent) și un identificator tipic de limbaj de programare (o secvență de litere, numere și litere de subliniere care încep cu o literă).

Număr = [ „+” | "-" ] NatNumber [ "." [ NatNumber ]][( "e" | "E" )[ "+" | "-" ] NatNumber ]. NatNumber = Cifră { Cifră }. Cifra = "0" | „1” | „2” | „3” | „4” | „5” | „6” | „7” | „8” | „9” . Ident = Letter { Letter | Cifra | „_” }.

Definiția literei non-terminale nu este dată aici din cauza evidenței și a greutății - reprezintă o alegere din alfabetul acceptat.

RBNF și alte moduri de descriere a gramaticilor formale

RBNF și BNF

Asemănările și diferențele dintre BNF și RBNF sunt evidente din descriere. Diferența constă, în general, în două puncte principale:

În RBNF, sintaxa pentru regulile de scriere a fost simplificată: semnul de definiție „ ::=” a fost înlocuit cu „ =”, iar utilizarea parantezelor unghiulare pentru a distinge non-terminale a fost eliminată. Ca urmare, posibilitatea de a numi non-terminale cu identificatori verbose a dispărut, dar înregistrarea a devenit mai scurtă. Într-o modificare a sintaxei RBNF care denotă concatenarea cu virgulă, pot fi utilizați identificatori cu mai multe cuvinte.
RBNF introduce două elemente sintactice noi: apariția condiționată (exprimarea între paranteze drepte) și repetiția (exprimarea între paranteze).

Pot exista opinii diferite despre succesul sau eșecul primei modificări, dar, în orice caz, nu afectează posibilitățile expresive ale formei. Dar a doua inovație este foarte semnificativă. De asemenea, nu adaugă posibilități expresive fundamental noi (tot ce este scris în RBNF poate fi scris în mod adecvat în BNF obișnuit), dar reduce și simplifică semnificativ notația.

Principalul avantaj al RBNF față de BNF este capacitatea de a descrie construcții simple repetate de lungime nedefinită (liste, șiruri, secvențe și așa mai departe) fără reguli recursive. Absența construcției repetiției în BNF duce la faptul că orice repetiție trebuie definită prin introducerea de simboluri intermediare non-terminale suplimentare și reguli recursive, ceea ce face definiția prea mare și obscură. Descrierea repetărilor în EBNF se dovedește a fi atât mai scurtă, cât și mai convenabilă pentru percepția umană.

Ca exemplu, luați în considerare regulile care definesc „lista” non-terminală, care este un set de la zero la orice număr de identificatori separați prin virgule (presupunând că caracterele „RightBracket”, „LeftBracket”, „Comma” și „Ident”. " sunt deja definite).

Definiția din RBNF include o singură regulă:

Listă = LeftBracket [ Ident { Comma Ident }] RightBracket .

Definiția din BNF arată astfel:

Deja din acest exemplu, diferențele dintre forme sunt vizibile:

În BNF, în regula care definește Lista, există două opțiuni - pentru o listă goală și pentru oricare alta. În RBNF, datorită construcției apariției condiționate, necesitatea unei descrieri explicite a celor două opțiuni a dispărut.
În BNF, a fost necesar să se introducă o regulă recursivă artificială IdentList pentru a descrie o secvență de identificatori separați prin virgule. În RBNF, datorită construcției repetiției, acest fragment de sintaxă este scris direct în regula principală, și într-o formă mai simplă.
Deoarece există o singură regulă RBNF, lungimea ei este mai mică și nu conține variante și recursivitate, este mult mai ușor de înțeles. Pentru a restabili forma listei în conformitate cu descrierile date, în cazul unei descrieri RBNF, este suficient să notați succesiv valorile simbolurilor, iar pentru o descriere BNF, va trebui să determinați ordinea în care sunt aplicate regulile și construiți liste pentru fiecare opțiune (și există două dintre ele în fiecare regulă).

Desigur, prețul pentru avantajele RBNF față de BNF este complexitatea mai mare a interpretării automate a descrierilor RBNF. Generatoarele formale de analiză gramaticală care folosesc BNF sunt mai simple decât cele care folosesc RBNF.

RBNF și diagrame de sintaxă

RBNF sunt echivalente cu o subclasă de diagrame de sintaxă care sunt utilizate pe scară largă pentru a descrie gramaticile. Orice gramatică RBNF poate fi reprezentată în mod adecvat printr-o diagramă de sintaxă, dar, în general, diagramele de sintaxă vă permit să creați descrieri care nu pot fi reprezentate în RBNF (sau, în orice caz, nu pot fi traduse direct în RBNF fără a converti mai întâi descrierea grafică) .

Aplicații, avantaje și dezavantaje ale RBNF

RBNF, ca și predecesorul său, BNF, este utilizat pe scară largă ca mijloc de descriere a limbajelor artificiale, în primul rând limbaje de programare și sisteme de notație aferente. În special, inventatorul RBNF, Niklaus Wirth, a folosit acest formalism în cărțile sale pentru a descrie toate limbajele de programare luate în considerare acolo.

Complexitatea mai mare a RBNF în comparație cu BNF duce la faptul că există semnificativ mai puține generatoare de analiză bazate pe RBNF decât cele bazate pe BNF. Cu toate acestea, ele există și se aplică. RBNF este baza pentru Spirit C++ Parser Framework, Coco/R, SLK Parser Generator și altele. Pentru utilizarea în astfel de sisteme, sintaxa RBNF este extinsă în aceeași direcție cu sintaxa BNF atunci când se utilizează generatoarele de analizatori yacc sau bison - codul care îl procesează este inserat direct în descrierea gramaticală, iar interacțiunea cu analizatorul lexical este cumva organizată. . Restricții suplimentare pot fi impuse și asupra structurii regulilor - nu toate regulile care pot fi descrise în RBNF pot fi convertite efectiv în cod.

Avantajele absolute ale RBNF includ simplitatea (limbajul RBNF în sine conține doar 10 caractere speciale - trei tipuri de paranteze, o bară verticală, un semn egal și ghilimele, eventual o virgulă; sintaxa sa este determinată de cinci reguli), putere suficientă și vizibilitate, ceea ce îl face convenabil pentru realizarea de descrieri destinate nu numai interpretării automate, ci și citirii umane. Apropierea construcțiilor RBNF de diagramele sintactice face posibilă extragerea acestora din urmă direct din descrierea RBNF.

Dezavantajele RBNF, ca, într-adevăr, ale BNF, includ faptul că ele descriu structura gramaticală a unui limbaj formal fără a ține cont de dependențe contextuale, ceea ce înseamnă că, în prezența unor astfel de dependențe, descrierea RBNF se dovedește a fi incompletă. , iar unele reguli de sintaxă ale limbajului descris trebuie enunțate în formă normală de text. Acest lucru duce la faptul că textul care se potrivește exact cu gramatica RBNF poate fi în continuare incorect din punct de vedere sintactic. De exemplu, într-o gramatică RBNF, nu este posibil să se reprezinte în mod natural faptul că o operație necesită operanzi de același tip. Asemenea verificări trebuie efectuate cu ajutorul unui cod de analizor gramatical scris de mână. Pe de altă parte, sistemele de descriere gramaticală care includ definirea dependențelor de context, de exemplu, gramatica lui van Wiingaarden , se dovedesc a fi mult mai complicate, iar utilizarea lor pentru generarea automată de analizatori se dovedește a fi dificilă.

Note

↑ ISO/ IEC 14977 . ISO / IEC (15 decembrie 1996). Consultat la 20 februarie 2015. Arhivat din original pe 11 martie 2007.

Link -uri

ISO/IEC 14977 (engleză) . Laboratorul de calculatoare . Universitatea din Cambridge (15 decembrie 1996). Preluat: 20 februarie 2015.
Andrew Bushman. ISO/IEC 14977 (traducere neoficială) . Localizare ISO/IEC 14977:1996(E) (BNF extins) . Grupuri Google (21 iulie 2013). Preluat: 20 februarie 2015. (nedefinit)