El análisis de arriba hacia abajo en informática es una estrategia de análisis en la que primero se mira el nivel más alto del árbol de análisis y se trabaja hacia abajo utilizando las reglas de reescritura de una gramática formal . [1] Los analizadores LL son un tipo de analizador que utiliza una estrategia de análisis de arriba hacia abajo.
El análisis de arriba hacia abajo es una estrategia para analizar relaciones de datos desconocidas mediante la hipótesis de estructuras generales de árbol de análisis y luego considerando si las estructuras fundamentales conocidas son compatibles con la hipótesis. Ocurre en el análisis tanto de lenguajes naturales como de lenguajes informáticos .
El análisis de arriba hacia abajo puede verse como un intento de encontrar derivaciones más a la izquierda de un flujo de entrada mediante la búsqueda de árboles de análisis utilizando una expansión de arriba hacia abajo de las reglas gramaticales formales dadas . La elección inclusiva se utiliza para dar cabida a la ambigüedad ampliando todos los lados derechos alternativos de las reglas gramaticales. [2]
Las implementaciones simples de análisis de arriba hacia abajo no terminan para gramáticas recursivas por la izquierda , y el análisis de arriba hacia abajo con retroceso puede tener una complejidad temporal exponencial con respecto a la longitud de la entrada para CFG ambiguos . [3] Sin embargo, Frost, Hafiz y Callaghan han creado analizadores de arriba hacia abajo más sofisticados, [4] [5] que se adaptan a la ambigüedad y la recursividad por la izquierda en el tiempo polinómico y que generan representaciones de tamaño polinómico del número potencialmente exponencial. de árboles de análisis.
Un compilador analiza la entrada de un lenguaje de programación en una representación interna haciendo coincidir los símbolos entrantes con las reglas de producción . Las reglas de producción se definen comúnmente utilizando la forma Backus-Naur . Un analizador LL es un tipo de analizador que realiza un análisis de arriba hacia abajo aplicando cada regla de producción a los símbolos entrantes, trabajando desde el símbolo más a la izquierda generado en una regla de producción y luego pasando a la siguiente regla de producción para cada símbolo no terminal. encontrado. De esta manera, el análisis comienza en el lado izquierdo del resultado (lado derecho) de la regla de producción y evalúa primero los no terminales de la izquierda y, por lo tanto, avanza por el árbol de análisis para cada nuevo no terminal antes de continuar con el siguiente. símbolo de una regla de producción.
Por ejemplo:
que produce la cadena A = acdf
coincidiría e intentaría igualar el siguiente. Entonces sería juzgado. Como es de esperar, algunos idiomas son más ambiguos que otros. Para un lenguaje no ambiguo, en el que todas las producciones para un no terminal producen cadenas distintas, la cadena producida por una producción no comenzará con el mismo símbolo que la cadena producida por otra producción. Un lenguaje no ambiguo puede ser analizado mediante una gramática LL(1) donde (1) significa que el analizador lee un token a la vez. Para que un analizador LL analice un lenguaje ambiguo, el analizador debe anticipar más de 1 símbolo, por ejemplo, LL(3).
La solución común a este problema es utilizar un analizador LR , que es un tipo de analizador de desplazamiento-reducción y realiza un análisis de abajo hacia arriba .
Una gramática formal que contiene recursividad hacia la izquierda no puede ser analizada por un analizador de descenso recursivo ingenuo a menos que se convierta a una forma recursiva hacia la derecha débilmente equivalente. Sin embargo, investigaciones recientes demuestran que es posible acomodar gramáticas recursivas por la izquierda (junto con todas las demás formas de CFG generales ) en un analizador descendente más sofisticado mediante el uso de reducción. Frost y Hafiz describieron en 2006 un algoritmo de reconocimiento que se adapta a gramáticas ambiguas y restringe un análisis recursivo directo a la izquierda cada vez mayor al imponer restricciones de profundidad con respecto a la longitud de entrada y la posición de entrada actual. [6] Ese algoritmo se extendió a un algoritmo de análisis completo para dar cabida a la recursividad indirecta (mediante la comparación del contexto previamente calculado con el contexto actual), así como directa a la izquierda en tiempo polinómico , y para generar representaciones compactas de tamaño polinómico del número potencialmente exponencial de árboles de análisis para gramáticas altamente ambiguas de Frost, Hafiz y Callaghan en 2007. [4] Desde entonces, el algoritmo se ha implementado como un conjunto de combinadores de analizadores escritos en el lenguaje de programación Haskell . Los detalles de implementación de este nuevo conjunto de combinadores se pueden encontrar en un artículo [5] de los autores, que se presentó en PADL'08. El sitio X-SAIGA tiene más información sobre los algoritmos y los detalles de implementación.
Además, se puede utilizar una pila estructurada en gráficos (GSS) además de la reducción antes mencionada para dar cabida a la recursividad hacia la izquierda "fusionando" pilas con prefijos comunes y evitando la recursividad infinita, reduciendo así el número y el contenido de cada pila, y por lo tanto reduciendo la complejidad temporal y espacial del analizador. Esto conduce a un algoritmo conocido como análisis LL generalizado, en el que se utiliza un GSS, una reducción de recursión izquierda y un analizador LL(k) para analizar cadenas de entrada relativas a un CFG determinado. [7] [8]
Cuando el analizador de arriba hacia abajo intenta analizar una entrada ambigua con respecto a un CFG ambiguo, puede necesitar un número exponencial de pasos (con respecto a la longitud de la entrada) para probar todas las alternativas del CFG para producir todos los árboles de análisis posibles. , lo que eventualmente requeriría un espacio de memoria exponencial. Norvig resolvió el problema de la complejidad temporal exponencial en analizadores de arriba hacia abajo construidos como conjuntos de funciones mutuamente recursivas en 1991. [9] Su técnica es similar al uso de programación dinámica y conjuntos de estados en el algoritmo de Earley (1970), y tablas en el algoritmo CYK de Cocke, Younger y Kasami.
La idea clave es almacenar los resultados de la aplicación de un analizador pen una posición jmemorable y reutilizar los resultados siempre que surja la misma situación. Frost, Hafiz y Callaghan [4] [5] también utilizan la memorización para abstenerse de cálculos redundantes para acomodar cualquier forma de CFG en tiempo polinómico ( Θ (n 4 ) para gramáticas recursivas por la izquierda y Θ (n 3 ) para gramáticas no recursivas por la izquierda ). Su algoritmo de análisis de arriba hacia abajo también requiere espacio polinómico para árboles de análisis ambiguos potencialmente exponenciales mediante "representación compacta" y "agrupación de ambigüedades locales". Su representación compacta es comparable con la representación compacta de análisis ascendente de Tomita . [10]
Utilizando PEG, otra representación de gramáticas, los analizadores packrat proporcionan un algoritmo de análisis elegante y potente. Consulte Análisis de la gramática de expresiones .
Algunos de los analizadores que utilizan análisis de arriba hacia abajo incluyen:
