¿Cómo funcionan los analizadores de ascenso recursivo?

Question

¿Cómo funcionan los analizadores de subida recursiva? He escrito un recursivo de descendencia analizador pero no entiendo muy bien los analizadores de LR. Lo que yo found on Wikipedia solo ha añadido a mi confusión.

Otra pregunta es por qué los analizadores de ascenso recursivos no se usan más que sus contrapartes basadas en tablas. Parece que los analizadores de ascenso recursivos tienen un mayor rendimiento en general.

Answer 1

El clásico dragon book explica muy bien cómo funcionan los analizadores LR. También hay Parsing Techniques. A Practical Guide. donde puedes leer sobre ellos, si mal no recuerdo. El artículo en wikipedia (al menos la introducción) no es correcto. Fueron creados por Donald Knuth y los explica en su Volumen 5 de El arte de la programación de computadoras. Si entiendes español, hay una lista completa de libros here publicados por mí. No todos los libros están en español, tampoco.

Antes de entender cómo funcionan, debe comprender algunos conceptos como primero, siguiente y anticipación. Además, realmente recomiendo que comprendas los conceptos detrás de los analizadores LL (descendentes) antes de tratar de entender los analizadores LR (ascendente).

Hay una familia de analizadores LR, especialmente LR (K), SLR (K) y LALR (K), donde K es la cantidad de anticipación que necesitan para trabajar. Yacc admite analizadores LALR (1), pero puede realizar ajustes, no basados ​​en teoría, para que funcione con tipos de gramáticas más potentes.

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

Answer 2

Personalmente estoy teniendo dificultades para entender cómo una llamada a función puede ser más rápida, mucho menos "significativamente más rápida" que una búsqueda de tabla. Y sospecho que incluso "significativamente más rápido" es insignificante cuando se compara con todo lo demás que un lexer/analizador tiene que hacer (principalmente leer y convertir el archivo en token). Miré la página de Wikipedia, pero no seguí las referencias; ¿el autor realmente perfiló un lexer/analizador completo?

Más interesante para mí es la disminución de los analizadores sintácticos basados ​​en tablas con respecto al descenso recursivo. Vengo de un fondo C, donde yacc (o equivalente) era el generador de analizadores sintáctico de elección. Cuando me mudé a Java, encontré una implementación basada en tablas (JavaCup) y varias implementaciones de descenso recursivo (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ñala en el artículo de Wikipedia, los analizadores basados ​​en tablas son prácticamente imposibles de entender desde el código (cuando los estaba usando, podía seguir sus acciones pero nunca podría haber reconstruido la gramática del analizador). El descenso recursivo, en comparación, es muy intuitivo (sin duda, es el motivo por el que es anterior a la creación de tablas en unos 20 años).

Answer 3

El artículo de Wikipedia sobre recursivo ascent referencias de análisis que parece ser el documento original sobre el tema ("Muy rápido LR Parsing"). Al hojear ese papel despejé algunas cosas para mí. Cosas que noté:

1. El documento habla sobre la generación de código de ensamblaje. Me pregunto si puede hacer lo mismo que ellos si genera código C o Java; ver secciones 4 y 5, "Recuperación de errores" y "Verificación de desbordamiento de pila". (No estoy tratando de aplicar su técnica a FUD, podría funcionar bien, solo digo que es algo en lo que deberías mirar antes de cometer.)

2. Comparan su herramienta de ascenso recursiva a su propio analizador sintáctico basado en tablas. 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 término medio en el que la estructura general todavía está basada en tablas, pero usted genera código personalizado para ciertas acciones para acelerar las cosas.

El documento al que hace referencia la página de Wikipedia:

• "Muy rápido análisis sintáctico LR" (1986)
• http://portal.acm.org/citation.cfm?id=13310.13326

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

• "analizadores compatibles con Yacc muy rápido (por muy poco esfuerzo)" (1999)
• http://www3.interscience.wiley.com/journal/1773/abstract

Además, tenga en cuenta que el análisis sintáctico descendente recursivo no es la manera más rápida para analizar lenguas elaborados a base de gramática LL:

• Difference between an LL and Recursive Descent parser?