"Jean-Marc Bourguet" <jm***bourguet.org> a écrit dans le message de news:
87ej57wzff.fsf***news.bourguet.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+
il est possible d'utiliser une notation de type "shortest match/au plus
court", c'est à dire, un noeud d'acceptation comme le noeud symbolique "$"
souvent utilisé en fin d'expression régulière, notons le #. Un noeud de ce
genre rend l'état qui le contient "accepteur', toute transition vers cet
état provoque l'acceptation de l'expression. Un expression acceptant tout
jusqu'à qqch devient donc : .*texte#. Une expression régulière acceptant
tout sauf cette chaîne est donc cette même expression régulière... mais on
considère tout état d'erreur comme état de succès (sur la fin de texte).

Armel