Je ne parviens pas à trouver le groupe le plus approprié pour poser ma
question. Désole pour le Hors-Charte, peut-etre quelqu'un saura t'il me
rediriger (voir me répondre).
Expression réguliere:
Il ya a t'il une syntaxe pour "tout sauf"
Quelle serait par exemple l'expression réguliere pour rechercher dans
la liste suivante les chaines avec un autre caractère que B à la
seconde place (tout sauf B)
AED
BBC
ZRE
Puisqu'on est, malgré les apparences, sur fclc++, aurais-tu moyen de créer une fonction capable de transformer une chaîne ("Microsoft"), en la regex associée (compatible avec Boost bien sûr) ?
Il me semble que boost est compatible avec PECL, donc il suffirait d'utiliser ^((?!Microsoft).)*$ proposé par Olivier.
Puisqu'on est, malgré les apparences, sur fclc++, aurais-tu moyen de
créer une fonction capable de transformer une chaîne ("Microsoft"), en
la regex associée (compatible avec Boost bien sûr) ?
Il me semble que boost est compatible avec PECL, donc il suffirait
d'utiliser ^((?!Microsoft).)*$ proposé par Olivier.
Puisqu'on est, malgré les apparences, sur fclc++, aurais-tu moyen de créer une fonction capable de transformer une chaîne ("Microsoft"), en la regex associée (compatible avec Boost bien sûr) ?
Il me semble que boost est compatible avec PECL, donc il suffirait d'utiliser ^((?!Microsoft).)*$ proposé par Olivier.
Heureusement, c'est deux fois la meme organisee differemment.
Ca plante sur les chaines qui se terminent par un prefixe de Microsoft. L'automate est facile a fixer, l'exprimer sous forme de regexp, je ne vois pas.
Un ou avec une expression qui passe toutes les chaînes ayant moins de caractères que "Microsoft" ? Quelque chose du genre :
Heureusement, c'est deux fois la meme organisee differemment.
Ca plante sur les chaines qui se terminent par un prefixe de
Microsoft. L'automate est facile a fixer, l'exprimer sous
forme de regexp, je ne vois pas.
Un ou avec une expression qui passe toutes les chaînes ayant
moins de caractères que "Microsoft" ? Quelque chose du genre :
Heureusement, c'est deux fois la meme organisee differemment.
Ca plante sur les chaines qui se terminent par un prefixe de Microsoft. L'automate est facile a fixer, l'exprimer sous forme de regexp, je ne vois pas.
Un ou avec une expression qui passe toutes les chaînes ayant moins de caractères que "Microsoft" ? Quelque chose du genre :
(Mais je n'aimerais pas avoir à l'entrer manuellement, sans l'aide du copier/coller.)
Moi non plus, d'autant plus que l'expression toute simple déjà donnée fonctionne bien mieux !
Jean-Marc Bourguet
Olivier Miakinen <om+ writes:
Moi non plus, d'autant plus que l'expression toute simple déjà donnée fonctionne bien mieux !
Le "probleme" naturellement, c'est que ca utilise une extension qui empeche la transformation en FSM. Alors qu'il y a une FSM toute simple qui resoud le probleme, toutes les expressions rationnelles (en utilisant rationnelle pour la syntaxe equivalent aux grammaires de type 1 par opposition a reguliere pour ce qui admets des extensions) me semble toujours compliquees.
J'ai toujours rien de plus simple que: (M(i(c(r(o(s(o(f[^t]|[^f])|[^o])|[^s])|[^o])|[^r])|[^c])|[^i])|[^M])*(M(i(c(r(o(s(of?)?)?)?)?)?)?)? ce qui necessite trois fois chaque lettre sauf la derniere et je n'ai toujours pas compris pourquoi fondamentalement avoir une fois la lettre et une fois sa negation n'a pas l'air possible.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Olivier Miakinen <om+news@miakinen.net> writes:
Moi non plus, d'autant plus que l'expression toute simple déjà donnée
fonctionne bien mieux !
Le "probleme" naturellement, c'est que ca utilise une extension qui empeche
la transformation en FSM. Alors qu'il y a une FSM toute simple qui resoud
le probleme, toutes les expressions rationnelles (en utilisant rationnelle
pour la syntaxe equivalent aux grammaires de type 1 par opposition a
reguliere pour ce qui admets des extensions) me semble toujours
compliquees.
J'ai toujours rien de plus simple que:
(M(i(c(r(o(s(o(f[^t]|[^f])|[^o])|[^s])|[^o])|[^r])|[^c])|[^i])|[^M])*(M(i(c(r(o(s(of?)?)?)?)?)?)?)?
ce qui necessite trois fois chaque lettre sauf la derniere et je n'ai
toujours pas compris pourquoi fondamentalement avoir une fois la lettre et
une fois sa negation n'a pas l'air possible.
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Moi non plus, d'autant plus que l'expression toute simple déjà donnée fonctionne bien mieux !
Le "probleme" naturellement, c'est que ca utilise une extension qui empeche la transformation en FSM. Alors qu'il y a une FSM toute simple qui resoud le probleme, toutes les expressions rationnelles (en utilisant rationnelle pour la syntaxe equivalent aux grammaires de type 1 par opposition a reguliere pour ce qui admets des extensions) me semble toujours compliquees.
J'ai toujours rien de plus simple que: (M(i(c(r(o(s(o(f[^t]|[^f])|[^o])|[^s])|[^o])|[^r])|[^c])|[^i])|[^M])*(M(i(c(r(o(s(of?)?)?)?)?)?)?)? ce qui necessite trois fois chaque lettre sauf la derniere et je n'ai toujours pas compris pourquoi fondamentalement avoir une fois la lettre et une fois sa negation n'a pas l'air possible.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Olivier Miakinen
Le 01/08/2008 21:03, Jean-Marc Bourguet a écrit :
J'ai toujours rien de plus simple que: (M(i(c(r(o(s(o(f[^t]|[^f])|[^o])|[^s])|[^o])|[^r])|[^c])|[^i])|[^M])*(M(i(c(r(o(s(of?)?)?)?)?)?)?)? ce qui necessite trois fois chaque lettre sauf la derniere et je n'ai toujours pas compris pourquoi fondamentalement avoir une fois la lettre et une fois sa negation n'a pas l'air possible.
Le problème est que lorsque une classe de caractères négative est utilisée (par exemple [^t]) sur la première lettre du mot cherché (le M de Microsoft), cette lettre est « consommée » et n'est donc pas prise en compte pour la reconnaissance du mot « Microsoft » qui se trouverait à cet endroit précis. On ne peut s'en sortir qu'avec une assertion, mais quitte à les utiliser autant le faire avec la méthode la plus simple.
Le 01/08/2008 21:03, Jean-Marc Bourguet a écrit :
J'ai toujours rien de plus simple que:
(M(i(c(r(o(s(o(f[^t]|[^f])|[^o])|[^s])|[^o])|[^r])|[^c])|[^i])|[^M])*(M(i(c(r(o(s(of?)?)?)?)?)?)?)?
ce qui necessite trois fois chaque lettre sauf la derniere et je n'ai
toujours pas compris pourquoi fondamentalement avoir une fois la lettre et
une fois sa negation n'a pas l'air possible.
Le problème est que lorsque une classe de caractères négative est
utilisée (par exemple [^t]) sur la première lettre du mot cherché (le M
de Microsoft), cette lettre est « consommée » et n'est donc pas prise
en compte pour la reconnaissance du mot « Microsoft » qui se trouverait
à cet endroit précis. On ne peut s'en sortir qu'avec une assertion, mais
quitte à les utiliser autant le faire avec la méthode la plus simple.
J'ai toujours rien de plus simple que: (M(i(c(r(o(s(o(f[^t]|[^f])|[^o])|[^s])|[^o])|[^r])|[^c])|[^i])|[^M])*(M(i(c(r(o(s(of?)?)?)?)?)?)?)? ce qui necessite trois fois chaque lettre sauf la derniere et je n'ai toujours pas compris pourquoi fondamentalement avoir une fois la lettre et une fois sa negation n'a pas l'air possible.
Le problème est que lorsque une classe de caractères négative est utilisée (par exemple [^t]) sur la première lettre du mot cherché (le M de Microsoft), cette lettre est « consommée » et n'est donc pas prise en compte pour la reconnaissance du mot « Microsoft » qui se trouverait à cet endroit précis. On ne peut s'en sortir qu'avec une assertion, mais quitte à les utiliser autant le faire avec la méthode la plus simple.
Jean-Marc Bourguet
Bon... retour à la case 0. Copie et suivi sur le groupe d'algo, vraisemblablement mieux adapté.
Problème: bâtir une expression rationnelle qui accepte n'importe quoi sauf une chaîne donnée. L'automate et la grammaire sont faciles à écrire, mais l'expression...
Retour chez Aho et Ullman (The theory of parsing, translation and compiling), le seul bouquin que j'ai qui donne un algo pour passer d'une grammaire à une expression.
Exemples sur les chaînes a, ab, abc et abcd. Je note 0 la chaîne vide.
Premièrement, si on a X -> e X | b ça veut dire que X -> e*|b (voir la démonstration dans le bouquin)
== a
A -> [^a] A | 0 -> [^a]* 0 -> [^a]*
== ab
A -> [^a] A | a B | 0 B -> [^ab] A | a B | 0 -> a B | ([^ab] A | 0) -> a*([^ab] A | 0) A -> [^a] A | a a*([^ab] A | 0) | 0 -> [^a] A | a a*[^ab] A | aa* | 0 -> ([^a]|aa*[^ab]) A | a* -> ([^a]|aa*[^ab])*a*
== abc
A -> [^a] A | a B | 0 B -> [^ab] A | a B | b C | 0 C -> [^ac] A | a B | 0
B -> [^ab] A | a B | b ([^ac] A | a B | 0) | 0 -> [^ab] A | a B | b [^ac] A | b a B | b | 0 -> (a | ba) B | ([^ab] | b [^ac]) A | b?
B -> (a|ba)*(([^ab] | b [^ac]) A | b | 0) -> (a|ba)*([^ab]|b[^ac]) A | (a|ba)*b?
A -> [^a] A | a ((a|ba)*([^ab]|b[^ac]) A | (a|ba)*b?) | 0 -> [^a] A | a(a|ba)*([^ab]|b[^ac]) A | a(a|ba)*b? | 0 -> ([^a]|a(a|ba)*([^ab]|b[^ac])) A | a(a|ba)*b? | 0
A -> ([^a]|a(a|ba)*([^ab]|b[^ac]))* (a(a|ba)*b? | 0) -> ([^a]|a(a|ba)*([^ab]|b[^ac]))*(a(a|ba)*b?)?
== abcd
A -> [^a] A | a B | 0 B -> [^ab] A | a B | b C | 0 C -> [^ac] A | a B | c D | 0 D -> [^ad] A | a B | 0
C -> [^ac] A | a B | c ([^ad] A | a B | 0) | 0 -> [^ac] A | a B | c[^ad] A | ca B | c | 0 -> ([^ac]|c[^ad]) A | (a|ca) B | c | 0
B -> [^ab] A | a B | b (([^ac]|c[^ad]) A | (a|ca) B | c | 0) | 0 -> [^ab] A | a B | b([^ac]|c[^ad]) A | b(a|ca) B | bc | b | 0 -> (a|b(a|ca)) B | ([^ab]|b([^ac]|c[^ad])) A | bc | b | 0 -> (a|b(a|ca))*(([^ab]|b([^ac]|c[^ad])) A | (bc|b)?) -> (a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | (a|b(a|ca))*(bc|b)?
A -> [^a] A | a ((a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | (a|b(a|ca))*(bc|b)?) | 0 -> [^a] A | a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | a(a|b(a|ca))*(bc|b)? | 0 -> ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad]))) A | (a(a|b(a|ca))*(bc|b)?)? -> ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])))*(a(a|b(a|ca))*(bc|b)?)?
Et un petit résumé (si je ne me suis pas trompé)
a [^a]* ab ([^a]|aa*[^ab])*a* abc ([^a]|a(a|ba)*([^ab]|b[^ac]))*(a(a|ba)*b?)? abcd ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])))*(a(a|b(a|ca))*(bc|b)?)?
Je ne vais pas jusqu'à "Microsoft" :-)
Est-ce qu'il y a des expressions plus simples que celles optenues par cet algo pour le même résultat?
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Bon... retour à la case 0. Copie et suivi sur le groupe d'algo,
vraisemblablement mieux adapté.
Problème: bâtir une expression rationnelle qui accepte n'importe quoi sauf
une chaîne donnée. L'automate et la grammaire sont faciles à écrire, mais
l'expression...
Retour chez Aho et Ullman (The theory of parsing, translation and
compiling), le seul bouquin que j'ai qui donne un algo pour passer d'une
grammaire à une expression.
Exemples sur les chaînes a, ab, abc et abcd. Je note 0 la chaîne vide.
Premièrement, si on a
X -> e X | b
ça veut dire que
X -> e*|b
(voir la démonstration dans le bouquin)
== a
A -> [^a] A | 0
-> [^a]* 0
-> [^a]*
== ab
A -> [^a] A | a B | 0
B -> [^ab] A | a B | 0
-> a B | ([^ab] A | 0)
-> a*([^ab] A | 0)
A -> [^a] A | a a*([^ab] A | 0) | 0
-> [^a] A | a a*[^ab] A | aa* | 0
-> ([^a]|aa*[^ab]) A | a*
-> ([^a]|aa*[^ab])*a*
== abc
A -> [^a] A | a B | 0
B -> [^ab] A | a B | b C | 0
C -> [^ac] A | a B | 0
B -> [^ab] A | a B | b ([^ac] A | a B | 0) | 0
-> [^ab] A | a B | b [^ac] A | b a B | b | 0
-> (a | ba) B | ([^ab] | b [^ac]) A | b?
B -> (a|ba)*(([^ab] | b [^ac]) A | b | 0)
-> (a|ba)*([^ab]|b[^ac]) A | (a|ba)*b?
A -> [^a] A | a ((a|ba)*([^ab]|b[^ac]) A | (a|ba)*b?) | 0
-> [^a] A | a(a|ba)*([^ab]|b[^ac]) A | a(a|ba)*b? | 0
-> ([^a]|a(a|ba)*([^ab]|b[^ac])) A | a(a|ba)*b? | 0
A -> ([^a]|a(a|ba)*([^ab]|b[^ac]))* (a(a|ba)*b? | 0)
-> ([^a]|a(a|ba)*([^ab]|b[^ac]))*(a(a|ba)*b?)?
== abcd
A -> [^a] A | a B | 0
B -> [^ab] A | a B | b C | 0
C -> [^ac] A | a B | c D | 0
D -> [^ad] A | a B | 0
C -> [^ac] A | a B | c ([^ad] A | a B | 0) | 0
-> [^ac] A | a B | c[^ad] A | ca B | c | 0
-> ([^ac]|c[^ad]) A | (a|ca) B | c | 0
B -> [^ab] A | a B | b (([^ac]|c[^ad]) A | (a|ca) B | c | 0) | 0
-> [^ab] A | a B | b([^ac]|c[^ad]) A | b(a|ca) B | bc | b | 0
-> (a|b(a|ca)) B | ([^ab]|b([^ac]|c[^ad])) A | bc | b | 0
-> (a|b(a|ca))*(([^ab]|b([^ac]|c[^ad])) A | (bc|b)?)
-> (a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | (a|b(a|ca))*(bc|b)?
A -> [^a] A | a ((a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | (a|b(a|ca))*(bc|b)?) | 0
-> [^a] A | a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | a(a|b(a|ca))*(bc|b)? | 0
-> ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad]))) A | (a(a|b(a|ca))*(bc|b)?)?
-> ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])))*(a(a|b(a|ca))*(bc|b)?)?
Et un petit résumé (si je ne me suis pas trompé)
a [^a]*
ab ([^a]|aa*[^ab])*a*
abc ([^a]|a(a|ba)*([^ab]|b[^ac]))*(a(a|ba)*b?)?
abcd ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])))*(a(a|b(a|ca))*(bc|b)?)?
Je ne vais pas jusqu'à "Microsoft" :-)
Est-ce qu'il y a des expressions plus simples que celles optenues par cet
algo pour le même résultat?
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Bon... retour à la case 0. Copie et suivi sur le groupe d'algo, vraisemblablement mieux adapté.
Problème: bâtir une expression rationnelle qui accepte n'importe quoi sauf une chaîne donnée. L'automate et la grammaire sont faciles à écrire, mais l'expression...
Retour chez Aho et Ullman (The theory of parsing, translation and compiling), le seul bouquin que j'ai qui donne un algo pour passer d'une grammaire à une expression.
Exemples sur les chaînes a, ab, abc et abcd. Je note 0 la chaîne vide.
Premièrement, si on a X -> e X | b ça veut dire que X -> e*|b (voir la démonstration dans le bouquin)
== a
A -> [^a] A | 0 -> [^a]* 0 -> [^a]*
== ab
A -> [^a] A | a B | 0 B -> [^ab] A | a B | 0 -> a B | ([^ab] A | 0) -> a*([^ab] A | 0) A -> [^a] A | a a*([^ab] A | 0) | 0 -> [^a] A | a a*[^ab] A | aa* | 0 -> ([^a]|aa*[^ab]) A | a* -> ([^a]|aa*[^ab])*a*
== abc
A -> [^a] A | a B | 0 B -> [^ab] A | a B | b C | 0 C -> [^ac] A | a B | 0
B -> [^ab] A | a B | b ([^ac] A | a B | 0) | 0 -> [^ab] A | a B | b [^ac] A | b a B | b | 0 -> (a | ba) B | ([^ab] | b [^ac]) A | b?
B -> (a|ba)*(([^ab] | b [^ac]) A | b | 0) -> (a|ba)*([^ab]|b[^ac]) A | (a|ba)*b?
A -> [^a] A | a ((a|ba)*([^ab]|b[^ac]) A | (a|ba)*b?) | 0 -> [^a] A | a(a|ba)*([^ab]|b[^ac]) A | a(a|ba)*b? | 0 -> ([^a]|a(a|ba)*([^ab]|b[^ac])) A | a(a|ba)*b? | 0
A -> ([^a]|a(a|ba)*([^ab]|b[^ac]))* (a(a|ba)*b? | 0) -> ([^a]|a(a|ba)*([^ab]|b[^ac]))*(a(a|ba)*b?)?
== abcd
A -> [^a] A | a B | 0 B -> [^ab] A | a B | b C | 0 C -> [^ac] A | a B | c D | 0 D -> [^ad] A | a B | 0
C -> [^ac] A | a B | c ([^ad] A | a B | 0) | 0 -> [^ac] A | a B | c[^ad] A | ca B | c | 0 -> ([^ac]|c[^ad]) A | (a|ca) B | c | 0
B -> [^ab] A | a B | b (([^ac]|c[^ad]) A | (a|ca) B | c | 0) | 0 -> [^ab] A | a B | b([^ac]|c[^ad]) A | b(a|ca) B | bc | b | 0 -> (a|b(a|ca)) B | ([^ab]|b([^ac]|c[^ad])) A | bc | b | 0 -> (a|b(a|ca))*(([^ab]|b([^ac]|c[^ad])) A | (bc|b)?) -> (a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | (a|b(a|ca))*(bc|b)?
A -> [^a] A | a ((a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | (a|b(a|ca))*(bc|b)?) | 0 -> [^a] A | a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])) A | a(a|b(a|ca))*(bc|b)? | 0 -> ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad]))) A | (a(a|b(a|ca))*(bc|b)?)? -> ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])))*(a(a|b(a|ca))*(bc|b)?)?
Et un petit résumé (si je ne me suis pas trompé)
a [^a]* ab ([^a]|aa*[^ab])*a* abc ([^a]|a(a|ba)*([^ab]|b[^ac]))*(a(a|ba)*b?)? abcd ([^a]|a(a|b(a|ca))*([^ab]|b([^ac]|c[^ad])))*(a(a|b(a|ca))*(bc|b)?)?
Je ne vais pas jusqu'à "Microsoft" :-)
Est-ce qu'il y a des expressions plus simples que celles optenues par cet algo pour le même résultat?
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
