Análisis léxico

La tokenización léxica es la conversión de un texto en tokens léxicos (semántica o sintácticamente) significativos que pertenecen a categorías definidas por un programa "lexer". En el caso de un lenguaje natural, esas categorías incluyen sustantivos, verbos, adjetivos, puntuaciones, etc. En el caso de un lenguaje de programación, las categorías incluyen identificadores, operadores, símbolos de agrupación y tipos de datos . La tokenización léxica está relacionada con el tipo de tokenización utilizado en los grandes modelos de lenguaje (LLM), pero con dos diferencias. En primer lugar, la tokenización léxica suele basarse en una gramática léxica , mientras que los tokenizadores LLM suelen basarse en la probabilidad . En segundo lugar, los tokenizadores LLM realizan un segundo paso que convierte los tokens en valores numéricos.

Un programa basado en reglas, que realiza tokenización léxica, se llama tokenizador , ^[1] o escáner , aunque escáner también es un término para la primera etapa de un analizador léxico. Un analizador léxico forma la primera fase de un frontend de compilador en el procesamiento. El análisis generalmente ocurre en una pasada. Los analizadores léxicos y los analizadores sintácticos se usan con mayor frecuencia para compiladores, pero se pueden usar para otras herramientas de lenguaje de computadora, como prettyprinters o linters . La lexificación se puede dividir en dos etapas: el escaneo , que segmenta la cadena de entrada en unidades sintácticas llamadas lexemas y las clasifica en clases de token, y la evaluación , que convierte los lexemas en valores procesados.

Los analizadores léxicos son generalmente bastante simples, y la mayor parte de la complejidad se deja para las fases de análisis sintáctico o semántico , y a menudo pueden generarse mediante un generador de analizadores léxicos, en particular lex o derived. Sin embargo, los analizadores léxicos a veces pueden incluir cierta complejidad, como el procesamiento de la estructura de frases para facilitar la entrada y simplificar el analizador, y pueden escribirse total o parcialmente a mano, ya sea para admitir más funciones o para mejorar el rendimiento.

Lo que se denomina "lexema" en el procesamiento del lenguaje natural basado en reglas no es igual a lo que se denomina lexema en lingüística. Lo que se denomina "lexema" en el procesamiento del lenguaje natural basado en reglas puede ser igual al equivalente lingüístico solo en lenguajes analíticos , como el inglés, pero no en lenguajes altamente sintéticos , como los lenguajes fusionales . Lo que se denomina lexema en el procesamiento del lenguaje natural basado en reglas es más similar a lo que se denomina palabra en lingüística (que no debe confundirse con palabra en arquitectura informática ), aunque en algunos casos puede ser más similar a un morfema .

Un token léxico es una cadena con un significado asignado y, por lo tanto, identificado, a diferencia del token probabilístico utilizado en los modelos de lenguaje grandes . Un token léxico consta de un nombre de token y un valor de token opcional . El nombre de token es una categoría de una unidad léxica basada en reglas. ^[2]

Considere esta expresión en el lenguaje de programación C :

x = a + b * 2;

El análisis léxico de esta expresión produce la siguiente secuencia de tokens:

[(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]

Un nombre simbólico es lo que podría denominarse una parte del discurso en lingüística.

La tokenización léxica es la conversión de un texto sin formato en tokens léxicos significativos (semántica o sintácticamente), pertenecientes a categorías definidas por un programa "analizador léxico", como identificadores, operadores, símbolos de agrupación y tipos de datos. Los tokens resultantes se pasan luego a otra forma de procesamiento. El proceso puede considerarse una subtarea del análisis de la entrada.

Por ejemplo, en la cadena de texto :

The quick brown fox jumps over the lazy dog

La cadena no se segmenta implícitamente en espacios, como lo haría un hablante de lenguaje natural" " . La entrada sin procesar, los 43 caracteres, se deben dividir explícitamente en los 9 tokens con un delimitador de espacio determinado (es decir, que coincida con la cadena o la expresión regular /\s{1}/ ).

Cuando una clase de token representa más de un lexema posible, el analizador léxico suele guardar suficiente información para reproducir el lexema original, de modo que pueda utilizarse en el análisis semántico . El analizador sintáctico normalmente recupera esta información del analizador léxico y la almacena en el árbol de sintaxis abstracta . Esto es necesario para evitar la pérdida de información en el caso de que los números también puedan ser identificadores válidos.

Los tokens se identifican según las reglas específicas del analizador léxico. Algunos métodos utilizados para identificar tokens incluyen expresiones regulares , secuencias específicas de caracteres denominadas banderas , caracteres de separación específicos llamados delimitadores y una definición explícita mediante un diccionario. Los analizadores léxicos suelen utilizar caracteres especiales, incluidos los caracteres de puntuación, para identificar tokens debido a su uso natural en lenguajes escritos y de programación. Un analizador léxico generalmente no hace nada con combinaciones de tokens, una tarea que se deja para un analizador sintáctico . Por ejemplo, un analizador léxico típico reconoce los paréntesis como tokens, pero no hace nada para garantizar que cada "(" coincida con un ")".

Cuando un analizador léxico envía tokens al analizador, la representación utilizada suele ser un tipo enumerado , que es una lista de representaciones numéricas. Por ejemplo, "Identificador" se puede representar con 0, "Operador de asignación" con 1, "Operador de suma" con 2, etc.

Los tokens suelen definirse mediante expresiones regulares , que son entendidas por un generador de analizadores léxicos como lex o autómatas de estados finitos equivalentes codificados manualmente . El analizador léxico (generado automáticamente por una herramienta como lex o hand-crafted) lee un flujo de caracteres, identifica los lexemas en el flujo y los clasifica en tokens. Esto se denomina tokenización . Si el analizador léxico encuentra un token no válido, informará un error.

Después de la tokenización se realiza el análisis . A partir de ahí, los datos interpretados se pueden cargar en estructuras de datos para uso general, interpretación o compilación .

La especificación de un lenguaje de programación a menudo incluye un conjunto de reglas, la gramática léxica , que define la sintaxis léxica. La sintaxis léxica suele ser la de un lenguaje regular , con reglas gramaticales que consisten en expresiones regulares ; definen el conjunto de posibles secuencias de caracteres (lexemas) de un token. Un analizador léxico reconoce cadenas y, para cada tipo de cadena que encuentra, el programa léxico realiza una acción, la mayoría de las veces simplemente produce un token.

Dos categorías léxicas comunes importantes son los espacios en blanco y los comentarios . Estos también se definen en la gramática y son procesados ​​por el analizador léxico, pero pueden descartarse (no producir ningún token) y considerarse no significativos , a lo sumo separando dos tokens (como en if xlugar de ifx). Hay dos excepciones importantes a esto. Primero, en lenguajes de reglas fuera de juego que delimitan bloques con sangría, el espacio en blanco inicial es significativo, ya que determina la estructura del bloque y generalmente se maneja en el nivel del analizador léxico; vea la estructura de la frase, a continuación. En segundo lugar, en algunos usos de los analizadores léxicos, los comentarios y los espacios en blanco deben conservarse; por ejemplo, un prettyprinter también necesita mostrar los comentarios y algunas herramientas de depuración pueden proporcionar mensajes al programador que muestran el código fuente original. En la década de 1960, en particular para ALGOL , los espacios en blanco y los comentarios se eliminaron como parte de la fase de reconstrucción de línea (la fase inicial de la interfaz del compilador ), pero esta fase separada se ha eliminado y ahora los maneja el analizador léxico.

La primera etapa, el escáner , se basa generalmente en una máquina de estados finitos (FSM). Tiene codificada en su interior información sobre las posibles secuencias de caracteres que pueden estar contenidas en cualquiera de los tokens que maneja (las instancias individuales de estas secuencias de caracteres se denominan lexemas). Por ejemplo, un lexema entero puede contener cualquier secuencia de caracteres numéricos . En muchos casos, el primer carácter que no sea un espacio en blanco se puede utilizar para deducir el tipo de token que sigue y los caracteres de entrada posteriores se procesan uno a la vez hasta llegar a un carácter que no está en el conjunto de caracteres aceptables para ese token (esto se denomina regla de coincidencia máxima o de coincidencia más larga ). En algunos lenguajes, las reglas de creación de lexemas son más complejas y pueden implicar retroceder sobre caracteres leídos previamente. Por ejemplo, en C, un carácter 'L' no es suficiente para distinguir entre un identificador que comienza con 'L' y un literal de cadena de caracteres anchos.

Un lexema, sin embargo, es sólo una cadena de caracteres que se sabe que son de un cierto tipo (por ejemplo, una cadena literal, una secuencia de letras). Para construir un token, el analizador léxico necesita una segunda etapa, el evaluador , que recorre los caracteres del lexema para producir un valor . El tipo del lexema combinado con su valor es lo que constituye propiamente un token, que puede entregarse a un analizador. Algunos tokens como los paréntesis en realidad no tienen valores, por lo que la función evaluadora para estos no puede devolver nada: sólo se necesita el tipo. De manera similar, a veces los evaluadores pueden suprimir un lexema por completo, ocultándolo del analizador, lo que es útil para los espacios en blanco y los comentarios. Los evaluadores para identificadores suelen ser simples (representan literalmente el identificador), pero pueden incluir algo de desajuste de caracteres . Los evaluadores para literales enteros pueden pasar la cadena (aplazando la evaluación a la fase de análisis semántico), o pueden realizar la evaluación ellos mismos, lo que puede estar involucrado para diferentes bases o números de punto flotante. Para un literal de cadena entre comillas simple, el evaluador solo necesita eliminar las comillas, pero el evaluador de un literal de cadena con escape incorpora un analizador léxico, que elimina el escape de las secuencias de escape.

Por ejemplo, en el código fuente de un programa de computadora, la cadena

net_worth_future = (assets – liabilities);

podría convertirse en el siguiente flujo de token léxico; se suprimen los espacios en blanco y los caracteres especiales no tienen valor:

IDENTIFICADOR patrimonio neto futuroIGUALABRIR PARÉNTESISIDENTIFICADOR activosMENOSIDENTIFICADOR pasivosCERRAR PARÉNTESISPUNTO Y COMA

Los analizadores léxicos pueden escribirse a mano. Esto es práctico si la lista de tokens es pequeña, pero los analizadores léxicos generados por herramientas automatizadas como parte de una cadena de herramientas de compilador-compilador son más prácticos para una mayor cantidad de tokens potenciales. Estas herramientas generalmente aceptan expresiones regulares que describen los tokens permitidos en el flujo de entrada. Cada expresión regular está asociada con una regla de producción en la gramática léxica del lenguaje de programación que evalúa los lexemas que coinciden con la expresión regular. Estas herramientas pueden generar código fuente que se puede compilar y ejecutar o construir una tabla de transición de estados para una máquina de estados finitos (que se conecta al código de plantilla para compilar y ejecutar).

Las expresiones regulares representan de forma compacta los patrones que pueden seguir los caracteres de los lexemas. Por ejemplo, para un idioma basado en inglés , un token IDENTIFIER puede ser cualquier carácter alfabético inglés o un guión bajo, seguido de cualquier número de instancias de caracteres alfanuméricos ASCII o guiones bajos. Esto se puede representar de forma compacta con la cadena [a-zA-Z_][a-zA-Z_0-9]*. Esto significa "cualquier carácter az, AZ o _, seguido de 0 o más de az, AZ, _ o 0-9".

Las expresiones regulares y las máquinas de estados finitos que generan no son lo suficientemente potentes para manejar patrones recursivos, como " n paréntesis de apertura, seguidos de una declaración, seguidos de n paréntesis de cierre". No pueden llevar la cuenta y verificar que n sea el mismo en ambos lados, a menos que exista un conjunto finito de valores permisibles para n . Se necesita un analizador completo para reconocer tales patrones en su totalidad. Un analizador puede insertar paréntesis en una pila y luego intentar sacarlos y ver si la pila está vacía al final (ver el ejemplo ^[3] en el libro Estructura e interpretación de programas informáticos ).

Por lo general, la tokenización léxica se produce a nivel de palabra. Sin embargo, a veces resulta difícil definir qué se entiende por "palabra". A menudo, un tokenizador se basa en heurísticas simples, por ejemplo:

• La puntuación y los espacios en blanco pueden o no estar incluidos en la lista de tokens resultante.
• Todas las cadenas contiguas de caracteres alfabéticos son parte de un token; lo mismo ocurre con los números.
• Los tokens están separados por caracteres de espacio en blanco , como un espacio o un salto de línea, o por caracteres de puntuación.

En los lenguajes que utilizan espacios entre palabras (como la mayoría de los que utilizan el alfabeto latino y la mayoría de los lenguajes de programación), este enfoque es bastante sencillo. Sin embargo, incluso en este caso hay muchos casos extremos, como contracciones , palabras con guiones , emoticones y construcciones más grandes, como las URI (que para algunos fines pueden considerarse tokens individuales). Un ejemplo clásico es "con sede en Nueva York", que un tokenizador ingenuo puede dividir en el espacio, aunque la mejor división es (posiblemente) en el guion.

La tokenización es particularmente difícil para los idiomas escritos en scriptio continua , que no presentan límites de palabras, como el griego antiguo , el chino ^[4] o el tailandés . Los idiomas aglutinantes , como el coreano, también complican las tareas de tokenización .

Algunas formas de abordar los problemas más difíciles incluyen el desarrollo de heurísticas más complejas, la consulta de una tabla de casos especiales comunes o el ajuste de los tokens a un modelo de lenguaje que identifique colocaciones en un paso de procesamiento posterior.

Los analizadores léxicos suelen generarse mediante un generador de analizadores léxicos , análogo a los generadores de analizadores sintácticos , y estas herramientas suelen ir juntas. El más establecido es lex , emparejado con el generador de analizadores sintácticos yacc , o más bien algunas de sus muchas reimplementaciones, como flex (a menudo emparejado con GNU Bison ). Estos generadores son una forma de lenguaje específico de dominio , que toman una especificación léxica (generalmente expresiones regulares con algún marcado) y emiten un analizador léxico.

Estas herramientas permiten un desarrollo muy rápido, lo cual es muy importante en las primeras etapas del desarrollo, tanto para obtener un analizador léxico funcional como porque la especificación de un lenguaje puede cambiar con frecuencia. Además, suelen proporcionar funciones avanzadas, como condiciones previas y posteriores, que son difíciles de programar a mano. Sin embargo, un analizador léxico generado automáticamente puede carecer de flexibilidad y, por lo tanto, puede requerir alguna modificación manual o un analizador léxico escrito completamente de forma manual.

El rendimiento del analizador léxico es una preocupación, y vale la pena optimizarlo, más aún en lenguajes estables donde el analizador léxico se ejecuta muy a menudo (como C o HTML). Los analizadores léxicos generados por lex/flex son razonablemente rápidos, pero es posible lograr mejoras de dos a tres veces utilizando generadores más ajustados. A veces se utilizan analizadores léxicos escritos a mano, pero los generadores de analizadores léxicos modernos producen analizadores léxicos más rápidos que la mayoría de los codificados a mano. La familia de generadores lex/flex utiliza un enfoque basado en tablas que es mucho menos eficiente que el enfoque codificado directamente. ^{[ dudoso – discutir ]} Con el último enfoque, el generador produce un motor que salta directamente a los estados de seguimiento a través de declaraciones goto. Herramientas como re2c ^[5] han demostrado producir motores que son entre dos y tres veces más rápidos que los motores producidos por flex. ^{[ cita requerida ]} En general, es difícil escribir a mano analizadores que funcionen mejor que los motores generados por estas últimas herramientas.

El análisis léxico segmenta principalmente el flujo de entrada de caracteres en tokens, simplemente agrupando los caracteres en partes y clasificándolos. Sin embargo, el análisis léxico puede ser significativamente más complejo; de manera más simple, los analizadores léxicos pueden omitir tokens o insertar tokens adicionales. Omitir tokens, en particular espacios en blanco y comentarios, es muy común cuando el compilador no los necesita. Con menos frecuencia, se pueden insertar tokens adicionales. Esto se hace principalmente para agrupar tokens en declaraciones , o declaraciones en bloques, para simplificar el analizador.

La continuación de línea es una característica de algunos lenguajes en los que una nueva línea es normalmente un terminador de sentencia. La mayoría de las veces, terminar una línea con una barra invertida (seguida inmediatamente por una nueva línea ) da como resultado que la línea continúe : la línea siguiente se une a la línea anterior. Esto generalmente se hace en el analizador léxico: la barra invertida y la nueva línea se descartan, en lugar de convertir la nueva línea en tokens. Algunos ejemplos incluyen bash , ^[6] otros scripts de shell y Python. ^[7]

Muchos lenguajes utilizan el punto y coma como terminador de una declaración. La mayoría de las veces esto es obligatorio, pero en algunos lenguajes el punto y coma es opcional en muchos contextos. Esto se hace principalmente en el nivel del analizador léxico, donde el analizador léxico genera un punto y coma en el flujo de tokens, a pesar de que no esté presente en el flujo de caracteres de entrada, y se denomina inserción de punto y coma o inserción automática de punto y coma . En estos casos, los puntos y coma son parte de la gramática formal de frases del lenguaje, pero pueden no encontrarse en el texto de entrada, ya que pueden ser insertados por el analizador léxico. Los puntos y coma opcionales u otros terminadores o separadores también se manejan a veces en el nivel del analizador, en particular en el caso de comas finales o puntos y comas.

La inserción de punto y coma es una característica de BCPL y su descendiente lejano Go , ^[8] aunque está ausente en B o C. ^[9] La inserción de punto y coma está presente en JavaScript , aunque las reglas son algo complejas y muy criticadas; para evitar errores, algunos recomiendan usar siempre punto y coma, mientras que otros usan punto y coma iniciales, denominados punto y coma defensivos , al comienzo de declaraciones potencialmente ambiguas.

La inserción de punto y coma (en idiomas con declaraciones terminadas en punto y coma) y la continuación de línea (en idiomas con declaraciones terminadas en nueva línea) pueden verse como complementarias: la inserción de punto y coma agrega un token aunque las nuevas líneas generalmente no generan tokens, mientras que la continuación de línea evita que se genere un token aunque las nuevas líneas generalmente sí generan tokens.

La regla del off-side (bloques determinados por sangría) se puede implementar en el analizador léxico, como en Python , donde aumentar la sangría da como resultado que el analizador léxico emita un token INDENT y disminuir la sangría da como resultado que el analizador léxico emita uno o más tokens DEDENT. ^[10] Estos tokens corresponden a la llave de apertura {y la llave de cierre }en lenguajes que usan llaves para bloques y significa que la gramática de frases no depende de si se usan llaves o sangría. Esto requiere que el analizador léxico mantenga el estado, es decir, una pila de niveles de sangría, y por lo tanto puede detectar cambios en la sangría cuando esta cambia, y por lo tanto la gramática léxica no es libre de contexto : INDENT–DEDENT dependen de la información contextual de los niveles de sangría anteriores.

En general, las gramáticas léxicas son independientes del contexto, o casi, y por lo tanto no requieren mirar hacia atrás ni hacia adelante, ni retroceder, lo que permite una implementación simple, limpia y eficiente. Esto también permite una comunicación unidireccional simple del analizador léxico al analizador sin necesidad de que fluya información de vuelta al analizador léxico.

Sin embargo, existen excepciones. Algunos ejemplos simples incluyen la inserción de punto y coma en Go, que requiere mirar hacia atrás un token; la concatenación de cadenas literales consecutivas en Python, ^[7] que requiere mantener un token en un búfer antes de emitirlo (para ver si el siguiente token es otra cadena literal); y la regla del off-side en Python, que requiere mantener un recuento de niveles de sangría (de hecho, una pila de cada nivel de sangría). Todos estos ejemplos solo requieren contexto léxico y, si bien complican un poco el análisis léxico, son invisibles para el analizador y las fases posteriores.

Un ejemplo más complejo es el truco del analizador léxico en C, donde la clase de token de una secuencia de caracteres no se puede determinar hasta la fase de análisis semántico, ya que los nombres de los tipos definidos y los nombres de las variables son léxicamente idénticos, pero constituyen clases de token diferentes. Por lo tanto, en el truco, el analizador léxico llama al analizador semántico (por ejemplo, la tabla de símbolos) y verifica si la secuencia requiere un nombre de tipo definido. En este caso, la información debe fluir de regreso no solo desde el analizador sintáctico, sino desde el analizador semántico de regreso al analizador léxico, lo que complica el diseño.

• Lexicalización
• Semántica léxica
• Lista de generadores de analizadores sintácticos

• Yang, W.; Tsay, Chey-Woei; Chan, Jien-Tsai (2002). "Sobre la aplicabilidad de la regla de la coincidencia más larga en el análisis léxico". Lenguajes informáticos, sistemas y estructuras . 28 (3): 273–288. doi :10.1016/S0096-0551(02)00014-0. NSC 86-2213-E-009-021 y NSC 86-2213-E-009-079.
• Trim, Craig (23 de enero de 2013). "El arte de la tokenización". Developer Works . IBM. Archivado desde el original el 30 de mayo de 2019.
• Tarea de segmentación de mención de palabras, un análisis