¿Busca una definición clara de lo que son un "tokenizador", "analizador sintáctico" y "lexers" y cómo se relacionan entre sí y se usan?

151

Estoy buscando una definición clara de lo que son "tokenizer", "parser" y "lexer" y cómo se relacionan entre sí (por ejemplo, ¿un analizador utiliza un tokenizer o viceversa)? Necesito crear un programa que vaya a través de archivos fuente c / h para extraer la declaración de datos y las definiciones.

He estado buscando ejemplos y puedo encontrar información, pero realmente me cuesta entender los conceptos subyacentes como las reglas gramaticales, los árboles de análisis y el árbol de sintaxis abstracta y cómo se interrelacionan entre sí. Finalmente, estos conceptos deben almacenarse en un programa real, pero 1) cómo se ven, 2) hay implementaciones comunes.

He estado buscando en Wikipedia sobre estos temas y programas como Lex y Yacc, pero nunca he asistido a una clase de compilador (EE mayor). Me resulta difícil entender completamente lo que está sucediendo.

parsing lexer tokenize Lordhog
fuente

Respuestas:

166

Un tokenizer divide una secuencia de texto en tokens, generalmente buscando espacios en blanco (pestañas, espacios, nuevas líneas).

Un lexer es básicamente un tokenizador, pero generalmente adjunta contexto adicional a los tokens: este token es un número, ese token es un literal de cadena, este otro token es un operador de igualdad.

Un analizador toma el flujo de tokens del lexer y lo convierte en un árbol de sintaxis abstracta que representa el programa (generalmente) representado por el texto original.

Lo último que revisé fue que el mejor libro sobre el tema fue "Compiladores: principios, técnicas y herramientas", generalmente conocido como "El libro del dragón".

Roger Lipscombe
fuente
8
Sin duda, "The Dragon Book" es un buen libro, pero requiere que el lector tenga una buena base en CS. Algunos libros con un atractivo más práctico serían "Redacción de compiladores e intérpretes" de Ronald Mak, "Implementación del compilador moderno", Andrew Appel; "Construcción del compilador", Niklaus Wirth; "Compilando con C # y Java" y "Compiladores y generadores de compiladores: una introducción con C ++" de Pat Terry; y, por supuesto, "La referencia definitiva de ANTLR" de Terrence Parr.
Andre Artus
55
Solo para estar seguro, no estoy rechazando tu recomendación. "The Dragon Book" fue mi primer libro sobre tecnología de compilación, pero fue difícil en comparación con, por ejemplo, el libro de Wirth, que es un libro que puedes asimilar en pocas horas. En aquel entonces tenía pocas opciones, ya que era el único libro que podía tener en mis manos (era 1991, antes de Amazon y WWW). Tenía eso y una colección de archivos de texto producidos por Jack W. Crenshaw llamado "CONSTRUIMOS UN COMPILADOR" (¡gracias Jack!). Este sigue siendo el libro para obtener una comprensión más completa de los principios, pero la mayoría de los programadores solo necesitan una introducción pragmática.
Andre Artus
10
No estaría de acuerdo con que un analizador sintético / por definición / produzca un árbol de sintaxis abstracta. Los analizadores pueden producir todo tipo de salidas diferentes. Por ejemplo, es común que un analizador produzca una secuencia de llamadas a alguna interfaz de generador: consulte el Patrón de generador en el libro Patrones de la cuadrilla de cuatro. El punto clave es que el analizador analiza una secuencia de tokens para determinar si la secuencia se ajusta o no a una gramática (generalmente libre de contexto) y puede producir algún resultado basado en la estructura gramatical de la secuencia.
Theodore Norvell
2
"Let's Build a Compiler" está aquí: compilers.iecc.com/crenshaw . Encontré el enlace desde aquí: prog21.dadgum.com/30.html
Roger Lipscombe
1
@Pithkos: si esas son las únicas restricciones, todo lo que ha dicho es que la función toma una entrada en un dominio (matemático) sin nombre y produce y genera en otro dominio sin nombre, por ejemplo, F (X) -> Y Más o menos esto significa solo puedes llamar a esto una "función". Si insiste en que el dominio de X es <StreamOfCharacter, Grammar> y el dominio de Y es Tree con la propiedad de que refleja la forma de la gramática, entonces F (X, G) -> T sería algo que llamaría un analizador A menudo curry F con respecto a G porque G no cambia a menudo, por lo que F [G] (X) -> T es lo que comúnmente se ve como un analizador sintáctico.
Ira Baxter
18

Ejemplo:

int x = 1;

Un lexer o tokeniser lo dividirá en tokens 'int', 'x', '=', '1', ';'.

Un analizador tomará esos tokens y los usará para comprender de alguna manera:

  • tenemos una declaración
  • es una definición de un entero
  • el entero se llama 'x'
  • 'x' debe inicializarse con el valor 1
Gra
fuente
9
Un lexer notará que "int", "=" y ";" son fichas sin significado adicional, que "x" es un nombre identificador o algo, valor "x", y "1" es un número entero o número, valor "1". Un tokenizer no necesariamente hará eso.
David Thornley
5

Diría que un lexer y un tokenizer son básicamente lo mismo, y que rompen el texto en sus partes componentes (los 'tokens'). El analizador interpreta los tokens usando una gramática.

Sin embargo, no me obsesionaría demasiado con el uso terminológico preciso: las personas a menudo usan 'análisis' para describir cualquier acción de interpretación de un fragmento de texto.

Will Dean
fuente
1
Con los analizadores PEG, la distinción entre tokenizer y analizador es aún menos clara.
Andre Artus
0

( agregando a las respuestas dadas )

  • Tokenizer también eliminará cualquier comentario y solo devolverá tokens al Lexer.
  • Lexer también definirá ámbitos para esos tokens (variables / funciones)
  • El analizador luego construirá la estructura del código / programa
mcha
fuente
1
Hola @downvoter, ¿puedes explicar por qué realmente votaste en contra?
Koray Tugay
1
No soy el votante negativo, pero creo que el voto negativo puede haber sido porque su respuesta no parece correcta. Un tokenizador puede eliminar el ruido (generalmente espacios en blanco, pero quizás también comentarios), pero a menudo no alimenta al lexer. Un lexer basado en DFA tokenizará e identificará qué tokens son (por ejemplo, un número, una cadena, un identificador, pero también un espacio en blanco o un comentario), pero no puede abarcar estos, ya que esto requeriría el árbol de sintaxis que luego se construye por el analizador
Lucero
1) No entiendo su aparente distinción entre "lexer" y "tokenizer". He creado analizadores para más de 50 idiomas y nunca he tenido dos mecanismos separados que rompan el texto fuente en átomos, por lo que para mí son solo sinónimos. 2) Si está compilando, eliminar comentarios y espacios en blanco tiene sentido en el lexer. Si está creando herramientas de transformación de fuente a fuente, no puede perder comentarios porque deben reaparecer en el texto transformado. Entonces SIEMPRE eliminar comentarios está mal; podemos discutir sobre cómo se puede preservar el espacio en blanco. ...
Ira Baxter
1
... [Las herramientas que construyo (vea mi biografía) capturan ambas con la fidelidad adecuada para reproducirlas en el código transformado; vamos más allá y capturamos el formato de los átomos, incluidas cosas extrañas como las comillas utilizadas en las cadenas de caracteres y el número de radix / zero zero en números, todo en servicio para evitar que el usuario rechace el resultado transformado. Entonces, lo que se perdió no solo es que los lexers no necesariamente eliminan información, sino que de hecho pueden necesitar capturar información más allá del token sin procesar]. ....
Ira Baxter
... 3) Los Lexers solo definen "ámbitos" en analizadores irremediablemente incómodos que tienen dificultades para manejar ambigüedades sintácticas. Los analizadores C y C ++ son el ejemplo canónico; vea mi discusión en stackoverflow.com/a/1004737/120163 ). Uno no tiene que hacerlo de esa manera (fea). Entonces encuentro su respuesta simplemente equivocada.
Ira Baxter