La notazione di Backus-Naur (conosciuta come BNF o Backus-Naur Form) è un metodo matematico formale usato per descrivere la sintassi di un linguaggio.
Il metodo prende il nome dal suo inventore, John Backus, che lo utilizzò per descrivere la sintassi del linguaggio di programmazione Algol 60.
In che modo si descrive il linguaggio?
Attraverso la BNF definiamo la grammatica del linguaggio (ciò che è permesso o non è permesso fare) in maniera formale (senza ambiguità e in maniera "esatta"). Più semplicemente possiamo considerarla come un gioco matematico che funziona in questo modo:
Si parte con un simbolo che chiamiamo S e vengono fornite le regole (dette regole di produzione) per rimpiazzare questo simbolo con altri simboli o stringhe (le stringhe sono dette valori terminali).
Le regole di produzione hanno la forma seguente:
simbolo := alternativa1 | alternativa2 | ... | alternativaN
e indicano i modi in cui può essere rimpiazzato il simbolo ( indicato a sinistra del := ).
Con := si indica: "ciò che è alla mia sinistra si trasforma in una delle alternative che ho indicato alla mia destra".
Le alternative (separate da | ) possono essere altri simboli o valori terminali:
I simboli (non terminali) hanno sempre regole di produzione (devono essere sostituiti con altro)
I valori teminali non hanno regole di produzione ( non possono essere sostituiti con altro e quindi non si troveranno mai a sinistra del := ) e pertanto terminano il processo di produzione.
Esempio
Vediamo di chiarire meglio la BNF con un esempio. Utilizziamo la BFN per descrivere la grammatica della scrittura di un numero: ad esempio 34.6 oppure -4 oppure -45.35 .
S := '-' FN | FN
FN := DL | DL '.' DL
DL := D | D DL
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
I simboli sono abbreviazioni per: S è il simbolo iniziale (dal quale si partirà con le produzioni), FN (Fractional Number) è il numero frazionario, DL (Digit List) è un elenco di numeri (da 0 a 9, es. 12345), D (Digit) è un numero da 0 a 9.
Vediamo come produrre il numero 3.14 con la grammatica descritta nell'esempio:
- S - partiamo sempre dal simbolo iniziale. Abbiamo 2 scelte: una per rappresentare numeri negativi e l'altra positivi. 3.14 è positivo quindi:
- FN - per FN abbiamo 2 scelte: una per numeri interi e l'altra per numeri frazionari. 3.14 è un numero frazionario, quindi:
- DL '.' DL - prendiamo il primo DL. DL può essere o un numero (singolo) o un numero seguito da un elenco numeri. 3 di 3.14 che è prima del . è un singolo numero. Quindi:
- D '.' DL - D è un valore terminale che va quindi sostituito con il 3 di 3.14 . Quindi:
- 3 '.' DL - riprendiamo il secondo DL che avevamo lasciato in sospeso. Dobbiamo rappresentare il 14 di 3.14 . DL può quindi essere o un singolo numero (D ma non è questo il caso) oppure un singolo numero seguito da un elenco di numeri (D DL). Quest'ultima trasformazione è ciò che interessa. Quindi:
- 3 '.' D DL - l'ultimo DL rimasto deve essere trasformato in 1 singolo numero
- 3 '.' D D - procedendo alla sostituzione degli ultimi 2 D rimasti:
- 3 '.' 1 D
- 3 '.' 1 4
Da notare come le regole di produzione rendano impossibile una rappresentazione impropria dei numeri frazionari: ad esempio è impossibile produrre un 3..14 o un 3.1.4 .
L'esempio dimostra come in alcuni casi la BNF possa diventare complessa o di difficile lettura: ad esempio si è usata la ricorsione per rappresentare un elenco di numeri decimali (DL che produce altri DL).
Per tale motivo la BNF è stata estesa con la EBNF descritta nella sezione seguente.
EBNF: BNF estesa
L'EBNF estende la BFN descritta sopra con l'aggiunta di 3 operatori:
- ?: indica che il simbolo che sta alla sua sinistra è opzionale (può non essere presente oppure essere presente 1 volta)
- *: il simbolo alla sua sinistra può essere presente 0 o più volte (a differenza di ? dove il simbolo può essere presente 1 sola volta, in questo caso piò essere presente anche più di una volta)
- +: il simbolo alla sua sinistra può essere presente o 1 sola volta o più volte. A differenza dei precedenti dove il simbolo è opzionale, in questo caso il simbolo è obbligatorio.
Con simbolo in questo caso è possibile intendere anche un gruppo di simboli raggruppati in un "unico simbolo" attraverso l'uso di parantesi.
La grammatica dell'esempio precedente può quindi essere scritta nella forma seguente (molto più abbreviata e leggibile):
S := '-'? D+ ('.' D+)?
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Nota: l'EBNF non è più espressiva della BNF. Le regole che è possibile scrivere con la EBNF possono essere convertite nella BNF. L'EBNF è solo da intendersi come estensione utilizzata per rendere la BNF più leggibile e semplice.
0 commenti:
Posta un commento