Backus-Naur Form
Indice
sf. (o Backus Normal Form, o BNF). In informatica, notazione per descrivere formalmente la sintassi di linguaggi. Sviluppata da John Backus e Peter Naur nel 1960, la BNF è stata utilizzata per la prima volta per definire e progettare la sintassi di Algol-60, il precursore dei moderni linguaggi di programmazione di tipo “imperativo”. La BNF prescrive che le frasi, che compongono un linguaggio, possono essere specificate a partire da un unico simbolo iniziale di alto livello. Ogni simbolo di alto livello (non terminale) può essere sostituito da una frase fra un insieme di sottofrasi, comprendenti simboli sia non terminali sia di basso livello (terminali), mentre i simboli terminali non possono essere sostituiti. Il processo si arresta quando si ottiene una sequenza di soli simboli terminali. Il linguaggio definito da una BNF è costituito così da tutte le sequenze di simboli terminali ottenute applicando questo processo a partire dal simbolo iniziale di alto livello. La seguente BNF, per esempio, descrive il linguaggio delle frasi con la struttura Soggetto-Verbo-Complemento che utilizzano le parole "il", "la", "lo" "anziano", "bambino", "bambina", "mangia" "mela, "pera":
Come si può osservare, i simboli non terminali sono racchiusi fra parentesi angolari (<), i terminali fra virgolette ("), le diverse alternative per un non terminale sono separate da una barra verticale (|) e il segno := indica le possibili sostituzioni per il non terminale. Si può notare quindi che la BNF proposta non permette, ovviamente, di generare tutte le frasi della lingua italiana, ma ammette la possibilità di creare frasi non corrette come, per esempio, “lo bambino mangia la mela”. Nell'esempio specifico, però, quest'ultimo problema può essere facilmente risolto, modificando opportunamente la BNF in esame. Le sintassi definite mediante BNF, infatti, non possono in generale specificare l'insieme di tutte e sole le forme corrette in un linguaggio naturale. In particolare, è stato dimostrato che il potere espressivo delle BNF è pari a quello delle “grammatiche libere dal contesto” definite da Chomsky. È inoltre noto che il potere delle grammatiche libere dal contesto è insufficiente a specificare interamente un linguaggio naturale. D'altra parte, tentativi di espandere il potere espressivo di meccanismi sintattici, in modo da poter accettare un numero maggiore di tipi di costrutti presenti nel linguaggio naturale, porta spesso alla possibilità di generare costrutti scorretti. Il campo di applicazione della BNF è, quindi, specifico dei linguaggi di programmazione, linguaggi artificiali con un numero limitato e ben definito di tipi di costrutti. Anche in questo caso, però, si ricorre spesso alla verifica del soddisfacimento di vincoli contestuali sulle frasi (programmi) prodotte, che non possono essere espressi con BNF (per esempio che un identificatore sia utilizzato solo dopo essere stato dichiarato e inizializzato). Una estensione della BNF, detta Extendend BNF (EBNF), è stata introdotta da Niklaus Wirth per specificare la sintassi del linguaggio di programmazione Pascal. Nella EBNF i simboli {,}, (, ) e * possono comparire nel lato destro di una produzione. Una sequenza di simboli racchiusa fra { e } indica che tale sequenza è opzionale, mentre un simbolo, o una sequenza racchiusa fra ( e ), seguito da *, indica un numero arbitrario di ripetizioni della sequenza, incluso 0.