miércoles, 18 de mayo de 2011

UNIDAD 3: ANALISIS SINTÁCTICO


ANALISIS SINTÁCTICO
(Los apuntes son cortesía de la Maestra Theira Irasema Samperio Monroy)

Un analizador sintáctico (en inglés parser) es una de las partes de un compilador que transforma su entrada en un árbol de derivación.


El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.


El análisis sintáctico también es un estado inicial del análisis de frases de lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.






3.1 Función del análisis sintáctico

En el modelo del compilador, el analizador sintáctico obtiene una cadena de componentes léxicos del analizador léxico, y comprueba si la cadena puede ser generada por la gramática del programa fuente. Esta iteracción se esquematiza como sigue:





Existen 2 tipos generales de analizadores sintácticos para gramáticas:


a) Análisis sintáctico descendente. Construye árboles de análisis sintáctico desde arriba (raíz) hacia abajo (hojas). El análisis se realiza de lo general a lo particular.


b) Análisis sintáctico ascendente. Construyen árboles de análisis sintáctico comenzando en las hojas y suben hacia la raíz. El análisis se realiza de lo particular a lo general.





En ambos casos, se examina la entrada al analizador léxico de izquierda a derecha, un símbolo a la vez. La salida del analizador sintáctico es una representación del árbol de análisis sintáctico para la cadena de componentes léxicos producida por el analizador léxico.


3.2 Gramáticas independientes de contexto

Se puede describir la sintaxis de las construcciones de los lenguajes de programación por medio de gramáticas independientes de contexto. Una gramática describe de forma natural la estructura jerárquica de muchas construcciones de los lenguajes de programación.


Consta de:


TERMINALES. Símbolos básicos con que se forman las cadenas. Para un lenguaje de programación, cada palabra clave/reservada es un terminal. prop_if → if expr prop else prop


NO TERMINALES. Son variables sintácticas que denotan conjuntos de cadenas (identificadotes o variables). Los no terminales definen conjuntos de cadenas que ayudan a definir el lenguaje generado por la gramática. Imponen una estructura jerárquica sobre el lenguaje que es útil tanto para el análisis sintáctico como para la traducción. prop_if expr prop son no terminales


UN SÍMBOLO INICIAL. En una gramática, es un no terminal que representa un conjunto de cadenas. prop_if no terminal, símbolo inicial


PRODUCCIONES. Especifican cómo se pueden combinar los terminales y no terminales para formar cadenas. Cada producción consta de un No terminal (símbolo inicial), seguido por una flecha o símbolo de asignación, seguida por una cadena de no terminales y terminales. prop_if → if expr prop else prop Por ejemplo, la gramática con las siguientes producciones define expresiones aritméticas simples: expr → expr op expr expr → (expr) expr → - expr expr → id Op → + Op → - Op → / Op → * Op → %


3.3 Escritura de una gramática

Las gramáticas describen la mayoría de las sintaxis de los lenguajes de programación. Toda construcción que se pueda describir mediante una expresión regular también se puede describir por medio de una gramática. Por ejemplo, para la expresión regular (a|b)* abb Y la gramática: A0 a A0 | b A0| b A1 A1 b A2
A2 bA3 A3 є Describen el mismo lenguaje: el conjunto de cadenas de caracteres a y b que terminan en abb. 


Todo conjunto regular es un lenguaje independiente de contexto, ¿porqué utilizar expresiones regulares para definir la sintaxis léxica de un lenguaje? Razones para utilizar expresiones regulares para definir la sintaxis léxica de un lenguaje.


Ø Las reglas lexicogáficas de un lenguaje a menudo son bastante sencillas, y para describirlas no se necesita una notación tan poderosa como las gramáticas.


Ø Proporcionan una notación más concisa y más fácil de entender para los componentes léxicos.


Ø Se construyen automáticamente analizadores léxicos más eficientes a partir de expresiones regulares.


Ø Separar la estructura sintáctica de un lenguaje en partes léxicas y no léxicas proporciona una forma conveniente de modular la etapa inicial de un compilador en dos componentes de tamaño razonable.


Ø Las expresiones regulares son muy útiles para describir identificadores, constantes, palabras clave, etc.


Ø Las gramáticas son muy útiles para describir estructuras anidadas, estructuras de control, etc.


3.4 Análisis sintáctico descendente
Se considera un intento de encontrar una derivación por la izquierda para una cadena de entrada.


También se puede considerar como un intento de construir un árbol de análisis sintáctico para la entrada comenzando desde la raíz y creando nodos del árbol en orden previo. 3.5 Análisis sintáctico ascendente El análisis sintáctico ascendente intenta construir un árbol para la cadena de entrada que comienza por las hojas (el fondo) y avanza hacia la raíz (la cima).


Se puede considerar este proceso como de “reducir” una cadena x al símbolo inicial de la gramática.


3.5 Análisis sintáctico por precedencia de operadores
Para una pequeña clase de gramáticas se puede construir con facilidad a mano eficientes analizadores sintácticos ascendentes. Estas gramáticas, por precedencia de operadores, tienen la propiedad de que ningún lado derecho de la producción es є ni tiene 2 terminales adyacentes. Una gramática con esta última propiedad de denomina gramática de operadores. Esta técnica, históricamente, se describió primero como una manipulación de componentes léxicos sin hacer referencia a ninguna gramática subyacente. Dada su sencillez, se han construido muchos compiladores que utilizan las técnicas de análisis sintáctico por precedencia de operadores para expresiones.



3.6 Analizadores sintácticos Izquierda-Derecha (LR)
Es una técnica eficiente de análisis sintáctico ascendente que se puede utilizar para analizar una amplia clase de gramáticas independientes de contexto, denominada Análisis sintáctico LR(k) L es por el examen de la entrada de izquierda a derecha (left to right) R por construir una derivación por la derecha (right most derivation) en orden inverso. K por el número de símbolos de entrada de examen por anticipado utilizados para tomar decisiones del análisis sintáctico. Cuando se omite, se asume que k es 1. Este análisis es atractivo por varias razones:


•Reconocen prácticamente todas las construcciones de los lenguajes de programación para los que se pueden escribir gramáticas independientes del contexto.


•Puede detectar un error sintáctico tan pronto como sea posible hacerlo en un examen de izquierda a derecha de la entrada.


3.7 Uso de gramáticas ambiguas
Gramática ambigua es aquella que produce más de un árbol de análisis sintáctico para alguna frase, es decir, una gramática ambigua es la que produce más de una derivación por la izquierda o por la derecha para la misma frase. Algunos tipos de gramáticas ambiguas son útiles en la especificación e implementación de lenguajes. Se utiliza para el aislamiento de construcciones sintácticas habituales para optimación en casos especiales.
Con una gramática ambigua se pueden especificar las construcciones de casos especiales añadiendo cuidadosamente nuevas producciones a la gramática. Las construcciones ambiguas se deben usar raramente y de una manera estrictamente controlada, pues de lo contrario no se puede reconocer con seguridad el lenguaje que reconoce el analizador.
Para más informacion visita estos links (enlaces):


No la rieges

No hay comentarios.:

Publicar un comentario

Vistas a la página totales