Software is all about logic. La programación se ha ganado la reputación de ser un campo que es pesado en matemáticas y ecuaciones locas. Y la informática parece estar en el quid de este concepto erróneo.

Claro, hay algunas matemáticas y hay algunas fórmulas, pero ninguno de nosotros necesita tener un doctorado en cálculo para comprender cómo funcionan nuestras máquinas. De hecho, muchas de las reglas y paradigmas que aprendemos en el proceso de escribir código son las mismas reglas y paradigmas que se aplican a conceptos complejos de informática. Y a veces, esas ideas provienen de la informática, y nunca lo supimos.

Independientemente del lenguaje de programación que utilicemos, cuando la mayoría de nosotros escribimos nuestro código, nuestro objetivo es encapsular cosas distintas en clases, objetos o métodos, separando intencionalmente las diferentes partes de nuestro código. En otras palabras, sabemos que generalmente es bueno dividir nuestro código para que una clase, objeto o método solo se preocupe y sea responsable de una sola cosa. Si no hiciéramos esto, las cosas podrían ponerse súper desordenadas y entrelazarse en un desastre de red. A veces esto todavía sucede, incluso con la separación de preocupaciones.

Resulta que incluso el funcionamiento interno de nuestros ordenadores sigue paradigmas de diseño muy similares. Nuestro compilador, por ejemplo, tiene diferentes partes, y cada parte es responsable de manejar una parte específica del proceso de compilación. Encontramos un poco de esto la semana pasada, cuando aprendimos sobre el analizador, que es responsable de crear árboles de análisis. Pero el analizador no puede encargarse de todo.

El analizador necesita ayuda de sus amigos, ¡y finalmente es hora de que aprendamos quiénes son!

Cuando aprendimos sobre el análisis recientemente, nos sumergimos en la gramática, la sintaxis y cómo reacciona y responde el compilador a esas cosas dentro de un lenguaje de programación. ¡Pero nunca destacamos qué es exactamente un compilador! A medida que nos adentramos en el funcionamiento interno del proceso de compilación, vamos a aprender mucho sobre el diseño del compilador, por lo que es vital para nosotros entender exactamente de qué estamos hablando aquí.

Los compiladores pueden sonar un poco aterradores, pero sus trabajos en realidad no son demasiado complejos para entenderlos, especialmente cuando dividimos las diferentes partes de un compilador en partes del tamaño de un bocado.

Pero primero, comencemos con la definición más simple posible. Un compilador es un programa que lee nuestro código (o cualquier código, en cualquier lenguaje de programación), y lo traduce a otro lenguaje.

En términos generales, un compilador realmente solo va a traducir código de un lenguaje de alto nivel a un lenguaje de bajo nivel. Los lenguajes de nivel inferior a los que un compilador traduce el código a menudo se conocen como código ensamblador, código máquina o código objeto. Vale la pena mencionar que la mayoría de los programadores no están realmente tratando o escribiendo ningún código máquina; más bien, dependemos del compilador para tomar nuestros programas y traducirlos en código máquina, que es lo que nuestro equipo ejecutará como un programa ejecutable.

Podemos pensar en los compiladores como el intermediario entre nosotros, los programadores y nuestros ordenadores, que solo pueden ejecutar programas ejecutables en lenguajes de nivel inferior.

El compilador hace el trabajo de traducir lo que queremos que suceda de una manera que sea comprensible y ejecutable para nuestras máquinas.

Sin el compilador, nos veríamos obligados a comunicarnos con nuestros ordenadores escribiendo código máquina, que es increíblemente ilegible y difícil de descifrar. El código máquina a menudo puede parecer un montón de 0 y 1 para el ojo humano, todo es binario, ¿recuerdas? – lo que hace que sea muy difícil de leer, escribir y depurar. El compilador abstrajo el código máquina para nosotros como programadores, porque nos hizo muy fácil no pensar en código máquina y escribir programas utilizando lenguajes mucho más elegantes, claros y fáciles de leer.

Continuaremos desempaquetando más y más sobre el compilador misterioso durante las próximas semanas, lo que con suerte hará que sea menos un enigma en el proceso. Pero por ahora, volvamos a la pregunta: ¿cuáles son las partes más simples posibles de un compilador?

Cada compilador, sin importar cómo se diseñe, tiene fases distintas. Estas fases son como podemos distinguir las partes únicas del compilador.

Ya hemos encontrado una de las fases en nuestras aventuras de compilación cuando recientemente aprendimos sobre el analizador y los árboles de análisis. Sabemos que el análisis es el proceso de tomar algo de información y construir un árbol de análisis a partir de él, lo que a veces se conoce como el acto de analizar. Resulta que el trabajo de análisis es específico de una fase del proceso de compilación llamada análisis de sintaxis.

Sin embargo, el analizador no solo construye un árbol de análisis de la nada. ¡Tiene algo de ayuda! Recordaremos que al analizador se le dan algunos tokens (también llamados terminales), y construye un árbol de análisis a partir de esos tokens. ¿Pero de dónde saca esas fichas? Por suerte para el analizador, no tiene que funcionar en el vacío; en su lugar, tiene algo de ayuda.

Esto nos lleva a otra fase del proceso de compilación, una que viene antes de la fase de análisis sintáctico: la fase de análisis léxico.

El término «léxica» se refiere al significado de una palabra en el aislamiento de la frase que la contiene, y con independencia de su contexto gramatical. Si tratamos de adivinar nuestro propio significado basado únicamente en esta definición, podríamos postular que la fase de análisis léxico tiene que ver con las palabras/términos individuales en el programa en sí, y nada que ver con la gramática o el significado de la oración que contiene las palabras.

La fase de análisis léxico es el primer paso en el proceso de compilación. No conoce ni se preocupa por la gramática de una oración o el significado de un texto o programa; todo lo que conoce es el significado de las propias palabras.

El análisis léxico debe ocurrir antes de que se pueda analizar cualquier código de un programa fuente. Antes de que pueda ser leído por el analizador, un programa primero debe ser escaneado, dividido y agrupado de ciertas maneras.

Cuando empezamos a analizar la fase de análisis sintáctico la semana pasada, aprendimos que el árbol de análisis se construye observando partes individuales de la oración y dividiendo expresiones en partes más simples. Pero durante la fase de análisis léxico, el compilador no conoce ni tiene acceso a estas «partes individuales». Más bien, primero tiene que identificarlos y encontrarlos, y luego hacer el trabajo de dividir el texto en piezas individuales.

Por ejemplo, cuando leemos una oración de Shakespeare como To sleep, perchance to dream., sabemos que los espacios y la puntuación están dividiendo las «palabras» de una oración. Esto es, por supuesto, porque hemos sido entrenados para leer una oración, «lex», y analizarla para gramática.

Pero, para un compilador, la misma oración podría verse así la primera vez que la lee: Tosleepperhachancetodream. Cuando leemos esta oración, es un poco más difícil para nosotros determinar cuáles son las «palabras» reales. Estoy seguro de que nuestro compilador siente lo mismo.

Entonces, ¿cómo se ocupa nuestra máquina de este problema? Bueno, durante la fase de análisis léxico del proceso de compilación, siempre hace dos cosas importantes: escanea el código y luego lo evalúa.

El trabajo de escaneo y evaluación a veces se puede agrupar en un solo programa, o podría ser dos programas separados que dependen el uno del otro; en realidad, es solo una cuestión de cómo se diseñó uno de los más complejos. El programa dentro del compilador que es responsable de hacer el trabajo de escaneo y evaluación a menudo se conoce como el lexer o el tokenizador, y toda la fase de análisis léxico a veces se llama el proceso de lexing o tokenización.

Para escanear, tal vez para leer

El primero de los dos pasos principales en el análisis léxico es escanear. Podemos pensar en escanear como el trabajo de «leer» algo de texto de entrada. Recuerde que este texto de entrada puede ser una cadena, una oración, una expresión o incluso un programa completo. En realidad no importa, porque, en esta fase del proceso, es solo una masa gigante de caracteres que no significa nada por el momento, y es un trozo contiguo.

Veamos un ejemplo para ver cómo sucede exactamente esto. Usaremos nuestra oración original, To sleep, perchance to dream. , que es nuestro texto o código fuente. Para nuestro compilador, este texto de origen se leerá como texto de entrada que se parece a Tosleep,perchancetodream., que es solo una cadena de caracteres que aún no se ha descifrado.

Lo primero que tiene que hacer nuestro compilador es dividir ese blob de texto en sus partes más pequeñas posibles, lo que hará que sea mucho más fácil identificar dónde están realmente las palabras en el blob de texto.

La forma más sencilla de bucear un trozo gigante de texto es leerlo lenta y sistemáticamente, un carácter a la vez. Y esto es exactamente lo que hace el compilador.

A menudo, el proceso de escaneo es manejado por un programa separado llamado escáner, cuyo único trabajo es hacer el trabajo de leer un archivo/texto fuente, un carácter a la vez. Para nuestro escáner, realmente no importa cuán grande sea nuestro texto; todo lo que verá cuando «lea» nuestro archivo es un carácter a la vez.

Así es como nuestro escáner leería nuestra oración de Shakespeare:

Notaremos que To sleep, perchance to dream. ha sido dividido en caracteres individuales por nuestro escáner. Además, incluso los espacios entre las palabras se tratan como caracteres, al igual que la puntuación en nuestra oración. También hay un carácter al final de esta secuencia que es particularmente interesante: eof. Este es el carácter de «fin de archivo», y es similar a tabspace y newline. Dado que nuestro texto de origen es una sola oración, cuando nuestro escáner llega al final del archivo (en este caso, al final de la oración), lee el final del archivo y lo trata como un carácter.

Entonces, en realidad, cuando nuestro escáner leyó nuestro texto de entrada, lo interpretó como caracteres individuales, lo que resultó en esto: .

Ahora que nuestro escáner ha leído y dividido nuestro texto fuente en las partes más pequeñas posibles, le resultará mucho más fácil averiguar las «palabras» de nuestra oración.

A continuación, el escáner debe observar sus caracteres divididos en orden y determinar qué caracteres son partes de una palabra y cuáles no. Para cada carácter que lee el escáner, marca la línea y la posición de dónde se encontró ese carácter en el texto de origen.

La imagen que se muestra aquí ilustra este proceso para nuestra oración shakesperiana. Podemos ver que nuestro escáner está marcando la línea y la columna para cada carácter de nuestra oración. Podemos pensar en la representación de líneas y columnas como una matriz o matriz de caracteres.

Recuerde que, dado que nuestro archivo tiene una sola línea, todo vive en la línea 0. Sin embargo, a medida que avanzamos en la oración, la columna de cada carácter aumenta. También vale la pena mencionar que, dado que nuestro escáner lee spacesnewlineseof, y todos los signos de puntuación como caracteres, también aparecen en nuestra tabla de caracteres.

Una vez que el texto de origen ha sido escaneado y marcado, nuestro compilador está listo para convertir estos caracteres en palabras. Dado que el escáner no solo sabe dónde están los spacesnewlines y eof del archivo, sino también dónde viven en relación con los otros caracteres que los rodean, puede escanear los caracteres y dividirlos en cadenas individuales según sea necesario.

En nuestro ejemplo, el escáner vistazo a los caracteres T, luego o y, a continuación, un space. Cuando encuentre un espacio, dividirá To en su propia palabra, la combinación de caracteres más simple posible antes de que el escáner encuentre un espacio.

Es una historia similar para la siguiente palabra que encuentra, que es sleep. Sin embargo, en este escenario, lee s-l-e-e-p, y luego lee un ,, un signo de puntuación. Dado que esta coma está flanqueada por un carácter (p) y un space a cada lado, la coma es, en sí misma, considerada como una «palabra».

Tanto la palabra sleep como el símbolo de puntuación , se denominan lexemas, que son subcadenas del texto de origen. Un lexema es una agrupación de las secuencias de caracteres más pequeñas posibles en nuestro código fuente. Los lexemas de un archivo fuente se consideran las «palabras» individuales del archivo en sí. Una vez que nuestro escáner termine de leer los caracteres individuales de nuestro archivo, devolverá un conjunto de lexemas que se ven así: .

Observe cómo nuestro escáner tomó una gota de texto como entrada, que inicialmente no podía leer, y procedió a escanearlo una vez a la vez, leyendo y marcando simultáneamente el contenido. A continuación, procedió a dividir la cadena en sus lexemas más pequeños posibles utilizando los espacios y la puntuación entre caracteres como delimitadores.

Sin embargo, a pesar de todo este trabajo, en este punto de la fase de análisis léxico, nuestro escáner no sabe nada sobre estas palabras. Claro, divide el texto en palabras de diferentes formas y tamaños, pero en cuanto a cuáles son esas palabras, el escáner no tiene idea. Las palabras podrían ser una cadena literal, o podrían ser un signo de puntuación, o podrían ser algo completamente diferente.

El escáner no sabe nada sobre las palabras en sí, o qué «tipo» de palabra son. Solo sabe dónde terminan y comienzan las palabras dentro del texto en sí.

Esto nos prepara para la segunda fase del análisis léxico: evaluación. Una vez que hemos escaneado nuestro texto y dividido el código fuente en unidades de lexemas individuales, debemos evaluar las palabras que el escáner nos devolvió y averiguar con qué tipo de palabras estamos tratando, en particular, debemos buscar palabras importantes que signifiquen algo especial en el lenguaje que estamos tratando de compilar.

Evaluar las partes importantes

Una vez que hayamos terminado de escanear nuestro texto de origen e identificado nuestros lexemas, tendremos que hacer algo con nuestras «palabras»de lexemas. Este es el paso de evaluación del análisis léxico, al que a menudo se hace referencia en el diseño más complejo como el proceso de lexing o tokenización de nuestras aportaciones.

Cuando evaluamos nuestro código escaneado, todo lo que realmente estamos haciendo es echar un vistazo más de cerca a cada uno de los lexemas que generó nuestro escáner. Nuestro compilador tendrá que mirar cada palabra de lexema y decidir qué tipo de palabra es. El proceso de determinar qué tipo de lexema es cada «palabra» en nuestro texto es cómo nuestro compilador convierte cada lexema individual en un token, tokenizando así nuestra cadena de entrada.

Encontramos tokens por primera vez cuando estábamos aprendiendo sobre los árboles de análisis. Los tokens son símbolos especiales que están en el quid de cada lenguaje de programación. Los tokens, como (, ), +, -, if, else, then, ayudan a un compilador a comprender cómo se relacionan las diferentes partes de una expresión y varios elementos entre sí. El analizador, que es fundamental para la fase de análisis de sintaxis, depende de recibir tokens de algún lugar y luego convierte esos tokens en un árbol de análisis.

Bueno, ¿adivina qué? ¡Finalmente hemos descubierto el «en algún lugar»! Resulta que los tokens que se envían al analizador son generados en la fase de análisis léxico por el tokenizador, también llamado lexer.

¿Qué aspecto tiene exactamente un token? Un token es bastante simple, y generalmente se representa como un par, que consiste en un nombre de token y algún valor (que es opcional).

Por ejemplo, si tokenizamos nuestra cuerda shakesperiana, terminaríamos con fichas que serían en su mayoría literales de cuerda y separadores. Podemos representar el lexema "dream” como muestra así: <string literal, "dream">. En una vena similar, podemos representar el lexema . como el token, <separator, .>.

Notaremos que cada uno de estos tokens no está modificando el lexema en absoluto, simplemente están agregando información adicional a ellos. Un token es un lexema o unidad léxica con más detalle; específicamente, el detalle agregado nos dice qué categoría de token (qué tipo de «palabra») estamos tratando.

Ahora que hemos tokenizado nuestra oración shakesperiana, podemos ver que no hay tanta variedad en los tipos de tokens en nuestro archivo fuente. Nuestra oración solo tenía cadenas y puntuación, ¡pero eso es solo la punta del iceberg simbólico! Hay muchos otros tipos de «palabras» en las que un lexema podría categorizarse.

La tabla que se muestra aquí ilustra algunos de los tokens más comunes que nuestro compilador vería al leer un archivo fuente en casi cualquier lenguaje de programación. Vimos ejemplos de literals, que puede ser cualquier cadena, número o valor lógico/booleano, así como separators, que son cualquier tipo de puntuación, incluidas llaves ({}) y paréntesis (()).

However, there are also keywords, which are terms that are reserved in the language (such as ifvarwhilereturn), as well as operators, which operate on arguments and return some value ( +-x/). También podríamos encontrar lexemas que podrían ser tokenizados como identifiers, que normalmente son nombres de variables o cosas escritas por el usuario / programador para hacer referencia a otra cosa, así como , que podrían ser comentarios de línea o bloque escritos por el usuario.

Nuestra oración original solo nos mostraba dos ejemplos de fichas. Reescribamos nuestra oración para que diga: var toSleep = "to dream";. ¿Cómo podría nuestro compilador lex esta versión de Shakespeare?

Aquí, veremos que tenemos una mayor variedad de tokens. Tenemos un keyword en el var, donde estamos declarando una variable, y un identifiertoSleep, que es la manera en que estamos nombrando nuestra variable de referencia o el valor para venir. El siguiente es nuestro =, que es un operator token, seguido por el literal de cadena "to dream". Nuestra instrucción termina con un separador ;, que indica el final de una línea y delimita espacios en blanco.

Una cosa importante a tener en cuenta sobre el proceso de tokenización es que no estamos tokenizando ningún espacio en blanco (espacios, nuevas líneas, pestañas, final de línea, etc.).), ni pasarlo al analizador sintáctico. Recuerde que solo los tokens se entregan al analizador y terminarán en el árbol de análisis.

También vale la pena mencionar que los diferentes idiomas tendrán diferentes caracteres que constituyen espacios en blanco. Por ejemplo, en algunas situaciones, el lenguaje de programación Python utiliza sangría, incluidas pestañas y espacios, para indicar cómo cambia el alcance de una función. Por lo tanto, el tokenizador del compilador Python debe ser consciente del hecho de que, en ciertas situaciones, un tab o space en realidad necesita ser tokenizado como una palabra, ¡porque en realidad necesita ser pasado al analizador!

Este aspecto del tokenizador es una buena manera de contrastar cómo un lexer/tokenizador es diferente de un escáner. Mientras que un escáner es ignorante, y solo sabe cómo dividir un texto en sus partes posibles más pequeñas (sus «palabras»), un lexer/tokenizador es mucho más consciente y preciso en comparación.

El tokenizador necesita conocer las complejidades y especificaciones del lenguaje que se está compilando. Si tabs son importantes, debe saberlo; si newlines puede tener ciertos significados en el lenguaje que se está compilando, el tokenizador debe ser consciente de esos detalles. Por otro lado, el escáner ni siquiera sabe cuáles son las palabras que divide, y mucho menos lo que significan.

El escáner de un complier es mucho más independiente del lenguaje, mientras que un tokenizador debe ser específico del lenguaje por definición.

Estas dos partes del proceso de análisis léxico van de la mano, y son fundamentales para la primera fase del proceso de compilación. Por supuesto, los diferentes cumplidores están diseñados de manera única. Algunos compiladores hacen el paso de escanear y tokenizar en un solo proceso y como un solo programa, mientras que otros los dividirán en diferentes clases, en cuyo caso el tokenizador llamará a la clase scanner cuando se ejecute.

En cualquier caso, el paso del análisis léxico es muy importante para la compilación, porque la fase de análisis de sintaxis depende directamente de él. Y a pesar de que cada parte del compilador tiene sus propios roles específicos, se apoyan unos en otros y dependen unos de otros, al igual que los buenos amigos siempre lo hacen.

Recursos

Dado que hay muchas formas diferentes de escribir y diseñar un compilador, también hay muchas formas diferentes de enseñarles. Si investigas lo suficiente sobre los fundamentos de la compilación, queda bastante claro que algunas explicaciones entran en mucho más detalle que otras, lo que puede ser útil o no. Si desea obtener más información, a continuación encontrará una variedad de recursos sobre compiladores, con un enfoque en la fase de análisis léxico.

1. Capítulo 4-Creación de intérpretes, Robert Nystrom
2. Construcción del compilador, Profesor Allan Gottlieb
3. Conceptos básicos del compilador, Profesor James Alan Farrell
4. Escribir un lenguaje de programación — el Lexer, Andy Balaam
5. Notas sobre Cómo funcionan los Analizadores y Compiladores, Stephen Raymond Ferg
6. ¿Cuál es la diferencia entre un token y un lexema?, StackOverflow