En informática , el análisis revela la estructura gramatical del texto de entrada lineal, como primer paso para descubrir su significado. El análisis ascendente reconoce primero los pequeños detalles del nivel más bajo del texto, antes de sus estructuras de nivel medio, y deja la estructura general de nivel más alto al final. [1]
El nombre de abajo hacia arriba proviene del concepto de árbol de análisis , en el que las partes más detalladas se encuentran en la parte inferior del árbol invertido, y las estructuras más grandes compuestas a partir de ellas se encuentran en capas sucesivamente más altas, hasta llegar a la parte superior o "raíz". "del árbol, una sola unidad describe todo el flujo de entrada. Un análisis ascendente descubre y procesa ese árbol comenzando desde el extremo inferior izquierdo y avanza gradualmente hacia arriba y hacia la derecha. [2] Un analizador puede actuar en los niveles bajo, medio y alto de la jerarquía de estructura sin crear nunca un árbol de datos real; entonces el árbol está simplemente implícito en las acciones del analizador. El análisis ascendente espera pacientemente hasta que haya escaneado y analizado todas las partes de alguna construcción antes de comprometerse con cuál es la construcción combinada.
Lo opuesto a esto es el análisis de arriba hacia abajo , en el que la estructura general de la entrada se decide (o se adivina) primero, antes de tratar con las partes de nivel medio, dejando para el final la finalización de todos los detalles del nivel más bajo. Un analizador de arriba hacia abajo descubre y procesa el árbol jerárquico comenzando desde arriba y avanza gradualmente primero hacia abajo y luego hacia la derecha. El análisis de arriba hacia abajo decide con entusiasmo qué es una construcción mucho antes, cuando solo ha escaneado el símbolo más a la izquierda de esa construcción y aún no ha analizado ninguna de sus partes. El análisis de la esquina izquierda es un método híbrido que funciona de abajo hacia arriba a lo largo de los bordes izquierdos de cada subárbol y de arriba hacia abajo en el resto del árbol de análisis.
Si una gramática de un lenguaje tiene múltiples reglas que pueden comenzar con los mismos símbolos situados más a la izquierda pero tener terminaciones diferentes, entonces esa gramática puede manejarse eficientemente mediante un análisis determinista de abajo hacia arriba, pero no puede manejarse de arriba hacia abajo sin conjeturas y retrocesos . Así, en la práctica, los analizadores ascendentes manejan una gama algo mayor de gramáticas de lenguajes informáticos que los analizadores deterministas de arriba hacia abajo.
El análisis ascendente a veces se realiza retrocediendo . Pero mucho más comúnmente, el análisis ascendente lo realiza un analizador de reducción de desplazamiento , como un analizador LALR .
Algunos de los analizadores que utilizan análisis ascendente incluyen: