Problema:
Come definire formalmente un linguaggio di programmazione?
Ovvero come e possibile definire con precisione l’insieme infinito delle frasi che è possibile scrivere con tale linguaggio?

Soluzione:
definire l'insieme delle regole (in numero finito) che ci consentono di derivare solamente ed esattamente gli elementi dell’insieme che stiamo definendo.

Esempio:

la definizione formale dei naturali.

cifra ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9  ( | notazione alternativa leggi "oppure")

naturale ::= cifra | cifra naturale   ( ::= derivavione leggi "produce")

Definizione: i naturali sono tutte quelle frasi che sono derivabili utilizzando le regole sopra descritte.