Un programme peut être considéré comme une très longue chaîne de caractères, dont chaque élément est un des symboles le composant. Un minimum de terminologie sur les chaînes de caractères ou mots est nécessaire pour décrire les algorithmes d'analyse syntaxique. Pour plus de précisions sur les propriétés algébriques et combinatoires des mots, on pourra se reporter à [33].
On utilise un ensemble fini appelé alphabet 
dont les
éléments sont appelés des lettres. Un mot est une
suite finie 
de lettres, l'entier 
s'appelle sa longueur. On note par 
le mot vide, c'est le
seul mot de longueur 
. Le produit de deux mots 
et 
est
obtenu en écrivant puis à la suite, celui ci est noté 
.
On peut noter que la longueur de est égale à la somme des
longueurs de et de . En général est différent de 
.
Un mot est un facteur de s'il existe deux mots 
et
tels que 
, est facteur gauche de si
c'est un facteur droit si 
. L'ensemble des
mots sur l'alphabet est noté 
.