Gramaticas Independienes De Contexto

Gramaticas Independientes del Contexto,
Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la sintaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintácticoque, para una cadena de caracteres dada determinen como puede ser generada desde la gramática
Gramáticas Independientes del Contexto
Una Gramática independientes del contexto (GIC) es una gramática formal en la que cada regla de producción es de la forma:
Exp → x
Donde Exp es un símbolo no terminal y x es una cadena de terminales y/o no terminales. El término independiente del contexto serefiere al hecho de que el no terminal Exp puede siempre ser sustituido por x sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es independiente de contexto si hay una gramática libre de contexto que lo genera, este tipo de gramática fue creada por Backus-Naur y se utiliza para describir la mayoría de los lenguajes de programación.
Una GIC está compuesta por 4 elementos:
1.Símbolos terminales (elementos que no generan nada)
2. No terminales (elementos del lado izquierdo de una producción, antes de la flecha "->")
3. Producciones (sentencias que se escriben en la gramática)
4. Símbolo inicial (primer elemento de la gramática)
Ejemplo 1: Teniendo un lenguaje que genera expresiones de tipo:
9 + 5 – 2
Para determinar si una GIC está bien escrita se utilizan los arboles deanálisis sintáctico , así:
Producciones:
lista -> lista + digito
lista -> lista - digito
lista -> digito
digito -> 0|1|2|3|4|5|6|7|8|9
Arbol de analisis sintactico:

Figure 1
La gramática es correcta siempre y cuando el símbolo inicial este al lado izquierdo de las producciones y sea la raíz del árbol.
Ejemplo 2: Hacer una gramática que genere el número 5
Símbolo inicial (noterminal): Exp y Símbolo terminal: 5
Exp -> 5
Ejemplo 3: Hacer una gramática que genere un dígito.
Exp -> 0|1|2|3|4|5|6|7|8|9
Arbol de analisis sintactico:

Exp
|
3
Ejemplo 4: Hacer una gramática que repita muchas veces el número 5
Exp -> Exp 5|5
Prueba con el número 555

Figure 2

Arboles De Derivación
Existen básicamente dos formas de describir cómo en una cierta gramática una cadenapuede ser derivada desde el símbolo inicial. La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas. Si introducimos estrategias como reemplazar siempre el no terminal de más a la izquierda primero, entonces la lista de reglas aplicadas es suficiente. A esto se le llama derivación por laizquierda.
Por ejemplo, si tomamos la siguiente gramática:
: (1) S → S + S
: (2) S → 1
y la cadena “1 + 1 + 1″, su derivación a la izquierda está en la lista [ (1), (1), (2), (2), (2) ]. Análogamente, la derivación por la derecha se define como la lista que obtenemos si siempre reemplazamos primero el no terminal de más a la derecha. En ese caso, la lista de reglas aplicadas para laderivación de la cadena con la gramática anterior sería la [ (1), (2), (1), (2), (2)].
La distinción entre derivación por la izquierda y por la derecha es importante porque en la mayoría de analizadores la transformación de la entrada es definida dando una parte de código para cada producción que es ejecutada cuando la regla es aplicada. De modo que es importante saber qué derivación aplica elanalizador, por que determina el orden en el que el código será ejecutado.
Una derivación también puede ser expresada mediante una estructura jerárquica sobre la cadena que está siendo derivada. Por ejemplo, la estructura de la derivación a la izquierda de la cadena “1 + 1 + 1″ con la gramática anterior sería:
:S→S+S (1)
:S→S+S+S (1)
:S→1+S+S (2)
S→1+1+S (2)
:S→1+1+1 (2)
: { { { 1 }S + { 1...