¿Dónde puedo aprender los conceptos básicos para escribir un lexer?

85

Quiero aprender a escribir un lexer. Mi curso universitario tenía una tarea en la que teníamos que escribir un analizador sintáctico (y un lexer para acompañarlo), pero esto nos fue entregado sin instrucciones ni comentarios (más allá de la marca), así que realmente no aprendí mucho de él.

Después de buscar este tema, solo puedo encontrar escritos bastante avanzados que se enfocan en áreas que siento que están unos pasos por delante de donde estoy. Quiero una discusión sobre los conceptos básicos de escribir un lexer para un lenguaje muy simple que pueda usar como base para investigar la tokenización de lenguajes más complejos.

En esta etapa, no estoy realmente interesado en las mejores prácticas o técnicas de optimización, sino que prefiero centrarme en lo esencial. ¿Cuáles son algunos buenos recursos para comenzar?

Rupert Madden-Abbott
fuente

Respuestas:

72

Básicamente, existen dos enfoques principales para escribir un lexer:

  1. Creando uno escrito a mano en cuyo caso recomiendo este pequeño tutorial .
  2. Usando algunas herramientas generadoras de lexer como lex . En este caso, recomiendo leer los tutoriales de la herramienta en particular de su elección.

También me gustaría recomendar el tutorial de Kaleidoscope de la documentación de LLVM . Se ejecuta mediante la implementación de un lenguaje simple y, en particular, demuestra cómo escribir un pequeño lexer. Hay una versión C ++ y una Objective Caml del tutorial.

El libro de texto clásico sobre el tema es Compiladores: principios, técnicas y herramientas, también conocido como Dragon Book. Sin embargo, esto probablemente cae en la categoría de "escritos bastante avanzados".

vitaut
fuente
4
El tutorial de Kaleidoscope fue la parte que realmente me respondió esta pregunta.
Robert Byers
Para obtener más información sobre cómo escribir un analizador LL (1) a mano, consulte esta respuesta .
jchook