Discussion :

[cbv38]

Bonjour,

J'ai besoin d'aide pour un développement java que je dois effectuer. Il s'agît en fait plutôt d'un problème algorithmique, je ne suis donc pas sur de l'endroit ou poster mon message dans le forum. Si je fais erreur, merci de m'en faire part.

Je dois développer un module qui transforme un chaine de caractère contenant une expression de ce type :

critere1<5 ET critere2=1 ET critere3=1 ET (critere4=4 OU critere4=8 OU critere4=11 OU critere4=16)

(expression composée de critères, d'opérateurs <,>,<=,>=,=,!=,ET,OU, et de parentheses)

en une chaine de caractère contenant une expression de type xml :

<ET>
<EXPRESSION>
<NOM>critere1</NOM>
<INFERIEUR/>
<VALEUR>5</VALEUR>
</EXPRESSION>
<EXPRESSION>
<NOM>critere2</NOM>
<EGAL/>
<VALEUR>1</VALEUR>
</EXPRESSION>
<EXPRESSION>
<NOM>critere3</NOM>
<EGAL/>
<VALEUR>1</VALEUR>
</EXPRESSION>
<OU>
<EXPRESSION>
<NOM>critere4</NOM>
<EGAL/>
<VALEUR>4</VALEUR>
</EXPRESSION>
<EXPRESSION>
<NOM>critere4</NOM>
<EGAL/>
<VALEUR>8</VALEUR>
</EXPRESSION>
<EXPRESSION>
<NOM>critere4</NOM>
<EGAL/>
<VALEUR>11</VALEUR>
</EXPRESSION>
<EXPRESSION>
<NOM>critere4</NOM>
<EGAL/>
<VALEUR>16</VALEUR>
</EXPRESSION>
</OU>
</ET>

Quelqu'un aurait-il une idée de l'algorithme à utiliser, ou simplement quelques pistes à envisager.. ?

Merci d'avance

[Invité]

Salut,
Il faut construire l'arbre de ton expression en notation infixe. Avec cet arbre, en le parcourant tu peux générer ton XML.
J'utiliserais un parser pour construire l'arbre personnellement.
Comme un parser à écrire à la main c'est un peu fastidieux, il existe des outils pour le générer à partir de la grammaire, tels que JavaCC ou SableCC
Une fois l'arbre construit, tu peux grâce à un visiteur générer ton XML sous forme de chaine si tu veux.
A plus

[cbv38]

Merci pour tes indications. Je n'ai jamais utilisé de générateur de parser, mais je vais fouiller de ce côté là.
A plus

[cbv38]

Salut,
Il faut construire l'arbre de ton expression en notation infixe. Avec cet arbre, en le parcourant tu peux générer ton XML.
J'utiliserais un parser pour construire l'arbre personnellement.
Comme un parser à écrire à la main c'est un peu fastidieux, il existe des outils pour le générer à partir de la grammaire, tels que JavaCC ou SableCC
Une fois l'arbre construit, tu peux grâce à un visiteur générer ton XML sous forme de chaine si tu veux.
A plus

Bonjour,

J'ai suivi tes conseils et utilise Javacc pour générer mon parser.
Seulement, je rencontre un problème pour la définition de ma grammaire.
Petit rappel concernant la forme des expressions que je peux rencontrer : elles comprennent au minimum un critere, un opérateur et une valeur. Il peut s'y ajouter des ET des OU et des parenthèses.
Exemples :
(a=b et c>d ou e>=f)
(((a=b ou c=d) et y=z) ou e=f et g=h)

Si on écrit la grammaire de ces expressions cela donne :
Expression --> CritereOperateurValeur | Espression ETOU Expression | "(" Expression ")"

CritereOperateurValeur --> Mot Operateur Mot

En sachant que :
- ETOU peut être un ET ou un OU
- un Mot est une chaine de caractère
- un Operateur peut être une des chaines suivantes : "<" , ">" , "=" , "!=" , ">=" , "<="

Cependant, cette grammaire ne peut pas être mise en place via Javacc pour cause de récursivité :

Left recursion detected...



J'ai trouvé une solution intermédiaire qui consiste à ajouter manuellement un niveau de parenthèse pour pouvoir accepter les expression imbriquées. Mais si on entre plusieurs expression imbriquées cela ne marche pas..

Voici ce que j'ai écrit :

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
 
void Input() :
{}
{
 Expression() <EOF>
}
 
void Expression() :
{}
{
 (ExpressionSimple() (<ETOU> ExpressionSimple())*)
 |  "(" Expression()  ")"
 | (ExpressionSimple()(<ETOU> Expression())*)
}
 
void ExpressionSimple() :
{}
{
   (CritereOperateurValeur() (<ETOU> CritereOperateurValeur())*)
   | "("  ExpressionSimple()  ")"
}
 
void CritereOperateurValeur() :
{}
{
   <MOT> <OPERATEUR> <MOT>
}

Avec ceci ce genre d'expression avec plusieurs expressions imbriquées ne marche pas :
(((a=b ou c=d) et y=z) ou e=f et g=h)

Existe-il une solution, ou suis-je obligée d'ajouter les différents niveaux "manuellement" en ajoutant ExpressionNieau1, ExpressionNiveau2 (au risque de ne pas en faire assez..)

Merci d'avance !

[Invité]

Salut,
Il existe un moyen de transorfmer une récursion gauche en récusrrsion droite ce qui ne posera plus de problème à javacc car il est LL(k).
Tu pourras trouver le principe ici. C'est assez simple en fait.
Quand tu as une règle de production de type

Code :

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

1
2
 
<nt1> ::= <nt1> term1 | ... | <nt1> termk | t1 | ... | tl

Ton nt1 peut commencer par n'importe quel terme t1 jusque tl suivi d'un nombre quelconque de term1 -> termk.
Donc ca devient en (notation EBNF) :

Code :

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

1
2
3
4
5
 
// commence par les t1 -> tl
<nt1> ::= t1 <newterm> | ... | tl <newterm>
// suivi de rien ou alors dees term1 -> termk, et on répète récursivement sur les term1 -> termk
<newterm> ::= /\ | term1 <newterm> | ... | termk <newterm>

J'espère avoir été clair et limpide

[cbv38]

Merci ! J'ai enlevé la récursion gauche et ça marche !