Análisis de abajo hacia arriba

En informática , el análisis sintáctico revela la estructura gramatical de un texto lineal de entrada, 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 que sus estructuras de nivel medio, y deja la estructura general de nivel más alto para el 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 por 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 de abajo hacia arriba descubre y procesa ese árbol comenzando desde el extremo inferior izquierdo, y avanza incrementalmente hacia arriba y hacia la derecha. ^{[ 2 ]} Un analizador puede actuar sobre los niveles bajo, medio y alto de la jerarquía de la estructura sin crear nunca un árbol de datos real; el árbol es 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 una construcción antes de comprometerse con la construcción combinada.

Lo opuesto a esto es el análisis descendente , en el que la estructura general de la entrada se decide (o se infiere) primero, antes de abordar las partes de nivel medio, dejando para el final la finalización de todos los detalles de nivel más bajo. Un analizador descendente descubre y procesa el árbol jerárquico comenzando desde arriba, y avanza incrementalmente primero hacia abajo y luego hacia la derecha. El análisis descendente decide rápidamente 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 trabaja 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 lenguaje tiene varias reglas que pueden comenzar con los mismos símbolos de la izquierda pero tener terminaciones diferentes, entonces esa gramática puede ser procesada eficientemente por un analizador sintáctico ascendente determinista , pero no puede ser procesada de arriba hacia abajo sin recurrir a conjeturas y retrocesos . Por lo tanto, en la práctica, los analizadores sintácticos ascendentes manejan una gama algo mayor de gramáticas de lenguajes de programación que los analizadores sintácticos descendentes deterministas.

El análisis sintáctico ascendente a veces se realiza mediante retroceso . Pero mucho más comúnmente, el análisis sintáctico ascendente se realiza mediante un analizador de desplazamiento-reducción como un analizador LALR .

Algunos de los analizadores sintácticos que utilizan el análisis sintáctico ascendente incluyen:

• analizador de precedencia
  • analizador de precedencia simple
  • Analizador de precedencia de operadores
• Analizador sintáctico de contexto delimitado (BC)
• Analizador LR ( de izquierda a derecha, derivación más a la derecha en orden inverso )
  • Analizador LR simple (SLR)
  • Analizador LALR (con anticipación)
  • Analizador LR canónico (LR(1))
  • Analizador GLR (generalizado) ^{[ 3 ]}
• Analizador sintáctico CYK (Cocke-Younger-Kasami)
• Analizador sintáctico de ascenso recursivo
• Analizador sintáctico de desplazamiento-reducción