Definizioni:

Sia A un insieme finito di simboli, detto alfabeto o lessico.
Un Linguaggio sull'alfabeto A è un insieme di stringhe (parole) di lunghezza finita formate con simboli di A.
Con A* indichiamo l'insieme di tutte le stringhe di lunghezza finita formate con simboli di A. Un linguaggio sull'alfabeto A è un sottoinsieme di A*.

La sintassi è una quadrupla < A, V, S, P > dove:

• A è un alfabeto di simboli detti terminali;
• V è un insieme finito di simboli, tutti distinti dai simboli di A, detto alfabeto dei simboli non terminali;
• S è un simbolo non terminale detto simbolo iniziale;
• P è l'insieme delle derivazioni, ovvero delle regole di riscrittura, ciascuna delle quali ha la forma
                  
                  B::=a     dove B è un simbolo non terminale e a è una stringa formata da                           simboli terminali e non.