Análisis léxico - Lexical analysis

En informática , el análisis léxico , lexing o tokenización es el proceso de convertir una secuencia de caracteres (como en un programa informático o página web ) en una secuencia de tokens ( cadenas con un significado asignado y, por lo tanto, identificado). Un programa que realiza análisis léxico puede denominarse lexer , tokenizador o escáner , aunque escáner 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 lenguajes de programación , páginas web , etc.

Aplicaciones

Un lexer forma la primera fase de una interfaz de compilador en el procesamiento moderno. 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 un desmontaje y eliminaba los espacios en blanco y los comentarios (y tenía analizadores sintácticos sin escáner, sin un lexer separado). Estos pasos ahora se realizan como parte del lexer.

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 linters . El lexing 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 el evaluador , que convierte los lexemas en valores procesados.

Los lexers son generalmente bastante simples, con la mayor parte de la complejidad transferida a las fases del analizador sintáctico o del análisis semántico , y a menudo pueden ser generados por un generador de lexers , especialmente lex o derivados. Sin embargo, los lexers 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 parcial o totalmente a mano, ya sea para admitir más funciones o para mejorar 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 sonoras 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", "silla", "no puedo", "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.

Lexeme

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

Algunos autores denominan a esto un "token", usando "token" indistintamente para representar la cadena que se está tokenizando y la estructura de datos del token resultante de poner esta cadena en el proceso de tokenización .

La palabra lexema en informática se define de forma 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 .

Simbólico

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 : nombres que elige el programador;
  • palabra clave : nombres que ya están en el lenguaje de programación;
  • separador (también conocido como puntuadores): caracteres de puntuación y delimitadores emparejados;
  • operador : símbolos que operan sobre argumentos y producen resultados;
  • literal : literales numéricos, lógicos, textuales, de referencia;
  • comentario : línea, bloque (Depende del compilador si el compilador implementa comentarios como tokens, de lo contrario se eliminará).
Ejemplos de valores de token
Nombre del token Valores de token de muestra
identificador x, color,UP
palabra clave if, ,whilereturn
separador }, (,;
operador +, ,<=
literal true, ,6.02e23"music"
comentario /* Retrieves user data */, // must be negative

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 , y las reglas gramaticales consisten en expresiones regulares ; definen el conjunto de posibles secuencias de caracteres (lexemas) de una ficha. Un lexer reconoce cadenas, y para cada tipo de cadena encontrada, 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 , como máximo separando dos tokens (como en en if xlugar de ifx). Hay dos excepciones importantes a esto. Primero, en los lenguajes de reglas 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; consulte la estructura de frases , a continuación. En segundo lugar, en algunos usos de los lexers, los comentarios y los espacios en blanco deben conservarse; por ejemplo, una prettyprinter también necesita generar los comentarios y algunas herramientas de depuración pueden proporcionar mensajes al programador que muestren 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 la línea (la fase inicial de la interfaz del compilador ), pero esta fase separada se eliminó y ahora los maneja el lexer.

Tokenización

La tokenización es el proceso de demarcar y posiblemente clasificar secciones de una cadena de caracteres de entrada. Los tokens resultantes luego se pasan a otra forma de procesamiento. El proceso se puede considerar una subtarea de analizar la entrada.

Por ejemplo, en la cadena de texto :

The quick brown fox jumps over the lazy dog

la cadena no está segmentada implícitamente en espacios, como 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, coincidir con la cadena " "o expresión regular /\s{1}/ ).

Los tokens se pueden representar en XML ,

<sentence>
  <word>The</word>
  <word>quick</word>
  <word>brown</word>
  <word>fox</word>
  <word>jumps</word>
  <word>over</word>
  <word>the</word>
  <word>lazy</word>
  <word>dog</word>
</sentence>

o como una expresión-s ,

(sentence
  (word The)
  (word quick)
  (word brown)
  (word fox)
  (word jumps)
  (word over)
  (word the)
  (word lazy)
  (word dog))

Cuando una clase de token representa más de un lexema posible, el lexer suele guardar suficiente información para reproducir el lexema original, de modo que pueda utilizarse en 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 por 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.

Los tokens a menudo se clasifican por contenido de carácter 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 categorizan tokens como sustantivos, verbos, adjetivos o puntuación. Las categorías se utilizan para el posprocesamiento 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 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 son entendidas 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 un flujo de caracteres, identifica los lexemas en el flujo y los clasifica en tokens. Esto se denomina tokenización . Si el lexer encuentra un token no válido, informará de un error.

La siguiente tokenización 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). Contiene información codificada 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 subsiguientes 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 del munch máximo o del partido más largo ). 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 un literal de cadena de caracteres anchos.

Evaluador

Sin embargo, un lexema 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 repasa los caracteres del lexema para producir un valor . El tipo del lexema combinado con su valor es lo que constituye propiamente un token, que se puede dar a un analizador sintáctico. Algunos tokens, como los paréntesis, realmente no tienen valores, por lo que la función de evaluación para 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 sencillos (que representan literalmente el identificador), pero pueden incluir algunos descuelgues . 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 necesita eliminar solo las comillas, pero el evaluador de un literal de cadena de 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 token léxico; los espacios en blanco están suprimidos y los caracteres especiales no tienen valor:

IDENTIFIER net_worth_future
EQUALS
OPEN_PARENTHESIS
IDENTIFIER assets
MINUS
IDENTIFIER liabilities
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 se generan mediante 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 estados finitos (que se conecta al código de plantilla para compilar y ejecutar).

Las expresiones regulares representan de manera compacta patrones que los caracteres de los lexemas pueden seguir. Por ejemplo, para un idioma basado en inglés , un token IDENTIFICADOR puede ser cualquier carácter alfabético en 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 por 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 poderosas para manejar patrones recursivos, como " n paréntesis de apertura, seguida de una declaración, seguida 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 permitidos para n . Se necesita un analizador completo para reconocer tales patrones en su total generalidad. Un analizador puede insertar paréntesis en una pila y luego intentar 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 se produce 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 los espacios en blanco pueden o no estar incluidos en la lista de tokens resultante.
  • Todas las cadenas contiguas de caracteres alfabéticos forman 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 aquí hay muchos casos extremos, como contracciones , palabras con guiones , emoticonos y construcciones más grandes como URI (que para algunos propósitos pueden contar como tokens individuales). Un ejemplo clásico es "con sede en Nueva York", que un tokenizador ingenuo puede romper en el espacio aunque la mejor ruptura es (posiblemente) en el guión.

La tokenización es particularmente difícil para los idiomas escritos en scriptio continua que no exhiben límites de palabras, como el griego antiguo , el chino 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 identifica colocaciones en un paso de procesamiento posterior.

Generador Lexer

Los lexers a menudo se generan mediante un generador de lexers , análogo a los generadores de analizadores sintácticos , y estas herramientas a menudo se combinan. El más establecido es lex , emparejado con el generador de analizador sintáctico 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 lexer.

Estas herramientas producen un desarrollo muy rápido, lo cual es muy importante en el desarrollo inicial, tanto para obtener un lexer funcional como porque la especificación de un 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 la optimización vale la pena, 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 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. Con el último enfoque, el generador produce un motor que salta directamente a estados de seguimiento a través de declaraciones goto. Herramientas como re2c han demostrado producir motores entre dos y tres veces más rápidos que los motores producidos por flexión. En general, es difícil escribir a mano analizadores que funcionen mejor que los motores generados por estas últimas herramientas.

Estructura de la frase

El análisis léxico segmenta principalmente el flujo de entrada de caracteres en fichas, simplemente agrupando los personajes en partes y categorizándolos. Sin embargo, el lexing puede ser significativamente más complejo; 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 es normalmente 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 ) hace que la línea continúe : la siguiente línea 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 que la nueva línea sea tokenizada. 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 instrucciones. 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 uno 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 la frase formal 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 comas o puntos y comas finales .

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 punto y coma, mientras que otros usan punto y coma 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) pueden verse como complementarias: la inserción de punto y coma agrega un token, aunque las líneas nuevas generalmente no generan tokens, mientras que la continuación de línea evita un token que se genere, a pesar de que los saltos de línea por lo general hacen generar fichas.

Regla de fuera de juego

La regla de fuera de juego (bloques determinados por 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 un token DEDENT. Estos tokens corresponden a la llave de apertura {y de cierre }en los 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 : INDENT-DEDENT dependen de la información contextual del nivel de sangría anterior.

Lexing sensible al contexto

Generalmente, las gramáticas léxicas están libres de contexto, o casi, y por lo tanto no requieren mirar atrás o adelante, ni retroceder, lo que permite una implementación simple, limpia y eficiente. Esto también permite una comunicación unidireccional simple desde el lexer al analizador, sin necesidad de que la información fluya de regreso al lexer.

Sin embargo, existen excepciones. 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 un contexto léxico, y aunque complican un poco un lexer, son invisibles para el analizador y las fases posteriores.

Un ejemplo más complejo es el hack 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 variable son léxicamente idénticos pero constituyen clases de token diferentes. Por lo tanto, en el truco, el lexer llama al analizador semántico (digamos, tabla de símbolos) y verifica 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 regreso al lexer, lo que complica el diseño.

Ver también

Referencias

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) págs. 177. Boston: Pearson / Addison-Wesley.

enlaces externos