PONTIFICIA UNIVERSIDAD CATÓLICA DEL ECUADOR SEDE IBARRA ESCUELA DE INGENIERIA CARRERA DE SISTEMAS

NOMBRE: Grace Laguna FECHA: 03-05-2013

NIVEL: Quinto

ANALIZADOR SINTÁCTICO

EL PAPEL DEL ANALIZADOR SINTÁCTICO

En este modelo de 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 lenguaje fuente. Se supone que el analizador sintáctico informará de cualquier error de sintaxis de manera inteligible. También debería recuperarse de los errores que ocurren frecuentemente para poder continuar procesando el resto de su entrada.

Los métodos empleados generalmente en los compiladores se clasifican como descendentes o ascendentes. Como sus nombres indican, los analizadores sintácticos descendentes construyen árboles de análisis sintáctico desde arriba (la raíz) hasta abajo (las hojas), mientras que los analizadores sintácticos ascendentes comienzan en las hojas y suben hacia la raíz. En ambos casos, se examina la entrada al analizador sintáctico de izquierda a derecha, un símbolo a la vez.

ANÁLISIS SINTÁCTICO ASCENDENTE Y DESCENDENTE

Análisis sintáctico ascendente Los analizadores sintácticos ascendentes construyen el árbol sintáctico a partir de las hojas, paso a paso hasta llegar a la raíz. Es decir parten de los distintos tokens de la sentencia a analizar, y por medio de reducciones llegan al símbolo inicial de la gramática. Se llaman reducciones, para indicar que se efectúan en sentido contrario a las producciones de la gramática. El principal problema que se plantea en el análisis ascendente es el del retroceso, que se traduce en la elección de un pivote para realizar la reducción. Para salvar este inconveniente se definieron distintos tipos de gramáticas entre las cuales las más utilizadas son las LR(k). Los analizadores sintácticos ascendentes que reconocen lenguajes descritos por gramáticas LR(k), toman sus decisiones en función de los k tokens inspeccionados por delante (lookaheads) de cada vez en la cadena de

entrada, tomados de izquierda a derecha (Left to right), realizándose el análisis por derivaciones más a la derecha en sentido inverso (Rightmost). Las gramáticas LR(k) describen la mayor parte de los lenguajes libres de contexto, y son mucho menos restrictivas que las gramáticas LL(k). Sin embargo la complejidad de los analizadores sintácticos LR(k), hace que la mayor parte de estos se construyan por medio de herramientas software como por ejemplo el yacc incluido en el sistema operativo UNIX.

Análisis sintáctico descendente Los analizadores sintácticos descendentes construyen el árbol sintáctico a partir del símbolo inicial de la gramática, hasta llegar a los distintos tokens, que constituyen la sentencia a analizar. Es decir, se parte del símbolo inicial de la gramática y se van aplicando las distintas producciones hasta llegar a formar la sentencia. En el ejemplo de la figura 1, el árbol sintáctico se obtiene a partir de las reglas de derivación de <expresión> hasta llegar a la expresión. El orden de derivación es importante, siempre se deriva primero el no terminal situado más a la izquierda según se mira el árbol (derivaciones más a la izquierda).

Los principales problemas que se plantean en el análisis sintáctico descendente son dos: el retroceso (en inglés backtracking) y la recursividad a izquierdas.

El retroceso, se produce cuando se eligen mal las producciones para alcanzar la sentencia a analizar, y debe de darse marcha atrás en el proceso de análisis, para elegir otra alternativa. El retroceso se repite hasta que se ha elegido la alternativa correcta; evidentemente esto ralentiza enormemente el proceso de análisis.

La recursividad a izquierdas, se deriva de que en general se elige el criterio de tomar siempre en primera opción la alternativa más a la izquierda. Si en la gramática existen producciones de la forma: entonces el analizador sintáctico se introduce en un bucle infinito, del que no puede salir.

Para evitar la recursividad a izquierdas y el retroceso, las gramáticas deben de cumplir unas determinadas propiedades, dando lugar a una clasificación de las gramáticas. Los lenguajes de programación que se pueden describir mediante uno de estos tipos de gramáticas, llamadas LL(k), se pueden analizar en forma descendente sin retroceso, y sin recursividad a izquierdas. Las gramáticas LL(k) realizan el análisis descendente determinista, por medio del reconocimiento de la cadena de entrada de izquierda a derecha (Left to right) y que va tomando las derivaciones más a

la izquierda (Leftmost) con sólo mirar los k tokens situados a continuación de donde se halla. En general se utilizan las gramáticas LL(1) para la descripción de lenguajes, que sólo miran un token.

También existe una herramienta denominada Jack para generar analizadores sintácticos descendentes en lenguaje Java, a partir de unas especificaciones gramaticales del estilo de las herramientas clásicas de análisis sintáctico ascendente lex y yacc. Se caracteriza por:

Genera código en lenguaje Java. Las especificaciones léxicas, sintácticas y semánticas van en un fichero único Permite el uso de cualquier carácter Unicode. Realiza análisis descendente utilizando una gramática LL(k), donde se puede fijar K, es decir el

número de tokens que tiene que mirar hacia adelante (lookahead) para determinar la regla de la gramática que aplica.

En el análisis semántico utiliza tanto atributos sintetizados como heredados.

ANÁLISIS SEMÁNTICO Y TRATAMIENTO DE ERRORES

Análisis semántico

Se compone de un conjunto de rutinas independientes, llamadas por los analizadores morfológico y sintáctico. El análisis semántico utiliza como entrada el árbol sintáctico detectado por el análisis sintáctico para comprobar restricciones de tipo y otras limitaciones semánticas y preparar la generación de código. En compiladores de un solo paso, las llamadas a las rutinas semánticas se realizan directamente desde el analizador sintáctico y son dichas rutinas las que llaman al generador de código. El instrumento más utilizado para conseguirlo es la gramática de atributos. En compiladores de dos o más pasos, el análisis semántico se realiza independientemente de la generación de código, pasándose información a través de un archivo intermedio, que normalmente contiene información sobre el árbol sintáctico en forma linealizada (para facilitar su manejo y hacer posible su almacenamiento en memoria auxiliar). En cualquier caso, las rutinas semánticas suelen hacer uso de una pila (la pila semántica) que contiene la información semántica asociada a los operandos (y a veces a los operadores) en forma de registros semánticos.

Tratamiento de errores

Los errores encontrados en las distintas fases de análisis se envían a un módulo denominado manejo de errores. En el caso más sencillo puede ser un subprograma al que se le invoca enviándole el código de error, y que se encarga de escribir un mensaje con el error correspondiente, y el número de línea donde se ha producido, así como de cortar el proceso de traducción. Si se desea construir un tratamiento de errores más completo, por ejemplo detectando todos los errores del programa fuente, el módulo se complica dado que los analizadores deben proseguir su trabajo con falta de datos.

ÁRBOLES SINTÁCTICOS Árbol sintáctico, para una oración compuesta (el niño que me saludó me odia) en la que la oración subordinada es una oración de relativo. Dada una oración o construcción compleja esta puede dividirse en constituyentes sintácticos, cada uno de los cuales a su vez podría ser divisible o analizable en otros constituyentes. El conjunto de constituyentes sintácticos admite con la relación binaria de inclusión (o "ser parte de") es un conjunto parcialmente ordenado. Un árbol sintáctico es una representación de las relaciones jerárquicas entre los constituyentes sintácticos. Más formalmente, un árbol sintáctico es un grafo que representa esta relación de orden parcial. Cuando en una construcción un constituyente X es parte de un constituyente inmediato de otro constituyente más grande Y, el árbol sintáctico correspondiente tendrá una línea entre el nodo que representa a X y en nodo que representa a Y. Actualmente se acepta que toda lengua admite un análisis mediante árboles sintácticos binarios. En los árboles gráficos los núcleos sintácticos se suelen representar con una letra, por ejemplo X, seguida de un subíndice (por ejemplo ), mientras que las estructuras más complejas se señalan mediante una o dos barras superpuestas o mediante primas (por ejemplo, ) y si se trata de proyecciones máximas de un núcleo mediante la letras S antecediendo a la letra que designa al núcleo (por ejemplo SX).