c# - Comunicación entre lexer y analizador

c++ parsing (5)

Cada vez que escribo un lector y analizador simple, tropiezo con la misma pregunta: ¿cómo deben comunicarse el analizador y el analizador? Veo cuatro enfoques diferentes:

El lexer convierte ansiosamente toda la cadena de entrada en un vector de tokens. Una vez hecho esto, el vector se alimenta al analizador que lo convierte en un árbol. Esta es, de lejos, la solución más simple de implementar, pero como todos los tokens se almacenan en la memoria, se desperdicia mucho espacio.
Cada vez que el lexer encuentra un token, invoca una función en el analizador, pasando el token actual. En mi experiencia, esto solo funciona si el analizador sintáctico se puede implementar de forma natural como una máquina de estados como analizadores LALR. Por el contrario, no creo que funcione en absoluto para los analizadores de descenso recursivos.
Cada vez que el analizador necesita un token, le pregunta al lector por el siguiente. Esto es muy fácil de implementar en C # debido a la palabra clave yield , pero bastante difícil en C ++ que no lo tiene.
El lexer y el analizador se comunican a través de una cola asíncrona. Esto se conoce comúnmente bajo el título "productor / consumidor", y debería simplificar mucho la comunicación entre el analizador y el analizador. ¿También supera a las otras soluciones en multinúcleos? ¿O es lexing demasiado trivial?

¿Mi análisis es sensato? ¿Hay otros enfoques en los que no haya pensado? ¿Qué se usa en los compiladores del mundo real? Sería genial si los escritores de compiladores como Eric Lippert pudieran arrojar algo de luz sobre este tema.

Creo que no hay una regla de oro aquí. Los requisitos pueden variar de un caso a otro. Entonces, las soluciones razonables también pueden ser diferentes. Déjame comentar tus opciones desde mi propia experiencia.

"Vector de tokens". Esta solución puede tener una gran huella de memoria. Imagine compilar un archivo fuente con muchos encabezados. Almacenar la ficha en sí no es suficiente. El mensaje de error debe contener el contexto con el nombre del archivo y el número de línea. Puede suceder que lexer dependa del analizador. Ejemplo razonable: ">>": ¿se trata de un operador de desplazamiento o está cerrando 2 capas de instancias de plantilla? Yo abajo votaría esta opción.
(2,3). "Una parte llama a otra". Mi impresión es que un sistema más complejo debería llamar menos complejo. Considero que Lexer es más simple. Esto significa que el analizador debe llamar a Lexer. No veo por qué C # es mejor que C ++. Implementé C / C ++ lexer como una subrutina (en realidad esta es una clase compleja) que se llama desde el analizador basado en la gramática. No hubo problemas en esta implementación.
"Procesos de comunicación". Esto me parece un exceso. No hay nada de malo en este enfoque, pero tal vez es mejor mantener las cosas simples? Aspecto multinúcleo Compilar un solo archivo es un caso relativamente raro. Yo recomendaría cargar cada núcleo con su propio archivo.

No veo otras opciones razonables de combinar Lexer y Analizador juntos.

Escribí estas notas pensando en compilar las fuentes del proyecto de software. El análisis de una solicitud de consulta breve es completamente diferente, y las razones pueden variar significativamente. Mi respuesta se basa en mi propia experiencia. Otras personas pueden ver esto de manera diferente.

La forma en que lo manejo en mi proyecto de sistema de construcción de juguetes en progreso es teniendo una clase de "lector de archivos", con una función bool next_token(std::string&,const std::set<char>&) . Esta clase contiene una línea de entrada (para propósitos de informe de error con número de línea). La función acepta una referencia std::string para poner el token y un std::set<char> que contiene los caracteres "token-ending". Mi clase de entrada es tanto analizador como lexer, pero podrías dividirla fácilmente si necesitas más fantaseidad. Por lo tanto, las funciones de análisis solo llaman a next_token y pueden hacer lo suyo, incluida una salida de error muy detallada.

Si necesita mantener la entrada textual, necesitará almacenar cada línea que se lee en un vector<string> o algo, pero no almacenar cada token por separado y / o double-y.

El código del que estoy hablando se encuentra aquí:

https://github.com/rubenvb/Ambrosia/blob/master/libAmbrosia/Source/nectar_loader.cpp

(la búsqueda de ::next_token y la función extract_nectar es donde comienza todo)

La relación lexer-analizador es más simple que el caso más general de coroutines , porque en general la comunicación es unidireccional; el analizador no necesita enviar información al lexer. Esta es la razón por la cual el método de generación ansiosa funciona (con alguna penalización, aunque significa que puede descartar la entrada antes).

Como ha observado, si el lexer o el analizador se pueden escribir en un estilo reinvocable, el otro se puede tratar como una subrutina simple. Esto siempre se puede implementar como una transformación de código fuente, con variables locales traducidas a ranuras de objetos.

Aunque C ++ no tiene soporte de lenguaje para corutinas, es posible hacer uso de soporte de biblioteca , en particular fibers . La familia setcontext Unix es una opción; otra es utilizar el multihilo pero con una cola síncrona (esencialmente un solo subprocesamiento pero cambiando entre dos subprocesos de control).

Si bien no clasificaría mucho de lo anterior como incorrecto , creo que varios elementos son engañosos.

Lexing una entrada completa antes de ejecutar un analizador tiene muchas ventajas sobre otras opciones. Las implementaciones varían, pero en general la memoria requerida para esta operación no es un problema, especialmente cuando se considera el tipo de información que le gustaría tener disponible para informar errores de compilación.
- Beneficios
  - Potencialmente más información disponible durante el informe de errores.
  - Los lenguajes escritos de una manera que permite que ocurra el léxico antes del análisis son más fáciles de especificar y escribir compiladores.
- Inconvenientes
  - Algunos lenguajes requieren lexers sensibles al contexto que simplemente no pueden operar antes de la fase de análisis.
Nota de implementación del lenguaje: esta es mi estrategia preferida, ya que da como resultado un código separable y es más adecuado para la traducción y la implementación de un IDE para el idioma.
Nota de implementación del analizador: Experimenté con ANTLR v3 con respecto a la sobrecarga de memoria con esta estrategia. El objetivo C usa más de 130 bytes por token y el destino Java usa alrededor de 44 bytes por token. Con un objetivo C # modificado, mostré que es posible representar completamente la entrada tokenizada con solo 8 bytes por token, lo que hace que esta estrategia sea práctica incluso para archivos fuente bastante grandes.
Nota de diseño de idioma: animo a las personas que diseñan un nuevo idioma a que lo hagan de una manera que permita esta estrategia de análisis, ya sea que terminen o no por su compilador de referencia.
Parece que has descrito una versión "push" de lo que generalmente veo descrito como un analizador "pull" como el que tienes en el # 3. Mi énfasis en el trabajo siempre ha estado en el análisis de LL, por lo que esta no era realmente una opción para mí. Me sorprendería si hay beneficios para esto sobre el n. ° 3, pero no puedo descartarlos.
La parte más engañosa de esto es la afirmación sobre C ++. El uso adecuado de iteradores en C ++ lo hace excepcionalmente adecuado para este tipo de comportamiento.
Una cola parece una repetición del # 3 con un intermediario. Aunque abstraer operaciones independientes tiene muchas ventajas en áreas como el desarrollo de software modular, un par lexer / analizador para una oferta de producto distribuible es altamente sensible al rendimiento, y este tipo de abstracción elimina la capacidad de realizar ciertos tipos de optimización con respecto a estructura de datos y memoria . Me gustaría alentar el uso de la opción n. ° 3 sobre esto.
Como nota adicional sobre el análisis multinúcleo: las fases iniciales de compilación lexer / analizador para una única unidad de compilación generalmente no se pueden paralelizar, ni deben considerarse cuán fácil es ejecutar tareas de compilación paralelas en diferentes unidades de compilación ( por ejemplo, una operación lexer / analizador en cada archivo fuente, paralelizando a través de los archivos fuente pero solo usando un solo hilo para cualquier archivo dado).

En cuanto a otras opciones: para un compilador destinado a un uso generalizado (comercial o de otro tipo), generalmente los implementadores eligen una estrategia de análisis e implementación que proporciona el mejor rendimiento bajo las limitaciones del idioma de destino. Algunos lenguajes (por ej. Go) se pueden analizar excepcionalmente rápido con una estrategia de análisis de LR simple, y usar una estrategia de análisis "más potente" (léase: características innecesarias) solo serviría para desacelerar las cosas. Otros lenguajes (por ejemplo, C ++) son extremadamente difíciles o imposibles de analizar con algoritmos típicos, por lo que se emplean analizadores más lentos pero más potentes / flexibles.

También considere para el n. ° 1 que lee leyendas que no lo necesitan, por ejemplo, si hay un error, y además, puede tener poca memoria o ancho de banda de E / S. Creo que la mejor solución es la que utilizan los analizadores generados por herramientas como Bison, donde el analizador llama al lector para obtener el siguiente token. Minimiza los requisitos de espacio y los requisitos de ancho de banda de memoria.

#4 no va a valer la pena. Lexing y el análisis son inherentemente sincrónicos; simplemente no hay suficiente procesamiento para justificar los costos de la comunicación. Además, normalmente analiza / lee varios archivos al mismo tiempo, esto ya puede maximizar todos sus núcleos a la vez.