Analisis Sintactico 6

GLC

Definiciones y propiedades
¿Qué es una gramática?
• Modelo de estructuras recursivas.
• Definición de reglas para representar las expresiones de los lenguajes.
• Especificación rigurosa y explicita de estructura de un lenguaje.
Características:
• Ausencia de ambigüedad, por tanto bien definidas.
• Rigurosas (claridad, explicitud).
• Facilitan evaluación: comprobar, conclusiones, derivar.
• Hacer predicciones: generalización.
• Desarrollo de aplicaciones.
Existen varios tipos de Gramáticas, las que mas se usan en computación son las gramáticas
generativas, definidas por Noam Chomsky.
Las Gramáticas Generativas constan de la siguiente tupla de elementos:
G = (V, T, P, S)
Donde:
V: conjunto finito de Variables (símbolos no terminales/categorías sintácticas)
T: conjunto finito de símbolos Terminales (alfabeto terminal o alfabeto de símbolos)
P: conjunto finito de Producciones o Reglas (definición recursiva del lenguaje)

Cada regla o producción consta de:
• Cabeza: variable.
• a : símbolo de producción.
• Cuerpo: cadena de 0 o mas símbolos terminales y/o variables.
Es decir una regla tiene la forma: Cabeza a Cuerpo, por ejemplo: Por ejemplo:
Aa aBA donde A,B en V, a en T
S: símbolo inicial
Nota: Se asume que de V I T= 
Asignatura: Teoría de la Computación
Tema 4: Gramáticas independientes del
contexto
Prof. Hilda Contreras – Teoría de la Computación (Pregrado) 2
Las gramáticas generativas son modelos matemáticos finitos que nos permiten generar las
cadenas o palabras de un lenguaje finito o infinito.
Según la Jerarquía de Chomsky: las gramáticas generativas se clasifican en 4 tipos. Esta
clasificación es inclusiva, es decir tipo 3 ⊂ tipo 2 ⊂ tipo 1 ⊂ tipo 0