BNF
La BNF (Backus-Naur form o Backus normal form) è una metasintassi, ovvero un linguaggio formale attraverso il quale è possibile descrivere la sintassi di linguaggi formali (il prefisso meta ha proprio a che vedere con la natura circolare o ricorsiva di questa definizione). Si tratta di uno strumento ideale per descrivere, in modo preciso e non ambiguo, la sintassi di linguaggi di programmazione, protocolli di rete, e così via; benché non manchino, in letteratura, esempi di sue applicazioni a contesti anche non informatici e addirittura non tecnologici.
Attraverso la BNF si può descrivere la sintassi di un qualunque linguaggio formale, a patto che tale sintassi corrisponda a quella che i teorici chiamano una grammatica context-free o grammatica libera dal contesto.
La BNF è molto utilizzata in informatica; la maggior parte dei programmatori, in particolare, ne conosce almeno le linee essenziali. Fu inventata da John Backus per documentare formalmente la sintassi del linguaggio Algol 60. Su suggerimento di Donald Knuth, l'acronimo fu in seguito riletto come Backus-Naur form in onore di Peter Naur, che insieme a Backus fu uno dei più grandi pionieri nella storia dei linguaggi di programmazione e dei compilatori.
Introduzione
Una specifica BNF è un insieme di regole di derivazione della forma
- <simbolo> ::= <espressione>
dove <simbolo> viene detto un simbolo nonterminale e <espressione> è costituita da una o più sequenze di simboli (terminali, vedi sotto, o nonterminali) separate dalla barra verticale '|'. La regola esprime il fatto che il nonterminale a sinistra della regola può essere sostituito da una qualsiasi delle sequenze indicate sulla destra (come chiariremo a breve). In una sequenza, alcuni simboli o sottosequenze possono essere indicati come opzionali racchiudendoli fra parentesi quadre.
I simboli che non appaiono mai a sinistra di una regola di derivazione sono detti terminali. I terminali sono in un certo senso il punto di arrivo, perché rappresentano elementi che si troveranno effettivamente in un testo scritto secondo le regole sintattiche che la specifica BNF descrive. I nonterminali, viceversa, sono strumenti utilizzati esclusivamente dalla BNF; si può dire che essi rappresentano gli elementi astratti della grammatica.
Esempio
Immaginiamo di voler descrivere in modo formale, preciso e non ambiguo le regole che bisognerebbe seguire quando si scrive un indirizzo su una lettera. In realtà anche un "micro-linguaggio" come questo richiede una specifica BNF piuttosto articolata, e quindi ne riporteremo qui solo uno stralcio, applicando anche qualche semplificazione. La specifica BNF potrebbe essere grosso modo come segue:
- <indirizzo postale> ::= <destinatario> <indirizzo> <località>
- <destinatario> ::= [<titolo>] [<nome>|<iniziale>] <cognome> <a capo>
- <indirizzo> ::= <via> <numero civico> <a capo>
- <località> ::= [<CAP>] <comune> <provincia>
Questo frammento di specifica può essere tradotto in italiano come segue:
- un indirizzo postale include un destinatario, seguito da un indirizzo, seguito da una indicazione di località;
- il destinatario comprende sicuramente un cognome, a cui si possono far precedere, nell'ordine, un titolo (come Sig. o Dott. ecc.) e un nome o una iniziale;
- l'indirizzo comprende necessariamente una indicazione di via (o piazza, viale, ecc.) e il numero civico;
- l'indicazione della località comprende un codice di avviamento postale opzionale, seguito dal nome del comune e dalla provincia.
L'interpretazione più intuitiva della BNF è probabilmente quella generativa. In sostanza, immaginiamo di sostituire il nonterminale principale <indirizzo postale> con la sequenza indicata sulla destra, e poi ripetere il procedimento sostituendo via via un nonterminale con una sequenza data da una regola di derivazione per quel nonterminale.
Per esempio:
- <indirizzo postale>
- (applicando la regola 1 diventa)
- <destinatario> <indirizzo> <località>
- (applicando la regola 2 diventa)
- [<titolo>] [<nome>|<iniziale>] <cognome> <a capo> <indirizzo> <località>
- (applicando la regola 3 diventa)
- [<titolo>] [<nome>|<iniziale>] <cognome> <a capo> <via> <numero civico> <a capo> <località>
eccetera. Il procedimento terminerà quando avremo un testo composto solo da terminali, che rappresenterà un indirizzo postale sintatticamente corretto. Per mostrare una regola che includa dei terminali, consideriamo l'esempio del CAP:
- <CAP> ::= <cifra><cifra><cifra><cifra><cifra>
- <cifra> ::= 0|1|2|3|4|5|6|7|8|9
Questo frammento dice che un CAP è composto da cinque cifre, e che le cifre sono '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' e '0'. Nella regola di derivazione per cifra non compaiono le parentesi angolari "<" e ">"; i simboli a destra, infatti, sono terminali, ovvero rappresentano proprio i simboli concreti che devono apparire nel testo finale di un indirizzo.
Una specifica come quella sopra (una volta completata) può essere utilizzata per stabilire se un indirizzo postale è sintatticamente corretto. Si dirà infatti che un testo è sintatticamente corretto rispetto alla sintassi descritta da un insieme di regole BNF, se può essere ricavato partendo dal nonterminale principale applicando ripetutamente le regole di sostituzione, un numero finito di volte.
La specifica della sintassi di un linguaggio di programmazione ha tipicamente un nonterminale principale <programma>, e un insieme di regole di derivazione che descrivono come un programma è strutturato in moduli, i moduli in istruzioni, le istruzioni in espressioni, e via dicendo. Un testo scritto da un programmatore si potrà considerare sintatticamente corretto (e quindi effettivamente un programma nel linguaggio in questione) se è possibile ricavarlo per sostituzioni successive a partire dal nonterminale <programma>. Questo tipo di verifica, dato il testo da verificare e una specifica BNF, si presta a essere eseguito in modo automatico. Una verifica di questo tipo rappresenta infatti una parte importante del funzionamento dei compilatori.
Può essere interessante notare che è possibile descrivere, usando la BNF, la sintassi della BNF stessa.
Varianti
Sono state proposte, in letteratura, molte varianti ed estensioni della BNF. In effetti, persino le parentesi quadre utilizzate nell'esempio riportato sopra non erano previste dalla BNF originale, ma sono state introdotte in seguito dai progettisti della IBM per descrivere la sintassi del linguaggio PL/1; si tratta comunque di un'estensione riconosciuta ormai universalmente. Vere e proprie varianti o estensioni introducono modifiche più sostanziali, come i metacaratteri tipici delle espressioni regolari. Alcuni esempi sono la EBNF (Extended Backus-Naur form) e la ABNF (Augmented Backus-Naur form), che conta, fra le sue applicazioni tipiche, la descrizione dei protocolli IETF.
Categoria:linguaggi formali