Análisis de arriba hacia abajo - Top-down parsing

El análisis de arriba hacia abajo en ciencias de la computación es una estrategia de análisis en la que primero se observa el nivel más alto del árbol de análisis y se trabaja hacia abajo mediante el uso de las reglas de reescritura de una gramática formal . Los analizadores de LL son un tipo de analizador que utiliza una estrategia de análisis de arriba hacia abajo.

El análisis de arriba hacia abajo es una estrategia de análisis de relaciones de datos desconocidas mediante la hipótesis de estructuras de árbol de análisis sintáctico generales y luego considerando si las estructuras fundamentales conocidas son compatibles con la hipótesis. Se produce en el análisis de ambos naturales idiomas y lenguajes de programación .

El análisis de arriba hacia abajo se puede ver como un intento de encontrar las derivaciones más a la izquierda de un flujo de entrada mediante la búsqueda de árboles de análisis utilizando una expansión de arriba hacia abajo de las reglas gramaticales formales dadas . La elección inclusiva se usa para adaptarse a la ambigüedad al expandir todos los lados derechos alternativos de las reglas gramaticales.

Las implementaciones simples de análisis de arriba hacia abajo no terminan para las gramáticas recursivas por la izquierda, y el análisis de arriba hacia abajo con retroceso puede tener una complejidad de tiempo exponencial con respecto a la longitud de la entrada para CFG ambiguos . Sin embargo, Frost, Hafiz y Callaghan han creado analizadores de arriba hacia abajo más sofisticados que se adaptan a la ambigüedad y la recursividad a la izquierda en el tiempo polinomial y que generan representaciones de tamaño polinómico del número potencialmente exponencial de árboles de análisis sintáctico.

Aplicación de lenguaje de programación

Un compilador analiza la entrada de un lenguaje de programación a una representación interna haciendo coincidir los símbolos entrantes con las reglas de producción . Las reglas de producción se definen comúnmente utilizando el formulario Backus-Naur . Un analizador LL es un tipo de analizador que realiza un análisis de arriba hacia abajo aplicando cada regla de producción a los símbolos entrantes, trabajando desde el símbolo más a la izquierda obtenido en una regla de producción y luego pasando a la siguiente regla de producción para cada símbolo no terminal encontrado. De esta manera, el análisis comienza en el lado izquierdo del lado del resultado (lado derecho) de la regla de producción y evalúa los no terminales desde el lado izquierdo primero y, por lo tanto, avanza hacia abajo en el árbol de análisis para cada nuevo no terminal antes de continuar con el siguiente. símbolo de una regla de producción.

Por ejemplo:

• ${\ displaystyle A \ rightarrow aBC}$
• ${\ Displaystyle B \ rightarrow c \ mid cd}$
• ${\ displaystyle C \ rightarrow df \ mid eg}$

su cadena será A = acdf

coincidiría e intentaría coincidir a continuación. Entonces sería probado. Como es de esperar, algunos idiomas son más ambiguos que otros. Para un lenguaje no ambiguo en el que todas las producciones para un no terminal producen cadenas distintas: la cadena producida por una producción no comenzará con el mismo símbolo que la cadena producida por otra producción. Un lenguaje no ambiguo puede ser analizado por una gramática LL (1) donde el (1) significa que el analizador lee por adelantado un token a la vez. Para que un lenguaje ambiguo sea analizado por un analizador LL, el analizador debe buscar más de 1 símbolo, por ejemplo, LL (3). ${\ displaystyle A \ rightarrow aBC}$${\ Displaystyle B \ rightarrow c \ mid cd}$${\ displaystyle C \ rightarrow df \ mid eg}$

La solución común a este problema es utilizar un analizador sintáctico LR , que es un tipo de analizador sintáctico de reducción de cambios , y realiza un análisis sintáctico de abajo hacia arriba .

Acomodar la recursividad izquierda en el análisis de arriba hacia abajo

Una gramática formal que contiene recursividad por la izquierda no puede ser analizada por un analizador de descendencia recursivo ingenuo a menos que se convierta a una forma recursiva por la derecha débilmente equivalente. Sin embargo, investigaciones recientes demuestran que es posible acomodar gramáticas recursivas por la izquierda (junto con todas las otras formas de CFG generales ) en un analizador sintáctico de arriba hacia abajo más sofisticado mediante el uso de restricciones. En 2006, Frost y Hafiz describen un algoritmo de reconocimiento que se adapta a gramáticas ambiguas y restringe un análisis recursivo directo a la izquierda en constante crecimiento imponiendo restricciones de profundidad con respecto a la longitud de entrada y la posición de entrada actual. Ese algoritmo se extendió a un algoritmo de análisis sintáctico completo. para acomodar indirectos (comparando el contexto previamente calculado con el contexto actual) así como la recursividad directa por la izquierda en tiempo polinomial , y para generar representaciones compactas de tamaño polinomial del número potencialmente exponencial de árboles de análisis sintáctico para gramáticas altamente ambiguas por Frost, Hafiz y Callaghan en 2007. Desde entonces, el algoritmo se ha implementado como un conjunto de combinadores de analizadores sintácticos escritos en el lenguaje de programación Haskell . Los detalles de implementación de este nuevo conjunto de combinadores se pueden encontrar en un artículo de los autores, que fue presentado en PADL'08. El sitio X-SAIGA tiene más información sobre los algoritmos y los detalles de implementación.

Complejidad temporal y espacial del análisis de arriba hacia abajo

Cuando el analizador de arriba hacia abajo intenta analizar una entrada ambigua con respecto a un CFG ambiguo, puede necesitar un número exponencial de pasos (con respecto a la longitud de la entrada) para probar todas las alternativas del CFG con el fin de producir todos los árboles de análisis posibles , que eventualmente requeriría espacio de memoria exponencial. El problema de la complejidad de tiempo exponencial en analizadores de arriba hacia abajo construidos como conjuntos de funciones recursivas mutuas ha sido resuelto por Norvig en 1991. Su técnica es similar al uso de programación dinámica y conjuntos de estados en el algoritmo de Earley (1970), y tablas en el algoritmo CYK de Cocke, Younger y Kasami.

La idea clave es almacenar los resultados de la aplicación de un analizador pen la posición jen un memorable y reutilizar los resultados siempre que surja la misma situación. Frost, Hafiz y Callaghan también usan la memorización para abstenerse de cálculos redundantes para acomodar cualquier forma de CFG en tiempo polinomial ( Θ (n ⁴ ) para gramáticas recursivas a la izquierda y Θ (n ³ ) para gramáticas no recursivas a la izquierda). Su algoritmo de análisis de arriba hacia abajo también requiere espacio polinomial para árboles de análisis ambiguos potencialmente exponenciales mediante 'representación compacta' y 'agrupación de ambigüedades locales'. Su representación compacta es comparable con la representación compacta de Tomita del análisis de abajo hacia arriba .

Usando PEG, otra representación de gramáticas, los analizadores sintácticos packrat proporcionan un algoritmo de análisis elegante y potente. Consulte Análisis de la gramática de expresiones .

Ejemplos

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

• Cláusula gramaticales definidas analizadores
• Analizador sintáctico de descenso recursivo
• Analizador predictivo
• Analizador Earley

Ver también

• Análisis de abajo hacia arriba
• Analizando
• Analizar la gramática de la expresión

Referencias

enlaces externos

• X-SAIGA - EJECUTABLES ESPECÍFICAS DE GRAMAS