parsing - sintactico - ¿Por qué el análisis ascendente es más común que el análisis descendente?

analizador top down (6)

Parece que los analizadores de descendencia recursiva no solo son los más sencillos de explicar, sino también los más sencillos de diseñar y mantener. No se limitan a las gramáticas LALR (1), y el código en sí puede ser comprendido por simples mortales. En contraste, los analizadores de abajo hacia arriba tienen límites en las gramáticas que pueden reconocer, y deben ser generados por herramientas especiales (porque las tablas que los impulsan son casi imposibles de generar a mano).

¿Por qué, entonces, es más común el análisis de abajo hacia arriba (es decir, cambio-reducción) que el análisis de arriba hacia abajo (es decir, descenso recursivo)?

Los analizadores de descendencia recursiva intentan hipotetizar la estructura general de la cadena de entrada, lo que significa que se produce una gran cantidad de prueba y error antes de llegar al final de la cadena. Esto los hace menos eficientes que los analizadores de abajo hacia arriba, que no necesitan tales motores de inferencia.

La diferencia de rendimiento se magnifica a medida que aumenta la complejidad de la gramática.

Nunca vi una comparación real entre analizador descendente y de reducción de cambios:

solo 2 programas pequeños se ejecutaron al mismo tiempo, uno al lado del otro, uno que usa el enfoque de arriba hacia abajo y el otro que usa el enfoque de abajo hacia arriba, cada uno de aproximadamente ~ 200 líneas de código,

capaz de analizar cualquier tipo de operador binario personalizado y expresión matemática, los dos comparten el mismo formato de declaración gramatical, y luego posiblemente agregar declaraciones de variables y afectaciones para mostrar cómo se pueden implementar ''hacks'' (no libres de contexto).

Entonces, ¿cómo hablar honestamente de algo que nunca hicimos: comparar rigurosamente los dos enfoques?

Para agregar a otras respuestas, es importante darse cuenta de que, además de la eficiencia, los analizadores de abajo hacia arriba pueden aceptar significativamente más gramáticas que los analizadores de descendencia recursiva. Los analizadores descendentes, ya sean predictivos o no, solo pueden tener 1 token de búsqueda anticipada y fallan si el token actual y lo que sigue inmediatamente al token se pueden derivar utilizando dos reglas diferentes. Por supuesto, podría implementar el analizador para tener más lookaheads (por ejemplo, LL (3)), pero ¿hasta qué punto está dispuesto a empujarlo antes de que se vuelva tan complejo como un analizador de abajo hacia arriba? Por otro lado, los analizadores de abajo hacia arriba (específicamente LALR), mantienen una lista de los firsts y los follows y pueden manejar los casos en que los analizadores de arriba hacia abajo no pueden.

Por supuesto, la ciencia de la computación se trata de compensaciones. Si su gramática es lo suficientemente simple, tiene sentido escribir un analizador de arriba hacia abajo. Si es complejo (como las gramáticas de la mayoría de los lenguajes de programación), es posible que tenga que usar un analizador de abajo hacia arriba para aceptar con éxito la entrada.

Se deriva de un par de cosas diferentes.

BNF (y la teoría de las gramáticas y demás) proviene de la lingüística computacional: gente que investiga el análisis del lenguaje natural. BNF es una forma muy atractiva de describir una gramática, por lo que es natural querer consumir estas notaciones para producir un analizador.

Desafortunadamente, las técnicas de análisis de arriba hacia abajo tienden a caer cuando se aplican a tales notaciones, porque no pueden manejar muchos casos comunes (por ejemplo, recursión izquierda). Esto te deja con la familia LR, que se desempeña bien y puede manejar las gramáticas, y dado que están siendo producidos por una máquina, ¿a quién le importa cómo se ve el código?

Sin embargo, tienes razón: los analizadores de arriba hacia abajo funcionan más "intuitivamente", por lo que son más fáciles de depurar y mantener, y una vez que tienes un poco de práctica, son tan fáciles de escribir como los generados por las herramientas. (Especialmente cuando te involucras en el cambio / reducir el infierno). Muchas de las respuestas hablan sobre el rendimiento del análisis, pero en la práctica los analizadores de arriba hacia abajo a menudo se pueden optimizar para que sean tan rápidos como los analizadores generados por la máquina.

Es por eso que muchos compiladores de producción utilizan analizadores y analizadores escritos a mano.

Si elige un potente generador de analizador, puede codificar su gramática sin preocuparse por propiedades peculiares. (LA) LR significa que no tienes que preocuparte por la recursión de la izquierda, un dolor de cabeza menos. GLR significa que no tiene que preocuparse por la ambigüedad local o lookahead.

Y los analizadores de abajo hacia arriba tienden a ser bastante eficientes. Entonces, una vez que haya pagado el precio de un poco de maquinaria complicada, es más fácil escribir grammers y los analizadores funcionan bien.

Debería esperar ver este tipo de elección dondequiera que haya una construcción de programación que comúnmente ocurre: si es más fácil de especificar y funciona bastante bien, incluso si la maquinaria es complicada, la maquinaria compleja ganará. Como otro ejemplo, el mundo de la base de datos ha ido a las herramientas relacionales, a pesar del hecho de que usted mismo puede construir un archivo indexado manualmente. Es más fácil escribir los esquemas de datos, es más fácil especificar los índices, y con una maquinaria suficientemente complicada detrás (no tiene que mirar los engranajes, solo los usa), pueden ser bastante rápidos sin casi esfuerzo. Mismas razones

Tengo dos conjeturas, aunque dudo que lo explique completamente:

El análisis de arriba hacia abajo puede ser lento. Los analizadores de descendencia recursiva pueden requerir un tiempo exponencial para completar su trabajo. Eso pondría severas limitaciones en la escalabilidad de un compilador que usa un analizador de arriba hacia abajo.
Mejores herramientas. Si puede expresar el lenguaje en alguna variante de EBNF, entonces es probable que pueda Lex / Yacc a su manera más allá de un montón de código tedioso. No parece haber tantas herramientas para ayudar a automatizar la tarea de armar un analizador de arriba hacia abajo. Y seamos sinceros, el código del analizador simplemente no es la parte divertida de jugar con idiomas.