Forma Backus-Naur

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

BNF ( Backus-Naur Form sau Backus Normal Form ) este o metasintaxă , adică un formalism prin care este posibil să se descrie sintaxa limbajelor formale (prefixul meta are legătură cu natura circulară a acestei definiții). Este un instrument utilizat pe scară largă pentru a descrie într-un mod precis și fără echivoc sintaxa limbajelor de programare , a protocoalelor de rețea și așa mai departe, deși există și exemple de aplicații ale sale în contexte non-IT și chiar non-tehnologice în literatura de specialitate. BNF este utilizat în majoritatea textelor despre teoria limbajului de programare și în multe texte introductive despre limbaje specifice.

În termeni formali, BNF poate fi văzut ca un formalism pentru descrierea gramaticilor fără context . BNF a fost propus de John Backus în corpul definiției limbajului de programare ALGOL . Acronimul BNF a fost inițial conceput ca Backus Normal Form („formă normală a Backus”); la sugestia lui Donald Knuth , a fost recitită ulterior ca Forma Backus-Naur , în onoarea lui Peter Naur, un alt membru al comitetului ALGOL și pionier al limbajelor de programare (și mai ales al dezvoltării compilatorului ).

Introducere

O specificație BNF este un set de reguli de diferențiere, fiecare exprimată sub forma:

 < simbol > :: = __expresie__

sau în forma echivalentă:

 < simbol > → __expresie__

Cele două forme sunt absolut echivalente, dar a doua este greșită, deoarece nu face parte din BNF. Este o invenție a oricui a scris-o. Prima formă, care va fi utilizată în cele ce urmează, folosește caractere ASCII standard și este cea mai utilizată pentru a scrie gramatici care să fie utilizate de computere și citite în fișiere text. A doua formă este mai puțin utilizabilă în practică, dar este comună în texte și articole de informatică teoretică, deoarece exprimă mai bine operația de derivare a șirurilor unui limbaj datorită aplicării regulilor de derivare. În plus față de aceste două forme, pot fi găsite alte zeci de forme, important este să înțelegem că BNF este un metalimbaj formal și nu include alte simboluri cu excepția :: =. Alte limbi metalice care folosesc alte simboluri nu sunt BNF.

În regulile de derivare <simbol> (caracterele <și> sunt obligatorii) se numește un simbol non-terminal și __expression__ este alcătuit din una sau mai multe secvențe de simboluri terminale (descrise mai jos) sau simboluri non- terminale , identificabile deoarece sunt închis în <>; dacă secvențele sunt mai multe decât una, acestea sunt separate de bara verticală „|”. Regula exprimă faptul că non-terminalul din stânga regulii poate fi înlocuit cu oricare dintre secvențele indicate în dreapta. De asemenea, într-o secvență, unele simboluri sau subsecvențe pot fi indicate ca opționale prin încadrarea lor între paranteze drepte.

Simbolurile care nu apar niciodată în stânga unei reguli de diferențiere se numesc terminale . Terminalele sunt într-un anumit sens punctul de sosire, deoarece reprezintă elemente care vor fi de fapt găsite într-un text scris conform regulilor sintactice pe care le descrie specificația BNF. Simbolurile non-terminale, pe de altă parte, sunt instrumente utilizate exclusiv de BNF și sunt închise în <>; ele reprezintă elementele abstracte ale gramaticii.

Exemplu

Vrem să descriem într-un mod formal, precis și fără echivoc regulile de urmat pentru a scrie o adresă pe o scrisoare. Chiar și un „micro-limbaj” ca acesta necesită o specificație BNF destul de complexă, astfel încât exemplul a suferit unele simplificări. Acest prim exemplu conține doar simboluri non-terminale și specificația sa BNF ar putea fi:

 < adresă poștală > :: = < destinatar > < adresă > < localitate >

< destinatar > :: = [ < titlu > ] [ < nume > | <Home>] <name> <head>

< adresa > :: = < stradă > < numărul casei > < retur de transport >

< localitate > :: = [ < cod poștal > ] < municipalitate > < provincie >

Acest fragment de specificație poate fi tradus în italiană după cum urmează:

o adresă poștală include un destinatar, urmată de o adresă, urmată de un nume de loc;
destinatarul include cu siguranță un nume de familie, care poate fi precedat, în ordine, de un titlu (cum ar fi domnul sau dr. etc.) și un nume sau o inițială;
adresa include în mod necesar o indicație a străzii (sau a pieței, a bulevardului etc.) și a numărului casei;
indicația localității include un cod poștal opțional, urmat de numele municipalității și al provinciei.

Cea mai intuitivă interpretare a BNF este probabil cea generativă: înlocuiți <adresa poștală> non-terminală principală cu secvența indicată în dreapta și apoi repetați procedura, înlocuind treptat fiecare non-terminal cu o secvență dată de o regulă de derivare pentru acel non-terminal.

Ca exemplu:

 < adresa poștală >
(aplicarea regulii 1 devine) 
 < destinatar > < adresă > < localitate >
(aplicarea regulii 2 devine) 
 [ < title > ] [ < nume > | <Home>] <name> <head> <address> <location>
(aplicarea regulii 3 devine) 
 [ < title > ] [ < nume > | < inițială > ] < prenume > < întoarcere > < stradă > < număr casă > < întoarcere > < localitate >

etc. Procedura se încheie atunci când textul este compus doar din terminale și, prin urmare, reprezintă o adresă poștală corectă din punct de vedere sintactic . Pentru a afișa o regulă care include terminale, luați în considerare exemplul codului poștal:

 < Cod poștal > :: = < cifră > < cifră > < cifră > < cifră > < cifră >

< cifră > :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Acest fragment spune că un cod poștal este format din cinci cifre și că cifrele sunt „0”, „1”, „2”, „3”, „4”, „5”, „6”, „7”, „8”, „9”. Parantezele unghiulare "<" și ">" nu apar în regula de derivare cu cifră ; de fapt, simbolurile din dreapta sunt terminale, adică reprezintă simbolurile concrete care trebuie să apară în textul final al unei adrese.

O specificație ca cea de mai sus (odată completată) poate fi utilizată pentru a determina dacă o adresă poștală este corectă din punct de vedere sintactic. De fapt, un text este corect din punct de vedere sintactic în ceea ce privește sintaxa descrisă de un set de reguli BNF dacă poate fi obținut pornind de la non-terminalul principal prin aplicarea în mod repetat a regulilor de substituție de un număr finit de ori.

Specificația de sintaxă a unui limbaj de programare are de obicei un <program> nonterminal principal și un set de reguli de derivare care descriu modul în care un program este structurat în module, module în instrucțiuni, instrucțiuni în expresii și așa mai departe. Un text scris de un programator poate fi considerat corect din punct de vedere sintactic și, prin urmare, de fapt un program în limba în cauză, dacă este posibil să-l derivăm prin substituții succesive începând de la <program> nonterminal. Acest tip de verificare, având în vedere textul care trebuie verificat și un anumit BNF, se pretează a fi efectuat automat. O verificare de acest tip este de fapt o parte importantă a funcționării compilatoarelor .

Poate fi interesant de observat că folosind BNF este posibil să se descrie sintaxa BNF în sine.

Variante

Multe variante și extensii ale BNF au fost propuse în literatura de specialitate. De fapt, unele structuri din exemplul de mai sus nu au fost intenționate de BNF original, ci au fost introduse ulterior de proiectanții IBM pentru a descrie sintaxa limbajului PL / 1 . De fapt, definiția inițială a BNF nu prevedea utilizarea mai multor secvențe alternative de simboluri separate prin caracterul | și nici utilizarea parantezelor pătrate pentru a identifica simbolurile opționale. Pentru a reprezenta aceste situații a fost, prin urmare, necesar să se definească reguli de producție diferite pentru același simbol non-terminal din stânga, una pentru fiecare dintre posibilele secvențe. Cu toate acestea, aceste extensii, al căror scop este de a avea o reprezentare mai clară și mai compactă a gramaticii, sunt acum universal recunoscute ca parte integrantă a BNF. pentru a realiza avantajul considerabil al codului și clarității, care se obține folosind aceste constructe, observăm că una dintre regulile de producție văzute mai sus:

 < destinatar > :: = [ < titlu > ] [ < nume > | <Home>] <name> <head>

fără constructele [] și | ar necesita 6 reguli de producție:

 < destinatar > :: = < nume de familie > < returnare >
< destinatar > :: = < nume > < prenume > < returnare >
<Destinatar> :: = <start> <nume> <head>
< destinatar > :: = < titlu > < prenume > < returnare >
<Destinatar> :: = <titlu> <nume> <nume> <cap>
<Destinatar> :: = <titlu> <Acces> <nume> <cap>

În schimb, variantele reale sau extensiile introduc modificări mai substanțiale, cum ar fi metacaractere tipice ale expresiilor regulate . Câteva exemple sunt EBNF (forma Backus-Naur extinsă) și ABNF (forma Augmented Backus-Naur), care include, printre aplicațiile sale tipice, descrierea protocoalelor IETF .

Elemente conexe

Alte proiecte

linkuri externe

Adus de la „https://it.wikipedia.org/w/index.php?title=Backus-Naur_Form&oldid=115741721 ”