Analyse lexicale et Java: partie 1

Analyse lexicale et analyse

Lors de l'écriture d'applications Java, l'un des éléments les plus courants que vous devrez produire est un analyseur. Les analyseurs vont du simple au complexe et sont utilisés pour tout, de l'examen des options de ligne de commande à l'interprétation du code source Java. Dans le numéro de décembre de JavaWorld , je vous ai montré Jack, un générateur d'analyseur automatique qui convertit les spécifications de grammaire de haut niveau en classes Java qui implémentent l'analyseur décrit par ces spécifications. Ce mois-ci, je vais vous montrer les ressources fournies par Java pour écrire des analyseurs et analyseurs lexicaux ciblés. Ces analyseurs un peu plus simples comblent le vide entre la simple comparaison de chaînes et les grammaires complexes que Jack compile.

Le but des analyseurs lexicaux est de prendre un flux de caractères d'entrée et de les décoder en jetons de niveau supérieur qu'un analyseur peut comprendre. Les analyseurs utilisent la sortie de l'analyseur lexical et fonctionnent en analysant la séquence de jetons renvoyés. L'analyseur fait correspondre ces séquences à un état final, qui peut être l'un des nombreux états finaux. Les états finaux définissent les objectifsde l'analyseur. Lorsqu'un état final est atteint, le programme utilisant l'analyseur effectue une action - soit en configurant des structures de données, soit en exécutant du code spécifique à une action. De plus, les analyseurs peuvent détecter - à partir de la séquence de jetons qui ont été traités - quand aucun état final légal ne peut être atteint; à ce stade, l'analyseur identifie l'état actuel comme un état d'erreur. Il appartient à l'application de décider de l'action à entreprendre lorsque l'analyseur identifie un état final ou un état d'erreur.

La base de classes Java standard comprend quelques classes d'analyseur lexical, mais elle ne définit aucune classe d'analyseur à usage général. Dans cette colonne, je vais examiner en profondeur les analyseurs lexicaux fournis avec Java.

Analyseurs lexicaux de Java

La spécification du langage Java, version 1.0.2, définit deux classes d'analyseur lexical, StringTokenizeret StreamTokenizer. À partir de leurs noms, vous pouvez déduire qui StringTokenizerutilise des Stringobjets comme entrée et StreamTokenizerutilise des InputStreamobjets.

La classe StringTokenizer

Parmi les deux classes d'analyseurs lexicales disponibles, la plus simple à comprendre est StringTokenizer. Lorsque vous construisez un nouvel StringTokenizerobjet, la méthode constructeur prend nominalement deux valeurs: une chaîne d'entrée et une chaîne de délimitation. La classe construit ensuite une séquence de jetons qui représente les caractères entre les caractères de délimitation.

En tant qu'analyseur lexical, StringTokenizerpourrait être formellement défini comme indiqué ci-dessous.

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

Cette définition consiste en une expression régulière qui correspond à tous les caractères à l' exception des caractères de délimitation. Tous les caractères correspondants adjacents sont rassemblés en un seul jeton et renvoyés sous forme de jeton.

L'utilisation la plus courante de la StringTokenizerclasse est pour séparer un ensemble de paramètres - comme une liste de nombres séparés par des virgules. StringTokenizerest idéal dans ce rôle car il supprime les séparateurs et renvoie les données. La StringTokenizerclasse fournit également un mécanisme pour identifier les listes dans lesquelles il y a des jetons «nuls». Vous utiliseriez des jetons nuls dans les applications dans lesquelles certains paramètres ont des valeurs par défaut ou ne sont pas tenus d'être présents dans tous les cas.

L'applet ci-dessous est un simple StringTokenizerexerciseur. La source de l'applet StringTokenizer est ici. Pour utiliser l'applet, tapez du texte à analyser dans la zone de chaîne d'entrée, puis saisissez une chaîne composée de caractères de séparation dans la zone de chaîne de séparation. Enfin, cliquez sur Tokenize! bouton. Le résultat apparaîtra dans la liste des jetons sous la chaîne d'entrée et sera organisé comme un jeton par ligne.

Vous avez besoin d'un navigateur compatible Java pour voir cette applet.

Prenons comme exemple une chaîne, "a, b, d", passée à un StringTokenizerobjet qui a été construit avec une virgule (,) comme caractère de séparation. Si vous mettez ces valeurs dans l'applet de l'exerciseur ci-dessus, vous verrez que l' Tokenizerobjet renvoie les chaînes «a», «b» et «d». Si votre intention était de noter qu'un paramètre était manquant, vous avez peut-être été surpris de ne voir aucune indication à ce sujet dans la séquence de jetons. La capacité de détecter les jetons manquants est activée par la valeur booléenne du séparateur de retour qui peut être définie lorsque vous créez un Tokenizerobjet. Avec ce paramètre défini lors de la Tokenizerconstruction de, chaque séparateur est également renvoyé. Cochez la case Return Separator dans l'applet ci-dessus et laissez la chaîne et le séparateur seuls. Maintenant leTokenizerrenvoie "a, virgule, b, virgule, virgule et d." En notant que vous obtenez deux caractères de séparation dans l'ordre, vous pouvez déterminer qu'un jeton «nul» a été inclus dans la chaîne d'entrée.

L'astuce pour une utilisation réussie StringTokenizerdans un analyseur syntaxique consiste à définir l'entrée de telle sorte que le caractère délimiteur n'apparaisse pas dans les données. Il est clair que vous pouvez éviter cette restriction en concevant pour elle dans votre application. La définition de méthode ci-dessous peut être utilisée dans le cadre d'une applet qui accepte une couleur sous la forme de valeurs rouge, verte et bleue dans son flux de paramètres.

/ ** * Analyse un paramètre de la forme «10,20,30» comme un tuple * RVB pour une valeur de couleur. * / 1 Color getColor (String name) {2 String data; 3 StringTokenizer st; 4 int rouge, vert, bleu; 5 6 données = getParameter (nom); 7 if (data == null) 8 renvoie nul; 9 10 st = nouveau StringTokenizer (données, ","); 11 try {12 red = Integer.parseInt (st.nextToken ()); 13 vert = Integer.parseInt (st.nextToken ()); 14 bleu = Integer.parseInt (st.nextToken ()); 15} catch (Exception e) {16 return null; // (ERROR STATE) n'a pas pu l'analyser 17} 18 return new Color (rouge, vert, bleu); // (END STATE) terminé. 19}

Le code ci-dessus implémente un analyseur très simple qui lit la chaîne "nombre, nombre, nombre" et renvoie un nouvel Colorobjet. À la ligne 10, le code crée un nouvel StringTokenizerobjet contenant les données de paramètre (supposons que cette méthode fait partie d'une applet) et une liste de caractères de séparation composée de virgules. Ensuite, aux lignes 12, 13 et 14, chaque jeton est extrait de la chaîne et converti en un nombre à l'aide de la parseIntméthode Integer . Ces conversions sont entourées d'un try/catchbloc au cas où les chaînes de nombres ne seraient pas des nombres valides ou si Tokenizerelles lancent une exception car il n'y a plus de jetons. Si tous les nombres sont convertis, l'état final est atteint et un Colorobjet est renvoyé; sinon, l'état d'erreur est atteint et null est renvoyé.

Une caractéristique de la StringTokenizerclasse est qu'elle est facilement empilable. Regardez la méthode nommée getColorci-dessous, qui correspond aux lignes 10 à 18 de la méthode ci-dessus.

/ ** * Analyse un tuple de couleur "r, g, b" en un Colorobjet AWT . * / 1 Color getColor (String data) {2 int rouge, vert, bleu; 3 StringTokenizer st = nouveau StringTokenizer (données, ","); 4 essayez {5 red = Integer.parseInt (st.nextToken ()); 6 vert = Integer.parseInt (st.nextToken ()); 7 bleu = Integer.parseInt (st.nextToken ()); 8} catch (Exception e) {9 return null; // (ERROR STATE) n'a pas pu l'analyser 10} 11 return new Color (rouge, vert, bleu); // (END STATE) terminé. 12}

Un analyseur légèrement plus complexe est illustré dans le code ci-dessous. Cet analyseur est implémenté dans la méthode getColors, qui est définie pour renvoyer un tableau d' Colorobjets.

/ ** * Analyse un ensemble de couleurs "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" en * un tableau d'objets AWT Color. * / 1 Color [] getColors (String data) {2 Vector accum = new Vector (); 3 Couleur cl, résultat []; 4 StringTokenizer st = new StringTokenizer (données, ":"); 5 while (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 if (cl! = Null) {8 accum.addElement (cl); 9} else {10 System.out.println ("Erreur - mauvaise couleur."); 11} 12} 13 if (accum.size () == 0) 14 return null; 15 résultat = nouvelle couleur [accum.size ()]; 16 for (int i = 0; i <accum.size (); i ++) {17 result [i] = (Color) accum.elementAt (i); 18} 19 renvoie le résultat; 20}

Dans la méthode ci-dessus, qui n'est que légèrement différente de la getColorméthode, le code des lignes 4 à 12 crée un nouveau Tokenizerpour extraire les jetons entouré du caractère deux-points (:). Comme vous pouvez le lire dans le commentaire de la documentation de la méthode, cette méthode s'attend à ce que les tuples de couleur soient séparés par des deux-points. Chaque appel à nextTokendans la StringTokenizerclasse renverra un nouveau jeton jusqu'à ce que la chaîne soit épuisée. Les jetons retournés seront les chaînes de nombres séparés par des virgules; ces chaînes de jetons sont transmises à getColor, qui extrait ensuite une couleur des trois nombres. La création d'un nouvel StringTokenizerobjet à l'aide d'un jeton retourné par un autre StringTokenizerobjet permet au code de l'analyseur que nous avons écrit d'être un peu plus sophistiqué sur la façon dont il interprète l'entrée de chaîne.

Aussi utile soit-il, vous finirez par épuiser les capacités de la StringTokenizerclasse et devrez passer à son grand frère StreamTokenizer.

La classe StreamTokenizer

Comme le nom de la classe l'indique, un StreamTokenizerobjet s'attend à ce que son entrée provienne d'une InputStreamclasse. Comme StringTokenizerci - dessus, cette classe convertit le flux d'entrée en morceaux que votre code d'analyse peut interpréter, mais c'est là que la similitude s'arrête.

StreamTokenizerest un analyseur lexical basé sur des tables . Cela signifie que chaque caractère d'entrée possible se voit attribuer une signification, et le scanner utilise la signification du caractère actuel pour décider quoi faire. Dans l'implémentation de cette classe, les personnages se voient attribuer l'une des trois catégories. Ceux-ci sont:

  • Caractères d' espaces - leur signification lexicale est limitée à la séparation des mots

  • Caractères de mot - ils doivent être agrégés lorsqu'ils sont adjacents à un autre caractère de mot

  • Caractères ordinaires - ils doivent être renvoyés immédiatement à l'analyseur

Imaginez l'implémentation de cette classe comme une simple machine à états qui a deux états - inactif et accumulé . Dans chaque état, l'entrée est un caractère de l'une des catégories ci-dessus. La classe lit le personnage, vérifie sa catégorie et effectue une action, puis passe à l'état suivant. Le tableau suivant montre cette machine à états.

Etat Contribution action Nouvel état
tourner au ralenti caractère de mot repousser le personnage accumuler
caractère ordinaire caractère de retour tourner au ralenti
caractère d' espacement consommer du caractère tourner au ralenti
accumuler caractère de mot ajouter au mot courant accumuler
caractère ordinaire

retourner le mot courant

repousser le personnage

tourner au ralenti
caractère d' espacement

retourner le mot courant

consommer du caractère

tourner au ralenti

En plus de ce mécanisme simple, la StreamTokenizerclasse ajoute plusieurs heuristiques. Il s'agit notamment du traitement des nombres, du traitement des chaînes entre guillemets, du traitement des commentaires et du traitement de fin de ligne.

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.

L'exemple suivant est le traitement des chaînes entre guillemets. Il est souvent souhaitable de transmettre une chaîne entourée d'un guillemet (généralement un guillemet double (") ou simple (')) en tant que jeton unique. La StreamTokenizerclasse vous permet de spécifier n'importe quel caractère comme guillemet. Par défaut, ils sont les guillemets simples (') et doubles ("). La machine à états est modifiée pour consommer des caractères dans l'état d'accumulation jusqu'à ce qu'un autre caractère guillemet ou un caractère de fin de ligne soit traité. Pour vous permettre de citer le caractère guillemet, l'analyseur traite le caractère guillemet précédé d'une barre oblique inverse (\) dans le flux d'entrée et à l'intérieur d'une citation comme un caractère de mot.