Regex pour correspondre à une chaîne qui ne contient pas « xxx »

Question

une de mes questions aux devoirs a demandé de développer une expression rationnelle pour toutes les chaînes sur x,y,z qui ne contenait pas xxx

Après avoir fait un peu de lecture que j'ai découvert préanalyse négatif et ce qui fit fonctionne très bien:

(x(?!xx)|y|z)*

Pourtant, dans l'esprit d'exhaustivité, est de toute façon d'écrire cela sans négatif préanalyse? La lecture que j'ai faite me fait penser qu'il peut être fait avec une certaine combinaison de carets(^), mais je ne peux pas obtenir la bonne combinaison donc je ne suis pas sûr.

Prenant un peu plus loin, est-il possible d'exclure une chaîne comme xxx en utilisant uniquement l'opérateur or(|), mais toujours vérifier les cordes d'une manière récursive?

EDIT 9/6/2010:

pense avoir répondu à ma propre question. Je me suis trompé un peu plus, essayant de faire cette regex avec seulement or(|) des déclarations et je suis assez sûr que je l'ai compris ... et ce n'est pas aussi désordonné que je pensais que ce serait. Si quelqu'un d'autre a le temps de vérifier cela avec un oeil humain, je l'apprécierais.

(xxy|xxz|xy|xz|y|z)*(xxy|xxz|xx|xy|xz|x|y|z)

Answer 1

Essayez ceci:

^(x{0,2}(y|z|$))*$ 

L'idée de base est la suivante: pour match au plus 2 X de, suivie d'une autre lettre ou à la fin de la chaîne.

Lorsque vous atteignez un point où vous avez 3 X, la regex n'a pas de règle qui lui permet de continuer à correspondre, et elle échoue.

Exemple de travail: http://rubular.com/r/ePH0fHlZxL

Une manière moins compacte d'écrire la même chose est (avec des espaces libres, généralement le drapeau /x):

^(
y|   # y is ok 
z|   # so is z 
x(y|z|$)| # a single x, not followed by x 
xx(y|z|$) # 2 x's, not followed by x 
)*$ 

Basé sur la dernière édition, voici une version toujours plus plat du motif: je ne suis pas entièrement sûr de comprendre votre fascination pour le tuyau, mais vous pouvez éliminer plus d'options - en permettant un match vide sur le second groupe, vous n'avez pas besoin de répéter les permutations du premier groupe. Cette regex permet également ε, qui je pense est inclus dans votre langue.

^(xxy|xxz|xy|xz|y|z)*(xx|x|)$ 

Answer 2

Je sais que vous ne voulez pas utiliser préanalyse, mais voici une autre façon de résoudre ce:

^(?:(?!xxx)[xyz])*$ 

correspondra à une ligne de caractères x, y ou z tant qu'il n » t contiennent la chaîne xxx.

Answer 3

Fondamentalement, vous avez déjà la bonne réponse - bien fait vous.Carat (^) dans un ensemble [^abc] ne correspondra que s'il ne trouve pas de caractère dans cet ensemble, donc son application pour les ordres de caractères correspondants (c'est-à-dire les chaînes) est limitée et faible.

Regex a quantificateurs numériques {n} et {a,b} qui vous permettent de faire correspondre un nombre défini de repititions d'un motif, qui travaillerait pour ce modèle spécifique (parce qu'il est « x » répété), mais il est pas particulièrement expressive du problème que vous » réessayer de résoudre (même pour regex!) et est un peu fragile (il ne serait pas approprié pour le match négatif 'xyx' par exemple.)

Un ou modèle serait à nouveau verbeux et plutôt inexpressif mais cela pourrait être fait comme le fragment:

(x|xx)[^x] // x OR xx followed by NOT x 

Évidemment, vous pouvez le faire wi un algorithme itératif mais très inefficace par rapport à une regex.

Bien fait pour penser au-delà de la solution.