Comportamiento del motor de búsqueda de coincidencias
El motor de búsqueda de expresiones regulares de .NET Framework es un buscador de coincidencias de expresiones regulares con retroceso que incorpora un motor de búsqueda NFA (autómata finito no determinista) tradicional, como el que utiliza Perl, Python, Emacs y Tcl. Esto lo distingue de los motores de búsqueda DFA (autómatas finitos deterministas) de expresiones regulares puras, que son más rápidos, pero también más limitados, como los de awk, egrep o lex. Esto también lo distingue de los NFA POSIX estandarizados, que son más lentos.
Tres tipos de motores de búsqueda de expresiones regulares
En esta sección encontrará información general sobre las ventajas y los inconvenientes de los tres tipos de motores de búsqueda y una explicación del motivo por el cual el motor de .NET Framework implementa un buscador de coincidencias NFA tradicional.
Los motores de búsqueda DFA se ejecutan en tiempo lineal porque no requieren retroceso (y, por lo tanto, nunca comprueban el mismo carácter dos veces). Estos motores de búsqueda garantizan también la búsqueda de la cadena coincidente más larga posible. Sin embargo, dado que los motores de búsqueda DFA sólo contienen estados finitos, no pueden buscar las coincidencias de un patrón con referencias inversas, y puesto que no crean una expansión explícita, no pueden capturar subexpresiones.
Los motores de búsqueda NFA tradicionales ejecutan los denominados algoritmos "avariciosos" de coincidencia con retroceso, que comprueban todas las expansiones posibles de una expresión regular en un orden específico y aceptan la primera coincidencia. Como los motores de búsqueda NFA tradicionales crean una expansión específica de la expresión regular para lograr encontrar una coincidencia, son capaces de capturar subexpresiones y referencias inversas coincidentes. No obstante, como los motores de búsqueda NFA tradicionales tienen capacidad de retroceso, pueden visitar exactamente el mismo estado varias veces, si a dicho estado se llega por distintos caminos. Por consiguiente, pueden presentar un funcionamiento exponencialmente más lento, en el peor de los casos. Dado que los motores de búsqueda NFA tradicionales aceptan la primera coincidencia que encuentran, es posible que no encuentren otras coincidencias (probablemente más largas).
Los motores de búsqueda NFA POSIX son como los motores de búsqueda NFA tradicionales, con la excepción de que continúan el retroceso hasta que son capaces de garantizar que han encontrado la cadena coincidente más larga posible. Por tanto, un motor de búsqueda NFA POSIX es más lento que un motor de búsqueda NFA tradicional, y no permite dar prioridad a un cadena coincidente más corta frente a una más larga cambiando el orden de la búsqueda hacia atrás.
Los motores de búsqueda NFA tradicionales son muy populares entre los programadores porque ofrecen más información que los motores de búsqueda DFA o NFA POSIX. Aunque en el peor de los casos se pueden ejecutar con lentitud, se les puede dirigir para que busquen coincidencias en tiempo lineal o polinómico mediante patrones que reduzcan las ambigüedades y que limiten el retroceso.
Funciones del motor de .NET Framework
Además de incorporar las ventajas del motor de búsqueda NFA tradicional, el motor de búsqueda de expresiones regulares de .NET Framework incluye un conjunto completo de construcciones que permite a los programadores dirigir el motor de retroceso. Estas construcciones sirven para buscar cadenas coincidentes con mayor rapidez o para favorecer determinadas expansiones frente a otras.
Entre otras características incluye las siguientes funciones:
Cuantificadores "perezosos": ??, *?, +?, {n,m}?. Indican al motor de retroceso cómo buscar primero el número mínimo de repeticiones. A diferencia de los cuantificadores avariciosos normales, que intentan buscar primero el número máximo de repeticiones.
Búsqueda anticipada positiva. Permite que el motor de retroceso vuelva a la misma posición de texto después de encontrar una subexpresión coincidente. Sirve para buscar a lo largo del texto comprobando varios patrones a partir de la misma posición.
Búsqueda anticipada negativa. Esta característica permite buscar una expresión coincidente únicamente si no se encuentra ninguna subexpresión que coincida. Es especialmente eficaz a la hora de restringir una búsqueda, ya que normalmente las expresiones por eliminación son mucho más sencillas que las expresiones por inclusión. Por ejemplo, es difícil escribir una expresión para aquellas palabras que no empiezan con "in".
Evaluación condicional. Esta característica permite al motor realizar la búsqueda utilizando varios patrones alternativos, en función del resultado de la subexpresión coincidente anterior. Esto confiere mayor eficacia a la operación de referencia inversa, ya que permite, por ejemplo, buscar un paréntesis de cierre coincidente si se ha capturado previamente uno de apertura en una subexpresión.
Subexpresiones sin retroceso (denominadas también subexpresiones avariciosas). Permiten que el motor de retroceso se asegure de que una subexpresión coincida sólo con la primera coincidencia encontrada para esa subexpresión, como si la expresión se ejecutara independientemente de la expresión que la contiene. Sin esta construcción, las búsquedas con retroceso de expresiones de gran tamaño podrían cambiar el comportamiento de una subexpresión.
Búsqueda de coincidencias de derecha a izquierda. Es útil para buscar de derecha a izquierda en lugar de izquierda a derecha, o en los casos en los que es más eficaz iniciar una búsqueda de coincidencias en la parte derecha del patrón en lugar de en la parte izquierda.
Búsqueda tardía positiva y negativa. Es similar a la búsqueda anticipada. Dado que el motor de búsqueda de expresiones regulares permite realizar búsquedas de coincidencias completas de derecha a izquierda, las expresiones regulares permiten realizar búsquedas tardías no restringidas.