parseur spécial

Version imprimable

parseur spécial

Voilà, j'ai un problème de parseur que meme mon prof de stage ne donne pas une solution propre. Je vous confie pour ce problème.
Je veux lire un fichier contenant des lignes comme suite par exemple :
Code:

1 2 3 4 5 aardvark,1,0,0,1,0,0,1,1,1,1,0,0,4,0,0,1,1 chub,0,0,1,0,0,1,1,1,1,0,0,1,0,1,0,0,4 clam,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,7 crab,0,0,1,0,0,1,1,0,0,0,0,0,4,0,0,0,7 crayfish,0,0,1,0,0,1,1,0,0,0,0,0,6,0,0,0,7
dans laquelle c'est une suite des attributs de différente type. Chaque ligne contient le meme nombre d'attribut et que chaque attribut a un domaine. Par exemple :
-le premier attribut est un string, et le domaine de cet attribut est [aardvark,chub,clam,crab,crayfish] ---> le nom d'animaux
-le 5em attribut de droite à gauche est un attribut numérique et son domaine est [2,4,6,8]----> les pattes d'un animal
-le dernier est un attribut numérique et son domaine est {1..7} pour décrire la famille de l'animal.
-pour les autres attributs, ce sont des valeurs booléens pour décrire une caractère de l'animal ( avoir du poil ou non, par exemple)
Donc vous pouvez comprendre que chaque ligne est la description d'un animal.
Alors, mon parseur doit lire le fichier et construire un tableau de 2 dimensions dont la largeur est le nombre total des valeurs d'attribut et le longeur est le nbr de lignes.
Mon problème est de remplir la largeur. J'explique explicitement sur ''le nbr total des valeurs d'attributs". Je veux représenter les valeurs numériques et les strings (ou éventuellement les chars) par une suite des 0 et 1. Pour les booléens, c'est une suite 01 ou 10.
Par exemple:
Dans la premiere ligne de mon exemple

Code:

aardvark,1,0,0,1,0,0,1,1,1,1,0,0,4,0,0,1,1

: on aura
+10000 représente la valeur du premier attribut car cet attribut a un domaine de 5 valeurs et ''aardvark" est à la position 1 dans le domaine.
+0100 représente la valeur du 5eme attribut de droite à gauche car cet attribut a un domaine de 4 valeurs et "4'' est la deuxième valeur dans le domaine.
On calcule pas le dernier attribut( plutot je peux m'en occuper cet attribut).

Plus généralement, je représente chaque valeur i de l'attribut par un booléen, ce booleen vaut 1 si l'attribut a la valeur i, 0 sinon. Et ca doit etre valide pour n'importe quel type (numérique, string, char).
Donc pour résumer, je veux bien qu`à partir de la ligne

Code:

aardvark,1,0,0,1,0,0,1,1,1,1,0,0,4,0,0,1,1

je veux avoir une ligne correspondant

Code:

10000 01 10 10 01 10 10 01 01 01 01 10 10 0100 10 10 01 (dernier attribut non traité)

Quelqu'un a une idée pour faire ce parseur spécial?
Mon prof a proposé une solution de 2 étapes :
1. on lit le fichier pour collecter les domaines des attributs.
2. remplir le tableau à la fin.

Mais ce qui me gene est qu'il y a de différentes types dans une lignes, et je ne sais pas une structure de données spéciale de C++permettant stocker des différentes types..:(

J'attends vos idées génies.
Merci :calim2::calim2:

08/06/2011, 15h30
ManusDei

Est-ce que tu as pensé à regarder du côté de yacc (ou bison) et lex ?

A partir du moment où tu peux définir une grammaire (qui là me semble assez simple à faire), tu aurais un parseur plus propre en sortie.

En plus ça te permettrait de définir tes domaines assez facilement, et éventuellement de l'étendre à d'autres animaux, et d'autres caractéristiques (poils, plumes, poids, etc...).
08/06/2011, 16h25
jblecanard

Salut !

Citation:

Envoyé par ManusDei

Est-ce que tu as pensé à regarder du côté de yacc (ou bison) et lex ?

Trop lourd pour un débutant ! Et la syntaxe est si simple qu'on en a pas besoin.

De plus, le problème semble être situé au niveau du stockage en mémoire des données et pas au niveau du parsing. Vouloir faire un tableau à deux dimensions est ici une mauvaise idée. La meilleure chose à faire c'est :
- Un structure ou une classe qui possède les attributs nécessaires pour représenter un animal
- Un std::vector contenant des éléments de cette classe (ou structure)

minhkhue, est ce que tu vois où je veux en venir ? Nous allons trouver une solution à ton problème, mais pas à pas pour tu comprennes bien tout ce qui est fait.
08/06/2011, 17h34
minhkhue

Merci ManusDei. j'ai fait un tour sur le Net pour savoir un peu sur yacc/lex. Et j'avoue que c'est vaste par rapport à mon niveau.

Merci aussi jblecanard, mais je pense que j'ai pas tout expliqué mes travaux. En fait, ce que j'ai besoin à la fin est un tableau de 2 dimensions dont chaque ligne correspond bien avec la ligne trouvant dans le fichier au départ.
Donc, soit mon parseur est une sorte de données qui a comme paramètre un tableau de 2 dims, pour que je puisse l'utiliser directement faire d'autres choses avec . Soit j'écris ce tableau sur un autre fichier de texte et faire un nouveau parseur (un peu con, mais j'imagine quand meme).

En fait, je travaille dans l'Apprentissage , donc chaque fichier est une base données à apprendre des choses là dedans. Du coup, les contenus dans le fichier peuvent etre changé différemment.
Par exemple

Code:

a x j 0 4 positive

ou premier attribut a le domaine [a,b,c]
le deuxième a le domaine [x,y,z]
le troisième [i,j,k,l]
le quatrième est booléen
le cinqième est numérique {1..4}
le dernier est [positive,negative]

Donc, mon tableau à la fin doit avoir comme

Code:

100 100 0100 10 0001

je traite pas le dernier attribut.
Donc, le parseur doit etre générique pour lire de différents fichier qui ont meme principe de représenter les données, mais avec différentes type de données(numérique, string, char)

Du coup, créer une structure, ca me gene un peu...ou peut etre que j'ai pas assez imaginé.
Sinon, j'écoute votre proposition.
09/06/2011, 12h09
screetch

ah d'accord je commence a comprender

bon donc deux étapes:

* tu lis toutes les lignes pour trouver les domaines
pour chaque ligne, tu coupes aux virgules
pour chaque colonne, tu as un map<string, index>
pour chaque champs, si le champs existe déjà dans le map rien a faire, sinon tu l'ajoutes:
map.insert(make_pair(champs, map.size())

* tu relis chaque ligne
pour chaque ligne, tu coupes (encore) aux virgules
pour chaque champs, tu récupères son index dans le map
tu ecris pour map.size() de 0, sauf un 1 la ou il y a un champ.

si le domaine doit être trié alphabetiquement alors c'est un peu différent mais pas trop (la c'est dans l'ordre ou les valeurs apparaissent)
09/06/2011, 16h10
minhkhue

Super screetch, ta proposition me semble très intéressante, à tester.
J'imagine tout de suite dans ma tete comme suite :
je demande à l'utilisateur le nbr d'attribut au total.
je crée un tableau de type map<string,int>.
ensuite, je parcours le fichier pour collecter les domaines.
je parcours une nouvelle fois pour transformer les attributs.

:ccool::ccool: je vais débuter dans ce sens , je donne le résultat plutard :))
09/06/2011, 16h48
jblecanard

Hello

Je comprend aussi beaucoup mieux ! C'est un peu peu compliqué que ce que je pensais, mais mes remarques restent valables.

Citation:

Envoyé par screetch

* tu lis toutes les lignes pour trouver les domaines
pour chaque ligne, tu coupes aux virgules
pour chaque colonne, tu as un map<string, index>
pour chaque champs, si le champs existe déjà dans le map rien a faire, sinon tu l'ajoutes:
map.insert(make_pair(champs, map.size())

Je ne suis pas tout à fait d'accord avec screetch. A mon avis, il faut "configurer" le parseur pour lui donner les domaines. Créer les domaines à partir du fichier voudrait dire qu'on ne peut faire aucune vérification d'erreur, et donc que les domaines n'ont pas lieu d'être (puisqu'ils n'imposent aucune contrainte !).

Moi je verrais bien une aggrégation d'objets qui représentent les valeurs. En exploitant le(s) polymorphisme(s) de C++. Je reviens avec un proto.

Edit :
Bon ça a l'air de plaire à l'intéressé. Néanmoins screetch, tu passes sous silence la manière de gérer "champs". Car il va bien falloir un type qui puisse représenter n'importe quel champ.
09/06/2011, 17h29
screetch

ben ca dépend de l'utilisation, si on veut qu'il soit configurable, ou bien qu'il parse tout n'importe comment, ou bien...

d'ailleurs est-ce bien le rôle de ce parser de faire la vérification? n'est-ce pas le rôle d'un autre outil on dit bien une seule résponsabilité par classe/fonction)

moi si je travaillais dessus j'aurais fait ca différemment avec des titres aux colonnes pour indiquer le type, ce qui m'aurait permis de vérifier. Mais si il s'agit de parser tout sans aide exterieure, il n'y a pas trop le choix.

j'ai bien spécifié champs, c'est une string (quand j'a dit qu'on avait un map<string, int>)
09/06/2011, 17h48
jblecanard

Exact, au temps pour moi.

Citation:

Envoyé par minhkhue

Donc, le parseur doit etre générique pour lire de différents fichier qui ont meme principe de représenter les données, mais avec différentes type de données(numérique, string, char)

L'idée de screetch est bonne. Tu peux tout parser en std::string (tu n'as pas vraiment le choix de toute façon :mrgreen:). Et faire la conversion au moment opportun.

Sinon pour stocker vraiment des types différents un dans un même conteneur, et avoir des contraintes sur les valeurs possibles, il y a un snippet dispo ici. C'est une solution parmi d'autres.
09/06/2011, 17h50
screetch

(moi perso j'aurais mis des types un peu plus fort hein, mais si toute l'info qu'on a est dans le fichier, on peut pas vérifier facilement...
avec une aide externe au fichier, des infos sur les types ou quelque chose comme ca, jblecanard ferait un code beaucoup plus robuste, ce qui serait 'achement mieux, mais si ca doit parser tous les fichiers possibles, dans ce cas y'a pas le choix :()
09/06/2011, 17h51
screetch

Citation:

Envoyé par minhkhue

je demande à l'utilisateur le nbr d'attribut au total.

pourquoi? c'est pas le nombre de champs de la premiere ligne? tu peux le faire au fur et a mesure, a priori
10/06/2011, 00h46
jblecanard

Moi la bonne solution que je vois c'est :
- Un fichier qui contient le format (types et valeurs possibles) donné par l'utilisateur
- Un autre fichier avec tes données

Ainsi, ça fait deux parseurs triviaux à écrire et ça fera un système sympa pour l'utilisateur ! Moi j'aime pas quand un programme en ligne de commande me demande quelque chose, car ça veut dire que ça va m'emmerder à me redemander les mêmes trucs à chaque fois que je le lance.
10/06/2011, 14h46
minhkhue

En vérifiant les bases de données, je peux confirmer que les domaines sont fournis dans le fichier. C'est à dire que si l'on collecte toute les valeurs dans le fichier, on peut reconstruire complètement les domaines.
J'aime bcp la méthode de screetch, mais comme il a remarque' lors la proposition. Les domaines ne sont pas "triés", ou plutot, les maps ne sont pas trié en fonction des valeurs, mais pas des clés. Par contre, je l'ai besoin.
Avez vous une proposition pour trier le map comme je souhaite?
j'imagine, lorsqu'on récupère une valeur d'un attribut, on va regarder si cette valeur est déjà dans le map, sinon, on va l'ajouter de manière en ordre alphabetique. :oops: mais là ou je ne sais pas trop comment faire. Je crée un itérateur dans le map, et je parcours pour comparer le string qu'on récupère avec les string dans les champs? Si le string qu'on a est strictement inférieur au string courant, on s'arrete le parcours, on ajoute un paire avec la valeur comme le string qu'on a et la clé égale celle du string courant? et puis, on va incrémenter 1 pour toutes les clés qui restent dans le parcours?
Que pensez vous?
10/06/2011, 16h12
jblecanard

Je ne comprend rien du tout à cette histoire de map. Ca ne marchera pas avec les attributs entiers puisque la même valeur peut apparaître dans plusieurs colonnes.

Quelles sont les infos que tu veux extraire exactement ?
Les domaines, c'est quoi ? C'est la liste des valeurs possibles ou c'est le nombre d'occurrence de chaque valeur ? J'ai l'impression que ce n'est pas très clair dans ta tête, en tout cas c'est incompréhensible quand je te lis.

Deux choses :
- Quoi qu'on fasse, il n'y a pas besoin de parser le fichier deux fois. Une seule passe suffit, et on fait les calculs sur les données stockées. Lire un fichier c'est lent, pas la peine de répéter l'opération inutilement.
- Les clés des maps sont toujours triées par ordre alphabétique, ça fait partie de la spec.
10/06/2011, 16h15
screetch
un map (ou set) est la pour ca. un map (ou set) garde une liste ordonnée des éléments (en fonction de la clé), je pense que le tri par défaut sur les string est simplement l'ordre alphabetique.

ce que je propose désormais:
collecter toute les valeurs sans leur associer de clé (pour l'instant)
pour cela, utilise insert(): insert insère l'élément si il n'existe pas, sinon il l'ajoute.
puis pour chaque valeur dans le map, ajoute la valeur plus tard. en gros: (les changements par rapport a avant sont en gras)

* tu lis toutes les lignes pour trouver les domaines
pour chaque ligne, tu coupes aux virgules
pour chaque colonne, tu as un map<string, index>
pour chaque champs, si le champs existe déjà dans le map rien a faire, sinon tu l'ajoutes:
map.insert(make_pair(champs, 0)

* pour chaque domaine
* Pour chaque élément dans le map: en pseudo code c++

Code:

1 2 3 4 5 int i = 0; for (map<string, int>::iterator it = domain.begin(); it != domain.end(); ++it) { it->second = i; i++; }

du coup ici a chaque clé tu associes sont index, dans l'ordre alphabétique

* tu relis chaque ligne
pour chaque ligne, tu coupes (encore) aux virgules
pour chaque champs, tu récupères son index dans le map
tu ecris pour map.size() de 0, sauf un 1 la ou il y a un champ.

Je te laisse faire screetch, je n'y comprend plus rien à ces délires de map et d'index. Je m'en vais comme un prince et vous laisse un snippet de parsing :mrgreen:

Code:

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <boost/foreach.hpp>
 
struct Champ
{
  std::string chaine;
  int entier;
  bool est_entier;
 
  Champ(const std::string& iChaine) : chaine(iChaine), entier(0), est_entier(false)
  {}
 
  Champ(int iEntier) : chaine(""), entier(iEntier), est_entier(true)
  {}  
};
 
std::ostream& NewLine(std::ostream& iStream) { return iStream << std::endl; }
void CreerFichiersDeTest()
{
  std::ofstream data("donnees.txt");
  if(data)
  {
    data << "roger,cequetuveux,1,8,0";
    NewLine(data) << "philipbert,azezae,1,13,0";
    NewLine(data) << "fulbert,etlameremichelle,2,5,1";
    NewLine(data) << "marcel,elleaperdusonchat,0,13,0";
    data.close();
  }
}
 
typedef std::vector< Champ > LigneDeChamps;
typedef std::vector< LigneDeChamps > TableDeDonnees;
 
int main(int argc, char * argv[])
{
  // A ne pas reproduire : c'est juste pour l'exemple
  CreerFichiersDeTest();
 
  // Maintenant on parse
  std::ifstream donnee("donnees.txt");
  TableDeDonnees donneesParsees;
  if(donnee)
  {
    std::string ligne_str;
    while(std::getline(donnee,ligne_str))
    {
      LigneDeChamps ligne_courante;
      std::istringstream ligneSteam(ligne_str);
      std::string champ_str;
      while(std::getline(ligneSteam,champ_str,','))
      {
         std::istringstream intStream(champ_str);
         int intValue;
         if(intStream >> intValue)
         {
            ligne_courante.push_back(Champ(intValue));
         }
         else
         {
            ligne_courante.push_back(Champ(champ_str));
         }
      }
 
      donneesParsees.push_back(ligne_courante);
    }
  }
 
  // Affichage
  BOOST_FOREACH(const LigneDeChamps& ligneCourante, donneesParsees)
  {
    BOOST_FOREACH(const Champ& champ, ligneCourante)
    {
      if(champ.est_entier)
        std::cout << "int(" << champ.entier << ");";
      else
        std::cout << "string(" << champ.chaine << ");";
    }
 
    std::cout << std::endl;
  }
 
  return 0;
}