Analyse lexicale, partie 2: Créer une application

Le mois dernier, j'ai examiné les classes fournies par Java pour effectuer une analyse lexicale de base. Ce mois-ci, je vais parcourir une application simple qui utilise StreamTokenizerpour implémenter une calculatrice interactive.

Pour passer brièvement en revue l'article du mois dernier, deux classes d'analyseurs lexicaux sont incluses dans la distribution Java standard: StringTokenizeret StreamTokenizer. Ces analyseurs convertissent leur entrée en jetons discrets qu'un analyseur peut utiliser pour comprendre une entrée donnée. L'analyseur implémente une grammaire, qui est définie comme un ou plusieurs états d'objectif atteints en voyant diverses séquences de jetons. Lorsque l'état de l'objectif d'un analyseur est atteint, il exécute une action. Lorsque l'analyseur détecte qu'il n'y a aucun état d'objectif possible étant donné la séquence actuelle de jetons, il le définit comme un état d'erreur. Lorsqu'un analyseur atteint un état d'erreur, il exécute une action de récupération, qui ramène l'analyseur à un point auquel il peut recommencer l'analyse. En règle générale, cela est implémenté en consommant des jetons jusqu'à ce que l'analyseur revienne à un point de départ valide.

Le mois dernier, je vous ai montré quelques méthodes qui utilisaient un StringTokenizerpour analyser certains paramètres d'entrée. Ce mois-ci, je vais vous montrer une application qui utilise un StreamTokenizerobjet pour analyser un flux d'entrée et implémenter une calculatrice interactive.

Construire une application

Notre exemple est une calculatrice interactive similaire à la commande Unix bc (1). Comme vous le verrez, il pousse la StreamTokenizerclasse jusqu'au bord de son utilité en tant qu'analyseur lexical. Ainsi, il sert de bonne démonstration de l'endroit où la ligne entre les analyseurs "simples" et "complexes" peut être tracée. Cet exemple est une application Java et s'exécute donc mieux à partir de la ligne de commande.

Pour résumer rapidement ses capacités, la calculatrice accepte les expressions sous la forme

[nom de la variable] "=" expression 

Le nom de variable est facultatif et peut être n'importe quelle chaîne de caractères dans la plage de mots par défaut. (Vous pouvez utiliser l'applet d'exercice de l'article du mois dernier pour rafraîchir votre mémoire sur ces caractères.) Si le nom de la variable est omis, la valeur de l'expression est simplement imprimée. Si le nom de la variable est présent, la valeur de l'expression est affectée à la variable. Une fois les variables affectées, elles peuvent être utilisées dans des expressions ultérieures. Ainsi, ils remplissent le rôle de «souvenirs» sur une calculatrice portable moderne.

L'expression est composée d'opérandes sous la forme de constantes numériques (constantes à virgule flottante double précision) ou de noms de variables, d'opérateurs et de parenthèses pour regrouper des calculs particuliers. Les opérateurs légaux sont addition (+), soustraction (-), multiplication (*), division (/), ET bit à bit (&), OU bit à bit (|), XOR bit à bit (#), exponentiation (^) et négation unaire avec moins (-) pour le résultat du complément à deux ou bang (!) pour le résultat du complément à ceux.

En plus de ces instructions, notre application de calculatrice peut également prendre l'une des quatre commandes suivantes: «dump», «clear», «help» et «quit». La dumpcommande imprime toutes les variables actuellement définies ainsi que leurs valeurs. La clearcommande efface toutes les variables actuellement définies. La helpcommande imprime quelques lignes de texte d'aide pour démarrer l'utilisateur. La quitcommande entraîne la fermeture de l'application.

L'exemple d'application entier se compose de deux analyseurs: un pour les commandes et les instructions et un pour les expressions.

Construire un analyseur de commandes

L'analyseur de commandes est implémenté dans la classe d'application pour l'exemple STExample.java. (Voir la section Ressources pour un pointeur vers le code.) La mainméthode de cette classe est définie ci-dessous. Je vais parcourir les pièces pour vous.

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

Dans le code ci-dessus, la première chose que je fais est d'allouer une java.util.Hashtableclasse pour contenir les variables. Après cela, j'attribue un StreamTokenizeret l'ajuste légèrement par rapport à ses valeurs par défaut. La justification des changements est la suivante:

  • eolIsSignificant est défini sur true afin que le tokenizer renvoie une indication de fin de ligne. J'utilise la fin de la ligne comme point de fin de l'expression.

  • lowerCaseMode est défini sur true afin que les noms de variables soient toujours renvoyés en minuscules. De cette façon, les noms de variables ne sont pas sensibles à la casse.

  • Le caractère barre oblique (/) est défini comme un caractère ordinaire afin qu'il ne soit pas utilisé pour indiquer le début d'un commentaire, et peut être utilisé à la place comme opérateur de division.

  • Le caractère moins (-) est défini comme un caractère ordinaire de sorte que la chaîne "3-3" se segmentera en trois jetons - "3", "-" et "3" - plutôt que simplement "3" et "-3." (N'oubliez pas que l'analyse des nombres est définie sur "on" par défaut.)

Une fois le tokenizer configuré, l'analyseur de commandes s'exécute dans une boucle infinie (jusqu'à ce qu'il reconnaisse la commande "quit" à quel point il se termine). Ceci est illustré ci-dessous.

8 while (vrai) {9 Expression res; 10 int c = StreamTokenizer.TT_EOL; 11 Chaîne varName = null; 12 13 System.out.println ("Entrez une expression ..."); 14 try {15 while (true) {16 c = st.nextToken (); 17 if (c == StreamTokenizer.TT_EOF) {18 System.exit (1); 19} else if (c == StreamTokenizer.TT_EOL) {20 continue; 21} else if (c == StreamTokenizer.TT_WORD) {22 if (st.sval.compareTo ("dump") == 0) {23 dumpVariables (variables); 24 continuer; 25} else if (st.sval.compareTo ("clear") == 0) {26 variables = new Hashtable (); 27 continuer; 28} else if (st.sval.compareTo ("quit") == 0) {29 System.exit (0); 30} else if (st.sval.compareTo ("exit") == 0) {31 System.exit (0); 32} else if (st.sval.compareTo ("help") == 0) {33 help (); 34 continuer; 35} 36 varName = st.sval; 37 c = st.nextToken ();38} 39 pause; 40} 41 if (c! = '=') {42 throw new SyntaxError ("missing initial '=' sign."); 43}

Comme vous pouvez le voir à la ligne 16, le premier jeton est appelé en invoquant nextTokensur l' StreamTokenizerobjet. Cela renvoie une valeur indiquant le type de jeton qui a été analysé. La valeur de retour sera soit l'une des constantes définies dans la StreamTokenizerclasse, soit une valeur de caractère. Les jetons "meta" (ceux qui ne sont pas simplement des valeurs de caractères) sont définis comme suit:

  • TT_EOF- Cela indique que vous êtes à la fin du flux d'entrée. Contrairement à StringTokenizer, il n'y a pas de hasMoreTokensméthode.

  • TT_EOL - Cela vous indique que l'objet vient de passer une séquence de fin de ligne.

  • TT_NUMBER - Ce type de jeton indique à votre code d'analyseur qu'un nombre a été vu sur l'entrée.

  • TT_WORD - Ce type de jeton indique qu'un "mot" entier a été scanné.

Lorsque le résultat n'est pas l'une des constantes ci-dessus, il s'agit soit de la valeur de caractère représentant un caractère de la plage de caractères «ordinaire» qui a été scannée, soit de l'un des caractères de guillemet que vous avez définis. (Dans mon cas, aucun caractère de citation n'est défini.) Lorsque le résultat est l'un de vos caractères de citation, la chaîne entre guillemets peut être trouvée dans la variable d'instance de chaîne svalde l' StreamTokenizerobjet.

Le code des lignes 17 à 20 traite des indications de fin de ligne et de fin de fichier, tandis qu'à la ligne 21, la clause if est prise si un jeton de mot a été renvoyé. Dans cet exemple simple, le mot est soit une commande, soit un nom de variable. Les lignes 22 à 35 traitent des quatre commandes possibles. Si la ligne 36 est atteinte, alors il doit s'agir d'un nom de variable; par conséquent, le programme conserve une copie du nom de la variable et obtient le jeton suivant, qui doit être un signe égal.

Si à la ligne 41 le jeton n'était pas un signe égal, notre analyseur simple détecte un état d'erreur et lève une exception pour le signaler. J'ai créé deux exceptions génériques SyntaxErroret ExecError, pour distinguer les erreurs d'analyse des erreurs d'exécution. La mainméthode continue avec la ligne 44 ci-dessous.

44 res = ParseExpression.expression (st); 45} catch (SyntaxError se) {46 res = null; 47 varName = null; 48 System.out.println ("\ nErreur de syntaxe détectée! -" + se.getMsg ()); 49 while (c! = StreamTokenizer.TT_EOL) 50 c = st.nextToken (); 51 continuer; 52}

À la ligne 44, l'expression à droite du signe égal est analysée avec l'analyseur d'expression défini dans la ParseExpressionclasse. Notez que les lignes 14 à 44 sont enveloppées dans un bloc try / catch qui intercepte les erreurs de syntaxe et les traite. Lorsqu'une erreur est détectée, l'action de récupération de l'analyseur consiste à consommer tous les jetons jusqu'au jeton de fin de ligne suivant, y compris. Ceci est illustré aux lignes 49 et 50 ci-dessus.

À ce stade, si une exception n'a pas été levée, l'application a correctement analysé une instruction. La vérification finale consiste à voir que le jeton suivant est la fin de la ligne. Si ce n'est pas le cas, une erreur n'a pas été détectée. L'erreur la plus courante sera celle des parenthèses incompatibles. Cette vérification est indiquée aux lignes 53 à 60 du code ci-dessous.

53 c = st.nextToken (); 54 if (c! = StreamTokenizer.TT_EOL) {55 if (c == ')') 56 System.out.println ("\ nErreur de syntaxe détectée! - À plusieurs parens de fermeture."); 57 else 58 System.out.println ("\ nBogus token on input -" + 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 expression d'expression statique (StreamTokenizer st) jette SyntaxError {2 Expression result; 3 booléen done = false; 4 5 résultat = somme (st); 6 while (! Done) {7 try {8 switch (st.nextToken ()) 9 case '&': 10 result = new Expression (OP_AND, result, sum (st)); 11 pause; 12 case '23} catch (IOException ioe) {24 throw new SyntaxError ("Got an I / O Exception."); 25} 26} 27 renvoie le résultat; 28}