Mokibo

Gramática libre de contexto
Resumen: gramática libre de contexto en lingüística e informática es una gramática formal en la que cada regla de producción es de la forma V → w donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales.
El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta elcontexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera.
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 comopara permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada determinen como puede ser generada desde la gramática. Los analizadores LL y LR tratan restringidos subconjuntos de gramáticas libres de contexto.

Gramática Libre de Contexto
Una gramática libre de contexto en lingüística e informática es una gramática formal en la que cada regla deproducción es de la forma:
V → w
Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera.
Las gramáticas libres decontexto 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. La notación más frecuentemente utilizada para expresar gramáticas libres de contexto es la forma Backus-Naur.
Así como cualquier gramática formal, una gramática libre de contexto puede ser definida mediante la4-tupla:
G = (Vt,Vn,P,S) donde
* Vt es un conjunto finito de terminales
* Vn es un conjunto finito de no terminales
* P es un conjunto finito de producciones
* S Є Vn el denominado Símbolo Inicial
* los elementos de P son de la forma:
[1]
Árbol de Derivación
Un árbol de derivación (o árbol sintáctico) es una representacióngráfica de como se deriva una forma sentencial a partir del símbolo no-terminal inicial.
Un árbol es un grafo dirigido acíclico en el cual cada nodo se conecta con un nodo distinguido, llamado nodo raíz mediante un único camino. Un nodo n1 se dice descendiente de otro nodo n2 si se puede llegar a n1 a partir de n1. El nodo raíz no es descendiente de ningún nodo, y los nodos que no tienen descendientesse denominan hojas. El resto de los nodos se denominan nodos interiores.

Un árbol de derivación tiene las siguientes propiedades:
1. El nodo raíz está rotulado con el símbolo distinguido (inicial) de la gramática.
2. Cada hoja corresponde a un símbolo terminal o un símbolo no-terminal.
3. Cada nodo interior corresponde a un símbolo no-terminal.
Un árbol de derivación muestragráficamente las derivaciones (substituciones de símbolos no terminales) que hay que llevar a cabo para llegar a una forma sentencial a partir del símbolo inicial.[1]
Formas Normales de Chomsky

Es un modelo o forma normal para las producciones. Se dice que una GIC está en Forma Normal de Chomsky, si no contiene ε producciones y si todas las producciones son de la forma:

A→a, para a Є Σ
A→BC,con B y C no terminales

Toda GIC puede ser transformada en un GIC en Forma Normal de Chomsky.
* Sea G una GIC tal que ε∉L(G)
* Sea G una GIC tal que ε Є L(G)

* Sea G una GIC y ε∉L(G), G puede ser transformada en una GIC en F.N. de Chomsky.

1. Eliminar los símbolos inútiles, las ε-producciones y las producciones unitarias de G.
2. Para las producciones de la forma A→w y |w|...