Hispanopedia WikiLa tokenización léxica consiste en convertir un texto en tokens léxicos con significado (semántico o sintáctico) pertenecientes a categorías definidas por un programa analizador léxico. En el caso de un lenguaje natural, estas categorías incluyen sustantivos, verbos, adjetivos, signos de puntuación, etc. En el caso de un lenguaje de programación, las categorías incluyen identificadores , operadores , símbolos de agrupación , tipos de datos y palabras clave del lenguaje. 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 se basa generalmente en una gramática léxica , mientras que los tokenizadores de LLM se basan generalmente en probabilidades . En segundo lugar, los tokenizadores de LLM realizan un segundo paso que convierte los tokens en valores numéricos.
Programas basados en reglas
Un programa basado en reglas que realiza la 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 constituye la primera fase del front-end de un compilador en el procesamiento. El análisis generalmente ocurre en una sola pasada. Los analizadores léxicos y sintácticos se utilizan con mayor frecuencia para compiladores, pero pueden utilizarse para otras herramientas de lenguajes de computadora, como formateadores o analizadores de código . El análisis léxico 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 los lexemas en valores procesados.
Los analizadores léxicos suelen ser bastante sencillos, con la mayor parte de la complejidad reservada a las fases de análisis sintáctico o semántico , y a menudo pueden generarse mediante un generador de analizadores léxicos , como Lex o sus derivados. Sin embargo, en ocasiones pueden incluir cierta complejidad, como el procesamiento de la estructura de las frases para facilitar la entrada de datos y simplificar el analizador sintáctico, y pueden escribirse parcial o totalmente a mano, ya sea para admitir más funcionalidades o para mejorar el rendimiento.
Desambiguación de "lexema"
Lo que se denomina "lexema" en el procesamiento del lenguaje natural basado en reglas no es equivalente a lo que se denomina lexema en lingüística. Lo que se denomina "lexema" en el procesamiento del lenguaje natural basado en reglas solo puede ser equivalente a su equivalente lingüístico en lenguas analíticas , como el inglés, pero no en lenguas altamente sintéticas , como las lenguas fusionales . Lo que se denomina lexema en el procesamiento del lenguaje natural basado en reglas se asemeja más a lo que se denomina palabra en lingüística (que no debe confundirse con una palabra en arquitectura de computadoras ), aunque en algunos casos puede asemejarse más a un morfema .
Token léxico y tokenización léxica
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 grandes modelos de lenguaje . Un 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 ]
Consideremos 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 en lingüística podría denominarse una parte de la oración .
La tokenización léxica consiste en convertir un texto sin formato en tokens léxicos con significado (semántico o sintáctico), 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 procesan posteriormente. Este proceso puede considerarse una subtarea del análisis sintáctico 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 por espacios, como lo haría un hablante de lenguaje natural" " . La entrada sin procesar, los 43 caracteres, debe dividirse explícitamente en los 9 tokens con un delimitador de espacio dado (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 para identificar tokens incluyen expresiones regulares , secuencias específicas de caracteres denominadas indicadores , caracteres separadores específicos llamados delimitadores y la definición explícita mediante un diccionario. Los analizadores léxicos suelen utilizar caracteres especiales, incluidos los signos de puntuación, para identificar tokens debido a su uso natural en lenguajes escritos y de programación. Un analizador léxico generalmente no procesa combinaciones de tokens, tarea que corresponde a un analizador sintáctico . Por ejemplo, un analizador léxico típico reconoce los paréntesis como tokens, pero no se asegura de que cada paréntesis se corresponda con un paréntesis.
Cuando un analizador léxico introduce tokens en el analizador sintáctico, 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 interpretadas por un generador de analizadores léxicos como lex , o por autómatas finitos equivalentes programados manualmente . El analizador léxico (generado automáticamente por una herramienta como lex o programado manualmente) lee una secuencia de caracteres, identifica los lexemas y los clasifica en tokens. Este proceso se denomina tokenización . Si el analizador léxico encuentra un token no válido, informará de un error.
Tras la tokenización, se procede al análisis sintáctico . A partir de ahí, los datos interpretados pueden cargarse en estructuras de datos para su uso general, interpretación o compilación .
Gramática léxica
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. Esta sintaxis generalmente es un lenguaje regular , cuyas reglas gramaticales consisten en expresiones regulares ; estas definen el conjunto de secuencias de caracteres posibles (lexemas) de un token. Un analizador léxico reconoce cadenas de caracteres y, para cada tipo de cadena encontrada, el programa léxico realiza una acción, que en el mejor de los casos consiste en generar 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 (sin producir ningún token) y considerarse no significativos , separando como máximo dos tokens (como en lugar de ). Hay dos excepciones importantes a esto. Primero, en lenguajes de reglas fuera del lado que delimitan bloques con sangría, el espacio en blanco inicial es significativo, ya que determina la estructura del bloque, y generalmente se maneja a nivel del analizador léxico; véase estructura de frase , más abajo. Segundo, en algunos usos de analizadores léxicos, los comentarios y los espacios en blanco deben conservarse; por ejemplo, un formateador de código 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, 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 del frontend del compilador ), pero esta fase separada se ha eliminado y ahora son manejados por el analizador léxico.if xifx
Detalles
Escáner
La primera etapa, el escáner , suele basarse en una máquina de estados finitos (FSM). Contiene información codificada sobre las posibles secuencias de caracteres que pueden estar presentes en cualquiera de los tokens que procesa (las instancias individuales de estas secuencias de caracteres se denominan lexemas ). Por ejemplo, un lexema entero puede contener cualquier secuencia de dígitos numéricos . En muchos casos, el primer carácter que no sea un espacio en blanco se puede usar para deducir el tipo de token que le sigue, y los caracteres de entrada subsiguientes se procesan uno a uno hasta encontrar 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 solo carácter 'L' no es suficiente para distinguir entre un identificador que comienza con 'L' y un literal de cadena de caracteres anchos.
Evaluador
Un lexema , sin embargo, es simplemente una cadena de caracteres que se sabe que pertenece a un tipo determinado (por ejemplo, una cadena literal, una secuencia de letras). La segunda etapa de un analizador léxico, el evaluador , recorre los caracteres del lexema para producir un valor que contiene información relevante para el analizador sintáctico.
El tipo de lexema, combinado con su valor, es lo que propiamente constituye un token . El valor del token puede ser cualquier valor que el analizador sintáctico considere necesario para interpretar un token de ese tipo. Algunos ejemplos de valores típicos producidos por un evaluador incluyen:
- Un token para un identificador a menudo simplemente contendrá los caracteres del lexema asociado.
- Los valores de los tokens para palabras clave y caracteres especiales generalmente se omiten, ya que el tipo por sí solo contiene toda la información necesaria.
- Los evaluadores que procesan literales enteros pueden pasar la cadena tal cual (dejando la evaluación para la fase de análisis semántico) o pueden realizar la evaluación ellos mismos para producir valores numéricos.
- Para una cadena literal entre comillas simple, el evaluador solo necesita eliminar las comillas, pero el evaluador para una cadena literal con caracteres de escape también puede incorporar un analizador léxico, que elimina los caracteres de escape.
El evaluador también puede suprimir un lexema por completo, ocultándolo al analizador sintáctico, lo cual resulta útil para los espacios en blanco y los comentarios.
Por ejemplo, en el código fuente de un programa informático, la cadena
net_worth_future=(assets–liabilities);
podría convertirse en la siguiente secuencia de tokens léxicos; donde cada línea representa un token compuesto por un TYPEseguido de un valor opcional:
IDENTIFICADOR "net_worth_future" IGUAL PARÉNTESIS ABIERTO IDENTIFICADOR "activos" MENOS IDENTIFICADOR "pasivos" CERRAR_PARÉNTESIS PUNTO Y COMA
Los analizadores léxicos pueden escribirse manualmente. Esto resulta práctico si la lista de tokens es pequeña, pero los generados por herramientas automatizadas como parte de una cadena de compilación son más prácticos para un mayor número de tokens potenciales. Estas herramientas generalmente aceptan expresiones regulares que describen los tokens permitidos en el flujo de entrada. Cada expresión regular se asocia 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 integra en código plantilla para su compilación y ejecución).
Las expresiones regulares representan de forma compacta los patrones que pueden seguir los caracteres de los lexemas. Por ejemplo, en un idioma basado en inglés , un token IDENTIFICADOR podría ser cualquier carácter alfabético inglés o un guion bajo, seguido de cualquier número de caracteres alfanuméricos ASCII y/o guiones bajos. Esto se podría representar 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, seguidos de una instrucción, seguidos de n paréntesis de cierre". No pueden llevar la cuenta ni verificar que n sea el mismo en ambos lados, a menos que exista un conjunto finito de valores permitidos para n . Se requiere un analizador sintáctico completo para reconocer tales patrones en toda su generalidad. Un analizador sintáctico puede insertar paréntesis en una pila y luego intentar extraerlos para ver si la pila está vacía al final (véase el ejemplo [ 3 ] en el libro Estructura e interpretación de programas informáticos ).
Obstáculos
Por lo general, la tokenización léxica se realiza a nivel de palabra. Sin embargo, a veces es difícil definir qué se entiende por "palabra". A menudo, un tokenizador se basa en heurísticas simples, por ejemplo:
- La lista de tokens resultante puede incluir o no signos de puntuación y espacios en blanco.
- Todas las cadenas contiguas de caracteres alfabéticos forman parte de un mismo 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 idiomas que utilizan espacios entre palabras (como la mayoría de los que usan el alfabeto latino y la mayoría de los lenguajes de programación), este enfoque es bastante sencillo. Sin embargo, incluso aquí existen muchos casos especiales, como contracciones , palabras con guion , emoticonos y construcciones más grandes como las URI (que para algunos propósitos pueden considerarse tokens individuales). Un ejemplo clásico es "New York-based", que un analizador léxico ingenuo podría dividir en el espacio, aunque la división más adecuada sea (posiblemente) en el guion.
La tokenización es particularmente difícil para lenguas escritas en scriptio continua , que no presentan límites de palabras, como el griego antiguo , el chino [ 4 ] o el tailandés . Las lenguas aglutinantes , como el coreano, también complican las tareas de tokenización.
Algunas maneras 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 una etapa de procesamiento posterior.
Generador léxico
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 a menudo se utilizan conjuntamente. El más consolidado es lex , junto con el generador de analizadores sintácticos yacc , o más bien con alguna de sus numerosas reimplementaciones, como flex (que suele utilizarse con GNU Bison ). Estos generadores son una forma de lenguaje específico de dominio que recibe una especificación léxica —generalmente expresiones regulares con algún marcado— y genera un analizador léxico.
Estas herramientas permiten un desarrollo muy rápido, lo cual es fundamental en las primeras etapas, tanto para obtener un analizador léxico funcional como porque la especificación del lenguaje puede cambiar con frecuencia. Además, suelen ofrecer funciones avanzadas, como precondiciones y postcondiciones, que son difíciles de programar manualmente. Sin embargo, un analizador léxico generado automáticamente puede carecer de flexibilidad y, por lo tanto, requerir modificaciones manuales, o incluso un analizador léxico escrito completamente a mano.
El rendimiento del analizador léxico es importante, y su optimización es valiosa, sobre todo en lenguajes estables donde el analizador se ejecuta con mucha frecuencia (como C o HTML). Los analizadores generados por lex/flex son razonablemente rápidos, pero es posible lograr mejoras de dos a tres veces utilizando generadores más optimizados. A veces se utilizan analizadores escritos a mano, pero los generadores modernos producen analizadores más rápidos que la mayoría de los codificados manualmente. La familia de generadores lex/flex utiliza un enfoque basado en tablas, mucho menos eficiente que el enfoque de codificación directa. Con este último, el generador produce un motor que salta directamente a los estados subsiguientes mediante sentencias goto. Herramientas como re2c [ 5 ] han demostrado producir motores entre dos y tres veces más rápidos que los generados por flex. En general, es difícil escribir manualmente analizadores que superen el rendimiento de los motores generados por estas últimas herramientas.
Estructura de la frase
El análisis léxico segmenta principalmente el flujo de caracteres de entrada en tokens, agrupándolos y categorizándolos. Sin embargo, el análisis léxico puede ser significativamente más complejo; en su forma más simple, los analizadores léxicos pueden omitir tokens o insertar otros. Omitir tokens, especialmente espacios en blanco y comentarios, es muy común cuando el compilador no los necesita. Con menos frecuencia, se insertan tokens. Esto se hace principalmente para agrupar tokens en sentencias o sentencias en bloques, simplificando así el análisis sintáctico.
continuación de línea
La continuación de línea es una característica de algunos lenguajes donde un salto de línea normalmente termina una instrucción. Generalmente, terminar una línea con una barra invertida (seguida inmediatamente de un salto de línea ) da como resultado que la línea continúe ; la siguiente línea se une a la anterior. Esto generalmente se realiza en el analizador léxico: la barra invertida y el salto de línea se descartan, en lugar de tokenizar el salto de línea. Algunos ejemplos incluyen bash , [ 6 ] otros scripts de shell y Python. [ 7 ]
Inserción de punto y coma
Muchos idiomas utilizan el punto y coma como terminador de oraciones. Generalmente es obligatorio, pero en algunos idiomas es opcional en muchos contextos. Esto se realiza principalmente a nivel del analizador léxico, donde este inserta un punto y coma en el flujo de tokens, aunque no esté presente en el flujo de caracteres de entrada; este proceso se denomina inserción de punto y coma o inserción automática de punto y coma . En estos casos, el punto y coma forma parte de la gramática formal de frases del idioma, pero puede que no aparezca en el texto de entrada, ya que el analizador léxico puede insertarlo. Los puntos y comas opcionales u otros terminadores o separadores también se manejan a veces a nivel del analizador sintáctico, especialmente en el caso de comas o puntos y comas finales .
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 lenguajes con sentencias terminadas en punto y coma) y la continuación de línea (en lenguajes con sentencias terminadas en salto de línea) pueden considerarse complementarias: la inserción de punto y coma añade un token aunque los saltos de línea generalmente no generan tokens, mientras que la continuación de línea impide que se genere un token aunque los saltos de línea generalmente sí los generan.
Regla del fuera de juego
La regla del lado opuesto (bloques determinados por la indentación) puede implementarse en el analizador léxico, como en Python , donde aumentar la indentación resulta en que el analizador léxico emita un token INDENT y disminuir la indentación resulta en 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 la frase no depende de si se usan llaves o indentación. Esto requiere que el analizador léxico mantenga un estado, es decir, una pila de niveles de indentación, y por lo tanto puede detectar cambios en la indentación cuando esto 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 indentación anteriores.
Análisis léxico sensible al contexto
En general, las gramáticas léxicas son independientes del contexto, o casi, y por lo tanto no requieren retroceder ni avanzar, lo que permite una implementación sencilla, limpia y eficiente. Esto también facilita una comunicación unidireccional simple entre el analizador léxico y el analizador sintáctico, sin necesidad de que la información regrese al analizador léxico.
Sin embargo, existen excepciones. Algunos ejemplos sencillos incluyen la inserción de punto y coma en Go, que requiere retroceder un token; la concatenación de literales de cadena consecutivos en Python, [ 7 ] que requiere mantener un token en un búfer antes de emitirlo (para comprobar si el siguiente token es otro literal de cadena); y la regla de fuera de lado en Python, que requiere mantener un recuento del nivel de indentación (de hecho, una pila de cada nivel de indentación). Todos estos ejemplos solo requieren contexto léxico y, si bien complican un poco el análisis léxico, son invisibles para el analizador sintáctico 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 tipo definidos y los nombres de variables son léxicamente idénticos, pero constituyen clases de token diferentes. Por lo tanto, en este truco, el analizador léxico llama al analizador semántico (por ejemplo, la tabla de símbolos) y comprueba si la secuencia requiere un nombre de tipo definido. En este caso, la información debe fluir no solo desde el analizador sintáctico, sino también desde el analizador semántico hacia el analizador léxico, lo que complica el diseño.
Véase también
Referencias
- ↑ " Anatomía de un compilador y el tokenizador" . www.cs.man.ac.uk.
- ↑ página 111, "Compilers Principles, Techniques, & Tools, 2nd Ed." (WorldCat) por Aho, Lam, Sethi y Ullman, citado en https://stackoverflow.com/questions/14954721/what-is-the-difference-between-token-and-lexeme
- ↑ "Estructura e interpretación de programas informáticos" . mitpress.mit.edu . Archivado del original el 30 de octubre de 2012. Consultado el 7 de marzo de 2009 .
- ↑ Huang, C., Simon, P., Hsieh, S., & Prevot, L. (2007) Repensando la segmentación de palabras chinas: tokenización, clasificación de caracteres o identificación de rupturas de palabras
- ↑ Bumbulis, P.; Cowan, DD (marzo-diciembre de 1993). "RE2C: Un generador de escáner más versátil" . ACM Letters on Programming Languages and Systems . 2 ( 1–4 ): 70–84 . doi : 10.1145/176454.176487 . S2CID 14814637 .
- ↑ Manual de referencia de Bash , 3.1.2.1 Carácter de escape
- 1 2 "3.6.4 Documentación" . docs.python.org .
- ↑ Go efectivo , " Punto y coma "
- ↑ " Punto y coma en Go ", golang-nuts, Rob 'Commander' Pike, 12/10/09
- ↑ "Análisis léxico > Sangría" . The Python Language Reference . Consultado el 21 de junio de 2023 .
Fuentes
- Compilación con C# y Java , Pat Terry, 2005, ISBN 032126360X
- Algoritmos + Estructuras de datos = Programas , Niklaus Wirth, 1975, ISBN 0-13-022418-9
- Construcción del compilador , Niklaus Wirth, 1996, ISBN 0-201-40353-6
- Sebesta, RW (2006). Conceptos de lenguajes de programación (Séptima edición) pp. 177. Boston: Pearson/Addison-Wesley.
Enlaces externos
- Yang, W.; Tsay, Chey-Woei; Chan, Jien-Tsai (2002). "Sobre la aplicabilidad de la regla de coincidencia más larga en el análisis léxico" . Computer Languages, Systems & Structures . 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. Archivado del original el 17 de abril de 2022. Recuperado el 4 de septiembre de 2015 .
- Trim, Craig (23 de enero de 2013). "El arte de la tokenización" . Developer Works . IBM. Archivado del original el 30 de mayo de 2019.
- Tarea de segmentación de menciones de palabras , un análisis
- Análisis léxico
- Construcción de compiladores
- Implementación del lenguaje de programación
- Análisis sintáctico
