La tokenización léxica es la conversión de un texto en tokens léxicos significativos (semántica o sintácticamente) 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 no es el mismo proceso que la tokenización probabilística, utilizada para el preprocesamiento de datos de un modelo de lenguaje grande , que codifica texto en tokens numéricos , utilizando codificación de pares de bytes .
Un programa basado en reglas que realiza tokenización léxica se llama tokenizer , [1] o scanner , aunque scanner también es un término para la primera etapa de un lexer. Un lexer forma la primera fase de la interfaz de un compilador en procesamiento. El análisis generalmente ocurre en una sola pasada. Los Lexers y analizadores se utilizan con mayor frecuencia para compiladores, pero se pueden utilizar para otras herramientas de lenguaje informático, como Prettyprinters o Linter . Lexing se puede dividir en dos etapas: el escaneo , que segmenta la cadena de entrada en unidades sintácticas llamadas lexemas y las categoriza en clases de tokens; y la evaluación , que convierte lexemas en valores procesados.
Los lexers son generalmente bastante simples, y la mayor parte de la complejidad se remite al análisis sintáctico o las fases de análisis semántico y, a menudo, pueden generarse mediante un generador de lexer, en particular lex o derivados. Sin embargo, los lexers a veces pueden incluir cierta complejidad, como el procesamiento de estructuras de frases para facilitar la entrada y simplificar el analizador, y pueden escribirse parcial o totalmente a mano, ya sea para admitir más funciones o para mejorar el rendimiento.
Lo que se llama "lexema" en el procesamiento del lenguaje natural basado en reglas no es igual a lo que se llama lexema en lingüística. Lo que se llama "lexema" en el procesamiento del lenguaje natural basado en reglas puede ser igual al equivalente lingüístico sólo en lenguajes analíticos , como el inglés, pero no en lenguajes altamente sintéticos , como los lenguajes fusionales . Lo que se llama lexema en el procesamiento del lenguaje natural basado en reglas es más parecido a lo que se llama palabra en lingüística (no confundir con una palabra en arquitectura informática ), aunque en algunos casos puede ser más parecido a un morfema .
Un token léxico es una cadena con un significado asignado y, por tanto, identificado, en contraste con el token probabilístico utilizado en grandes modelos lingüísticos . El token léxico consta de un nombre de token y un valor de token opcional . El nombre del 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 arroja 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 "lexer", como identificadores, operadores, símbolos de agrupación y tipos de datos. Los tokens resultantes luego se pasan a alguna otra forma de procesamiento. El proceso puede considerarse una subtarea de análisis de entradas.
Por ejemplo, en la cadena de texto :
The quick brown fox jumps over the lazy dogla cadena no está implícitamente segmentada en espacios, como lo haría un hablante de lenguaje natural . La entrada sin formato, los 43 caracteres, debe dividirse explícitamente en los 9 tokens con un delimitador de espacio determinado (es decir, que coincida con la cadena " "o expresión regular /\s{1}/ ).
Cuando una clase de token representa más de un lexema posible, el lexer a menudo guarda suficiente información para reproducir el lexema original, de modo que pueda usarse en el análisis semántico . El analizador normalmente recupera esta información del lexer 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 lexer. Algunos métodos utilizados para identificar tokens incluyen: expresiones regulares , secuencias específicas de caracteres denominadas bandera , caracteres de separación específicos llamados delimitadores y definición explícita mediante un diccionario. Los lexers suelen utilizar caracteres especiales, incluidos los 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 queda para un analizador . 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 lexer alimenta tokens al analizador, la representación utilizada suele ser una lista enumerada de representaciones numéricas. Por ejemplo, "Identificador" se representa con 0, "Operador de asignación" con 1, "Operador de suma" con 2, etc.
Los tokens se definen a menudo mediante expresiones regulares , que se entienden mediante un generador de analizador léxico como lex , o autómatas de estado finito equivalentes codificados a mano . El analizador léxico (generado automáticamente por una herramienta como lex, o hecho a mano) lee una secuencia de caracteres, identifica los lexemas en la secuencia y los clasifica en tokens. Esto se denomina tokenización . Si el lexer encuentra un token no válido, informará un error.
La siguiente tokenización es 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 suele incluir 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 , y las reglas gramaticales consisten en expresiones regulares ; definen el conjunto de posibles secuencias de caracteres (lexemas) de un token. Un lexer reconoce cadenas, y para cada tipo de cadena encontrada, el programa léxico realiza una acción, generalmente produciendo 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 lexer, pero pueden descartarse (sin producir ningún token) y considerarse no significativos , separando como máximo dos tokens (como en if xlugar de ifx). Hay dos excepciones importantes a esto. En primer lugar, en los lenguajes de reglas fuera de juego que delimitan bloques con sangría, el espacio en blanco inicial es importante, ya que determina la estructura del bloque y generalmente se maneja en el nivel de lexer; consulte la estructura de la frase a continuación. En segundo lugar, en algunos usos de lexers, se deben conservar los comentarios y los espacios en blanco; por ejemplo, una impresora bonita también necesita generar 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, especialmente 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 eliminó y ahora son manejados por el lexer.
La primera etapa, el escáner , suele basarse en una máquina de estados finitos (FSM). Tiene codificada 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 de números enteros puede contener cualquier secuencia de caracteres de dígitos numéricos . En muchos casos, el primer carácter que no es 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 masticación máxima o coincidencia más larga ). En algunos idiomas, 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 una cadena literal de caracteres anchos.
Un lexema, sin embargo, es sólo una cadena de caracteres que se sabe que son de 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 repasa los caracteres del lexema para producir un valor . El tipo de lexema combinado con su valor es lo que constituye propiamente un token, que se puede entregar a un analizador. Algunos tokens, como los paréntesis, en realidad no tienen valores, por lo que la función evaluadora de estos no puede devolver nada: solo se necesita el tipo. De manera similar, a veces los evaluadores pueden suprimir un lexema por completo, ocultándolo del analizador, lo cual es útil para espacios en blanco y comentarios. Los evaluadores de identificadores suelen ser simples (literalmente representan el identificador), pero pueden incluir algunos desajustadores . Los evaluadores de literales enteros pueden pasar la cadena (diferiendo la evaluación a la fase de análisis semántico) o pueden realizar la evaluación ellos mismos, lo que puede implicar diferentes bases o números de punto flotante. Para un literal de cadena entrecomillado simple, el evaluador necesita eliminar solo las comillas, pero el evaluador de un literal de cadena con escape incorpora un lexer, 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 tokens léxicos; los espacios en blanco se suprimen y los caracteres especiales no tienen valor:
IDENTIFICADOR valor_neto_futuroIGUALOPEN_PARENTHESISIDENTIFICADOR de activosMENOSPasivos del IDENTIFICADORCLOSE_PARENTHESISPUNTO Y COMA
Los Lexers pueden escribirse a mano. Esto es práctico si la lista de tokens es pequeña, pero los lexers generados por herramientas automatizadas como parte de una cadena de herramientas 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 a 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 estado 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 patrones que podrían seguir los caracteres de los lexemas. Por ejemplo, para un idioma basado en inglés , un token IDENTIFICADOR podría 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 y/o guiones bajos. Esto podría representarse de forma compacta mediante 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, seguido de una declaración, seguido de n paréntesis de cierre". No pueden llevar la cuenta y verificar que n es 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 toda su generalidad. Un analizador puede insertar paréntesis en una pila y luego intentar sacarlos y ver si la pila está vacía al final (consulte el ejemplo [3] en el libro Estructura e interpretación de programas de computadora ).
Normalmente, 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:
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 aquí hay muchos casos extremos, como contracciones , palabras con guiones , emoticones y construcciones más grandes como URI (que para algunos propósitos pueden contar como tokens únicos). Un ejemplo clásico es "con sede en Nueva York", en el que un tokenizador ingenuo puede romper el espacio aunque la mejor ruptura sea (posiblemente) el guión.
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 lenguajes aglutinantes , como el coreano, también complican las tareas de tokenización.
Algunas formas de abordar los problemas más difíciles incluyen desarrollar heurísticas más complejas, consultar una tabla de casos especiales comunes o ajustar los tokens a un modelo de lenguaje que identifique colocaciones en un paso de procesamiento posterior.
Los lexers suelen ser generados por un generador de lexer , análogo a los generadores de analizadores , y estas herramientas suelen venir juntas. El más establecido es lex , combinado con el generador de analizador yacc , o más bien algunas de sus muchas reimplementaciones, como flex (a menudo combinado con GNU Bison ). Estos generadores son una forma de lenguaje de dominio específico , que toma una especificación léxica (generalmente expresiones regulares con algún marcado) y emite un lexer.
Estas herramientas producen un desarrollo muy rápido, lo cual es muy importante en las primeras etapas del desarrollo, tanto para obtener un lexer que funcione como porque la especificación del lenguaje puede cambiar con frecuencia. Además, suelen proporcionar funciones avanzadas, como condiciones previas y posteriores, que son difíciles de programar manualmente. Sin embargo, un lexer generado automáticamente puede carecer de flexibilidad y, por lo tanto, puede requerir alguna modificación manual o un lexer escrito totalmente manualmente.
El rendimiento de Lexer es una preocupación y vale la pena optimizarlo, más aún en lenguajes estables donde Lexer se ejecuta con mucha frecuencia (como C o HTML). Los lexers generados por lex/flex son razonablemente rápidos, pero es posible realizar mejoras de dos a tres veces utilizando más generadores sintonizados. A veces se utilizan lexers escritos a mano, pero los generadores de lexers modernos producen lexers 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 ] Con el último enfoque, el generador produce un motor que salta directamente a los estados de seguimiento mediante 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 con flexibilidad. [ cita necesaria ] 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 categorizándolos. Sin embargo, la lexing puede ser significativamente más compleja; En pocas palabras, los lexers pueden omitir tokens o insertar tokens adicionales. Omitir tokens, especialmente 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 donde una nueva línea normalmente es un terminador de declaración. 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 lexer: la barra invertida y la nueva línea se descartan, en lugar de tokenizar la nueva línea. Los ejemplos incluyen bash , [6] otros scripts de shell y Python. [7]
Muchos idiomas utilizan el punto y coma como terminador de declaraciones. En la mayoría de los casos, esto es obligatorio, pero en algunos idiomas el punto y coma es opcional en muchos contextos. Esto se hace principalmente en el nivel del lexer, donde el lexer genera un punto y coma en el flujo del token, 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, el punto y coma son parte de la gramática de frases formales del idioma, pero es posible que no se encuentren en el texto de entrada, ya que el lexer puede insertarlos. Los puntos y coma opcionales u otros terminadores o separadores también se manejan a veces en el nivel del analizador, especialmente en el caso de comas o puntos y coma al final.
La inserción de punto y coma es una característica de BCPL y su lejano descendiente 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 un token que se generen, aunque las nuevas líneas generalmente generan tokens.
La regla fuera de juego (bloques determinados mediante sangría) se puede implementar en el lexer, como en Python , donde aumentar la sangría da como resultado que el lexer emita un token INDENT, y disminuir la sangría da como resultado que el lexer emita uno o más tokens DEDENT. [10] Estos tokens corresponden a la llave de apertura {y la llave de cierre }en los idiomas que usan llaves para los bloques, y significa que la gramática de la frase no depende de si se usan llaves o sangría. Esto requiere que el lexer mantenga el estado, es decir, una pila de niveles de sangría, y por lo tanto pueda detectar cambios en la sangría cuando ésta cambia y, por lo tanto, la gramática léxica no está libre de contexto : INDENT-DEDENT depende de la información contextual de los niveles de sangría anteriores.
Generalmente, las gramáticas léxicas están libres de contexto, o casi, y por lo tanto no requieren mirar hacia atrás o hacia adelante, ni retroceder, lo que permite una implementación simple, limpia y eficiente. Esto también permite una comunicación unidireccional sencilla entre Lexer y el analizador, sin necesidad de que ninguna información regrese al Lexer.
Sin embargo, hay excepciones. Ejemplos simples incluyen: inserción de punto y coma en Go, que requiere mirar hacia atrás un token; concatenación de literales de cadena consecutivos en Python, [7] que requiere mantener un token en un búfer antes de emitirlo (para ver si el siguiente token es otro literal de cadena); y la regla fuera de juego en Python, que requiere mantener un recuento del nivel 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 al lexer, son invisibles para el analizador y las fases posteriores.
Un ejemplo más complejo es el truco de lexer 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 typedef y los nombres de variables son léxicamente idénticos pero constituyen clases de token diferentes. Por lo tanto, en el truco, el lexer llama al analizador semántico (por ejemplo, la tabla de símbolos) y verifica si la secuencia requiere un nombre de definición de tipo. En este caso, la información debe fluir no sólo desde el analizador, sino desde el analizador semántico hasta el lexer, lo que complica el diseño.