Gramatica libre de contextos

Gramática Libre De Contexto

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 noterminales. 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 decontexto 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 delenguajes 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 deaná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.La notación más frecuentemente utilizada para expresar gramáticas libres de contexto es la forma Backus-Naur.
Definición formal
Así como cualquier gramática formal, una gramática libre de contextopuede ser definida mediante la 4-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 deproducciones
• [pic]el denominado Símbolo Inicial
• los elementos de P son de la forma
[pic]

Ejemplo

Una simple gramática libre de contexto es
S → aSb | ε
donde | es un o lógicoy es usado para separar múltiples opciones para el mismo no terminal, ε indica una cadena vacía. Esta gramática genera el lenguaje no regular [pic].
Arbol de derivación

Un árbol de derivaciónpermite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje. Un árbol es un conjunto de puntos, llamados...