Brevet FR3078573A1 (20190906)

REVENDICATIONS1) Procédé d'analyse lexicale d'une chaîne de caractères, le procédé étant exécuté par un dispositif électronique, le dispositif électronique comprenant une mémoire dans laquelle est enregistré une liste de sous-chaînes de caractères prédéterminées, le dispositif électronique étant adapté pour recevoir, en entrée, une chaîne de caractères et pour enregistrer dans la mémoire, en sortie, une liste ordonnée des sous-chaînes comprises dans la chaîne de caractères, le procédé comprenant les étapes préalables de : pour chaque sous-chaîne de caractères prédéterminée, déterminer un condensat, dit condensat préfixe, en fonction des P premiers caractères de ladite sous- chaîne, P étant prédéterminé, - pour chaque sous-chaîne de caractères prédéterminée, déterminer, dans une table, dite table de hachage, enregistrée dans la mémoire du dispositif électronique, une entrée correspondant au condensat préfixe associé à ladite sous-chaîne, - pour chaque entrée de la table de hachage correspondant à un préfixe, déterminer une liste ordonnée des sous-chaînes prédéterminées associées, chaque sous-chaîne prédéterminée étant associée à un condensat, dit condensat sous-chaîne, fonction de la sous-chaîne prédéterminée, la liste étant ordonnées selon une longueur décroissante des sous-chaînes prédéterminées, et, - recevoir la chaîne de caractères et déterminer une position d'un pointeur sur la chaîne de caractères, la position correspondant initialement au premier caractère de la chaîne de caractères, le procédé comprenant de plus les étapes itératives de : déterminer un premier condensat de la sous-chaîne formée par P caractères de la chaîne de caractères à partir de la position du pointeur, - déterminer si une entrée condensat préfixe de la table de hachage correspond à ce premier condensat, si oui, pour chaque longueur des sous-chaînes prédéterminées de la liste associée à ladite entrée condensat préfixe, et dans l'ordre de la liste, déterminer un condensat de la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si ledit condensat est égal à un condensat sous-chaîne associé à l'une des sous-chaînes prédéterminées de même longueur, alors : 19 o vérifier que ladite sous-chaîne prédéterminée est égale à la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si c'est le cas, o enregistrer ladite sous-chaîne, dite sous-chaîne identifiée, dans la liste 5 ordonnée des sous-chaînes prédéterminées comprises dans la chaîne de caractères, o positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant à la position additionnée d'un nombre de caractères correspondant à la longueur de la sous-chaîne identifiée, 10 - si non, positionner le pointeur sur-la chaîne de caractères à une nouvelle position correspondant au déplacement d'un caractère sur la chaîne de caractères.\n<CLM>\1\tProcédé selon la revendication précédente, le procédé comprenant les étapes ultérieures de mise à jour de la liste de sous-chaînes de caractères prédéterminées : 15 - recevoir une sous-chaîne, - déterminer le condensat dit condensat préfixe, en fonction des P premiers caractères de ladite sous-chaîne, - déterminer une entrée dans la table de hachage correspondant audit condensat préfixe, 20 - enregistrer dans la liste ordonnée des sous-chaînes associées à l'entrée déterminée la sous-chaîne, la position dans la liste de la sous-chaîne étant fonction de la longueur de la sous-chaîne, - déterminer et enregistrer un condensat du la sous-chaîne en association avec la sous-chaîne dans la liste. 25\n<CLM>\1\tDispositif électronique permettant une analyse lexicale d'une chaîne de caractères, le dispositif électronique comprenant une mémoire dans laquelle est enregistrée une liste de sous-chaînes de caractères prédéterminées, le dispositif électronique étant adapté pour : 30 pour chaque sous-chaîne de caractères prédéterminée, déterminer un condensat, dit condensat préfixe, en fonction des P premiers caractères de ladite sous-chaîne, P étant prédéterminé, pour chaque sous-chaîne de caractères prédéterminée, déterminer, dans une table, dite table de hachage, enregistrée dans la mémoire du dispositif 20 électronique, une entrée correspondant au condensat préfixe associé à ladite sous-chaîne, pour chaque entrée de la table de hachage correspondant à un préfixe, déterminer une liste ordonnée des sous-chaînes prédéterminées associées, chaque sous- 5 chaîne prédéterminée étant associée à un condensat, dit condensat sous-chaîne, fonction de la sous-chaîne prédéterminée, la liste étant ordonnées selon une longueur décroissante des sous-chaînes prédéterminées, et, - recevoir une chaîne de caractères et déterminer une position d'un pointeur sur la chaîne de caractères, la position correspondant initialement au premier caractère 10 de la chaîne de caractères, le dispositif électronique étant de plus adapté pour : - déterminer un premier condensat de la sous-chaîne formée par P caractères de la chaîne de caractères à partir de la position du pointeur, - déterminer si une entrée condensat préfixe de la table de hachage correspond à 15 ce premier condensat, - si oui, pour chaque longueur des sous-chaînes prédéterminées de la liste associée à ladite entrée condensat préfixe, et dans l'ordre de la liste, déterminer un condensat de la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si ledit 20 condensat est égal à un condensat sous-chaîne associé à l'une des sous-chaînes prédéterminées de même longueur, alors : o vérifier que ladite sous-chaîne prédéterminée est égale à la sous-chaîne formée par un nombre de caractères de la chaîne de caractères égal à ladite longueur à partir de la position du pointeur, et, si c'est le cas, 25 o enregistrer ladite sous-chaîne, dite sous-chaîne identifiée, dans une liste ordonnée des sous-chaînes prédéterminées comprises dans la chaîne de caractères, ladite liste étant enregistrée dans la mémoire du dispositif électronique, o positionner le pointeur sur la chaîne de caractères à une nouvelle position 30 correspondant à la position additionnée d'un nombre de caractères correspondant à la longueur de la sous-chaîne identifiée, si non, positionner le pointeur sur la chaîne de caractères à une nouvelle position correspondant au déplacement d'un caractère sur la chaîne de caractères. 21\n<CLM>\1\tProgramme d'ordinateur, caractérisé en ce qu'il comprend des instructions pour mettre en oeuvre, par un processeur d'un dispositif électronique, le procédé d'analyse lexicale, selon l'une des revendications 1 à 2, lorsque le programme d'ordinateur est 5 exécuté par le processeur.\n<CLM>\1\tSupport d'enregistrement, lisible par un dispositif électronique, sur lequel est stocké le programme d'ordinateur selon la revendication précédente.