Análisis de arriba hacia abajo

El análisis sintáctico descendente en informática es una estrategia de análisis sintáctico en la que primero se examina el nivel más alto del árbol de análisis sintáctico y se trabaja hacia abajo en el árbol de análisis sintáctico utilizando las reglas de reescritura de una gramática formal . ^{[ 1 ]} Los analizadores LL son un tipo de analizador que utiliza una estrategia de análisis sintáctico descendente.

El análisis sintáctico descendente es una estrategia para analizar relaciones de datos desconocidas mediante la formulación de hipótesis sobre estructuras generales de árboles de análisis sintáctico , y posteriormente se considera si las estructuras fundamentales conocidas son compatibles con la hipótesis. Se utiliza tanto en el análisis de lenguajes naturales como de lenguajes de programación .

El análisis sintáctico descendente puede considerarse un intento de encontrar las derivaciones más a la izquierda de una secuencia de entrada mediante la búsqueda de árboles de análisis sintáctico utilizando una expansión descendente de las reglas gramaticales formales dadas . La elección inclusiva se utiliza para acomodar la ambigüedad mediante la expansión de todos los lados derechos alternativos de las reglas gramaticales. ^{[ 2 ]}

Las implementaciones simples de análisis descendente no terminan para gramáticas recursivas izquierdas , y el análisis descendente con retroceso puede tener una complejidad temporal exponencial con respecto a la longitud de la entrada para CFG ambiguas . ^{[ 3 ]} Sin embargo, Frost, Hafiz y Callaghan han creado analizadores descendentes más sofisticados, ^{[ 4 ] [ 5 ]} que sí admiten ambigüedad y recursión izquierda en tiempo polinomial y que generan representaciones de tamaño polinomial del número potencialmente exponencial de árboles de análisis.

Un compilador analiza la entrada de un lenguaje de programación y la convierte en una representación interna, haciendo coincidir los símbolos entrantes con las reglas de producción . Estas reglas se definen comúnmente mediante la forma Backus-Naur . Un analizador LL realiza un análisis descendente aplicando cada regla de producción a los símbolos entrantes, comenzando por el símbolo más a la izquierda resultante de la regla y continuando con la siguiente regla para cada símbolo no terminal encontrado. De esta forma, el análisis comienza en el lado izquierdo del resultado (lado derecho) de la regla de producción y evalúa primero los no terminales desde la izquierda, recorriendo así el árbol de análisis para cada nuevo no terminal antes de continuar con el siguiente símbolo de la regla de producción.

Por ejemplo:

• ${\displaystyle A\rightarrow aBC}$
• ${\displaystyle B\rightarrow c\mid cd}$
• ${\displaystyle C\rightarrow df\mid por ejemplo}$

lo que produce la cadena A = acdf

coincidiría${\displaystyle A\rightarrow aBC}$y tratar de igualar${\displaystyle B\rightarrow c\mid cd}$siguiente. Entonces${\displaystyle C\rightarrow df\mid por ejemplo}$Se intentaría. Como es de esperar, algunos lenguajes son más ambiguos que otros. En un lenguaje no ambiguo, donde todas las producciones de un no terminal generan cadenas distintas, la cadena producida por una producción no comenzará con el mismo símbolo que la producida por otra. Un lenguaje no ambiguo puede ser analizado por una gramática LL(1), donde el (1) indica que el analizador lee un token a la vez. Para que un lenguaje ambiguo sea analizado por un analizador LL, este debe anticipar más de un símbolo, por ejemplo, LL(3).

La solución común a este problema es utilizar un analizador LR , que es un tipo de analizador shift-reduce y realiza un análisis de abajo hacia arriba .

Una gramática formal que contiene recursión izquierda no puede ser analizada por un analizador sintáctico descendente recursivo ingenuo a menos que se convierta a una forma recursiva derecha débilmente equivalente. Sin embargo, investigaciones recientes demuestran que es posible incorporar gramáticas recursivas izquierdas (junto con todas las demás formas de gramáticas libres de contexto generales ) en un analizador descendente más sofisticado mediante el uso de la restricción. Frost y Hafiz describieron en 2006 un algoritmo de reconocimiento que admite gramáticas ambiguas y limita un análisis recursivo izquierdo directo cada vez mayor mediante la imposición de restricciones de profundidad con respecto a la longitud de entrada y la posición de entrada actual. ^{[ 6 ]} Dicho algoritmo fue extendido a un algoritmo de análisis completo para admitir tanto la recursión izquierda indirecta (mediante la comparación del contexto calculado previamente con el contexto actual) como la directa en tiempo polinomial , y para generar representaciones compactas de tamaño polinomial del número potencialmente exponencial de árboles de análisis para gramáticas altamente ambiguas. ^{[ 4 ]} Desde entonces, el algoritmo se ha implementado como un conjunto de combinadores de analizadores 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 ^{[ 5 ]} de los autores, que fue presentado en PADL'08. El sitio web de X-SAIGA contiene más información sobre los algoritmos y los detalles de implementación.

Además, se puede utilizar una pila estructurada en grafos, además de la limitación mencionada anteriormente, para acomodar la recursión izquierda mediante la "fusión" de pilas con prefijos comunes y la prevención de la recursión infinita, reduciendo así el número y el contenido de cada pila, y por consiguiente, la complejidad temporal y espacial del analizador. Esto da lugar a un algoritmo conocido como análisis LL generalizado , en el que se utiliza un GSS, una limitación de la recursión izquierda y un analizador LL(k) para analizar cadenas de entrada en relación con una CFG dada . ^{[ 7 ] [ 8 ]}

Cuando un analizador descendente intenta analizar una entrada ambigua con respecto a una gramática libre de contexto (GLC) ambigua, puede necesitar un número exponencial de pasos (con respecto a la longitud de la entrada) para probar todas las alternativas de la GLC y producir todos los árboles de análisis posibles, lo que eventualmente requeriría un espacio de memoria exponencial. El problema de la complejidad temporal exponencial en analizadores descendentes construidos como conjuntos de funciones mutuamente recursivas fue resuelto por Norvig en 1991. ^{[ 9 ]} 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 aplicar un analizador sintáctico pen una posición jde forma memorable y reutilizar los resultados siempre que surja la misma situación. Frost, Hafiz y Callaghan ^{[ 4 ] [ 5 ]} también utilizan la memorización para evitar cálculos redundantes y así acomodar cualquier forma de CFG en tiempo polinomial ( Θ (n4 ⁾ para gramáticas recursivas por la izquierda y Θ (n3 ⁾ para gramáticas no recursivas por la izquierda). Su algoritmo de análisis sintáctico descendente también requiere espacio polinomial para árboles de análisis sintáctico potencialmente exponenciales ambiguos mediante la «representación compacta» y la «agrupación de ambigüedades locales». Su representación compacta es comparable con la representación compacta de análisis sintáctico ascendente de Tomita . ^{[ 10 ]}

Utilizando PEG, otra representación de gramáticas, los analizadores packrat proporcionan un algoritmo de análisis sintáctico elegante y potente. Véase Análisis de gramáticas de expresiones .

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

• Analizadores sintácticos de gramática de cláusulas definidas ^{[ 11 ]}
• Analizador sintáctico descendente recursivo
• Analizador predictivo
• Analizador Earley

• Análisis de abajo hacia arriba
• Análisis sintáctico
• Gramática de expresiones de análisis sintáctico

• X-SAIGA - Especificaciones ejecutables de gramáticas