Análisis léxico

En informática, análisis léxico, lexing o tokenización es el proceso de convertir una secuencia de caracteres (como en un programa de computadora o página web) en una secuencia de tokens léxicos (cadenas con un significado asignado y por lo tanto identificado). Un programa que realiza análisis léxico puede denominarse lexer, tokenizer o scanner, aunque scanner también es un término para la primera etapa de un lexer. Un lexer generalmente se combina con un analizador, que juntos analizan la sintaxis de los lenguajes de programación, las páginas web, etc.

Aplicaciones

Un lexer forma la primera fase de una interfaz de compilación en el procesamiento. El análisis generalmente ocurre en un solo paso.

En lenguajes más antiguos como ALGOL, la etapa inicial era, en cambio, la reconstrucción de líneas, que realizaba la eliminación de líneas y eliminaba los espacios en blanco y los comentarios (y tenía analizadores sin escáner, sin lexer separado). Estos pasos ahora se realizan como parte del lexer.

Lexers y parsers se usan con mayor frecuencia para compiladores, pero se pueden usar para otras herramientas de lenguaje informático, como prettyprinters o linters. Lexing se puede dividir en dos etapas: el escaneado, que segmenta la cadena de entrada en unidades sintácticas denominadas lexemas y las clasifica en clases de token; y el evaluador, que convierte los lexemas en valores procesados.

Los lexers son generalmente bastante simples, con la mayor parte de la complejidad aplazada al analizador sintáctico o las fases de análisis semántico, y a menudo pueden ser generados por un generador lexer, especialmente lex o derivados. Sin embargo, los lexers a veces pueden incluir cierta complejidad, como el procesamiento de la estructura de la frase 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 el rendimiento.

El análisis léxico también es una etapa temprana importante en el procesamiento del lenguaje natural, donde el texto o las ondas de sonido se segmentan en palabras y otras unidades. Esto requiere una variedad de decisiones que no están completamente estandarizadas, y la cantidad de tokens que producen los sistemas varía para cadenas como "1/2", "chair's", "can't", "y/o", "1/1/2010", "2x4", "...,", y muchos otros. Esto contrasta con el análisis léxico para programación y lenguajes similares donde las reglas exactas se definen y conocen comúnmente.

Lexema

Un lexema es una secuencia de caracteres en el programa fuente que coincide con el patrón de un token y que el analizador léxico identifica como una instancia de ese token.

Algunos autores llaman a esto un "token", usando "token" indistintamente para representar la cadena que se tokeniza y la estructura de datos del token que resulta de poner esta cadena a través del proceso de tokenización.

La palabra lexema en informática se define de manera diferente a lexema en lingüística. Un lexema en informática corresponde aproximadamente a una palabra en lingüística (que no debe confundirse con una palabra en arquitectura informática), aunque en algunos casos puede ser más similar a un morfema. En algunos lenguajes naturales (por ejemplo, en inglés), el lexema lingüístico es similar al lexema en informática, pero esto generalmente no es cierto (por ejemplo, en chino, no es nada trivial encontrar límites de palabras debido a la falta de separadores de palabras).

Ficha

Un token léxico o simplemente token es una cadena con un significado asignado y por lo tanto identificado. Está estructurado como un par que consta de un nombre de token y un valor de token opcional. El nombre del token es una categoría de unidad léxica. Los nombres de token comunes son

• identificador: nombre que el programador elige;
• palabra clave: nombres ya en el lenguaje de programación;
• separador (también conocido como punctuadores): caracteres de punción y delimitadores emparejados;
• operador: símbolos que operan en argumentos y producen resultados;
• literal: numérico, lógico, textual, literal de referencia;
• comentario: línea, bloque (Depende del compilador si el compilador implementa comentarios como fichas de lo contrario será despojado).

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.

Gramática léxica

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 un lenguaje regular, con las reglas gramaticales que 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 que encuentra, el programa léxico realiza una acción, la mayoría simplemente produce un token.

Dos categorías léxicas comunes importantes son los espacios en blanco y los comentarios. Estos también están definidos en la gramática y 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 x en lugar 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 significativo, ya que determina la estructura del bloque y generalmente se maneja a nivel de lexer; ver la estructura de la frase, a continuación. En segundo lugar, en algunos usos de lexers, los comentarios y los espacios en blanco deben conservarse; 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 los maneja el lexer.

Tokenización

Tokenización es el proceso de delimitar y posiblemente clasificar secciones de una cadena de caracteres de entrada. Los tokens resultantes luego se pasan a alguna otra forma de procesamiento. El proceso puede considerarse una subtarea del análisis de entrada.

Por ejemplo, en la cadena de texto:

The quick brown fox jumps over the lazy dog

la 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 dado (es decir, haciendo coincidir la cadena " " o la 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 denominados delimitadores y definición explícita mediante un diccionario. Los lexers 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.

Los tokens a menudo se clasifican por contenido de caracteres o por contexto dentro del flujo de datos. Las categorías están definidas por las reglas del lexer. Las categorías a menudo involucran elementos gramaticales del lenguaje utilizado en el flujo de datos. Los lenguajes de programación a menudo clasifican los tokens como identificadores, operadores, símbolos de agrupación o por tipo de datos. Los lenguajes escritos comúnmente clasifican las fichas como sustantivos, verbos, adjetivos o puntuación. Las categorías se utilizan para el procesamiento posterior de los tokens, ya sea por el analizador o por otras funciones del programa.

Un analizador léxico generalmente no hace nada con combinaciones de tokens, una tarea que se deja 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 ")".

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 son comprendidas por un generador de analizador léxico como lex. 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.

Seguir tokenizando es analizar. A partir de ahí, los datos interpretados pueden cargarse en estructuras de datos para uso general, interpretación o compilación.

Escáner

La primera etapa, el escáner, generalmente se basa en una máquina de estados finitos (FSM). Ha codificado 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 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 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 (este se denomina regla de comida 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, una 'L' carácter no es suficiente para distinguir entre un identificador que comienza con 'L' y un literal de cadena de caracteres anchos.

Evaluadora

Un lexema, sin embargo, es solo 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 revisa 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 dar a un analizador. Algunos tokens, como los paréntesis, en realidad no tienen valores, por lo que la función de evaluación 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 los espacios en blanco y los comentarios. Los evaluadores de identificadores suelen ser sencillos (representan literalmente el identificador), pero pueden incluir algunos desarmados. Los evaluadores de 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 debe eliminar solo las comillas, pero el evaluador de un literal de cadena con escape incorpora un lexer, que elimina las secuencias de escape.

Por ejemplo, en el código fuente de un programa informático, la cadena

net_worth_future = (assets – liabilities);

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

IDENTIFIER net_worth_future
EQUALS
OPEN_PARENTHESIS
Activos IDENTIFIER
MINUS
Pasivo IDENTIFIER
CLOSE_PARENTHESIS
SEMICOLON

Debido a las restricciones de licencia de los analizadores existentes, puede ser necesario escribir un lexer a mano. Esto es práctico si la lista de tokens es pequeña, pero en general, los lexers son generados por herramientas automatizadas. 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 estado para una máquina de estado finito (que se conecta al código de plantilla para compilar y ejecutar).

Las expresiones regulares representan de forma compacta patrones que pueden seguir los caracteres de los lexemas. Por ejemplo, para un idioma basado en inglés, un token IDENTIFICADOR 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 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 a-z, A-Z o _, seguido de 0 o más de a-z, A-Z, _ o 0-9".

Las expresiones regulares y las máquinas de estado finito que generan no son lo suficientemente poderosas 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 sea igual en ambos lados, a menos que exista un conjunto finito de valores permitidos 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 tratar de sacarlos y ver si la pila está vacía al final (vea el ejemplo en el libro Estructura e interpretación de programas de computadora).

Obstáculos

Normalmente, la tokenización ocurre 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 puntuación y el espacio blanco pueden o no incluirse en la lista resultante de fichas.
• Todas las cuerdas contiguas de caracteres alfabéticos forman parte de una ficha; igualmente con números.
• Las fichas están separadas por caracteres blancos, como un espacio o una ruptura de línea, o por caracteres de puntuación.

En los idiomas que usan 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í hay muchos casos extremos, como contracciones, palabras con guión, 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", que un tokenizador ingenuo puede romper en el espacio aunque la mejor ruptura sea (posiblemente) en el guión.

La tokenización es particularmente difícil para los idiomas escritos en scriptio continuo que no muestran límites entre palabras, como el griego antiguo, el chino 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 desarrollar heurísticas más complejas, consultar una tabla de casos especiales comunes o adaptar los tokens a un modelo de lenguaje que identifique colocaciones en un paso de procesamiento posterior.

Generador Lexer

Los lexers a menudo son generados por un generador de lexer, de forma análoga a los generadores de analizadores, y estas herramientas a menudo se combinan. El más establecido es lex, emparejado con el generador de parser 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 toma una especificación léxica, generalmente expresiones regulares con algunas marcas, 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 léxico funcional como porque la especificación del lenguaje puede cambiar con frecuencia. Además, a menudo ofrecen funciones avanzadas, como condiciones previas y posteriores, que son difíciles de programar a mano. 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 completamente manualmente.

El rendimiento de Lexer es una preocupación, y vale la pena optimizarlo, más aún en lenguajes estables donde el lexer se ejecuta con mucha frecuencia (como C o HTML). Los lexers generados por lex/flex son razonablemente rápidos, pero son posibles mejoras de dos a tres veces usando generadores más sintonizados. A veces se utilizan lexers escritos a mano, pero los generadores de lexer 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 de codificación directa. Con el último enfoque, el generador produce un motor que salta directamente a los estados de seguimiento a través de sentencias goto. Se ha demostrado que herramientas como re2c producen motores que son entre dos y tres veces más rápidos que los motores producidos por flex. En general, es difícil escribir a mano analizadores que funcionen mejor que los motores generados por estas últimas herramientas.

Estructura de frase

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; más simplemente, los lexers pueden omitir tokens o insertar tokens agregados. 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 agregados. Esto se hace principalmente para agrupar tokens en declaraciones, o declaraciones en bloques, para simplificar el analizador.

Continuación de línea

La continuación de línea es una característica de algunos idiomas 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 de una nueva línea) hace que la línea continúe: la línea siguiente se unirá 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, otros scripts de shell y Python.

Inserción de punto y coma

Muchos idiomas usan el punto y coma como terminador de declaraciones. La mayoría de las veces esto es obligatorio, pero en algunos idiomas el punto y coma es opcional en muchos contextos. Esto se hace principalmente en el nivel de lexer, donde el lexer 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 comas 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 pueden ser insertados por el lexer. Los puntos y comas opcionales u otros terminadores o separadores también se manejan a veces en el nivel del analizador, especialmente en el caso de las comas finales o los puntos y comas.

La inserción de punto y coma es una característica de BCPL y su descendiente lejano Go, aunque está ausente en B o C. 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 puntos y comas, mientras que otros usan puntos y comas iniciales, denominados puntos y comas 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) se pueden considerar complementarias: la inserción de punto y coma agrega un token, aunque las nuevas líneas generalmente no generar tokens, mientras que la continuación de línea evita que se genere un token, aunque las nuevas líneas generalmente sí generan tokens.

Regla del fuera de juego

La regla de fuera de juego (bloqueos determinados por sangría) se puede implementar en el lexer, como en Python, donde al aumentar la sangría, el lexer emite un token INDENT y al disminuir la sangría, el lexer emite un token DEDENT.. Estos tokens corresponden a la llave de apertura { y la llave de cierre } en idiomas que usan llaves para 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, el nivel de sangría actual, y por lo tanto puede detectar cambios en la sangría cuando esto cambia y, por lo tanto, la gramática léxica no está libre de contexto: INGENT-DEDENT depende de la información contextual del nivel de sangría anterior.

Lexing sensible al contexto

Por lo general, 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 simple de lexer a parser, sin necesidad de que la información fluya de regreso al lexer.

Hay excepciones, sin embargo. Los 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, 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 de 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 aunque complican un poco a un lexer, son invisibles para el analizador y las fases posteriores.

Un ejemplo más complejo es el lexer hack 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 typedef y variables son léxicamente idénticos pero constituyen diferentes clases de token. Así, en el truco, el lexer llama al analizador semántico (por ejemplo, la tabla de símbolos) y comprueba si la secuencia requiere un nombre typedef. En este caso, la información debe fluir de regreso no solo desde el analizador, sino desde el analizador semántico de vuelta al lexer, lo que complica el diseño.