Brevet FR2686437A1 — publié le 19930723

La présente invention concerne de façon générale le domaine de la conception de compilateurs et, plus particulièrement, la construction d'analyseurs lexiques qui peuvent accepter efficacement des ensembles de caractères à octets multiples. Les analyseurs lexiques constituent une série de pierres angulaires de la création de compilateurs et sont utilisés pour de multiples applications dans de nombreux domaines de la science des ordinateurs. L'identification de mots et de délimiteurs est une tâche nécessaire dans une tâche quelconque de traitement de langages La tâche principale de l'analyseur lexique est de lire des caractères entrés à partir d'un programme source et de produire comme sortie une séquence de jetons Ce procédé, qui consiste en somme à transformer en une séquence de jetons un programme source, est également appelé en anglais "tokenization" parce que le processus engendre des jetons de mots et de ponctuation. Jusqu'ici, des analyseurs lexiques ont été constitués pour reconnaître seulement des caractères qui sont situés à l'intérieur du domaine des ensembles de caractères à octet unique Des ensembles de caractères à octet unique sont suffisants pour représenter la plupart des langues anglaise et européenne Cependant, des langues provenant des côtes pacifiques, comme l'ensemble de caractères Kanji utilisés au Japon, exigent deux octets pour représenter la multitude de caractères. Constituer un analyseur lexique pour un jeu de caractères exige en général la construction de tables comprenant un nombre d'entrées approximativement égal au nombre de caractères différents qu'il faut reconnaître Dans un ensemble de caractères à octet unique, ceci exige un nombre d'entrées de l'ordre de 256 dans ses tables (c'est- à-dire deux élevé à la puissance huit) En suivant cette logique, un analyseur lexique d'un ensemble de caractères à deux octets exigerait un nombre d'entrées de l'ordre 65 536 dans ses tables (c'est-à-dire deux élevé à la puissance seize) Ceci est une quantité d'espaces d'une importance prohibitive qui serait nécessaire pour constituer et faire fonctionner l'analyseur lexique. Par conséquent, il est immédiatement apparent qu'un système et un procédé plus efficaces sont nécessaires pour reconnaître des ensembles de caractères qui ne peuvent être représentés que par deux octets de données. Compte tenu de ce qui précède, la présente invention fournit un système et un procédé de constitution d'un analyseur lexique qui peut balayer des ensembles de caractères à octets multiples La présente invention met en facteurs des expressions régulières qui contiennent des caractères à octets multiples d'une manière telle qu'il est possible de construire un automate d'état fini à octet unique. De façon plus particulière, selon un premier aspect, la présente invention réalise un système, à base d'ordinateur, de transformation, en une séquence de jetons, d'un programme source écrit dans un langage de programmation qui est représenté tant par des valeurs à octet unique que par des valeurs à octets multiples, caractérisé en ce qu'il comprend: (a) un moyen générateur prévu pour constituer un analyseur lexical ou lexique, ledit moyen générateur étant configuré pour accepter une spécification d'entrée, ladite spécification d'entrée incluant au moins une expression régulière, et (b) un moyen de mise en facteurs prévu pour mettre en facteurs ladite expression régulière si ladite expression régulière contient au moins un caractère à octets multiples. Le système peut comprendre en outre: un moyen compilateur pour compiler ledit analyseur lexique en un automate efficace d'état fini pour ladite expression régulière mise en facteurs. Ledit moyen de mise en facteurs peut être configuré pour mettre en facteurs en (aylbz) une plage de caractères de la forme laybzl, o ay et bz sont des caractères valides à deux octets. Ledit moyen de mise en facteurs peut être configuré de façon à mettre en facteurs en (aly-zl), une plage de caractères de la forme lay- bzl, o ay et bz sont des caractères valides à deux octets, si un premier octet du premier caractère de ladite plage de caractères est égal -à un premier octet du dernier caractère de ladite plage de caractères et si un dernier octet du premier caractère est supérieur au dernier octet du dernier caractère. Ledit moyen de mise en facteurs peut être configuré pour mettre en facteurs en (aly-255 l) (bl 0- zl) une plage de caractères de la forme lay-bzl, o ay et bz sont des caractères valides à deux octets, si un premier octet du premier caractère de ladite plage de caractères n'est pas égal à un premier octet du dernier caractère de ladite plage de caractères et si ledit premier octet du dernier caractère de la dernière plage de caractères est égal audit premier octet du premier caractère de ladite plage de caractères plus un. Ledit moyen de mise en facteurs peut être configuré pour mettre en facteurs en (aly-255 l)1 (l(a+l)-(b-1)ll 0-255 l)I(bl 0-zl) une plage de caractères de la forme lay-bzl, o ay et bz sont des caractères valides à deux octets si un premier octet du premier caractère de ladite plage de caractères n'est pas égal à un premier octet du dernier caractère de ladite plage de caractères et si ledit premier octet du dernier caractère de ladite plage de caractères n'est pas égal audit premier octet du premier caractère de ladite plage de caractères plus un. Ledit moyen de mise en facteurs peut comprendre en outre un moyen de vérification d'erreur pour vérifier ladite expression régulière afin de déterminer si elle contient des caractères valides. Le système peut comprendre en outre un moyen universel de génération d'une classe de caractères universels pour un ensemble de caractères à octets multiples, dans lequel ledit moyen universel comprend un moyen de détermination de la plus petite et de la plus grande valeurs à octets multiples, ladite valeur à octets multiples représentant un caractère valide, et de formation d'une expression régulière de la forme lay-bzl, grâce à quoi ladite expression régulière lay-bzl représente une plage incluant la plus petite et la plus grande valeurs à octets multiples. Selon un deuxième aspect, la présente invention fournit un procédé, à base d'ordinateur, de transformation, en une séquence de jetons, d'un programme source écrit dans un langage de programmation représenté par des caractères à octet unique et/ou à octets multiples, caractérisé en ce qu'il comprend les étapes consistant à: ( 1) recevoir une spécification d'entrée, ladite spécification d'entrée incluant au moins une expression régulière; ( 2) mettre en facteurs en une représentation à octet unique ladite expression régulière au moins unique; et ( 3) constituer un analyseur lexique basé sur ladite représentation à octet unique. Le procédé peut comprendre en outre les étapes consistant à: ( 1) compiler ledit analyseur lexique, ledit analyseur lexique compilé étant un automate efficace d'état fini de ladite expression régulière mise en facteurs; ( 2) entrer dans ledit analyseur lexique compilé une séquence de caractères; et ( 3) analyser ladite séquence de caractères en liaison avec ladite expression régulière mise en facteurs. Ladite étape de mise en facteurs peut comprendre une mise en facteurs en (aylbz) d'une plage de caractères de la forme laybzl, o ay et bz sont des caractères valides à deux octets. Ladite étape de constitution peut comprendre la construction d'une table de transition basée sur ladite représentation à octet unique. Ladite étape d'analyse peut comprendre en outre l'étape consistant à produire à partir de ladite séquence de symboles une chaîne de jetons. Le procédé peut comprendre en outre l'étape d'envoi de ladite chaîne de jetons à un décomposeur. Ladite étape de mise en facteurs peut comprendre une mise en facteurs en (aly-zl) d'une plage de caractères de la forme lay-bzl si un premier octet du premier caractère de ladite plage de caractères est égal à un premier octet du dernier caractère de -ladite de plage de caractères, et si un dernier octet du premier caractère est supérieur au dernier octet du dernier caractère. Ladite étape de mise en facteurs peut comprendre une mise en facteurs en (aly-255 l)|(bl 0-zl) d'une plage de caractères de la forme lay-bzl si un premier octet du premier caractère de ladite plage de caractères n'est pas égal à un premier octet du dernier caractère de ladite plage de caractères et si ledit premier octet du dernier caractère de ladite plage de caractères est égal audit premier octet du premier caractère de ladite plage de caractères plus un. Ladite étape de mise en facteurs peut comprendre une mise en facteurs en (aly-255 l)I(l(a+l)-(b-1)ll 0- 255 l)l(bl 0-zl) d'une plage de caractères de la forme lay-bzl si un premier octet du premier caractère de ladite plage de caractères n'est pas égal à un premier octet du dernier caractère de ladite plage de caractères et ' si ledit premier octet du dernier caractère de ladite plage de caractères n'est pas égal audit premier octet du premier caractère de ladite plage de caractères plus un. Le procédé peut comprendre en outre une étape de génération d'une classe universelle de caractères comprenant les étapes consistant à: (a) déterminer la plus petite et la plus grande valeurs à deux octets, ladite valeur à deux octets représentant un caractère valide, et (b) former une expression régulière de la forme lay-bzl dans laquelle ay est la plus petite valeur à deux octets et bz est la plus grande valeur à deux octets. Ladite étape de mise en facteurs peut comprendre une mise en facteurs en lawbx-cydzl de l'expression régulière (awllbz-cyljdz). Selon un troisième aspect, la présente invention fournit un procédé de mise en facteurs d'une expression régulière à plage de classes de caractères à deux octets en une expression régulière à classe de plage de caractères à octet unique, o la plage de classes de caractères est de la forme lay-bzl, o a, b, y et z sont des valeurs à octet unique, caractérisé en ce qu'il comprend les étapes consistant à: (a) déterminer si ledit premier octet du premier caractère est égal audit premier octet du dernier caractère et produire, si tel est le cas, un signal d'erreur si un dernier octet du dernier caractère est supérieur à un dernier octet du premier caractère ou mettre en facteurs, dans le cas contraire, en (aly-zl) la plage de classes de caractères; et (b) déterminer si ledit premier octet du dernier caractère est égal audit premier octet du premier caractère plus un, et mettre en facteurs, s'ils sont égaux, en (aly- 255 l)I(blO-zl) la plage de classes de caractères, et mettre en facteurs, s'ils ne sont pas égaux, en (aly-225 l)I(l(a+l)-(b-1)ll 0-255 l)I(blO- zl) la plage de classes de caractères. La présente invention constitue alors un programme C d'un analyseur lexique basé sur la représentation à octet unique L'analyseur lexique est compilé en un automate efficace d'état fini de l'expression régulière mise en facteurs. Ultérieurement, une séquence de caractères est entrée dans l'analyseur lexique compilé et les caractères sont vérifiés en liaison avec l'expression régulière mise en facteurs afin de construire un ensemble de jetons et d'exécuter les actions associées. La présente invention permettra de réaliser un analyseur lexique de dimensions sensiblement moindres qui utilise sensiblement moins de mémoire et un analyseur lexique qui reconnait facilement une chaîne d'entrée hétérogène de caractères à octet unique ou à deux octets. Les avantages indiqués ci-dessus de la présente invention, ainsi que d'autres, seront mieux compris en se référant à la description qui suit, prise en liaison avec les dessins annexés dans lesquels: la FIG 1 est un environnement général d'équipement 100 dans lequel peut fonctionner un mode de réalisation préféré de la présente invention; la FIG 2 (a) est une illustration détaillée d'une phase particulière du compilateur 105; la FIG 2 (b) est une illustration détaillée de la manière dont l'analyseur lexique 210 de la présente invention est engendré; la FIG 3 est un automate d'état fini (ou FSA) d'échantillons qui accepte une entrée à laquelle est donnée la définition régulière (aj Bjd); ' la FIG 4 est un exemple d'un automate d'état fini qui applique la procédure de classes de caractère de la présente invention en mettant en facteurs en expressions régulières à caractères à octet unique une expression régulière à caractères à deux octets; la FIG 5 est un schéma logique d'une procédure de plage de classes de caractères 500 selon la présente invention; la FIG 6 est un schéma logique de la procédure composée de classe/plage de caractères 600 de la présente invention; la FIG 7 est un schéma logique d'une procédure universelle 700 de construction de plage de caractères selon la présente invention; la FIG 8 est un exemple d'un automate d'état fini classique qui accepte des caractères qui sont représentés au moyen de deux octets de données; et la FIG 9 est un exemple d'un automate d'état fini qui applique la procédure de plage de classes de caractères 500 de la présente invention en mettant en facteurs en expressions régulières à caractères à octet unique des expressions régulières à caractères à deux octets. On décrira en premier lieu l'environnement de la présente invention. La FIG 1 illustre un environnement général d'équipement dans lequel peut fonctionner un mode de réalisation préféré de la présente invention. L'environnement 100 de la présente invention inclut des programmes d'applications 102 a, 102 b et 102 c Un type spécifique de programme d'application est un compilateur 105 Un compilateur est basé sur une séquence de transformations qui préservent la signification opérationnelle d'un programme mais qui ne préserve pas nécessairement toute l'information qu'il contient, ni même la séquence exacte d'opérations demandée dans le programme source Un compilateur 105 est configuré de manière à transformer un programme source en un code exécutable optimisé ou, de façon plus générale, pour transformer d'un code source à un code objet Un compilateur 105 fonctionne sur une plate- forme d'ordinateur 104. La plate-forme d'ordinateur 104 inclut une unité de matériel 112, qui inclut éventuellement des unités centrales de traitement multiples (UCT) 116, une mémoire vive (REM) 114, et une interface entrée/sortie 118 La plate-forme d'ordinateur 104 inclut un système d'exploitation 108 et peut inclure un code de micro- instructions 110 Divers composants périphériques peuvent être reliés à la plate-forme d'ordinateur 104, par exemple un terminal 126, un dispositif de mémorisation de données 130, et un dispositif d'impression 134. Dans un mode de réalisation préféré de la présente invention, la plateforme d'ordinateur 104 est un ordinateur personnel quelconque, une station de travail ou un ordinateur d'unité principale Le système d'exploitation sensible peut être un système d'exploitation quelconque compatible avec la plate- forme d'ordinateur 104 qui est utilisée. En outre, dans le mode de réalisation préféré de la présente invention, le compilateur 105 utilise les programmes utilitaires LEX et YACC disponibles dans le système d'exploitation UNIX et il contient des sous- programmes écrits dans le langage de programmation C. Le programme utilitaire LEX est modifié pour accepter des caractères qui sont représentés par deux octets de données L'homme de l'art est en position d'apporter directement au programme utilitaire LEX les modifications mineures nécessaires pour incorporer les enseignements de la présente invention On se reportera, pour des informations complémentaires concernant le programme utilitaire LEX à "LEX-A Lexical Analyzer Generator" (ou LEX-un générateur d'analyseur lexique), de LESK et Al, Computer Science Technical Reports, 39, Bell Labs, Murray Hill, N J (Oct 1975). A la FIG 2 (a) est représentée une illustration plus détaillée d'une phase particulière du compilateur La présente invention concerne essentiellement "l'extrémité frontale" du compilateur 105 L'extrémité frontale inclut habituellement, par exemple, des mécanismes prévus pour l'analyse lexique, la décomposition et la génération de code intermédiaire. Typiquement, un programme source 205 est entré dans le système 200 et un code optimisé d'objet 250 est produit. Un analyseur lexical ou lexique 210 est la première phase du compilateur 105 Sa tâche principale est de lire les caractères entrés à partir du programme source 205 et de produire comme sortie une séquence de jetons 215 que il l'analyseur spécifique de décomposition, appelé le décomposeur, 220 utilise pour l'analyse de syntaxe. Cette interaction, résumée à la FIG 2 (a), est mise en oeuvre de façon classique en amenant l'analyseur lexique 210 à être un sous- programme ou un co-programme du décomposeur 220 Lors de la réception d'un ordre "obtenir jeton suivant" du décomposeur, l'analyseur lexique lit des caractères d'entrée jusqu'à ce qu'il puisse identifier le jeton suivant 215 Des analyseurs lexiques sont parfois divisés en une cascade à deux phases, la première appelée "balayage" et la deuxième "analyse lexique" Le dispositif de balayage est responsable de l'exécution de tâches simples, alors que l'analyseur lexique proprement dit effectue les opérations plus complexes. La séquence de jetons 215 émise par l'analyseur lexique 210 est ensuite traitée par le décomposeur, 220 Le décomposeur 220 détermine la structure sous- jacente du programme Jusqu'à ce que le décomposeur 220 ' soit atteint, les jetons 215 ont été collectés sans tenir compte de leur contexte à l'intérieur du programme d'ensemble, ou en tenant peu compte de ce contexte Le décomposeur 220 considère le contexte de chaque jeton 215 et classe des groupes de jetons en grandes entités comme des déclarations, des formulations et des structures de commande Le produit du décomposeur est habituellement un arbre de syntaxe d'abstraction Un arbre est une représentation utile d'un programme ou d'un segment de programme dans la mesure o il facilite plusieurs transformations ultérieures conçues de manière à minimiser le nombre d'instructions de machines nécessaires pour effectuer les opérations demandées. En plus de l'interprétation structurelle, une table de symboles 230 est construite et gérée La table de symboles fournit une association d'identificateurs apparaissant dans le programme source 205 avec divers attributs. L'homme de l'art comprendra immédiatement les équivalents des structures décrites ci-dessus. On va maintenant donner une vue d'ensemble de l'analyseur lexique. Une description plus détaillée de certains des concepts de base décrits dans cette section est trouvée dans plusieurs références, y compris: "Compilers: Principles, Techniques, and Tools" (ou compilateurs: principes techniques et outils), de Aho et al, Addison- Wesley ( 1986) et dans "Compiler Construction, Theory and Practive" (ou Construction de compilateurs, théorie et pratique) de Barret et al, Science Research Associates ( 1986), qui sont incorporés ici dans leur totalité à titre de référence. Les éléments d'un langage de programmation (par exemple C, Fortran, APL) sont son alphabet, sa grammaire et sa sémantique L'alphabet est un ensemble fini de caractères dont sont composées des phrases du langage de programmation La grammaire est un ensemble de règles structurelles définissant les contextes légaux de jetons dans des phrases La sémantique est un ensemble de règles qui définissent l'effet opérationnel d'un programme quelconque écrit dans le langage de programmation lorsqu'il est traduit et exécuté sur une machine. Chaque programme source consiste en une certaine séquence de caractères tirés de l'alphabet du langage source de programmation Typiquement, certaines séquences de caractères faciles à reconnaître sont collectées ensemble pour former des jetons Par exemple, des jetons peuvent correspondre à des mots individuels, des chiffres, des symboles, et/ou des espaces blancs dans un langage particulier, par exemple l'anglais ou le japonais Les jetons forment des phrases en utilisant un ensemble structuré de règles (c'est-à-dire la grammaire). Un dispositif de reconnaissance d'un langage de programmation est un programme qui prend comme entrée une chaîne X et qui entre "oui" si X est une phrase de la langue et "non" dans le cas contraire Des configurations ou séquences de caractères sont spécifiées par une expression régulière En bref, une expression régulière définit un ensemble Des expressions régulières sont compilées dans un dispositif de reconnaissance en construisant un schéma généralisé de transition appelé un automate d'état fini (FSA) Un automate d'état fini peut être déterministe (DFA) ou non déterministe (NDFA), o "non déterministe" signifie que plus d'une transition est possible à partir d'un état sur le même symbole d'entrée Les automates d'état fini sont habituellement conçus pour analyser (reconnaître) des chaînes provenant d'un langage particulier de programmation Les phrases ' seraient divisées en jetons par l'automate d'état fini (c'est-à-dire l'analyseur lexique 210) et utilisées comme entrées dans le décomposeur 220 pour déterminer si les éléments de la phrase sont d'une forme légale spécifiée. La FIG 2 (b) illustre la manière dont l'analyseur lexique 210 de la présente invention est engendré A l'origine, une spécification d'entrée 260, consistant en expressions régulières souhaitées et en actions associées, est entrée dans le générateur 265 d'analyseur lexique Une action associée est une action particulière (par exemple imprimer "un espace") qui est effectuée si un jeu de caractères satisfait aux exigences de l'expression régulière. La présente invention est utilisée à l'intérieur du générateur 265 de l'analyseur lexique Comme décrit plus haut, le mode de réalisation préféré de la présente invention utilise le programme utilitaire LEX comme générateur 265 d'analyseur lexique On envisage que d'autres générateurs d'analyseur lexique seront améliorés avec la présente invention Il n'existe aucun élément inhérent au programme utilitaire LEX qui le rend plus adaptable à être interfacé avec le système et le procédé de la présente invention. Le générateur 265 de l'analyseur lexique produit comme sortie un analyseur lexique 270, qui est représenté dans le programme utilitaire LEX sous la forme lex yy c Dans le cas du programme utilitaire LEX, l'analyseur lexique 270 est un fichier de source C qui peut être compilé pour créer un analyseur lexique exécutable Un compilateur 275 de LEX 265 peut engendrer un dispositif de reconnaissance efficace d'automate d'état fini pour l'expression régulière. Ainsi, le fichier de source C est compilé par le compilateur 275 en un analyseur lexique exécutable 210 (appelé ci-après l'analyseur lexique 210) Rappelons que l'analyseur lexique 210 fait partie du compilateur , comme représenté à la FIG 2 (a). Finalement, le programme source 205 qui consiste en une séquence de caractères est entré dans l'analyseur lexique 210 En fonctionnement, l'analyseur lexique 210 attend des caractères d'entrée provenant du programme source 205 Lorsqu'il reconnait un ensemble de caractères d'entrée en concordance avec l'une des expressions régulières de la spécification d'entrée 260, il exécute l'action associée correspondante Ceci continue jusqu'à ce que le programme soit déterminé ou que l'on rencontre une fin de fichier (EOF). Typiquement, la sortie 280 de l'analyseur lexique 210 est un ensemble de jetons. L'homme de l'art comprendra immédiatement les équivalents des structures décrites ci-dessus. La FIG 3 représente un exemple d'un analyseur lexique exagérément simplifié (en d'autres termes une machine d'état fini) qui "transforme en jetons" des groupes de mots et/ou de nombres Un analyseur lexique 375 est conçu pour accepter (en d'autres termes, effectuer l'action qui lui est associée) toute séquence de nombres comprise entre zéro et neuf et/ou toute séquence de lettres comprise entre A et Z (avec la définition régulière la IB Idl, o a représente l'expression régulière lA à Zl, B représente un espace, et d représente l'expression régulière l O à 9 l) et fournit la sortie représentée au tableau 1 L'action associée est indiquée à la droite de chaque état d'arrêt individuel "Jetons" représente une variable globale utilisée pour retenir le jeton qui vient d'être reconnu par l'analyseur lexique 375 Le but de l'analyseur lexique 375 est de reconnaître des nombres et des mots tout en filtrant des espaces Il indique qu'un espace a été filtré en envoyant la chaîne "un ' espace". TABLEAU 1 Entrée: HERE IS A 75 (mot à mot: voici un 75) Sortie: HERE "un espace" IS "un espace" A "un espace" L'analyseur lexique 375 commence son analyse de la chaîne d'entrée à l'état d'origine S 380 Les états B 383 et C 287 sont appelés des états d'arrêt ou états d'acceptation, et ils sont indiqués de cette manière par les doubles cercles Les flèches reliant les états représentent des transitions d'états Chacune est étiquetée par un symbole reconnu par la machine. Lorsque chaque jeton de la chaîne d'entrées est balayé, la machine se déplace d'un état à l'autre, selon les symboles de la flèche Par exemple, dans la chaîne d'entrées "HERE IS A 7511, puisque le premier élément de la chaîne est un H, l'analyseur lexique 375 passe par une ligne de transition 382 de l'état S 380 à l'état C 387. L'analyseur lexique 375 continue ses transitions jusqu'à ce que, soit il finit la chaîne (balaie tous les éléments), soit il rencontre un élément auquel aucune transition n'est associée Dès lors que l'analyseur lexique 375 entre dans un état d'arrêt (B ou C) il a localisé au moins une partie d'un jeton. Dans notre exemple, dès qu'il sort de l'état d'arrêt, l'action associée est exécutée (un analyseur lexique plus complexe pourrait comporter une capacité de prévision) Par exemple, comme indiqué précédemment, si un analyseur lexique 375 se déplace de l'état S 380 à l'état C 387 en réponse à la lettre "H", il reste dans ' l'état d'arrêt C 387 par l'intermédiaire d'une ligne de transition 390 pour les lettres "E", "R" et "E" Il rencontre ensuite un espace de la chaîne d'entrée, et l'analyseur lexique 375 s'arrête donc et imprime "HERE" Dès lors que l'analyseur lexique 375 sort de l'état d'arrêt C 390, la représentation de jetons du lexème "HERE" serait envoyée au décomposeur 220. La présente invention concerne la possibilité de déterminer si un élément de la chaîne est un caractère acceptable et, si tel est le cas, de présenter ensuite un jeton au décomposeur 220 Dans l'exemple ci- dessus, dès lors que l'analyseur lexique 375 balaie H, il vérifie si c'est un caractère légal Typiquement, un analyseur lexique 375 vérifie dans une table pour trouver la lettre H Puisque H peut être représenté par un octet unique, ceci ne présente aucun problème pour l'analyseur lexique 375. Cependant, un analyseur lexique qui pourrait reconnaître la chaîne la E * D 1, peut avoir à regarder une combinaison de caractères à octet unique (par exemple des espaces) et de caractères à deux octets La table associée à un ensemble de caractères à deux octets serait importante au point d'être prohibitive, et le schéma de consultation serait compliqué par le besoin de distinguer entre une entrée à caractère à octet unique et une entrée à caractère à deux octets. On va maintenant détailler la mise en facteurs d'expressions régulières à deux octets en expressions régulières à un octet. La présente invention fournit un système et un procédé de mise en facteurs d'expressions régulières contenant des caractères à deux octets en expressions régulières contenant des caractères à octet unique. Généralement, les analyseurs lexiques ont été réalisés jusqu'ici pour ne reconnaître que des caractères qui tombent à l'intérieur du domaine des ensembles de ' caractères à octet unique Le problème de base consiste à traduire en un analyseur lexique une spécification d'entrée qui consiste en une expression régulière et en une action associée Ce processus général est bien connu de l'homme de l'art de la construction du compilateurs. Dans la spécification d'entrée, des classes de caractères peuvent être utilisées pour décrire un ensemble de caractères qui font partie d'une expression régulière Des classes de caractères sont désignées par un ensemble de caractères et/ou des plages de caractères entourées par des crochets (ll) Par exemple, labcl est utilisé pour reconnaître le caractère "a",, ou "b" ou "c", ou, de façon plus spécifique, les valeurs 141, 142 et 143 qui sont les valeurs ASCII de "a", "b", et "c". Une plage est spécifiée en plaçant un trait d'union (-) entre deux caractères La plage qui en résulte est constituée par tous les caractères qui sont situés entre les deux caractères ainsi que par les deux caractères eux-mêmes Par exemple la-tl reconnaît toutes les lettres comprises entre "a" et "t", ou plus spécifiquement, les valeurs 141 à 164 qui sont les valeurs ASCII d'un "a" et d'un "t". Tous les caractères décrits ci-dessus peuvent être représentés par des valeurs à octet unique La difficulté apparait lorsque sont utilisés des caractères à deux octets Diverses classes de caractères contiennent des caractères à deux octets, par exemple l'ensemble de caractères HP 15 utilisé pour -15 représenter le japonais Une classe de caractères peut maintenant ressembler à lô %E *J o l *I est représenté par les deux octets 139 et 65, l* 4 l est représenté par deux octets 139 et 73, et l* | est représenté par les deux octets 145 et 89 Lorsque l'utilisateur entre au clavier un caractère japonais sur l'écran, il est représenté de façon interne par deux octets Par conséquent, un automate d'état fini devrait rechercher dans une table extrêmement grande pour déterminer si le caractère entré au clavier a correspondu à une transition valide à l'état suivant dans l'automate. d'état fini. On va maintenant analyser successivement la procédure de classe de caractères, la procédure de plage de classes de caractères, la procédure composée de classe/plage de caractères et la construction universelle de caractères. La procédure de classe de caractères est relativement simple Etant donné une classe de caractères laybzl, o a, y, b et z sont chacun des valeurs à octet unique et ay et bz sont des caractères valides à deux octets, la procédure de classe de caractères traduit la classe de caractères en une classe qui reconnait soit ay, soit bz Celle-ci est désignée par "aylbz" La FIG 4 représente un exemple d'un automate d'état fini (FSA) 400 qui reconnait la classe de caractères laybzl Par exemple, l**I est traduit en 139 (représenté par a) suivi par 65 (représenté par y) ou 145 (représenté par b) suivi par 89 (représenté par z) Ainsi, tous autres caractères qui entrent dans l'automate d'état fini 400 ne seraient pas acceptés. Il faut maintenant deux transitions d'état pour reconnaître la représentation d'octet unique, à la différence de la transition d'état unique qui serait nécessaire si l'automate d'état fini devait reconnaître un caractère à représentation à deux octets Cependant, ainsi qu'il ressortira, la complexité additionnelle de l'automate d'état fini est plus que compensée par l'espace économisé dans la mémorisation de la table de transition. ' On va maintenant décrire la procédure de plage de classes de caractères. La traduction d'une plage de classes de caractères est plus difficile à traduire en une représentation à octet unique qu'une simple classe de caractères Etant donné une plage lay-bzl, o a, b, y et z sont toutes des valeurs à 8 bits et o ay et bz sont des caractères valides à deux octets, la procédure de plage de classes de caractères consiste à mettre en facteurs les plages à deux octets en une représentation équivalente à octet unique Il faut noter que a, b, y et z ne représentent pas les lettres de l'alphabet anglais Elles sont simplement symboliques d'une valeur à 8 bits. En se référant à la FIG 5, un schéma logique de la procédure de plage de classes de caractères 500 est représenté Comme représenté dans la case 510, la plage d'entrées à octets multiples lay-bzl est donnée à la procédure 500 pour être maniée La case 515 vérifie les deux premiers octets du premier élément de la plage de classes de caractères pour déterminer s'il s'agit d'un caractère légal à deux octets (c'est-à- dire si "ay" est un premier octet légal) Si ce n'est pas un caractère légal, un message d'erreur est donné à la case 540 pour signifier qu'une plage invalide de caractères a été donnée à la procédure 500 Dans le cas contraire, la procédure 500 passe à la case 520. La case 520 vérifie les deux premiers octets du dernier élément de la plage de classes de caractères (c'est-à-dire bz) pour déterminer si c'est un caractère légal à deux octets Si ce n'est pas un caractère légal, un message d'erreur est envoyé à la case 540 pour signifier qu'une plage invalide de caractères a été donnée à la procédure 500 Dans le cas contraire, la procédure 500 passe à la case 525. La case 525 vérifie afin de déterminer si le ' premier octet du premier élément est plus grand que le premier octet du dernier élément, parce qu'une plage de classes de caractères doit aller d'une plus petite valeur vers une plus grande valeur Si le premier octet du premier élément n'est pas plus grand, la procédure 500 passe à la case 540 Ici aussi, la case 540 renvoie un message d'erreur puisqu'une plage invalide de caractères a été donnée à la procédure 500. Dans le cas contraire, la procédure 500 passe à la case 530. La case 530, la case 535 et la case 545 sont des étapes clés dans la procédure de classe de caractères 500 La case 530 vérifie afin de déterminer si le premier octet du premier élément est égal au premier octet du dernier élément Si tel est le cas, la procédure passe à la case 535 Dans le cas contraire, la procédure passe à la case 545. La case 535 détermine si le deuxième octet du premier élément est plus grand que le deuxième octet du dernier élément Si tel est le cas, la procédure 500 renvoie un message d'erreur à la case 540 Dans le cas contraire, la procédure 500 traduit la plage de caractères pour donner le résultat suivant à octet unique: ( 1) a ly-zl La case 545 détermine si le premier octet du dernier élément est égal au premier octet du premier élément plus un S'il est égal à cette valeur, la procédure 500 traduit en un résultat à octet unique la plage de caractères La représentation à octet unique est: ( 2) (aly-255 l)I(bl 0-zl). La barre verticale signifie ici "ou", les parenthèses sont utilisées pour grouper des sous- expressions et la Juxtaposition de a avec ly-255 l signifie un enchaînement. En revanche, si le premier octet du dernier élément n'est pas égal au premier octet du premier élément plus un, la procédure 300 traduit la plage de classes de caractères en la représentation suivante à octet unique: ( 3) (aly-255 l)j(l(a+l)-(b-1)ll 0-255 l)I(bl 0-zl) L'analyseur lexique utilise les résultats ci- dessus Par conséquent, si l'utilisateur demande une plage à deux caractères à 16 bits, la plage sera divisée en une représentation à octet unique et cette représentation sera ensuite utilisée comme entrée vers un automate d'état fini déterministe (DFA) à octet unique L'exemple suivant représente la construction classique d'une table de transition, tant avant qu'après l'application des transformations fournies par la présente invention En outre, l'exemple démontre la quantité différente d'espace de mémorisation exigé pour représenter une table de transition à utiliser dans la construction d'une machine d'état fini. Supposons pour le présent exemple que la valeur 32769 ( 800116) représente un caractère Kanji valide qui est celui qui est désigné par l'idéogramme it et que 65534 (fffe 16) représente un caractère Kanji valide qui est désigné par l'idéogramme t L'expression régulière d'échantillon de cet exemple est l'ft-tl+ 1 ce qui représente une ou plusieurs des apparitions de l'un quelconque des caractères de la plage donnée La FIG 8 et le tableau 2 représentent un automate d'état fini 800 et une table de transition correspondante, respectivement, qui serait engendrés en utilisant une procédure classique (voir Aho et al). L'automate d'état fini (FSA) 800 ne possède que deux états de transition: l'état de début A 810 et l'état d'arrêt B 820 Il vérifie chaque caractère de la chaîne d'entrée afin de déterminer si sa représentation à deux octets est à l'intérieur de la plage valide ' (c'est-à-dire entre 800116 et fffe 16) Si le premier caractère est bien à l'intérieur de la plage valide, il existe une transition depuis l'état de début A 810 vers l'état d'arrêt B 820 Ensuite, chaque caractère ultérieur est vérifié et, s'il est à l'intérieur de la plage valide, une transition d'état est faite en retour vers l'état d'arrêt B 820 Comme expliqué ci-dessus, l'automate d'état fini 800 continue ses transitions jusqu'à ce que, soit il finit la chaîne d'entrées, soit il rencontre un jeton auquel aucune transition n'est associée S'il balaie toute la chaîne d'entrée (ce qui est indiqué par un caractère de fin de fichier (EOF)) et qu'il se termine à l'état d'arrêt B 820, la chaîne est acceptée En revanche, s'il balaie la chaîne mais ne se termine pas en état d'arrêt, ou s'il est incapable de balayer la chaîne par ce qu'il ne trouve pas de transition concordante sur un certain jeton, l'automate d'état fini 800 n'accepte pas la chaîne, et on dit qu'il se bloque. Le tableau 2 représente la table de transition qui serait utilisée pour construire l'automate d'état fini 800 Puisque les caractères Kanji sont représentés par deux octets de données, la table devrait comprendre 65.537 entrées Aucune compression n'est possible puisqu'il n'existe pas deux états ou davantage qui présentent des indications identiques pour toutes les entrées données Le nombre total d'entrées de table qu'il faudrait mémoriser serait de 131 074 puisqu'il existe deux états "goto"l, "error" et "ACCEPT" signifient dans ce tableau et les suivants: "aller à", "erreur" et"ACCEPTER". TABLEAU 2 Symbole suivant en entree La FIG 9 représente un exemple d'un automate d'état fini 800 qui a été construit après application, à la plage de classes de caractères llé-l, de la procédure de plage de classes de caractères 500 selon la présente invention a été appliquée Le tableau 3 représente la table de transition correspondante pour l'automate d'état fini (FSA) 900 De façon spécifique, on traduit la plage l 800116-fffe 16 l en 8016 l 10116-ff 16 l ll 8116-fe 16 l l 0016-ff 16 l Iff 16 oo 16-fe 6 l . On trouvera immédiatement ci-dessous l'automate d'état fini 900 et la table de transition qui correspondent. DecarnalO 3 ' 7683276932770 6553465535 EOF 0 x 000Ox 0001Ox 8 OO OI 8001O x 8002OxfffeOxffff Hex l|A erreur erreurerreuralleraller aller A _ eurerreur a B à B à B rreur erreur erreurerreur erreuralleraller aller à erreurACCEPTER à B à B B __ TABLEAU 3 Symbole suivant en entrée En outre, la compression de table est possible pour la table de transition de l'automate d'état fini 900 puisque des états d'arrêt C, E, et G possèdent des actions identiques pour toutes les entrées données Des procédés classiques de compression de table peuvent être trouvés dans Aho et al La table comprimée qui en résulte est représentée au tableau 4 Les états C, E et G ont été comprimés en un état unique C L'état F est devenu l'état E Bien que l'automate d'état fini 900 soit plus compliqué que l'automate d'état fini 800, la table de transition de l'automate d'état fini 900 est sensiblement plus petite que la table de transition de l'automate d'état fini 900 Par conséquent, puisque les caractères Kanji peuvent maintenant être représentés par des octets uniques, la table de transition n'exige que 257 colonnes Lorsque la compression est achevée, il n'existe que 1 285 entrées exigeant un emplacement en mémoire Les transformations décrites ci-dessus ont réduit dans cet exemple de 131 074 à 1 285 l'exigence Deofmai O 1 127 128 129 254 255 EOF Ha Oxw 0101 " Ox 7 fCx SO 831 * Oxf Ozff A erreurerreur erreuraller àaller à'f aller àaller àerreur B erreuraller à aller àaller àaller à*aller àaller àerreur c c c c' r C erreurerreur erreur aller àaller à aller àaller àACCEPTER B D F D aller àaller à aller àaller àaller à lier àaller àerreur Etat E E E E E E erreurerreur erreuraller àaller à iler àaller àACCEPTER B D F aller àaller à aller àaller àaller à* lier àerreurerreur G G G GI Qerreurerreur erreuraller àaller à aller àaller àACCEPTER B D d'emplacement en mémoire pour représenter la table de transition En d'autres termes, dans cet exemple, la présente invention a permis une économie de mémoire de 99,02 %. TABLEAU 4 Symbole suivant en entrée On va maintenant décrire la procédure de classe/plage de caractères composés. A la FIG 6 est représenté un schéma logique de la procédure de classe/plage de caractères 600 Comme représenté à la case 610, la plage composée de classes de caractères à octets multiples lawbx-cydzl est donnée à une procédure 600, o aw, bx, cy et dz sont des caractères valides à deux octets A la case 620, la procédure composée de classe/plage de caractères 600 traduit la classe donnée de caractères en: ( 4) awllbx-cylldz Puis, la procédure de plage de classes de caractères 500 décrite ci-dessus est appliquée au deuxième terme (lbx-cyl) dans la représentation ( 4) Il en résulte une représentation à octet unique. Evidemment, une vérification additionnelle d'erreur pourrait à volonté être incorporée dans la procédure ci-dessus. Decimai O I 127 128 129 254 255 Hez Ox OO mxi O " O x 7 fox 80xmi xfe oxff EOF A erreurerreur ' erreuraller àaller à aller à aller àerreu B 1) D F B erreuraller à C'aller à C aller àaller à ller àaller àerreu wc c c Etat C erreur erreur ' erreuraller àaller à aller àaller à ACCEPTE B D T) F D aller àaller aller aaller àaller à aller àaller àerreu E aller àaller à aller laller à aller à aller àerreurerreur c c c c r r - On va maintenant lister plusieurs plages composées classiques (classes de caractères) que l'on mentionnera afin d'être complet. La classe de caractères la-i-zl, o a, i et z sont des caractères à un ou deux octets, serait traduite en la-zl La classe de caractères la-ij-zl, o a, i, j et z sont des caractères à un octet ou à deux octets serait traduite en la-il lj-zl La classe de caractères la- hij-zl o a, h, i, j et z sont des caractères à un ou deux octets, serait traduite en la-hlliilj-zl Finalement, la classe de caractères la-hijk-zl o a, h, i, j, k et z sont des caractères à un ou deux octets, serait traduite en la-hllli-jlIlk-zl Après les traductions mentionnées ci-dessus, les procédures 500 et/ou 600 seraient appliquées selon les besoins à toutes plages qui contiendraient des caractères à deux octets. On peut trouver des plages au milieu d'une classe de caractères Ceci exige de séparer des plages les classes normales de caractères et d'effectuer une opération "ou" entre elles Par exemple, si la procédure de plage de caractères 500 a reçu la plage de classes de caractères à deux octets lac-xzl, o a, c, x et z sont tous des caractères à deux octets (une variable unique est utilisée pour les caractères à deux octets dans un but de simplicité), la plage serait à l'origine divisée en: ( 5) lazlllc-xl Puis, la procédure de plage de classes de caractères 500 décrite ci-dessus est appliquée à plage de classes de caractères lc-x-l. On va maintenant étudier la construction de caractères universels. Une autre notation utilisée dans la création de l'analyseur lexique est le "caractère universel". Celui-ci est représenté par un point " " Il est utilisé pour représenter tous les caractères légaux. Lorsqu'un point est trouvé, il indique qu'un caractère valide quelconque doit être reconnu à cet emplacement. En se référant à la FIG 7, une procédure 700 de construction d'un caractère universel est représentée. A l'origine, comme représenté à la case 710, la procédure 700 trouve les valeurs du plus petit caractère valide à deux octets et du plus grand caractère valide à deux octets à l'intérieur d'un langage spécifié La case 720 établit une plage entre les deux en utilisant, par exemple, une consultation de table Supposons que ab représente le plus petit caractère légal à deux octets dans l'ensemble de caractères et que yz est le plus grand caractère légal à deux octets de l'ensemble de caractères Par conséquent, a est le premier octet du plus petit caractère légal à deux octets, b est le deuxième octet du plus petit caractère légal à deux octets, y est le , premier octet du plus grand caractère légal à deux octets, et z est le deuxième octet du plus grand caractère légal à deux octets. Sur la base de la procédure de la plage de classes de caractères 500 décrite ci-dessus, la plage de classes de caractères lab-yzl est mise en facteurs selon l'expression: ( 6) alb-255 l 1 l(a+l)-(y-1)ll 0-255 l 1 ylO-zl comme représenté à la case 730. Un autre avantage de la présente invention consiste en ce qu'elle simplifie le problème de création d'un analyseur lexique qui comprenne une combinaison de caractères tant à un qu'à deux octets puisque toutes les expressions régulières de caractères à deux octets sont divisées en expressions régulières correspondantes consistant uniquement en caractères à octet unique De plus, le générateur de balayage sous- jacent n'a à établir que des tables et une machine pour des caractères à octet unique. L'enseignement de la présente invention est clairement applicable à divers champs situés à l'intérieur de la conception de compilateurs et à l'extérieur de la conception de compilateurs On envisage que la présente invention serait utilisée dans tous les environnements de reconnaissance de symboles. Tant qu'une information est représentée par une valeur à octets multiples, la présente invention fournit un mécanisme de réduction de la mémoire nécessaire pour reconnaître l'information Par exemple, les techniques d'établissement d'un analyseur lexique décrites ci- dessus peuvent être appliquées à des domaines comme l'édition générale de textes, l'édition d'un texte sensible au contexte, l'édition d'un texte dirigé en syntaxe, la reconnaissance grammaticale, la correction grammaticale, les applications d'orthographe, pour n'en nommer que quelques-unes Dans chaque application, le ' problème sous- jacent réside dans la spécification et la conception de programmes qui exécutent des actions déclenchées par des configurations en chaînes de caractères. Bien que la description ci-dessus concerne directement la mise en facteurs d'expressions régulières contenant au moins un caractère à deux octets, on envisage que les enseignements de la présente invention concerneront la mise en facteurs d'expressions régulières contenant des caractères représentés par plus de deux octets L'homme de l'art appliquera directement les enseignements de la présente invention à la mise en facteurs des expressions régulières contenant des caractères -provenant d'ensembles de caractères à octets multiples, et à l'établissement ultérieur d'un analyseur lexique qui peut balayer des jeux de caractères à octets multiples. Alors que l'invention a été représentée et décrite plus particulièrement en référence à des modes de réalisation préférés de celle-ci, l'homme de l'art comprendra que diverses modifications de formes et de détails peuvent y être apportées sans s'écarter de l'esprit et du cadre de la présente invention. Revendications 1 Système ( 200), à base d'ordinateur ( 104), de transformation ( 105), en une séquence de jetons ( 215), d'un programme source ( 205, 305) écrit dans un langage de programmation qui est représenté tant par des valeurs à octet unique que par des valeurs à octets multiples, caractérisé en ce qu'il comprend: (a) un moyen générateur ( 265) prévu pour constituer un analyseur lexical ( 270), ledit moyen générateur ( 265) étant configuré pour accepter une spécification d'entrée ( 260), ladite spécification d'entrée ( 260) incluant au moins une expression régulière, et (b) un moyen ( 210) de mise en facteurs prévu pour mettre en facteurs ladite expression régulière si ladite expression régulière contient au moins un caractère à octets multiples. 2 Système ( 200) selon la revendication 1, caractérisé en ce qu'il comprend en outre: un moyen compilateur ( 175, 275, 375) pour compiler ledit analyseur lexical ( 270) en un automate efficace d'état fini ( 400, 800, 900) pour ladite expression régulière mise en facteurs. 3 Système ( 200) selon la revendication 1, caractérisé en ce que ledit moyen ( 400) de mise en facteurs est configuré pour mettre en facteurs en (ay|bz) une plage de caractères de la forme laybzl, o ay et bz sont des caractères valides à deux octets. 4 Système ( 200) selon la revendication 1, caractérisé en ce que ledit moyen ( 500) de mise en facteurs est configuré de façon à mettre en facteurs en (aly-zl), une plage de caractères de la forme lay- bzl, o ay et bz sont des caractères valides à deux octets ( 515, 520), si ( 530) un premier octet du premier caractère de ladite plage de caractères est égal à un premier octet du dernier caractère de ladite plage de caractères et si ( 535) un dernier octet du premier caractère est supérieur au dernier octet du dernier caractère. Système ( 200) selon la revendication 1, caractérisé en ce que ledit moyen de mise en facteurs est configuré pour mettre en facteurs en (aly-255 l)I(bl 0-zl) une plage de caractères de la forme lay-bzl, o ay et bz sont des caractères valides à deux octets ( 515, 520), si ( 530) un premier octet du premier caractère de ladite plage de caractères n'est pas égal à un premier octet du dernier caractère de ladite plage de caractères et si ( 545) ledit premier octet du dernier caractère de la dernière plage de caractères est égal audit premier octet du premier caractère de ladite plage de caractères plus un. 6 Système ( 200) selon la revendication 1, caractérisé en ce que ledit moyen de mise en facteurs est configuré pour mettre en facteurs en (aly-255 l)I(l(a+l)-(b-1)ll 0-255 l)|(bl 0- zl) une plage de caractères de la forme lay-bzl, o ay et bz sont des caractères valides à deux octets ( 515, 520) si ( 530) un premier octet du premier caractère de ladite plage de caractères n'est pas égal à un premier octet du dernier caractère de ladite plage de caractères et si ( 545) ledit premier octet du dernier caractère de ladite plage de caractères n'est pas égal audit premier octet du premier caractère de ladite plage de caractères plus un. 7 Système ( 200) selon la revendication 1, caractérisé en ce que ledit moyen de mise en facteurs comprend en outre un moyen de vérification d'erreur pour vérifier ladite expression régulière afin de déterminer si elle contient des caractères valides. 8 Système ( 200) selon la revendication 1, caractérisé en ce qu'il comprend en outre un moyen universel ( 700) de génération d'une classe de caractères universels pour un ensemble de caractères à octets multiples, dans lequel ledit moyen universel comprend un moyen de détermination ( 710) de la plus petite et de la plus grande valeurs à octets multiples, ladite valeur à octets multiples représentant un caractère valide, et -de formation ( 720) d'une expression régulière de la forme lay-bzl, grâce à quoi ladite expression régulière lay-bzl représente une plage incluant la plus petite et la plus grande valeurs à octets multiples. 9 Procédé, à base d'ordinateur, de transformation, en une séquence de jetons, d'un ' programme source écrit dans un langage de programmation représenté par des caractères à octet unique et/ou à octets multiples, caractérisé en ce qu'il comprend les étapes consistant à: ( 1) recevoir une spécification d'entrée, ladite spécification d'entrée incluant au moins une expression régulière; ( 2) mettre en facteurs en une représentation à octet unique ladite expression régulière au moins unique; et ( 3) constituer un analyseur lexical basé sur ladite représentation à octet unique. Procédé selon la revendication 9, caractérisé en ce qu'il comprend en outre les étapes consistant à: ( 1) compiler ledit analyseur lexical} ledit analyseur lexical compilé étant un automate efficace à états finis de ladite expression régulière mise en facteurs; ( 2) entrer dans ledit analyseur lexical compilé une séquence de caractères; et ( 3) analyser ladite séquence de caractères en liaison avec ladite expression régulière mise en facteurs. 11 Procédé selon la revendication 9, caractérisé en ce que ladite étape de mise en facteurs met en facteurs en (aylbz> une plage de caractères de la forme laybzl, o ay et bz sont des caractères valides à deux octets. 12 Procédé selon la revendication 9, caractérisé en ce que ladite étape de constitution comprend la construction d'une table de transition basée sur ladite représentation à octet unique. 13 Procédé selon la revendication 9, caractérisé en ce que ladite étape d'analyse comprend en outre l'étape consistant à produire à partir de ladite séquence de symboles une chaîne de jetons. 14 Procédé selon la revendication 10, caractérisé en ce qu'il comprend en outre l'étape d'envoi de ladite chaîne de jetons à un décomposeur. , Procédé selon la revendication 9, caractérisé en ce que ladite étape de mise en facteurs met en facteurs en (aly-zl) une plage de caractères de la forme lay-bzl si un premier octet du premier caractère de ladite plage de caractères est égal à un premier octet du dernier caractère de ladite de plage de caractères, et si un dernier octet du premier caractère est supérieur au dernier octet du dernier caractère. 16 Procédé selon la revendication 9, caractérisé en ce que ladite étape de mise en facteurs met en facteurs en (aly-255 l)i(blO-zl) une plage de caractères de la forme lay-bzl si un premier octet du premier caractère de ladite plage de caractères n'est pas égal à un premier octet du dernier caractère de ladite plage de caractères et si ledit premier octet du dernier caractère de ladite plage de caractères est égal audit premier octet du premier caractère de ladite plage de caractères plus un. 17 Procédé selon la revendication 9, caractérisé en ce que ladite étape de mise en facteurs met en facteurs en (aly-255 l)I(l(a+l)-(b-1)ll 0-255 l)1 (blO-zl) une plage de caractères de la forme lay-bzl si un premier octet du premier caractère de ' ladite plage de caractères n'est pas égal à un premier octet du dernier caractère de ladite plage de caractères et si ledit premier octet du dernier caractère de ladite plage de caractères n'est pas égal audit premier octet du premier caractère de ladite plage de caractères plus un. 18 Procédé selon la revendication 9, caractérisé en ce qu'il comprend en outre une étape de génération d'une classe universelle de caractères comprenant les étapes consistant à: (a) déterminer la plus petite et la plus grande valeurs à deux octets, ladite valeur à deux octets représentant un caractère valide, et (b) former une expression régulière de la forme lay-bzl dans laquelle ay est la plus petite valeur à deux octets et bz est la plus grande valeur à deux octets. 19 Procédé selon la revendication 9, caractérisé en ce que ladite étape de mise en facteurs met en facteurs en lawbx-cydzl l'expression régulière (awllbz-cyl|dz). Procédé de mise en facteurs d'une expression régulière à plage de classes de caractères à deux octets en une expression régulière à classe de plage de caractères à octet unique, o la plage de classes de caractères est de la forme lay-bzl, o a, b, y et z sont des valeurs à octet unique, caractérisé en ce qu'il comprend les étapes consistant à: (a) déterminer si ledit premier octet du premier caractère est égal audit premier octet du dernier caractère et produire, si tel est le cas, un signal d'erreur si un dernier octet du dernier caractère est supérieur à un dernier octet du premier caractère ou mettre en facteurs, dans le cas contraire, en (aly-zl) la plage de classes de caractères; et (b} déterminer si ledit premier octet du dernier caractère est égal audit premier octet du premier caractère plus un, et mettre en facteurs, s'ils sont égaux, en (aly- 255 l)1 (bl 0-zl) la plage de classes de caractères, et mettre en facteurs, s'ils ne sont pas égaux, en (aly-225 l)I(l(a+l)-(b-1)ll 0-255 l)I(bl 0-zl) la plage de classes de caractères.