parsing - what - ¿Cómo se comparan los analizadores de Pratt con otros tipos de analizadores y por qué se usan tan poco?
reached end of file while parsing (1)
Recientemente aprendí sobre los analizadores de Pratt por this excelente artículo y encontré los analizadores de Pratt de una manera más simple y mucho más elegante que los analizadores de descendencia recursivos. Traté de encontrar un poco más de información acerca de cómo se comparan con otros tipos de analizadores, pero descubrí que el artículo de Wikipedia es apenas un trozo y la cantidad de proyectos más grandes que lo usan que podría encontrar son dos.
¿Por qué los analizadores de Pratt son tan poco utilizados? ¿Tienen limitaciones o desventajas graves que no conozco? ¿Cómo se comparan exactamente con otros tipos de analizadores? ¿Cuándo debería y cuándo no debería usarlos?
Hay muy poca diferencia entre un analizador de Pratt y el denominado analizador "shunting yard" (que tiene un artículo de Wikipedia mucho más largo adjunto); La principal diferencia es que Pratt usa la recursión y, por lo tanto, la pila, mientras que Djikstra (el "patio de maniobras") mantiene una pila explícita. Aparte de eso, hacen exactamente la misma secuencia de operaciones. Supongo que la expresión de Djikstra del algoritmo es más común debido a la recursofobia.
Hay algunas ventajas al usar la pila de programas; Una de ellas es que es más fácil mantener la seguridad de tipos, ya que la pila completa no tiene que ser de un solo tipo. Por otro lado, muchos analizadores de expresiones solo tienen un tipo.
El Libro del Dragón incluye un algoritmo que generará una tabla de precedencia de operadores desde una gramática. Como señala, el hecho de que el algoritmo sea exitoso no implica necesariamente que el analizador de precedencia del operador analice exactamente el mismo idioma. Hay más información interesante allí que ciertamente he olvidado; Si estás interesado en el algoritmo, ese es uno de los lugares donde puedes buscar. Incluye la interesante perspectiva de que los operadores de relación de <y> la precendencia se pueden generar al observar una derivación, si rodea el resultado de una producción con <y> de la manera obvia.
En general, mi experiencia es que la mayoría de las veces, cuando encuentras una publicación en el blog que dice "Dios mío, acabo de encontrarme con X y es genial, y ¿por qué no lo sabe más gente?", El la respuesta es: "Por favor, no asumas que tu ignorancia es universal". Pero tal vez estoy de humor cínico hoy.
Por cierto, el analizador Lua es un analizador de descenso recursivo construido a mano que utiliza el análisis de estilo Pratt para analizar expresiones; Creo que esa es una técnica bastante común, y probablemente la encontrará en otros lugares, aunque es posible que tenga que revisar el código para ver el patrón.