top sintactico recursivo predictivo por parser izquierda factorizacion down descenso descendente analizador analisis parsing recursion

parsing - sintactico - ¿Cómo funcionan los analizadores de ascenso recursivo?



factorizacion por la izquierda (3)

¿Cómo funcionan los analizadores de ascenso recursivo? Yo mismo he escrito un analizador de descenso recursivo , pero no entiendo muy bien los analizadores LR. Lo que encontré en Wikipedia solo ha agregado a mi confusión.

Otra pregunta es por qué los analizadores de ascenso recursivo no se usan más que sus equivalentes basados ​​en tablas. Parece que los analizadores de ascenso recursivo tienen un mayor rendimiento en general.

El artículo de Wikipedia sobre el análisis de ascenso recursivo hace referencia a lo que parece ser el artículo original sobre el tema ("Análisis de LR muy rápido"). Quitar ese papel aclaró algunas cosas para mí. Cosas que noté:

  1. El artículo habla de generar código ensamblador. Me pregunto si puede hacer lo mismo que ellos si están generando código C o Java en su lugar; Consulte las secciones 4 y 5, "Recuperación de errores" y "Comprobación de desbordamiento de pila". (No estoy tratando de hacer FUD con su técnica, podría funcionar bien, solo decir que es algo que deberías considerar antes de cometer).

  2. Ellos comparan su herramienta de ascenso recursivo con su propio analizador basado en tablas. A partir de la descripción en su sección de resultados, parece que su analizador basado en tablas está "completamente interpretado"; no requiere ningún código generado personalizado. Me pregunto si hay un punto medio en el que la estructura general aún esté basada en tablas, pero usted genera un código personalizado para ciertas acciones para acelerar el proceso.

El artículo al que hace referencia la página de Wikipedia:

Otro artículo sobre el uso de la generación de código en lugar de la interpretación de tablas:

Además, tenga en cuenta que el análisis de descendencia recursiva no es la forma más rápida de analizar lenguajes basados ​​en la gramática LL:

El clásico libro del dragón explica muy bien cómo funcionan los analizadores LR. También hay técnicas de análisis. Una guía práctica. Donde puedes leer sobre ellos, si no recuerdo mal. El artículo en wikipedia (al menos la introducción) no es correcto. Fueron creados por Donald Knuth, y él los explica en su Volumen 5, El arte de la programación de computadoras. Si entiendes el español, aquí hay una lista completa de libros publicados por mí. Tampoco todos los libros están en español.

Antes de entender cómo funcionan, debes entender algunos conceptos como primero, sigue y mira hacia delante. Además, realmente te recomiendo que entiendas los conceptos detrás de los analizadores LL (descendientes) antes de tratar de entender los analizadores LR (ascendentes).

Hay una familia de analizadores LR, especialmente LR (K), SLR (K) y LALR (K), donde K es cuántos lookahead necesitan para trabajar. Yacc es compatible con los analizadores LALR (1), pero puedes hacer ajustes, no basados ​​en la teoría, para que funcione con gramáticas más potentes.

Sobre el rendimiento, depende de la gramática que se analiza. Se ejecutan en tiempo lineal, pero la cantidad de espacio que necesitan depende de cuántos estados se crean para el analizador final.

Personalmente, me resulta difícil entender cómo una llamada de función puede ser más rápida, y mucho menos "significativamente más rápida" que una búsqueda en la tabla. Y sospecho que incluso "significativamente más rápido" es insignificante en comparación con todo lo que un lexer / analizador tiene que hacer (principalmente leer y tokenizar el archivo). Miré la página de Wikipedia, pero no seguí las referencias; ¿El autor realmente perfiló un completo lexer / parser?

Más interesante para mí es el declive de los analizadores basados ​​en tablas con respecto al descenso recursivo. Vengo de un fondo en C, donde yacc (o equivalente) fue el generador de analizadores de elección. Cuando me mudé a Java, encontré una implementación basada en tablas (JavaCup) y varias implementaciones de descendencia recursiva (JavaCC, ANTLR).

Sospecho que la respuesta es similar a la respuesta de "por qué Java en lugar de C": la velocidad de ejecución no es tan importante como la velocidad de desarrollo. Como se señaló en el artículo de Wikipedia, los analizadores controlados por tablas son prácticamente imposibles de entender a partir del código (cuando los estaba usando, podía seguir sus acciones pero nunca habría podido reconstruir la gramática desde el analizador). El descenso recursivo, en comparación, es muy intuitivo (lo que sin duda es una razón por la cual es anterior a la tabla de unos 20 años).