Análisis léxico y Java: Parte 1

Análisis y análisis léxico

Al escribir aplicaciones Java, una de las cosas más comunes que se le pedirá que produzca es un analizador. Los analizadores varían de simples a complejos y se utilizan para todo, desde buscar opciones de línea de comandos hasta interpretar el código fuente de Java. En la edición de diciembre de JavaWorld , les mostré Jack, un generador de analizador automático que convierte especificaciones gramaticales de alto nivel en clases de Java que implementan el analizador descrito por esas especificaciones. Este mes le mostraré los recursos que proporciona Java para escribir analizadores y analizadores léxicos específicos. Estos analizadores sintácticos algo más simples llenan el espacio entre la comparación simple de cadenas y las gramáticas complejas que compila Jack.

El propósito de los analizadores léxicos es tomar un flujo de caracteres de entrada y decodificarlos en tokens de nivel superior que un analizador pueda entender. Los analizadores consumen la salida del analizador léxico y operan analizando la secuencia de tokens devueltos. El analizador compara estas secuencias con un estado final, que puede ser uno de los muchos estados finales. Los estados finales definen los objetivosdel analizador. Cuando se alcanza un estado final, el programa que usa el analizador realiza alguna acción, ya sea configurando estructuras de datos o ejecutando algún código específico de acción. Además, los analizadores pueden detectar, a partir de la secuencia de tokens que se han procesado, cuando no se puede alcanzar un estado final legal; en ese punto, el analizador identifica el estado actual como un estado de error. Depende de la aplicación decidir qué acción tomar cuando el analizador identifica un estado final o un estado de error.

La base de clases estándar de Java incluye un par de clases de analizador léxico, sin embargo, no define ninguna clase de analizador de propósito general. En esta columna, echaré un vistazo en profundidad a los analizadores léxicos que vienen con Java.

Analizadores léxicos de Java

La especificación del lenguaje Java, versión 1.0.2, define dos clases de analizador léxico StringTokenizery StreamTokenizer. De sus nombres se puede deducir que StringTokenizerusa Stringobjetos como entrada y StreamTokenizerusa InputStreamobjetos.

La clase StringTokenizer

De las dos clases de analizadores léxicos disponibles, la más fácil de entender es StringTokenizer. Cuando construye un StringTokenizerobjeto nuevo , el método constructor toma nominalmente dos valores: una cadena de entrada y una cadena delimitadora. Luego, la clase construye una secuencia de tokens que representa los caracteres entre los caracteres delimitadores.

Como analizador léxico, StringTokenizerpodría definirse formalmente como se muestra a continuación.

[~ delim1, delim2, ..., delim N ] :: Token

Esta definición consta de una expresión regular que coincide con todos los caracteres excepto los delimitadores. Todos los caracteres coincidentes adyacentes se recopilan en un solo token y se devuelven como token.

El uso más común de la StringTokenizerclase es para separar un conjunto de parámetros, como una lista de números separados por comas. StringTokenizeres ideal en este rol porque elimina los separadores y devuelve los datos. La StringTokenizerclase también proporciona un mecanismo para identificar listas en las que hay tokens "nulos". Usaría tokens nulos en aplicaciones en las que algunos parámetros tienen valores predeterminados o no es necesario que estén presentes en todos los casos.

El siguiente subprograma es un StringTokenizerejercicio sencillo . La fuente del subprograma StringTokenizer está aquí. Para usar el subprograma, escriba un texto que se analizará en el área de la cadena de entrada, luego escriba una cadena que consta de caracteres separadores en el área Cadena de separación. Finalmente, haga clic en Tokenize! botón. El resultado se mostrará en la lista de tokens debajo de la cadena de entrada y se organizará como un token por línea.

Necesita un navegador compatible con Java para ver este subprograma.

Considere como ejemplo una cadena, "a, b, d", pasada a un StringTokenizerobjeto que ha sido construido con una coma (,) como carácter separador. Si coloca estos valores en el subprograma de ejercicio anterior, verá que el Tokenizerobjeto devuelve las cadenas "a", "b" y "d". Si su intención era notar que faltaba un parámetro, es posible que se haya sorprendido al no ver ninguna indicación de esto en la secuencia del token. La capacidad de detectar tokens faltantes está habilitada por el valor booleano del Separador de retorno que se puede establecer cuando crea un Tokenizerobjeto. Con este parámetro establecido cuando Tokenizerse construye, también se devuelve cada separador. Haga clic en la casilla de verificación para el separador de retorno en el subprograma de arriba y deje la cadena y el separador solo. Ahora elTokenizerdevuelve "a, coma, b, coma, coma y d". Al observar que obtiene dos caracteres separadores en secuencia, puede determinar que se incluyó un token "nulo" en la cadena de entrada.

El truco para usar con éxito StringTokenizeren un analizador es definir la entrada de tal manera que el carácter delimitador no aparezca en los datos. Claramente, puede evitar esta restricción diseñando para ella en su aplicación. La siguiente definición del método se puede utilizar como parte de un subprograma que acepta un color en forma de valores rojo, verde y azul en su flujo de parámetros.

/ ** * Analiza un parámetro de la forma "10,20,30" como una * tupla RGB para un valor de color. * / 1 Color getColor (Nombre de cadena) {2 Datos de cadena; 3 StringTokenizer st; 4 int rojo, verde, azul; 5 6 datos = getParameter (nombre); 7 if (data == null) 8 return null; 9 10 st = nuevo StringTokenizer (datos, ","); 11 pruebe {12 rojo = Integer.parseInt (st.nextToken ()); 13 verde = Integer.parseInt (st.nextToken ()); 14 azul = Integer.parseInt (st.nextToken ()); 15} catch (Excepción e) {16 return null; // (ERROR STATE) no pudo analizarlo 17} 18 return new Color (rojo, verde, azul); // (ESTADO FINAL) hecho. 19}

El código anterior implementa un analizador muy simple que lee la cadena "número, número, número" y devuelve un nuevo Colorobjeto. En la línea 10, el código crea un nuevo StringTokenizerobjeto que contiene los datos de los parámetros (suponga que este método es parte de un subprograma) y una lista de caracteres separadores que consta de comas. Luego, en las líneas 12, 13 y 14, cada token se extrae de la cadena y se convierte en un número utilizando el parseIntmétodo Integer . Estas conversiones están rodeadas por un try/catchbloque en caso de que las cadenas de números no sean números válidos o Tokenizerarrojen una excepción porque se han quedado sin tokens. Si todos los números se convierten, se alcanza el estado final y Colorse devuelve un objeto; de lo contrario, se alcanza el estado de error y se devuelve nulo .

Una característica de la StringTokenizerclase es que se apila fácilmente. Observe el método que se menciona a getColorcontinuación, que es de las líneas 10 a 18 del método anterior.

/ ** * Analiza una tupla de color "r, g, b" en un Colorobjeto AWT . * / 1 Color getColor (datos de cadena) {2 int rojo, verde, azul; 3 StringTokenizer st = nuevo StringTokenizer (datos, ","); 4 prueba {5 rojo = Integer.parseInt (st.nextToken ()); 6 verde = Integer.parseInt (st.nextToken ()); 7 azul = Integer.parseInt (st.nextToken ()); 8} catch (Excepción e) {9 return null; // (ERROR STATE) no pudo analizarlo 10} 11 return new Color (rojo, verde, azul); // (ESTADO FINAL) hecho. 12}

En el código siguiente se muestra un analizador un poco más complejo. Este analizador se implementa en el método getColors, que está definido para devolver una matriz de Colorobjetos.

/ ** * Analizar un conjunto de colores "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" en * una matriz de objetos AWT Color. * / 1 Color [] getColors (datos de cadena) {2 Acumulación de vectores = nuevo Vector (); 3 colores cl, resultado []; 4 StringTokenizer st = new StringTokenizer (datos, ":"); 5 while (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 if (cl! = Null) {8 elemento de adición acumulativo (cl); 9} else {10 System.out.println ("Error: mal color"); 11} 12} 13 if (tamaño acumulado () == 0) 14 devuelve nulo; 15 resultado = nuevo Color [tamaño acumulado ()]; 16 para (int i = 0; i <tamaño acumulado (); i ++) {17 resultado [i] = (Color) elemento acumulado en (i); 18} 19 devuelve resultado; 20}

En el método anterior, que es solo ligeramente diferente del getColormétodo, el código en las líneas 4 a 12 crea un nuevo Tokenizertokens para extraer rodeado por el carácter de dos puntos (:). Como puede leer en el comentario de la documentación del método, este método espera que las tuplas de color estén separadas por dos puntos. Cada llamada a nextTokenen la StringTokenizerclase devolverá un nuevo token hasta que la cadena se haya agotado. Los tokens devueltos serán cadenas de números separados por comas; se alimentan estas cadenas de fichas getColor, que luego extraen un color de los tres números. La creación de un nuevo StringTokenizerobjeto utilizando un token devuelto por otro StringTokenizerobjeto permite que el código del analizador que hemos escrito sea un poco más sofisticado sobre cómo interpreta la entrada de la cadena.

Tan útil como es, eventualmente agotarás las habilidades de la StringTokenizerclase y tendrás que pasar a su hermano mayor StreamTokenizer.

La clase StreamTokenizer

Como sugiere el nombre de la clase, un StreamTokenizerobjeto espera que su entrada provenga de una InputStreamclase. Al igual que lo StringTokenizeranterior, esta clase convierte el flujo de entrada en fragmentos que su código de análisis puede interpretar, pero ahí es donde termina la similitud.

StreamTokenizeres un analizador léxico basado en tablas . Esto significa que a cada carácter de entrada posible se le asigna un significado y el escáner usa el significado del carácter actual para decidir qué hacer. En la implementación de esta clase, a los personajes se les asigna una de tres categorías. Estos son:

  • Caracteres de espacio en blanco : su significado léxico se limita a separar palabras

  • Caracteres de palabra : deben agregarse cuando estén adyacentes a otro carácter de palabra.

  • Caracteres ordinarios : deben devolverse inmediatamente al analizador.

Imagine la implementación de esta clase como una máquina de estado simple que tiene dos estados: inactivo y acumulado . En cada estado, la entrada es un personaje de una de las categorías anteriores. La clase lee el personaje, verifica su categoría, realiza alguna acción y pasa al siguiente estado. La siguiente tabla muestra esta máquina de estados.

Estado Entrada Acción Nuevo estado
ocioso carácter de palabra Rechazar personaje acumular
personaje ordinario carácter de retorno ocioso
carácter de espacio en blanco consumir carácter ocioso
acumular carácter de palabra agregar a la palabra actual acumular
personaje ordinario

devolver la palabra actual

Rechazar personaje

ocioso
carácter de espacio en blanco

devolver la palabra actual

consumir carácter

ocioso

Además de este mecanismo simple, la StreamTokenizerclase agrega varias heurísticas. Estos incluyen procesamiento de números, procesamiento de cadenas entre comillas, procesamiento de comentarios y procesamiento de fin de línea.

The first example is number processing. Certain character sequences can be interpreted as representing a numerical value. For example, the sequence of characters 1, 0, 0, ., and 0 adjacent to each other in the input stream represent the numerical value 100.0. When all of the digit characters (0 through 9), the dot character (.), and the minus (-) character are specified as being part of the word set, the StreamTokenizer class can be told to interpret the word it is about to return as a possible number. Setting this mode is achieved by calling the parseNumbers method on the tokenizer object that you instantiated (this is the default). If the analyzer is in the accumulate state, and the next character would not be part of a number, the currently accumulated word is checked to see if it is a valid number. If it is valid, it is returned, and the scanner moves to the next appropriate state.

El siguiente ejemplo es el procesamiento de cadenas entre comillas. A menudo es deseable pasar una cadena rodeada por un carácter de comillas (normalmente comillas dobles (") o simples (')) como un solo token. La StreamTokenizerclase le permite especificar cualquier carácter como un carácter de comillas . De forma predeterminada, son los caracteres de comillas simples (') y comillas dobles ("). La máquina de estado se modifica para consumir caracteres en el estado acumulado hasta que se procesa otro carácter de comillas o un carácter de final de línea. Para permitirle citar el carácter de la cita, el analizador trata el carácter de la cita precedido por una barra diagonal inversa (\) en el flujo de entrada y dentro de una cita como un carácter de palabra.