Gramatica Libre de Contexto

 

GRAMÁTICA LIBRE DE CONTEXTO
El análisis gramatical tiene como tarea
determinar la estructura de un programa,
por esta razón es conocido también como
análisis sintáctico. Esta estructura o
también conocida como sintaxis de un
lenguaje de programación es regulado
mediante
unas
reglas
gramaticales
inmersas dentro de una gramática libre
de contexto.
La estructura básica empleadaen estas
gramáticas es por lo general alguna
clase de árbol, conocida como árbol de
análisis gramatical o árbol sintáctico.

Figura 1. Estructura básico, árbol sintáctico


 

Al
contrario
de
los
analizadores
léxicos, donde existe un solo método
algorítmico, representado por autómatas
finitos,
el
análisis
sintáctico
involucra tener que elegir entre varios
métodosdiferentes
entre
si,
con
diferentes propiedades y capacidades,
destacándose entre estos dos clases de
algoritmos,
análisis
sintáctico
descendente
y
análisis
sintáctico
ascendente.

La gramática de libre contexto hace el
uso
de
convenciones
para
nombrar
expresiones regulares, con el uso de
operaciones muy similares entre si,
teniendo en cuenta que las reglas libres
de contexto sonaltamente recursivas.
Los algoritmos empleados para reconocer
estas estructuras también difieren mucho
de los algoritmos de análisis léxico,
debido a la recursividad inmersos en
estos algoritmos.


 

Un ejemplo de esta recursividad, es el
uso
de
una
proposición
condicional
definida
por
una
regla
como
la
siguiente:
Ejemplo 1.1
Ø Si S1 y S2 son proposiciones y E es
unaexpresión, entonces.
Ø “If E then
proposición.

S1

else

S2”

es

una

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


 

TERMINOLOGIA PARA EL ANÁLISIS SINTACTICO
1. TERMINALES.Los terminales son los símbolos
básicos con que se forman las
diferentes cadenas, en el ejemplo
anterior podemos reconocer cada una
de las palabras claves if, then y
else son terminales.
2. NO TERMINALES.
Los no terminales son variables
sintácticas
los
cuales
denotan
conjuntos de cadenas, en el ejemplo
anterior
podemos
observar
dos
estructuras no terminales en prop y
expr.Estas estructuras definen un
conjunto de cadenas que definen el
lenguaje generado por la gramática,
estos imponen también estructuras
jerárquicas sobre el lenguaje, útil
para su análisis sintáctico como
para su traducción.


 

3. SIMBOLO INICIAL.
En una gramática, un no terminal se
considera a su vez como el símbolo
inicial, y a su vez el conjunto de
expresiones
representado
porel
lenguaje que es definido por la
gramática.
4. PRODUCCIONES.
Las producciones de una gramática
son aquellas que especifican la
forma
como
se
combinan
los
terminales y los no terminales para
formar diferentes expresiones entre
si. Cada producción consta de un no
terminal, seguido de una flecha u
otro
símbolo
que
reemplaza
la
misma, seguido por una cadena de
terminales y noterminales.


 

Ejemplo 1.2
Ø expr
Ø expr
Ø expr
Ø expr
Ø op
Ø op
Ø op
Ø op

à
à
à
à
à
à
à
à

expr op expr
( expr )
- expr
id
+
*
/

Teniendo
la
gramática
anterior,
la
terminología utilizada para el análisis
sintáctico viene dada por las siguientes
estructuras:
Símbolos terminales
id + - * / ( )
Símbolos no terminales
expr op
Símboloinicial
expr
Producción
>


 

DERIVACIONES Y EL LENGUAJE DEFINIDO POR
UNA GRAMÁTICA
Existen diferentes formas de considerar
el
proceso
mediante
el
cual
una
gramática hace una definición de un
lenguaje.
Las
reglas
gramaticales
determinan un lenguaje especifico, el
cual esta compuesto por conjuntos de
cadenas legales de tokens. Estas reglas
gramaticales
libres
de...