Création d'un analyseur syntaxique

**tomy29** · 19/09/2008, 11h44

Bonjour,

Je dois créer le programme suivant :

J'ai un fichier texte avec des enregistrement.
Je dois rejeter chaque ligne qui comporte au moins un caractère non latin.
Les fichiers peuvent contenir des centaine de milliers de lignes.

Existe-t-il un composant qui aiderait à exécuter cette analyse syntaxique des caractères? Un outil rapide. Ou suis-je obligé de prendre caractère par caractère et de le comparer avec tous les caractères latins pour tester s'il est valide ou non?

Merci!

**Gilbert Geyer** · 19/09/2008, 12h48

Salut,

... Je dois rejeter chaque ligne qui comporte au moins un caractère non latin.

1) créer par exemple un Type ChrNonLatin : array[1..N] of Char,
2) scruter chaque ligne à partir de son début avec une boucle à interrompre au premier if MaLigne[i]=ChrNonLatin[j] then Rejet de la ligne et passage à la ligne suivante.

Les fichiers peuvent contenir des centaine de milliers de lignes.

... Peu importe : Si t'as une mem-vive-disponible suffisante tu peux charger le tout dans un TMemoryStream (rapidité maxi) ... sinon tu peux utiliser un TFileStream ou bien parcourir le fichier laissé sur disque ligne par ligne avec Readln().

A+

**petitcoucou31** · 19/09/2008, 12h54

salut

Juste une idée.. j'ai pas de reponse pour les composant faisant cela.

Si Ton texte est formaté et pas brut, tu peux peut être faire une recherche du nom de la police (avec les balises) dans la ligne courante et la comparer a une liste de police mais cela demande d'identifier tous les noms de polices latines ??.

La méthode de lecture de contrôle de caractères semble plus sure, mais peut être pas assez rapide.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
function CtrlChaineLatine(Lg:string):boolean;
const ChaineLatine='abcdefghijklmnopqrstv123456789....'; // chaine de caracteres valide.
var i:integer;
begin
    result:=true;
    for i:=1 to length(Lg)do
    begin
        if pos(lg[i],ChaineLatine)=0 then
        begin
          result:=false;
          exit;
        end;
    end;
end;

tu peux aussi mixer les deux pour gagner du temps, quand dans une ligne tu tombe sur une police qui t'es inconnu, alors tu contrôle les caractères..

**Franck SORIANO** · 19/09/2008, 13h29

Quoi que tu fasses, il faudra bien lire chaque caractère au moins une fois pour savoir s'il appartient au jeu de caractère que tu veux.

Personnellement, je ferais le teste avec un tableau lookup qui indique si un caractère est correct ou non :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
const
  CharIsOk : array[char] of boolean = (false, false, ....., true, ...... ); // A définir en fonction des caractères valides.
 
function CtrlChaine(const s : string) : boolean;
var p : pChar;
begin
  if s = ''
  then result := true
  else begin
    result := true;
    p := @s[1];
    while (p^<>#0) and result do
    begin
      result := result and CharIsOk[p^];
      inc(p);
    end;
  end;
end;

Maintenant libre à toi de voir comment gerer la lecture des chaines à tester.

**tomy29** · 19/09/2008, 14h56

Merci pour vos réponses,

Franck, je ne comprends pas trop comment utiliser et définir la constante CharIsOk?
A supposer que l'alphabet latin ne soit composé que de cinq caractères : a b c d e, comment remplirais-tu le tableau?
Et si la ligne étudiée est celle ci : abc]ac, peux tu me montrer grossièrement comment réagit ton algorythme?

Merci!

**Gilbert Geyer** · 19/09/2008, 16h25

Re-Salut,

je ne comprends pas trop comment utiliser et définir la constante CharIsOk?
A supposer que l'alphabet latin ne soit composé que de cinq caractères : a b c d e, comment remplirais-tu le tableau?

const CharIsOk : array[char] of boolean = (false, false, ....., true, ...... );

array[char] comprend les '0..255' caractères de la table Ascii
donc dans ton exemple des cinq caractères a b c d e, le 'a' occupe la 97ième position et les quatre autres suivent.
Donc tu mets au début 96 fois false au début et ensuite 5 fois true (pour a b c d e) et ensuite toute une série de false couvrant la plage 102..255 c'est à dire du 'f' jusqu'à la fin.

Les 96 false du début correspondent aux caractères qui précèdent le 'a'

Oups, faut remplacer le 32ième false du début par true : il correspond au caractère ' ' espace.

Le mieux serait que tu prennes une table Ascii pour choisir les caractères à fixer à true car tes lignes de texte peuvent comporter des caractères de ponctuation (,;!

des majuscules etc : à toi de choisir.

A+

**tomy29** · 19/09/2008, 16h50

ok, merci pour cet éclaircissement!!

**droggo** · 19/09/2008, 20h01

Hie,

Plutôt qu'un tableau, pourquoi ne pas utiliser un ensemble

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
type
  charSet = set of char;
 
const
  okChars : charSet = ['a'..'e','z']; { caractères a-e, z }

utilisation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
...
  {c est un catactère }
  if (c in okChars)
  then
  begin
    ...
  end;

Ça va tout aussi vite qu'avec un tableau, et ça me paraît nettement plus clair.

Pascal, donc Delphi disposent de base ce type fort utile, utilisons-le !!

**petitcoucou31** · 19/09/2008, 20h10

salut ,

Et pourquoi pas une simple chaine, et un POS sur la chaine...
En fait quelle est la solution la plus rapide ?

**Franck SORIANO** · 20/09/2008, 08h16

Envoyé par droggo

Hie,

Plutôt qu'un tableau, pourquoi ne pas utiliser un ensemble
Ça va tout aussi vite qu'avec un tableau, et ça me paraît nettement plus clair.

Ben en fait non, ce n'est pas aussi rapide qu'avec un tableau. Le type ensemble est implémenté sous la forme d'un tableau de bits packé à l'intérieur d'un entier.
Pour tester si un élément fait parti de l'ensemble, il faut identifier le numéro du bit de l'élément à tester, identifier l'adresse du bit a tester et tester le bit.
Heureusement, il y a une instruction assembleur qui fait ça directement. Mais elle n'est pas aussi rapide qu'un simple lookup dans un tableau.

Pour ce qui est du Pos, c'est beaucoup, beaucoup plus lent. Avec le tableau lookup, tu lis un caractères en entrée, tu fais une lecture directe dans le tableau et tu connais le résultat. Globalement, tu fais un test par caractère.

Avec un Pos, tu lis un caractère en entrée, puis tu le compare au premier caractère de la chaîne de référence, puis au deuxième, au troisième... jusqu'à avoir trouver celui qui t'intéresse.
Donc il faut que tu testes un par un tous les caractères du jeu latin avant de te rendre compte que le caractère n'est pas bon.
Avec les autres méthodes, tu n'as toujours qu'un seul et unique test.

Faites les tests :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
function TestSet(const s : string) : boolean;
var
  p : pchar;
begin
  if s = ''
  then result := true
  else begin
    result := true;
    p := @s[1];
    while (p^<>#0) and result do
    begin
      result := result and (p^ in okChars);
      inc(p);
    end;
  end;
end;
 
function TestTableau(const s : string) : boolean;
var
  p : pchar;
begin
  if s = ''
  then result := true
  else begin
    result := true;
    p := @s[1];
    while (p^<>#0) and result do
    begin
      result := result and CharIsOk[p^];
      inc(p);
    end;
  end;
end;
 
function TestPos(const s : string) : boolean;
var
  p : pchar;
begin
  if s = ''
  then result := true
  else begin
    result := true;
    p := @s[1];
    while (p^<>#0) and result do
    begin
      result := result and (pos(p^, ChaineLatine)>0);
      inc(p);
    end;
  end;
end;

Avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
var
  okChars : set of char = ['a'..'z', 'A'..'Z', '0'..'9'];
  CharIsOk : array[char] of boolean;
  ChaineLatine : string;
 
var
  cpt : char;
 
initialization
  ChaineLatine  := '';
  for cpt := low(CharIsOk) to high(CharIsOk) do
  begin
    CharIsOk[cpt] := cpt in okChars;
    if CharIsOk[cpt]
    then ChaineLatine := ChaineLatine + cpt;
  end;
end.

J'obtiens :

TestSet : 357ms.
TestTableau : 228ms.
TestPos : 6 340ms.

**tomy29** · 23/09/2008, 15h45

Question toute bête, à la déclaration de CharIsOk il me dit : le nombre d'élément diffère de la déclaration.

voici mon code , j'ai pourtant bien l'impression d'avoir mes 255 éléments :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const
  CharIsOk : array[char] of boolean = (
  false, false, false, false, false, false,
  false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true, true, true, true, true, true,
true,true,true);

**Gilbert Geyer** · 23/09/2008, 17h08

Salut,

Il manque un seul true à la fin. (Suffisait d'en rajouter ou d'en enlever à la fin jusqu'à ce que le compilo arrête de tousser).

A+

EDIT même jour 17h18 : Au fait il me semblait que tu voulais retenir seulement les caractères latins (de a à z, de A à Z, plus les caractères de ponctuation et éventuellement les caractères accentués français or avec la tartine de 'true' située à la fin de ton CharIsOk tu dois ramasser plein de caractères qui ne sont ni français ni latins, faudrait choisir avec ta table de caractères.

**tomy29** · 23/09/2008, 18h21

ok

c'était juste pour faire un test.
Par contre je suis surpris par la rapidité, j'ai un fichier de 1200000 lignes, et je mets un caractère non autorisé a la ligne 540000, avec des lignes de 68 caractères, et il met 3 secondes a me dire quelle ligne a ce caractère.

je vais des tests plus poussé parce que là ça me sidère.

**Franck SORIANO** · 23/09/2008, 19h02

Donc tu dois lire 540000*68 caractères pour trouver l'erreur.
Ca représente grosso modo 40 Mo à lire séquentiellement. De nos jours, un disque dur est capable de lire trois fois plus de données en une seconde.

3 secondes pour scanner 40 Mo, je pense qu'on doit pouvoir encore améliorer ça.
Les secondes comprennent le temps de lecture du fichier ? Si c'est le cas, tu peux grandement améliorer les performances en travaillant avec un fichier binaire au lieu d'un fichier text et en travaillant directement sur les données binaires, sans te préoccuper du découpage en lignes.
Pendant le scan, tu pourrais détecter les retours à ligne (caractère #13 et #10) pour compter les lignes au fur et à mesure du scan.
De plus tu pourrais également améliorer les perfs en multi-threadant le tout :
- Tu as un thread qui lit un bloc de donnée sur le fichier. Lorsqu'il a finit la lecture, il place le bloc dans une file d'attente et commence à lire un autre bloc de données sur le disque.
- Pendant ce temps, un deuxième thread traite la file des blocs lus pour faire le scan.
L'intérêt de la chose, c'est qu'un accès disque c'est essentiellement des temps d'attente et de la logique cablée.
En multi-threadant l'appli, on peut récupérer les temps d'attentes pour effectuer le scan des données. De cette façon, la recherche peut s'effectuer à la vitesse de l'élément le plus lent : La lecture du disque, ou le scan des données. Si on ne multi-thread pas le traitement, on additionne durées des deux traitements.

Bon j'arrête le délire, visiblement la solution actuelle est déjà suffisante pour satisfaire tes besoins.

PS: Pour CharIsOk, j'avais déclaré une constante typée pour présenter rapidement le principe, mais tu ferais mieux de déclarer une variable et de l'initialiser avec un bout de programme. Parce que un tableau de 256 boolean, c'est pas très lisible... on a vite fait de se planter.

**tomy29** · 24/09/2008, 10h31

Merci pour ces précisions!!
Effectivement, les besoins des utilisateurs ne méritent pas un investissement en temps de développement trop important. Et déjà si je leur annonce un temps de 4 sec pour un fichier d'un million de lignes, ils vont m'offrir le resto a la Tour d'argent.

Merci pour ton aide en tout cas!

Création d'un analyseur syntaxique

Langage Delphi

Discussions similaires

Partager

Partager