Comunicación entre lexer y parser

Question

Comunicación entre lexer y parser

Cada vez que escribo un lexer y un parser simples, me encuentro con la misma pregunta: ¿cómo deben comunicarse el lexer y el parser? 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, con mucho, la solución más simple de implementar, pero como todos los tokens se almacenan en la memoria, desperdicia mucho espacio.
Cada cuando el lexer encuentra un token, invoca una función en el analizador sintáctico, pasando el token actual. En mi experiencia, esto solo funciona si el analizador puede implementarse naturalmente como una máquina de estado como los analizadores LALR. Por el contrario, no creo que funcionaría en absoluto para analizadores de descenso recursivos.
Cada vez que el analizador necesita un token, le pide al lexer 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 tiene se.
El lexer y el parser 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 lexer y el parser. ¿También supera a las otras soluciones en multicores? ¿O Lexing es demasiado trivial?

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

35

c++compiler-construction parsing lexer

Author: fredoverflow, 2012-07-09

Source

5 answers

Creo que no hay una regla de oro aquí. Los requisitos pueden variar de un caso a otro. Por lo tanto, las soluciones razonables también pueden ser diferentes. Permítanme comentar sobre sus opciones de mi propia experiencia.

"Vector of tokens". Esta solución puede tener una gran huella de memoria. Imagine compilar un archivo fuente con muchos encabezados. Almacenar el token en sí no es suficiente. El mensaje de error debe contener un contexto con el nombre del archivo y el número de línea. Puede suceder que lexer dependa de la analizador. Ejemplo razonable: "> > " - ¿es este un operador shift o esto es el cierre de 2 capas de instanciaciones de plantilla? Votaría en contra de esta opción.
(2,3). "Una parte llama a otra". Mi impresión es que un sistema más complejo debería llamar a uno menos complejo. Considero que Lexer es más simple. Esto significa que parser 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 la gramática analizador basado. No hubo problemas en esta implementación.
"Procesos de comunicación". Esto me parece una exageración. No hay nada 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. Recomendaría cargar cada núcleo con su propio archivo.

No veo otras opciones razonables de combinar lexer y parser juntos.

Escribí estas notas pensando en compilación de fuentes del proyecto de software. Analizar una solicitud de consulta corta es algo completamente diferente, y las razones pueden diferir significativamente. Mi respuesta se basa en mi propia experiencia. Otras personas pueden ver esto de manera diferente.

4

Author: Kirill Kobelev,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-02-02 11:35:20

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

Como has observado, si el lexer o el parser se pueden escribir en un estilo reinvocable, entonces el otro se puede tratar como un simple subrutina. 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 para language para las corrutinas, es posible hacer uso del soporte para library, en particular fibers. La familia Unix setcontext es una opción; otra es usar multihilo pero con una cola síncrona (esencialmente un solo hilo pero cambiando entre dos hilos de control).

2

Author: ecatmur,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-07-09 15:13:59

También considere para #1 que lex tokens que no lo necesitan, por ejemplo, si hay un error, y además, puede quedarse sin memoria o ancho de banda de E/S. Creo que la mejor solución es la empleada por los analizadores generados por herramientas como Bison, donde el analizador llama al lexer para obtener el siguiente token. Minimiza los requisitos de espacio y ancho de banda de memoria.

#4 no va a valer la pena. El lexing y el análisis son inherentemente sincrónicos, simplemente no hay suficiente el procesamiento que se lleva a cabo para justificar los costos de la comunicación. Además, por lo general, analiza/lex varios archivos al mismo tiempo, esto ya puede maximizar todos sus núcleos a la vez.

2

Author: Puppy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-07-09 15:26:57

La forma en que lo manejo en mi proyecto de toy buildsystem en progreso es teniendo una clase "file reader", 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 reporte de errores con número de línea). La función acepta una referencia std::string para colocar el token, y un std::set<char> que contiene los caracteres "token-ending". Mi clase de entrada es parser y lexer, pero podrías dividirlo fácilmente si necesitas más fantasía. Así que las funciones de análisis solo llaman next_token y pueden hacer su cosa, incluyendo salida de error muy detallada.

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

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

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

(buscar ::next_token y la función extract_nectar es donde comienza todo)

1

Author: rubenvb,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-07-09 15:18:58

score 11 · Accepted Answer

Aunque 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 si se considera el tipo de información que le gustaría tener disponible para informar de errores de compilación.
- Beneficios
  - Potencialmente más información disponible durante la notificación de errores.
  - Los lenguajes escritos de una manera que permita que el lexing ocurra antes del análisis son más fáciles de especificar y escribir para los 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 resulta en código separable y es la más adecuada para la traducción a implementando un IDE para el lenguaje.

Nota de implementación del analizador: Experimenté con ANTLR v3 con respecto a la sobrecarga de memoria con esta estrategia. El objetivo C utiliza más de 130 bytes por token, y el objetivo Java utiliza 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: I anime a las personas que diseñen un nuevo lenguaje a hacerlo de una manera que permita esta estrategia de análisis, ya sea que terminen o no eligiéndolo para su compilador de referencia.
Parece que has descrito una versión " push "de lo que generalmente veo descrito como un analizador" pull " como tienes en #3. Mi énfasis de trabajo siempre ha sido el análisis de LL, así que esto no era realmente una opción para mí. Me sorprendería si hay beneficios en esto sobre #3, pero no puedo gobernarlos fuera.
La parte más engañosa de esto es la declaración sobre C++. El uso adecuado de iteradores en C++ lo hace excepcionalmente muy adecuado para este tipo de comportamiento.
Una cola parece un refrito de #3 con un intermediario. Si bien abstraer operaciones independientes tiene muchas ventajas en áreas como el desarrollo de software modular, un par lexer / parser para una oferta de productos distribuibles es altamente sensible al rendimiento, y este tipo de abstracción elimina la capacidad de hacer ciertos tipos de optimización con respecto a la estructura de datos y el diseño de memoria. Me gustaría alentar el uso de la opción # 3 sobre esto.

Como nota adicional sobre el análisis multinúcleo: Las fases iniciales de compilación de lexer/parser para una sola unidad de compilación generalmente no se pueden paralelizar, ni necesitan considerar lo fácil que es simplemente ejecutar tareas de compilación paralelas en diferentes unidades de compilación (por ejemplo, una operación de lexer/parser en cada archivo fuente, a través de los archivos de origen, pero solo utilizando un solo hilo para cualquier archivo dado).

Con respecto 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 restricciones del lenguaje de destino. Algunos lenguajes (por ejemplo, Go) se pueden analizar excepcionalmente rápido con una estrategia de análisis LR simple, y utilizando una estrategia de análisis "más potente" (leer: características innecesarias) solo servirían para ralentizar 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.