En informática , el análisis sintáctico revela la estructura gramatical de un texto de entrada lineal, como primer paso para descifrar su significado. El análisis sintáctico ascendente reconoce primero los pequeños detalles de nivel más bajo del texto, antes de las estructuras de nivel medio, y deja la estructura general de nivel más alto para el final. [1]
El nombre de "de abajo hacia arriba" proviene del concepto de un árbol de análisis sintáctico , 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 que en la parte superior o "raíz" del árbol una sola unidad describe todo el flujo de entrada. Un análisis sintáctico de abajo hacia arriba descubre y procesa ese árbol comenzando desde el extremo inferior izquierdo, y avanza de manera incremental hacia arriba y hacia la derecha. [2] Un analizador sintáctico puede actuar en los niveles inferior, medio y superior de la jerarquía de la estructura sin crear nunca un árbol de datos real; el árbol está entonces meramente implícito en las acciones del analizador sintáctico. El análisis sintáctico de abajo hacia arriba espera pacientemente hasta que haya escaneado y analizado todas las partes de alguna construcción antes de comprometerse con lo que es la construcción combinada.
El opuesto de esto es el análisis de arriba hacia abajo , en el que primero se decide (o se adivina) la estructura general de la entrada, antes de tratar las partes de nivel medio, dejando la finalización de todos los detalles de nivel más bajo para el final. Un analizador de arriba hacia abajo descubre y procesa el árbol jerárquico comenzando desde arriba, y avanza de manera incremental 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 lenguaje tiene múltiples reglas que pueden comenzar con los mismos símbolos más a la izquierda pero tienen diferentes terminaciones, entonces esa gramática puede ser manejada eficientemente por un análisis determinista de abajo hacia arriba, pero no puede ser manejada de arriba hacia abajo sin conjeturas y retrocesos . Por lo tanto, los analizadores de abajo hacia arriba en la práctica manejan una gama algo más grande de gramáticas de lenguaje de computadora que los analizadores deterministas de arriba hacia abajo.
El análisis ascendente a veces se realiza mediante retroceso , pero lo más habitual es que el análisis ascendente se realice mediante un analizador de desplazamiento-reducción, como un analizador LALR .
Algunos de los analizadores que utilizan análisis de abajo hacia arriba incluyen: