Las cadenas válidas para un determinado lenguaje se pueden establecer por medio de gramáticas libres de contexto.
Las gramáticas libres de contexto son muy importantes en la práctica, ya que permiten definir la mayoría de los lenguajes de programación.
Una gramática es una 4-tupla, G= (V, T, P, S) donde:
T: Los terminales son los símbolos básicos con que se forman las cadenas.
V: Los no terminales son variables sintácticas que denotan conjuntos de cadenas.
S: En la gramática existe un símbolo no terminal a partir del cual se empieza a derivar, este no terminal es el símbolo inicial.
P: Las producciones especifican la forma de relacionar terminales y no terminales para formar cadenas válidas para la gramática definida. Cada producción consta de un no terminal, seguido por una flecha, seguido por una cadena de no terminales y terminales: A→α donde A∈V y α∈(V∪T)+ Además, también se permiten producciones nulas A→ε.
Ejemplo:
LISTA → LISTA + DIGITO
LISTA → LISTA – DIGITO
LISTA → DIGITO
DIGITO → 0 | 1 | 2| 3| 4 | 5 | 6 | 7 | 8 | 9