GRAMATICAS LIBRES DEL CONTEXTO Rúsbin Zunún UMG

1. DEFINICION: Estas gramáticas, conocidas también como gramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto

1.1. Como toda gramática se definen mediante una cuadrupla G = (N, T, P, S), siendo - N es un conjunto finito de símbolos no terminales - T es un conjunto finito de símbolos terminales N ∩ T = ∅ - P es un conjunto finito de producciones - S es el símbolo distinguido o axioma S ∉ (N ∪ T) En una gramática libre del contexto, cada producción de P tiene la forma A ∈ N ∪ {S} A → ω ω ∈ (N ∪ T)* - {ε}

1.2. IMPORTANCIA: Estos lenguajes son importantes tanto desde el punto de vista teórico, por relacionar las llamadas Gramáticas Libres de Contexto con los Autómatas de Pila, como desde el punto de vista practico, ya que casi todos los lenguajes de programación están basados en los LLC.

1.3. USOS: Un ejemplo de esta recursividad, es el uso de una proposición condicional definida por una regla como la siguiente: Ejemplo: -Si S1 y S2 son proposiciones y E es una expresión, entonces. -“If E then proposición. S1 else S2” es una proposición. Usando la variable sintáctica prop, con el fin de denotar la clase de proposiciones y expr para la clase de expresiones, se puede expresar recursivamente usando una producción gramatical. -prop if expr then prop else prop