Come hai sottolineato, gli umani comunicano tra loro in una lingua "naturale" come inglese, francese, tedesco. Sono chiamati naturali perché li acquisiamo naturalmente piuttosto che inventarli intenzionalmente (l'esperanto è un'eccezione).
Un linguaggio formale è uno inventato per qualche scopo o altro. Un linguaggio di programmazione come C, ad esempio, è un linguaggio formale inventato allo scopo di programmare i computer.
Tutte le lingue, possono essere descritte usando una grammatica. Una gerarchia di grammatiche è stata descritta da Noam Chomsky nel 1956. Si compone dei seguenti livelli:
Grammatiche di tipo 0 (grammatiche senza restrizioni). Sono i più generali e equivalgono a una macchina di Turing. In quanto tale, il problema di decidere se una determinata stringa fa parte di una grammatica senza restrizioni è indecidibile.
Grammatiche di tipo 1 (grammatiche sensibili al contesto). Quasi tutte le lingue naturali come l'inglese sono sensibili al contesto. Un esempio di sensibilità al contesto in inglese sono le due frasi: "Il tempo vola come una freccia". e "La frutta vola come una banana". In generale, è difficile per i computer capire i linguaggi sensibili al contesto.
Grammatiche di tipo 2 (senza contesto). Le lingue prive di contesto sono la base teorica per la sintassi della maggior parte dei linguaggi di programmazione.
Grammatiche di tipo 3 (grammatiche regolari). La famiglia di lingue regolari può essere ottenuta tramite espressioni regolari. Le lingue regolari sono comunemente usate per definire i modelli di ricerca e la struttura lessicale dei linguaggi di programmazione.
Le grammatiche di tipo 2 (context-free) e di tipo 3 (regolari) sono più spesso dai computer perché i parser per loro possono essere implementati in modo efficiente.
BNF (Backus Normal Form o Backus-Naur Form) è una tecnica di notazione per il contesto - grammatiche libere, spesso utilizzate per descrivere la sintassi dei linguaggi utilizzati nell'informatica.
Ad esempio un identificatore può essere descritto come:
<identifier> ::= <letter> { <letter> | <digit> }
che significa che deve iniziare con una lettera e può contenere ulteriori lettere o cifre.
In precedenza, una lettera è definita a 'a' | 'b' | 'c' ecc. e le cifre sono definite da '0' a '9' usando lo stesso tipo di notazione.
Un'istruzione C per "potrebbe essere definita come:
<for_statement> ::=
'for' '(' <expression> ';' <expression> ';' <expression> ')' <statement>
Gli analizzatori e parser lessicali (i primi stadi di un compilatore o di un interprete) sono quindi costruiti per accettare la grammatica specifica descritta dal BNF per un particolare linguaggio. Gli analizzatori lessicali vengono in genere utilizzati per separare i vari token di una lingua (come una parola chiave, un identificatore o un numero) e il parser viene utilizzato per capire come funzionano i token, ad esempio come viene costruita una istruzione "for" .