Analisis Sintactico

ANÁLISIS SINTÁCTICO

GRAMATICA DE LIBRE CONTEXTO

La GLC (Gramatica de libre contexto) o tambien llamadas CFL’s (Context-Free Languages). Un lenguaje libre de contexto es aquel generado por una gramática libre de contexto. Estos conceptos pertenecen a un área de la Ciencia de la Computación llamada Computación Teórica. No hay algoritmo que nos diga el lenguaje de la gramática, por eso tenemos que ir viendo los símbolos y cadenas que produce.

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

Caracteristicas

• Capturan la noción de constituyente sintáctico y la noción de orden.

• Herramienta formal que puede ser vista tanto desde un punto de vista generador como estructurador.

• Propiedades computacionales interesantes: se puede reconocer en tiempo polinómico.

Definicion formal de GLC

Una gramatica libre de contexto se define con G = (V, T,P,S) donde:

• V es un conjunto de variables

• T es un conjunto de terminales

• P es un conjunto finito de producciones de la forma A ! α, donde A es una variables y α 2 (V [ T)

• S es una variable designada llamada el sımbolo inicial

Las Gramaticas Libres de Contexto forman la base de la sintaxis BNF(Forma de Backus-Naur).

Son actualmente importantes para XML (eXtensible Markup Lenguaje Deriva del lenguaje SGML )y sus DTD’s (document type definition).

BNF

Las gramáticas libres del contexto se escriben, frecuentemente, utilizando una notación conocida como BNF (Backus-Naur Form). BNF es la técnica más común para definir la sintaxis de los lenguajes de programación.

La siguiente es una definición BNF del lenguaje que consiste de cadenas de paréntesis anidados:

<cadena_par> :: = <cadena_par> <paréntesis> <paréntesis> <paréntesis> ::= (<cadena_par> ) ( )

Por ejemplo las cadenas ( ) ( ( ) ) y ( ) ( ) ( ) son cadenas válidas. En cambio las cadenas ( ( ) y ( ) ) ) no pertenecen al lenguaje.

ARBOLES DE DERIVACIÒN

Derivacion

Aplicación de las producciones de una gramática para obtener una cadena de terminales.

Consiste en sustituir la variable de la cabeza por el cuerpo de la producción.

Derivación a la Izquierda. Cuando se aplica en cada derivación directa la producción al símbolo no terminal que está más a la izquierda de la cadena.

Derivación a la Derecha. Cuando se aplica al símbolo que está más a la derecha de la cadena.

Árbol de derivación

Un árbol de derivación permite 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 nodos, unidos por líneas, llamadas arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de nodos y arcos debe satisfacer ciertas propiedades:

- el nodo raíz está rotulado con el símbolo distinguido de la gramática;

- cada hoja corresponde a un símbolo terminal o un símbolo no terminal;

- cada nodo interior corresponde a un símbolo no terminal

Relación entre derivaciones y árboles

Si leemos las etiquetas de las hojas de izquierda a derecha tenemos una sentencia. Llamamos a esta cadena la producción del árbol de derivación.

Ejemplo:

DIAGRAMAS DE SINTAXIS.

Un diagrama de sintaxis es también llamados diagramas de conway es un grado dirigido donde los elementos no terminales aparecen como rectángulos, y los terminales como círculos o elipses.

Sean a y b dos terminales o no terminales. Un arco entre a y b significa que a “a” le puede seguir “b”. Por lo que una manera de representar todas las sentencias válidas es ver los diferentes caminos entre a y b.

Para ver si una sentencia es válida sintácticamente, no tenemos de otra más que comprobar si puede ser representada por un camino válido.

En cualquier diagrama en notación BNF tiene su correspondiente diagrama de sintaxis y encontrarlo es sencillo. Notación bnf

la notación mas frecuente utilizada para expresar gramáticas libre de contexto es una forma BACKUS –NAUR

Eliminación de la ambigüedad

Una GLC es ambigua si existe una cadena w Î L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más árboles de derivación. En caso de que toda cadena w Î L(G) tenga un único árbol de derivación, la gramática no es ambigua.

TIPOS DE AMBIGÜEDAD

Ambigüedad Inherente

La gramática es ambigua: hay cadenas con más de una

derivación más izquierda: Considere: aabbccdd (m = n = 2) S ⇒ AB ⇒ aAbB ⇒ aabbB ⇒ aabbcBd ⇒ aabbccdd, S ⇒ C ⇒ aCd ⇒ aaDdd ⇒ aabDcdd ⇒ aabbccdd.

Ambigüedad Transitoria

Este tipo de ambigüedad puede llegar a ser eliminada realizando una serie de transformaciones sobre la gramática original. Una vez que se logra lo anterior, la gramática queda lista para ser reconocida por la mayor parte de los analizadores sintácticos. (Se le considera "ambigüedad" porque existen métodos para realizar análisis sintáctico que no aceptan gramáticas con estas características). Dónde se presenta la Ambigüedad Transitoria generalmente la ambigüedad se presenta cuando existen producciones con factores comunes (distintas alternativas para un símbolo no-terminal que inician de la misma forma); ó cuando existen producciones que son recursivas izquierdas (producciones para un símbolo no-terminal en las cuales el primer símbolo de su forma sentencial es ese mismo símbolo no-terminal).

GENERACION DE MATRIZ PREDICTIVA (CALCULO DEL FIRST Y FOLLOW)

FIRST

Si α es cualquier cadena de símbolos gramaticales, se considera FIRST(α) como el conjunto de terminales que encabezan las cadenas derivadas de α. Si α =*=> λ, entonces λ también está en FIRST(α).

Para

...