El análisis de arriba hacia abajo en informática es una estrategia de análisis en la que primero se observa el nivel más alto del árbol de análisis y se avanza por el árbol de análisis 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 que consiste en analizar relaciones de datos desconocidos mediante la formulación de hipótesis sobre estructuras generales de árboles de análisis y, a continuación, considerando si las estructuras fundamentales conocidas son compatibles con la hipótesis. Se utiliza en el análisis de lenguajes naturales y de lenguajes informáticos .
El análisis de arriba hacia abajo puede considerarse 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 mediante la expansión de 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 sí admiten la ambigüedad y la recursión por la izquierda en tiempo polinomial y que generan representaciones de tamaño polinomial 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 obtenido en una regla de producción y luego procediendo a la siguiente regla de producción para cada símbolo no terminal encontrado. De esta manera, el análisis comienza en la izquierda del lado del resultado (lado derecho) de la regla de producción y evalúa los no terminales desde la izquierda primero y, por lo tanto, avanza hacia abajo en el árbol de análisis para cada nuevo no terminal antes de continuar con el siguiente símbolo para una regla de producción.
Por ejemplo:
que produce la cadena A = acdf
coincidiría e intentaría coincidir a continuación. Entonces se intentaría. Como se puede esperar, algunos idiomas son más ambiguos que otros. Para un idioma 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 idioma no ambiguo puede ser analizado por una gramática LL(1) donde el (1) significa que el analizador lee hacia adelante un token a la vez. Para que un analizador LL analice un idioma ambiguo, el analizador debe mirar hacia adelante 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 recursión por la izquierda no puede ser analizada por un analizador sintáctico descendente recursivo ingenuo a menos que se convierta a una forma recursiva por 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 sintáctico 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 limita un análisis recursivo por la izquierda directo en constante crecimiento imponiendo restricciones de profundidad con respecto a la longitud de entrada y la posición de entrada actual. [6] Ese algoritmo se amplió a un algoritmo de análisis completo para adaptarse a la recursión por la izquierda indirecta (al comparar el contexto calculado previamente con el contexto actual) así como a la recursión por la izquierda directa en tiempo polinomial , y para generar representaciones compactas de tamaño polinomial del número potencialmente exponencial de árboles de análisis para gramáticas altamente ambiguas por Frost, Hafiz y Callaghan en 2007. [4] Desde entonces, el algoritmo se ha implementado como un conjunto de combinadores de analizadores sintácticos 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 grafos (GSS) además de la restricción mencionada anteriormente para dar cabida a la recursión por la izquierda "fusionando" pilas con prefijos comunes y evitando la recursión infinita, reduciendo así el número y el contenido de cada pila, reduciendo así 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 restricción de recursión por la izquierda y un analizador LL(k) para analizar cadenas de entrada en relación con un CFG determinado. [7] [8]
Cuando un 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 con el fin de producir todos los árboles de análisis posibles, lo que eventualmente requeriría un espacio de memoria exponencial. El problema de la complejidad temporal exponencial en analizadores de arriba hacia abajo construidos como conjuntos de funciones recursivas mutuas fue resuelto por Norvig 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 evitar cálculos redundantes para acomodar cualquier forma de CFG en tiempo polinomial ( Θ (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 polinomial para árboles de análisis ambiguos potencialmente exponenciales mediante "representación compacta" y "agrupamiento de ambigüedades locales". Su representación compacta es comparable con la representación compacta de Tomita del análisis de abajo hacia arriba . [10]
Al utilizar PEG, otra representación de gramáticas, los analizadores de Packrat proporcionan un algoritmo de análisis elegante y potente. Consulte Análisis de gramática de expresiones .
Algunos de los analizadores que utilizan análisis de arriba hacia abajo incluyen:
