Gramáticas libres de Contexto
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
Submenu
|
