ANÁLISIS SINTÁCTICO DESCENDENTE

Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia. Se puede considerar también como un intento de construir un árbol de análisis sintáctico para la entrada comenzando desde la raíz y creando los nodos del árbol en orden previa. Empezamos derivando por la izquierda, y los caracteres son leídos de izquierda a derecha, se lee 1 solo elemento de entrada. Para trabajar el análisis sintáctico descendente se debe realizar primeramente algunas operaciones, las cuales son:

Eliminar Ambigüedad Eliminar Recursividad por la Izquierda debido a que da lugar a un bucle infinito de

recursión. Factorizar Primeros y siguientes

• Ambigüedad

Una gramática es ambigua si derivando de forma diferente con el mismo tipo de derivación se llega al mismo resultado. Además una gramática es ambigua cuando genera más de un árbol de derivación. Ejemplo: Considérese la gramática

E -> E + E E -> E * E E -> ( E ) E -> id | num

Para eliminar la ambigüedad se debe reescribir la gramática, o replantear el diseño de la misma para encontrar una gramática no ambigua equivalente (que genere el mismo lenguaje).

• Recursividad por la Izquierda Una gramática es recursiva por la izquierda si tiene alguna producción que sea recursiva por la izquierda, o bien si tiene un no Terminal A tal que existe una derivación A->Aα para alguna cadena. Es decir por simple observación podemos identificar que el no terminal A vuelve a ser el primero por la izquierda.

Para eliminar la recursividad por la izquierda se utiliza la siguiente formula.

Ejemplo: Gramática Recursiva

• Factorizar por la izquierda Si dos producciones alternativas de un símbolo A empiezan igual, no se sabrá por cuál de ellas seguir. Para ello se deberá reescribir las producciones de A para retrasar la decisión hasta haber visto lo suficiente de la entrada como para elegir la opción correcta. Regla general para factorizar por la izquierda Encontrar el prefijo más largo común a dos o más producciones de A, pero siempre aquél que sea común a más producciones. Si existe un prefijo común más corto en varias producciones y otro más largo en un par de ellas, hay que eliminar primero el más corto común a las varias ( = tal que | | < | |).

Ejemplo: Sustituir las producciones:

Donde indica todas las alternativas que no empiezan por , por:

• Conjuntos de Predicción: Primeros y siguientes

Son conjuntos de símbolos terminales: Ayudan a predecir qué regla se debe aplicar para el no terminal que hay que derivar. Se construyen a partir de los símbolos de las partes derechas de las producciones de la

gramática. El analizador consulta el siguiente símbolo en la entrada. si pertenece al conjunto de

predicción de una regla aplica esa regla, si no da error.

Los conjuntos de predicción se calculan: En función de los primeros símbolos que puede generar la parte derecha de la regla, y Cuando la parte derecha puede generar la cadena vacía, en función de los símbolos que

pueden aparecer a continuación de la parte izquierda de la regla en una forma sentencial derivable del símbolo inicial.

Para poder definir los conjuntos de predicción es necesario determinar: Conjunto de primeros calcular los primeros símbolos que genera una cadena de

terminales y no terminales. Conjunto de siguientes obtener los símbolos que pueden seguir a un no terminal en una

forma sentencial.

ANÁLISIS SINTÁCTICO ASCENDENTE

Parte de la cadena de entrada para construir la inversa de una derivación por la derecha. Genera el árbol de análisis sintáctico partiendo de las hojas hasta alcanzar el axioma. Se construye el árbol de análisis sintáctico de la cadena de entrada desde las hojas hasta la raíz o de abajo hacia arriba, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente (si hablamos del caso con retroceso). Tanto si hay retroceso como si no, en un momento dado, la cadena de entrada estará dividida en dos partes α y β: En las hojas tenemos la cadena a analizar (los símbolos terminales) que se intentan reducir al axioma, que se encontrara en la raíz, si la cadena es correcta sintácticamente. ¿Cómo construir el árbol? Se trata de desplazarse en la entrada hasta encontrar una subcadena de símbolos que represente la parte derecha de una producción, en ese momento sustituimos esa subcadena por el no-terminal de la parte izquierda correspondiente de la producción, la reducimos. Los métodos ascendentes se caracterizan porque analizan la cadena de componentes léxicos de izquierda a derecha, obtienen la derivación más a la derecha y el ´árbol de derivación se construye desde la raíz hasta las hojas. El analizador sintáctico para poder trabajar puede realizar una de las cuatro operaciones siguientes:

• Aceptar: Cadena reconocida. • Rechazar: La entrada no es válida. • Reducir: Aplicar una regla de producción a los elementos de α.

Mediante reducciones y desplazamientos, tenemos que llegar a aceptar o rechazar la cadena de entrada. Antes de hacer los desplazamientos tenemos que hacerles todas las reducciones posibles a α. Cuando β es el axioma inicial y α es la tira nula, se acepta la cadena de entrada. Cuando β no es la tira nula o α no es el axioma inicial y no se puede aplicar ninguna regla, entonces se rechaza la cadena de entrada.

Análisis Ascendente con retroceso. Cuando se da cuenta que llega a una situación en la que no puede continuar, entonces vuelve atrás deshaciendo todos los cambios. En el análisis con retroceso no se permiten las reglas J, puesto que estas se podrán aplicar de forma indefinida.

Analizadores LR Es una técnica eficiente de análisis sintáctico ascendente que se puede utilizar para analizar una amplia clase de gramáticas de contexto libre. La técnica se denomina análisis sintáctico LR(k); la “L” es por el examen de la entrada de izquierda a derecha (en inglés, left-to-right), la “R” por construir una derivación por la derecha (en inglés, rightmost derivation) en orden inverso, y la k por el número de símbolos de entrada de examen por anticipado utilizados para tomar las decisiones del análisis sintáctico. Cuando se omite, se asume que k, es 1. El análisis LR es atractivo por varias razones:

• Pueden reconocer la inmensa mayoría de los lenguajes de programación que puedan ser generados mediante gramáticas de contexto-libre.

• El método de funcionamiento de estos analizadores posee la ventaja de localizar un error sintáctico en el mismo instante que se produce con lo que se adquiere una gran eficiencia de tiempo de compilación frente a procedimientos menos adecuados como puedan ser los de retroceso.

El principal inconveniente del método es que supone demasiado trabajo construir un analizador sintáctico LR a mano para una gramática de un lenguaje de programación típico. Se necesita una herramienta especializada - un generador de analizadores sintácticos LR - . Pero si existen disponibles varios de estos generadores. Con este generador se puede escribir una gramática de contexto libre y el generador produce automáticamente un analizador sintáctico de dicha gramática. Si la gramática contiene ambigüedades u otras construcciones difíciles de analizar en un examen de izquierda a derecha de la entrada, el generador puede localizar dichas construcciones e informar al diseñador del compilador de su presencia. Existen tres técnicas para construir una tabla de análisis sintáctico LR para una gramática. El primer método, llamado LR sencillo (SLR, en inglés) es el más fácil de implantar, pero el menos poderoso de los tres. Puede que no consiga producir una tabla de análisis sintáctico para algunas gramáticas que otros métodos si consiguen. El segundo método, llamado LR canónico, es el más poderoso y costoso. El tercer método, llamado LR con examen por anticipado (LALR, en inglés), está entre los otros dos en cuanto a poder y costo. El método LALR funciona con las gramáticas de la mayoría de los lenguajes de programación y, con un poco de esfuerzo, se puede implantar en forma eficiente. Funcionalmente hablando, un analizador LR consta de dos partes diferenciadas, un programa de proceso y una tabla del análisis. El programa de proceso posee un funcionamiento muy simple y permanece invariable de analizador a analizador. Según sea la gramática a procesar deberá variarse el contenido de la tabla de análisis que es la que identifica plenamente al analizador.

DIFERENCIA ENTRE ANÁLISIS SINTÁCTICO DESCENDENTE Y ASCENDENTE

¿Cuándo usar recursión a derecha o a izquierda? Ejemplo: Al momento de programar: Reconocer identificadores separados por comas

id, id, id, ... , id

Podríamos optar por 2 gramáticas diferentes (1 y 2):

1. lista -> ID | lista ‘,’ ID

2. lista -> ID | ID ‘,’ lista

¿Qué diferencia hay entre 1 y 2?

1. Alternativamente se va desplazando y reduciendo con lo que el tamaño de la pila se

mantiene siempre estable (es más conveniente, pero no siempre se puede aplicar la recursión a la izquierda).

2. Si hacemos la recursión a derecha, siempre existe la posibilidad de que se desborde la pila.

Por la forma de construir las tablas pueden aparecer conflictos: Shift/Reduce Reduce/Reduce Shift/Reduce: aparece cuando en la tabla de acciones hay que poner una R de

reducir y una D de desplazar, el conflicto es que el programa no sabe si reducir o desplazar.

Ejemplo: expr -> expr ‘+’ expr

| NUM

En gramáticas con ambigüedad se produce el conflicto shift/reduce (relacionado con el hecho de considerar la gramática como asociativa a izquierda o asociativa a derecha). - Reduce/Reduce: Se pueden utilizar dos reglas para reducir y no sabe cual elegir. Ejemplo:

S -> aaBdd S -> aCd B -> a C -> aa

Esta gramática reconoce estas dos secuencias de tokens:

aaadd aaad

Suponemos la secuencia

Aquí aunque lo correcto sería reducir por C, como el reconocimiento LALR(1) sólo permite ver un token a la entrada, pues sólo se ve la d. Como no se sabe si detrás hay otra d o no, pues es imposible tomar una decisión. Estamos ante una gramática LALR(2). Los conflictos reduce/reduce se pueden eliminar en la mayoría de los casos. Ejemplo: S -> aaBdd S Ú aaadd S -> aCd S Ú aaad B -> a C -> aa En este caso lo que se ha hecho ha sido añadir las secuencias que producen el conflicto como parte de la gramática. WEBGRAFÍA:

• Fausto Loja Mora. Análisis Sintáctico Descendente LL(1). [Seriada en línea]. Pág.1-3. Disponible en: URL: http://faustol.wordpress.com/2007/09/05/anlisis-sintctico descendente-ll1/, [Consultado Diciembre 14, 2010]-

• Tema 4. Análisis Sintáctico Descendente. [Seriada en línea]. Pág.2-7. Disponible en: URL: http://www2.uah.es/jcaceres/uploaded/teoria/LenguajesProgramacion/tema4.pdf, [Consultado Diciembre 14, 2010]-

• Análisis Sintáctico Descendente. [Seriada en línea]. Pág.1-47. Disponible en: URL: http://www.lsi.uned.es/procleng/apuntes/2006-2007/AnalisisSintacticoDescendente.pdf, [Consultado Diciembre 14, 2010]-

• Análisis Sintáctico Ascendente. [Seriada en línea]. Pág.2-43. Disponible en: URL: http://serdis.dis.ulpgc.es/~ii-pl/ftp/transp/tr-asint-ver.pdf, [Consultado Diciembre 14, 2010]-

• Tema 3. Análisis Sintáctico. [Seriada en línea]. Pág.1-35. Disponible en: URL: http://www.lcc.uma.es/~galvez/ftp/tci/tictema3.pdf, [Consultado Diciembre 14, 2010]-