Regex AlphaNumeric simple (espaciado simple) sin retrotracción catastrófica

Tengo la siguiente expresión REGEX (que funciona) para permitir Alpha-Numeric (así como ' y - ) y sin espacio doble:

  ^([a-zA-Z0-9'-]+\s?)*$ 

Debido a la agrupación anidada, esto permite que ocurra un retroceso catastrófico, lo que es malo.

¿Cómo puedo simplificar esta expresión para evitar el retroceso catastrófico? (Idealmente, esto no permitiría espacio en blanco en los primeros y últimos caracteres)

Explicación

El grupo nested no causa automáticamente retrocesos catastróficos. En su caso, es porque su expresión regular degenera al ejemplo clásico de retroceso catastrófico (a*)* .

Dado que \s en opcional en ^([a-zA-Z0-9'-]+\s?)*$ , En la entrada sin espacios pero tiene caracteres fuera de la lista permitida, la expresión regular simplemente degenera en ^([a-zA-Z0-9'-]+)*$ .

También puedes pensar en términos de expansión de la expresión regular original:

 [a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?... 

Como \s es opcional, podemos eliminarlo:

 [a-zA-Z0-9'-]+[a-zA-Z0-9'-]+[a-zA-Z0-9'-]+[a-zA-Z0-9'-]+... 

Y tenemos una serie de [a-zA-Z0-9'-]+ consecutivos, que intentarán todas las maneras de distribuir los personajes entre ellos y explotar la complejidad.

Solución

La forma estándar de escribir una expresión regular para hacer coincidir token delimiter token ... delimiter token es token (delimiter token)* . Si bien es posible reescribir la expresión regular para evitar la repetición de token , recomendaría no hacerlo, ya que es más difícil hacerlo bien. Para evitar la repetición, es posible que desee construir la expresión regular por cadena de concatenación en su lugar.

Siguiendo la receta de arriba:

 ^[a-zA-Z0-9'-]+(\s[a-zA-Z0-9'-]+)*$ 

Aunque puede ver repetición en repetición aquí, no hay retroceso catastrófico, ya que la expresión regular solo puede expandirse a:

 [a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+... 

Y \s y [a-zA-Z0-9'-] son exclusivos mutuos: solo hay una forma de hacer coincidir cualquier cadena.