Análisis léxico, parte 2: crear una aplicación

El mes pasado miré las clases que ofrece Java para hacer análisis léxico básico. Este mes analizaré una aplicación sencilla que se utiliza StreamTokenizerpara implementar una calculadora interactiva.

Para revisar brevemente el artículo del mes pasado, hay dos clases de analizador léxico que se incluyen con la distribución estándar de Java: StringTokenizery StreamTokenizer. Estos analizadores convierten su entrada en tokens discretos que un analizador puede usar para comprender una entrada determinada. El analizador implementa una gramática, que se define como uno o más estados objetivo alcanzados al ver varias secuencias de tokens. Cuando se alcanza el estado objetivo de un analizador, ejecuta alguna acción. Cuando el analizador detecta que no hay estados de objetivo posibles dada la secuencia actual de tokens, lo define como un estado de error. Cuando un analizador alcanza un estado de error, ejecuta una acción de recuperación, que hace que el analizador vuelva a un punto en el que puede comenzar a analizar nuevamente. Normalmente, esto se implementa consumiendo tokens hasta que el analizador vuelve a un punto de inicio válido.

El mes pasado les mostré algunos métodos que usaban StringTokenizerpara analizar algunos parámetros de entrada. Este mes les mostraré una aplicación que usa un StreamTokenizerobjeto para analizar un flujo de entrada e implementar una calculadora interactiva.

Construyendo una aplicación

Nuestro ejemplo es una calculadora interactiva que es similar al comando Unix bc (1). Como verá, lleva a la StreamTokenizerclase al límite de su utilidad como analizador léxico. Por lo tanto, sirve como una buena demostración de dónde se puede trazar la línea divisoria entre analizadores "simples" y "complejos". Este ejemplo es una aplicación Java y, por lo tanto, se ejecuta mejor desde la línea de comandos.

Como resumen rápido de sus capacidades, la calculadora acepta expresiones en la forma

[nombre de variable] "=" expresión 

El nombre de la variable es opcional y puede ser cualquier cadena de caracteres en el rango de palabras predeterminado. (Puede usar el subprograma de ejercicio del artículo del mes pasado para refrescar su memoria sobre estos caracteres). Si se omite el nombre de la variable, simplemente se imprime el valor de la expresión. Si el nombre de la variable está presente, el valor de la expresión se asigna a la variable. Una vez que se han asignado las variables, se pueden usar en expresiones posteriores. Por lo tanto, cumplen el papel de "recuerdos" en una calculadora de mano moderna.

La expresión se compone de operandos en forma de constantes numéricas (constantes de punto flotante de doble precisión) o nombres de variables, operadores y paréntesis para agrupar cálculos particulares. Los operadores legales son suma (+), resta (-), multiplicación (*), división (/), AND bit a bit (&), OR bit a bit (|), XOR bit a bit (#), exponenciación (^) y negación unaria con menos (-) para el resultado del complemento a dos o bang (!) para el resultado del complemento a uno.

Además de estas declaraciones, nuestra aplicación de calculadora también puede aceptar uno de cuatro comandos: "volcar", "borrar", "ayudar" y "salir". El dumpcomando imprime todas las variables que están definidas actualmente, así como sus valores. El clearcomando borra todas las variables definidas actualmente. El helpcomando imprime algunas líneas de texto de ayuda para que el usuario comience. El quitcomando hace que la aplicación se cierre.

La aplicación de ejemplo completa consta de dos analizadores: uno para comandos y declaraciones y otro para expresiones.

Construyendo un analizador de comandos

El analizador de comandos se implementa en la clase de aplicación para el ejemplo STExample.java. (Consulte la sección Recursos para obtener un puntero al código). El mainmétodo para esa clase se define a continuación. Revisaré las piezas por ti.

1 public static void main (String args []) lanza IOException {2 variables Hashtable = new Hashtable (); 3 StreamTokenizer st = nuevo StreamTokenizer (System.in); 4 st.eolIsSignificant (verdadero); 5 st.lowerCaseMode (verdadero); 6 st.ordinaryChar ('/'); 7 st.ordinaryChar ('-');

En el código anterior, lo primero que hago es asignar una java.util.Hashtableclase para contener las variables. Después de eso, asigno un StreamTokenizery lo ajusto ligeramente de sus valores predeterminados. La justificación de los cambios es la siguiente:

  • eolIsSignificant se establece en verdadero para que el tokenizador devuelva una indicación del final de la línea. Utilizo el final de la línea como el punto donde termina la expresión.

  • lowerCaseMode se establece en true para que los nombres de las variables siempre se devuelvan en minúsculas. De esta forma, los nombres de variables no distinguen entre mayúsculas y minúsculas.

  • El carácter de barra inclinada (/) se establece como un carácter ordinario, de modo que no se utilizará para indicar el comienzo de un comentario y se puede utilizar en su lugar como operador de división.

  • El carácter menos (-) está configurado para ser un carácter ordinario, de modo que la cadena "3-3" se segmentará en tres fichas: "3", "-" y "3", en lugar de solo "3" y "-3". (Recuerde, el análisis de números está configurado como "activado" de forma predeterminada).

Una vez que el tokenizador está configurado, el analizador de comandos se ejecuta en un bucle infinito (hasta que reconoce el comando "salir", momento en el que sale). Esto se muestra a continuación.

8 while (verdadero) {9 Expresión res; 10 int c = StreamTokenizer.TT_EOL; 11 String varName = null; 12 13 System.out.println ("Ingrese una expresión ..."); 14 prueba {15 while (verdadero) {16 c = st.nextToken (); 17 if (c == StreamTokenizer.TT_EOF) {18 System.exit (1); 19} else if (c == StreamTokenizer.TT_EOL) {20 continuar; 21} else if (c == StreamTokenizer.TT_WORD) {22 if (st.sval.compareTo ("dump") == 0) {23 dumpVariables (variables); 24 continúan; 25} else if (st.sval.compareTo ("clear") == 0) {26 variables = new Hashtable (); 27 continúan; 28} else if (st.sval.compareTo ("salir") == 0) {29 System.exit (0); 30} else if (st.sval.compareTo ("salir") == 0) {31 System.exit (0); 32} else if (st.sval.compareTo ("ayuda") == 0) {33 ayuda (); 34 continúan; 35} 36 varName = st.sval; 37 c = st.nextToken ();38} 39 descanso; 40} 41 if (c! = '=') {42 throw new SyntaxError ("falta el signo inicial '='"); 43}

Como puede ver en la línea 16, el primer token se llama invocando nextTokenen el StreamTokenizerobjeto. Esto devuelve un valor que indica el tipo de token que se escaneó. El valor de retorno será una de las constantes definidas en la StreamTokenizerclase o será un valor de carácter. Los tokens "meta" (aquellos que no son simplemente valores de caracteres) se definen de la siguiente manera:

  • TT_EOF- Esto indica que está al final del flujo de entrada. A diferencia StringTokenizer, no existe un hasMoreTokensmétodo.

  • TT_EOL - Esto le indica que el objeto acaba de pasar una secuencia de final de línea.

  • TT_NUMBER - Este tipo de token le dice al código del analizador que se ha visto un número en la entrada.

  • TT_WORD - Este tipo de token indica que se escaneó una "palabra" completa.

Cuando el resultado no es una de las constantes anteriores, es el valor de carácter que representa un carácter en el rango de caracteres "ordinarios" que se escaneó o uno de los caracteres de comillas que ha establecido. (En mi caso, no se establece ningún carácter de comillas). Cuando el resultado es uno de sus caracteres de comillas, la cadena entre comillas se puede encontrar en la variable svalde instancia de cadena del StreamTokenizerobjeto.

El código de las líneas 17 a 20 trata de las indicaciones de fin de línea y fin de archivo, mientras que en la línea 21 se toma la cláusula if si se devuelve un token de palabra. En este ejemplo simple, la palabra es un comando o un nombre de variable. Las líneas 22 a 35 tratan de los cuatro comandos posibles. Si se alcanza la línea 36, ​​debe ser un nombre de variable; en consecuencia, el programa guarda una copia del nombre de la variable y obtiene el siguiente token, que debe ser un signo igual.

Si en la línea 41 el token no era un signo igual, nuestro analizador simple detecta un estado de error y lanza una excepción para señalarlo. Creé dos excepciones genéricas SyntaxErrory ExecError, para distinguir los errores en tiempo de análisis de los errores en tiempo de ejecución. El mainmétodo continúa con la línea 44 a continuación.

44 res = ParseExpression.expression (st); 45} catch (SyntaxError se) {46 res = null; 47 varName = null; 48 System.out.println ("\ n¡Error de sintaxis detectado! -" + se.getMsg ()); 49 while (c! = StreamTokenizer.TT_EOL) 50 c = st.nextToken (); 51 continúan; 52}

En la línea 44, la expresión a la derecha del signo igual se analiza con el analizador de expresiones definido en la ParseExpressionclase. Tenga en cuenta que las líneas 14 a 44 están envueltas en un bloque try / catch que atrapa los errores de sintaxis y los trata. Cuando se detecta un error, la acción de recuperación del analizador es consumir todos los tokens hasta el siguiente token de fin de línea inclusive. Esto se muestra en las líneas 49 y 50 anteriores.

En este punto, si no se lanzó una excepción, la aplicación ha analizado correctamente una declaración. La verificación final es ver que el siguiente token es el final de la línea. Si no es así, no se ha detectado un error. El error más común serán los paréntesis que no coincidan. Esta verificación se muestra en las líneas 53 a 60 del siguiente código.

53 c = st.nextToken (); 54 if (c! = StreamTokenizer.TT_EOL) {55 if (c == ')') 56 System.out.println ("\ n¡Error de sintaxis detectado! - Para muchos padres de cierre."); 57 else 58 System.out.println ("\ nBogus token en la entrada -" + c); 59 while (c! = StreamTokenizer.TT_EOL) 60 c = st.nextToken (); 61} else {

When the next token is an end of line, the program executes lines 62 through 69 (shown below). This section of the method evaluates the parsed expression. If the variable name was set in line 36, the result is stored in the symbol table. In either case, if no exception is thrown, the expression and its value are printed to the System.out stream so that you can see what the parser decoded.

62 try { 63 Double z; 64 System.out.println("Parsed expression : "+res.unparse()); 65 z = new Double(res.value(variables)); 66 System.out.println("Value is : "+z); 67 if (varName != null) { 68 variables.put(varName, z); 69 System.out.println("Assigned to : "+varName); 70 } 71 } catch (ExecError ee) { 72 System.out.println("Execution error, "+ee.getMsg()+"!"); 73 } 74 } 75 } 76 } 

In the STExample class, the StreamTokenizer is being used by a command-processor parser. This type of parser commonly would be used in a shell program or in any situation in which the user issues commands interactively. The second parser is encapsulated in the ParseExpression class. (See the Resources section for the complete source.) This class parses the calculator's expressions and is invoked in line 44 above. It is here that StreamTokenizer faces its stiffest challenge.

Building an expression parser

The grammar for the calculator's expressions defines an algebraic syntax of the form "[item] operator [item]." This type of grammar comes up again and again and is called an operator grammar. A convenient notation for an operator grammar is:

id ( "OPERATOR" id )* 

The code above would be read "An ID terminal followed by zero or more occurrences of an operator-id tuple." The StreamTokenizer class would seem pretty ideal for analyzing such streams, because the design naturally breaks the input stream into word, number, and ordinary character tokens. As I'll show you, this is true up to a point.

The ParseExpression class is a straightforward, recursive-descent parser for expressions, right out of an undergraduate compiler-design class. The Expression method in this class is defined as follows:

1 expresión de expresión estática (StreamTokenizer st) arroja SyntaxError {2 resultado de expresión; 3 booleano hecho = falso; 4 5 resultado = suma (st); 6 while (! Done) {7 try {8 switch (st.nextToken ()) 9 case '&': 10 result = new Expression (OP_AND, result, sum (st)); 11 descanso; 12 case '23} catch (IOException ioe) {24 throw new SyntaxError ("Obtuve una excepción de E / S."); 25} 26} 27 devuelve resultado; 28}