Backus-Naur Form: differenze tra le versioni

m
nelle spiegazioni passaggio da discorso in prima persona a discorso impersonale ed eliminato metalinguaggio, incisi tra parentesi trasformati in incisi tra virgole, eliminate virgole inutile e ristrutturati alcuni periodi
m (Annullate le modifiche di 81.73.134.145 (discussione), riportata alla versione precedente di Fringio)
m (nelle spiegazioni passaggio da discorso in prima persona a discorso impersonale ed eliminato metalinguaggio, incisi tra parentesi trasformati in incisi tra virgole, eliminate virgole inutile e ristrutturati alcuni periodi)
La '''BNF''' ('''Backus-Naur Form''' o '''Backus Normal Form''') è una [[metasintassi]], ovvero un [[formalismo]] attraverso il qualecui è possibile descrivere la [[sintassi (informatica)|sintassi]] di [[linguaggi formali]] (il prefisso ''meta'' ha proprio a che vedere con la natura ''circolare'' di questa definizione). Si tratta di uno strumento molto usato per descrivere, in modo preciso e non ambiguo, la sintassi dei [[linguaggio di programmazione|linguaggi di programmazione]], dei [[protocollo di rete|protocolli di rete]] e così via, benché non manchino, in letteratura, esempi di sue applicazioni a contesti anche non informatici e addirittura non tecnologici. La BNF viene usata nella maggior parte dei testi sulla teoria dei linguaggi di programmazione (e in molti testi introduttivi su specifici linguaggi).
 
In termini formali, la BNF può essere vista come un formalismo per descrivere [[grammatica libera dal contesto|grammatiche libere dal contesto]].
:<nowiki><simbolo> → __espressione__</nowiki>
 
Le due forme sono assolutamente equivalenti. La prima forma, (che verrà utilizzata nel seguito), utilizza caratteri ASCII standard ed è quella più utilizzata per scrivere grammatiche che devono essere utilizzate dai calcolatori e lette in file di testo. La seconda forma è meno utilizzabile nella pratica, ma è comune nei testi e negli articoli di informatica teorica in quanto meglio esprime l'operazione di derivazione delle stringhe di un linguaggio a causa dell'applicazione delle regole di derivazione.
Nelle regole di derivazione <simbolo> (i caratteri < e > sono obbligatori) viene detto un '''simbolo nonterminale''' e __espressione__ è costituita da una o più sequenze di simboli '''terminali''' (vedidescritti sottopiù avanti) o nonterminali, (identificatiidentificabili dal fatto di essereperché racchiusi tra < >); se le sequenze sono più di una esse sono 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 chiarito nel seguito). Inoltre 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 simboli nonterminali, viceversa, sono strumenti utilizzati esclusivamente dalla BNF e sono racchiusi tra <>; si può dire che essi rappresentano gli ''elementi astratti'' della grammatica.
 
== Esempio ==
ImmaginiamoSi di volervuole descrivere in modo formale, preciso e non ambiguo le regole che bisognerebbeda seguire quandoper si scrivescrivere un indirizzo su una lettera. In realtà ancheAnche un "micro-linguaggio" come questo richiede una specifica BNF piuttosto articolata, e quindi ne riporteremo qui solo uno stralcio,l'esempio applicandoha anchesubito qualchealcune semplificazionesemplificazioni. In particolareQuesto cominciamo con unprimo esempio che contiene (per ora) solo simboli non terminali; e la sua specifica BNF potrebbe essere grosso modo come segue:
 
:<nowiki><indirizzo postale> ::= <destinatario> <indirizzo> <località></nowiki>
: 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:''. Insi sostanza, immaginiamo di sostituiresostituisce il nonterminale principale <indirizzo postale> con la sequenza indicata sulla destra, e poi ripeteresi ripete il procedimento sostituendo via via unciascun nonterminale con una sequenza data da una regola di derivazione per quel nonterminale.
 
Come esempio:
:<nowiki>[<titolo>] [<nome>|<iniziale>] <cognome> <a capo> <via> <numero civico> <a capo> <località></nowiki>
 
eccetera. Il procedimento termineràtermina quando avremoil untesto testoè composto solo da terminali, chee rappresenteràquindi rappresenta un indirizzo postale ''sintatticamente corretto''. Per mostrare una regola che includa dei terminali, consideriamosi consideri l'esempio del CAP:
 
:<nowiki><CAP> ::= <cifra><cifra><cifra><cifra><cifra></nowiki>
:<nowiki><cifra> ::= 0|1|2|3|4|5|6|7|8|9</nowiki>
 
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'. Nella regola di derivazione per ''cifra'' non compaiono le [[parentesi angolari]] "<" e ">"; infatti 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 cheInfatti 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àpuò considerare sintatticamente corretto, (e quindi effettivamente un [[Programma (informatica)|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 [[compilatore|compilatori]].
 
Può essere interessante notare che è possibile descrivere, usando la BNF, è possibile descrivere la sintassi della BNF stessa.
 
== Varianti ==
SonoIn letteratura sono state proposte, in letteratura, molte varianti ed estensioni della BNF. In effetti alcune strutture 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]]. Infatti nella definizione originale della BNF non era previsto né l'uso di più sequenze alternative di simboli separate dal carattere |, né l'uso delle parentesi quadre per identificare simboli opzionali. Per rappresentare queste situazioni era quindi necessario definire differenti regole di produzione per lo stesso simbolo nonterminale a sinistra, una per ciascuna delle sequenze possibili. Comunque queste estensioni, il cui scopo è quello di avere una rappresentazione più chiara e compatta della grammatica, sono riconosciute ormai universalmente come parte integrante della BNF. per rendersi conto del notevole vantaggio, di codice e di chiarezza, che si ottiene utilizzando questi costrutti notiamo che una delle regole di produzione viste sopra:
Per rappresentare queste situazioni era quindi necessario definire differenti regole di produzione per lo stesso simbolo nonterminale a sinistra, una per ciascuna delle sequenze possibili. Comunque queste estensioni (il cui scopo è quello di avere una rappresentazione più chiara e compatta della grammatica) sono riconosciute ormai universalmente come parte integrante della BNF. per rendersi conto del notevole vantaggio, sia di codice che di chiarezza, che si ottiene utilizzando questi costrutti notiamo che una delle regole di produzione viste sopra:
 
:<nowiki><destinatario> ::= [<titolo>] [<nome>|<iniziale>] <cognome> <a capo></nowiki>