language agnostic - Generadores de analizador sin escáner
language-agnostic parser-generator (5)
Lo siento por un necropost. Puede probar esto: una implementación de PEG / Packrat incorporable para .NET:
Prólogo: aunque el conjunto de idiomas reconocidos por los analizadores (gramáticas sin contexto) es estrictamente más grande que el de los escáneres (gramáticas regulares), la mayoría de los generadores de analizadores necesitan un escáner.
(Por favor, no intentes explicar las razones detrás de esto, las conozco bastante bien).
He visto analizadores, que no requieren un escáner como
Hay ciertas ventajas de no usar escáner:
- Solo un concepto (gramáticas sin contexto) en lugar de dos
- Analizar múltiples idiomas en un archivo (como HTML / Javascript)
- Analizar lenguajes sin palabras clave reservadas (como PL/1 )
A menudo, las "soluciones alternativas" se utilizan como cambiar el escáner a petición del analizador.
Pregunta: ¿Conoce algún otro generador de analizador sin escáner (cualquier idioma)? ¿Son estos prácticos en uso (o puramente académicos)? ¿Hay otros enfoques que Tomita / GLR?
Respuestas:
- boost::spirit::qi de AraK
- LPEG gramáticas de expresión ( LPEG para Lua) por Norman Ramsey
- Yakker por Norman Ramsey
- MBase por SK-logic
- Waxeye de Trevor Robinson
Los generadores de analizador no necesitan un escáner. Pero estás bastante loco si no usas uno.
Los analizadores creados por generadores de analizador no se preocupan por lo que les alimenta, siempre que los llame tokens.
Para crear un generador de analizadores sin un escáner, simplemente defina su gramática hasta el nivel de caracteres y alimente caracteres individuales al analizador como tokens.
La razón por la que esto es una locura es que el análisis es una actividad más compleja que el lexing. Puede construir lexers como máquinas de estados finitos, que se traducen al código de máquina como "comparar y saltar al estado siguiente". Para la velocidad, eso es muy difícil de superar. Los generadores de analizador construyen analizadores que realizan análisis predictivos de descenso recursivo (para la mayoría de los generadores de LL como ANTLR) o realizan búsquedas en tablas mediante hashing, búsqueda binaria o lineal, etc. personaje.
Si alimenta caracteres a un analizador como tokens, entonces gastará en consecuencia más energía en el personaje que el equivalente de lexer. Si procesa una gran cantidad de texto de entrada, esto eventualmente será importante, ya sea que lo haga por millones de flujos de entrada pequeños o por unos pocos realmente grandes.
Los llamados analizadores GLR sin escáner sufren este problema de rendimiento, en relación con los analizadores GLR que están diseñados para usar tokens.
Mi empresa construye una herramienta, el kit de herramientas de reingeniería de software DMS que utiliza un analizador GLR (y analiza con éxito todos los idiomas comunes que conoces y muchos más extraños que no, porque tiene un analizador GLR). Sabíamos sobre analizadores sin escáner y decidimos no implementarlos debido al diferencial de velocidad; tenemos un subsistema similar a LEX de estilo clásico (pero extremadamente poderoso) para definir tokens léxicos. En el caso en el que el DMS fue de nariz a nariz frente a una herramienta basada en XT (una herramienta con un analizador GLR sin escáner) que procesa la misma entrada, el DMS parece ser 10 veces más rápido que el paquete XT. Para ser justos, el experimento realizado fue ad hoc y no se repitió, pero como coincidía con mis sospechas, no vi ninguna razón para repetirlo. YMMV. Y, por supuesto, si queremos ir sin escáner, bueno, es bastante fácil escribir una gramática con terminales de caracteres, como ya he señalado.
Los analizadores GLR Scannerless tienen otra propiedad muy agradable que no le importará a la mayoría de las personas. Puede tomar dos gramáticas separadas para un analizador sin escáner, y literalmente concatenarlas, y aún así obtener un analizador (a menudo con muchas ambigüedades). Esto importa mucho cuando construyes un lenguaje incrustado dentro de otro. Si eso no es lo que estás haciendo, esto es solo una curiosidad académica.
Y, AFAIK, Elkhound no es sin escáner. (Podría estar equivocado en esto). (EDIT: 2/10: parece que estaba equivocado. No será la primera vez en mi vida :)
Otros dos
Las Gramáticas de Expresión de Análisis (PEG) de Bryan Ford no requieren escáner. Eficiente, perezoso "packrat parser" es opcional. Solo he tenido una buena experiencia con la versión Lua LPEG , que se compila en una máquina de bytecode eficiente. Muy práctico.
YAKKER parece muy intrigante, aunque todavía está claramente en un estado previo al lanzamiento. Están utilizando lo que dicen ser una variación eficiente en el algoritmo de análisis de Earley.
En realidad soy un gran fan de los analizadores sin escáner; Ellos simplifican enormemente la configuración. Y los generadores de escáner típicos, por decirlo suavemente, no son muy divertidos de usar. De la página del manual para Lex:
El asteroide para matar a este dinosaurio todavía está en órbita.
Finalmente, no tengo experiencia personal con Elkhound, pero los informes de segunda mano que escucho son impresionantes. Yo diría que no hay duda, pero algunos generadores de analizador sin escáner son muy prácticos.
Waxeye : Analizador sin escáner basado en el análisis de gramáticas de expresión (PEG).
boost::spirit::qi no necesita un lexer, aunque puede usar boost::spirit::lex como interfaz. Desde la introducción de boost::spirit::lex :
De hecho, Spirit.Qi le permite escribir analizadores sin usar un lexer, analizando el flujo de caracteres de entrada directamente, y en su mayor parte, esta es la forma en que se ha utilizado Spirit desde su invención.
boost::spirit (el original) en realidad funcionó como usted quería exactamente, pero se ha movido para boost::spirit::classic . spirit::qi , spirit::lex es el nuevo diseño de spirit, así que dejé la versión clásica fuera :)