Análisis de abajo hacia arriba - Bottom-up parsing

En informática , el análisis sintáctico revela la estructura gramatical del texto de entrada lineal, como primer paso para descubrir su significado. El análisis de abajo hacia arriba 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 del nivel más alto para que dure.

De abajo hacia arriba versus de arriba hacia abajo

El nombre de abajo hacia arriba proviene del concepto de un árbol de análisis , en el que las partes más detalladas están en la parte inferior del árbol invertido, y las estructuras más grandes compuestas a partir de ellas están 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 de abajo hacia arriba descubre y procesa ese árbol comenzando desde el extremo inferior izquierdo, y avanza gradualmente hacia arriba y hacia la derecha. Un analizador puede actuar en los niveles bajo, medio y más alto de la jerarquía de estructura sin ni siquiera crear un árbol de datos real; el árbol está entonces simplemente implícito en las acciones del analizador. El análisis 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.

Árbol de análisis típico para
A = B + C * 2; D = 1
Pasos de análisis de abajo hacia arriba
Pasos de análisis de arriba hacia abajo

Lo opuesto a esto es el análisis de arriba hacia abajo , en el que la estructura general de la entrada se decide (o adivina) primero, 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 la parte superior 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 la gramática de un idioma tiene varias reglas que pueden comenzar con los mismos símbolos del extremo izquierdo pero con terminaciones diferentes, entonces esa gramática puede manejarse de manera eficiente mediante un análisis determinista de abajo hacia arriba, pero no puede manejarse de arriba hacia abajo sin conjeturas y retrocesos . Por lo tanto, los analizadores de abajo hacia arriba manejan una gama algo mayor de gramáticas del lenguaje informático que los analizadores de arriba hacia abajo deterministas.

El análisis de abajo hacia arriba a veces se realiza retrocediendo . Pero mucho más comúnmente, el análisis de abajo hacia arriba se realiza mediante un analizador shift-reduce como un analizador LALR .

Ejemplos

Algunos de los analizadores que utilizan el análisis de abajo hacia arriba incluyen:

Referencias