Backus-Naur Form: differenze tra le versioni

La '''BNF''' ('''Backus-Naur Form''' o '''Backus Normal Form''') è una [[metasintassi]], ovvero un [[formalismo]] attraverso il quale è possibile descrivere la [[sintassi (informatica)|sintassi]] di [[Linguaggio formale (matematica)|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).

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''' (vedi sotto) o nonterminali (identificati dal fatto di essere 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.

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. In particolare cominciamo con un esempio che contiene (per ora) solo simboli non terminali; la sua specifica BNF potrebbe essere grosso modo come segue:

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.

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.

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: