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 de nivel más bajo del texto, antes de sus estructuras de nivel medio, y deja la estructura general de nivel más alto para durar. [1]
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 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 de abajo hacia arriba 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 más alto de la jerarquía de la 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.
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 la finalización de todos los detalles del 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 diferentes terminaciones, 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 de
Algunos de los analizadores que utilizan el análisis de abajo hacia arriba incluyen:
- Analizador de precedencia
- Analizador de contexto delimitado (BC)
- LR analizador ( L eft a derecha, R derivación ightmost a la inversa)
- Analizador sintáctico LR simple (SLR)
- Analizador LALR (anticipado)
- Analizador sintáctico canónico LR (LR (1))
- Analizador GLR (generalizado) [3]
- Analizador CYK (Cocke – Younger – Kasami)
- Analizador sintáctico de ascenso recursivo
- Analizador de cambio-reducción
Referencias
- ^ Arvind Kumar Bansal (14 de diciembre de 2013). Introducción a los lenguajes de programación . Prensa CRC. ISBN 978-1-4665-6514-2.
- ^ Compiladores: principios, técnicas y herramientas (segunda edición), por Alfred Aho, Monica Lam, Ravi Sethi y Jeffrey Ullman, Prentice Hall 2006.
- ^ Dick Grune; Ceriel JH Jacobs (29 de octubre de 2007). Técnicas de análisis: una guía práctica . Springer Science & Business Media. ISBN 978-0-387-68954-8.