DFA y NFA

 Las expresiones regulares brotaron en el estudio neurofisiológico de la década de 1940, primero descrito formalmente por el famoso matemático Stephen Kleene. Específicamente, Kleene resumió los estudios neurofisiológicos mencionados anteriormente, definió un "conjunto regular" en un documento titulado "Álgebra regular de conjuntos", definió un sistema algebraico e introdujo un El sistema de token se usa para describir el conjunto regular, que se denomina "expresión regular" por quo. Después de estudiarse en el círculo de las matemáticas teóricas durante décadas, en 1968, Ken Thompson, quien más tarde inventó el sistema UNIX, primero utilizó expresiones regulares en el campo de las computadoras, y desarrolló dos herramientas prácticas de procesamiento de texto, qed y grep. Gran exito En la próxima década, aproximadamente, un gran número de científicos informáticos y hackers líderes realizaron una investigación y práctica intensivas sobre expresiones regulares. A principios de la década de 1980, los dos centros del Movimiento UNIX, Bell Labs y la Universidad de California, Berkeley, estudiaron e implementaron el motor de expresión regular alrededor de la herramienta grep. Al mismo tiempo, el compilador "Alfred Aho", autor del libro "Dragon Book", desarrolló la herramienta Egrep, que expandió y mejoró enormemente la funcionalidad de las expresiones regulares. Desde entonces, ha inventado el popular lenguaje de edición de texto awk con otros tres, Brian Kernighan, autor de C Programming Language. En 1986, las expresiones regulares habían dado paso a un salto. Primero, el principal pirata informático del lenguaje C, Henry Spencer, lanzó una biblioteca de expresiones regulares escrita en lenguaje C (no llamada código abierto en ese momento) en el código fuente, llevando así el misterio de las expresiones regulares a los hogares de las personas comunes, y luego la culpa técnica. Jay Larry Wall nació y lanzó la primera versión del lenguaje Perl. Desde entonces, Perl ha sido el abanderado de las expresiones regulares. Se puede decir que el estándar y el estado de las expresiones regulares de hoy están conformados por Perl. Después del lanzamiento de Perl 5.x, las expresiones regulares entraron en un período de madurez estable, y sus poderosas capacidades han conquistado casi todas las plataformas de lenguaje principales, convirtiéndose en la herramienta básica que todo desarrollador profesional debe dominar.

2.DFA y NFA
Recomendaciones Los motores de expresión regular de DFA y NFA se clasifican en dos categorías, una llamada DFA (autómata finito determinista) y la otra NFA (no determinista) Máquina autonómica sexual). Para funcionar sin problemas, ambos tipos de motores deben tener una expresión regular y una cadena de texto, una en la mano y otra para comer. DFA pinza la cadena de texto para comparar la expresión regular. Cuando ve una expresión sub-regular, marca todas las cadenas coincidentes posibles, luego mira la siguiente parte de la expresión regular y actualiza la etiqueta en función del nuevo resultado coincidente. La NFA mantiene el estilo normal para comparar el texto, comer un personaje, compararlo con el estilo normal, y la coincidencia se anota: "¡Un determinado día del mes coincide en algún lugar!" ", luego baja. Una vez que no haya coincidencia, escupe el personaje que acabas de comer, escupe uno por uno hasta que regreses a la última coincidencia. La diferencia entre el mecanismo de DFA y NFA trae cinco efectos: 1. DFA solo necesita escanear cada carácter en la cadena de texto una vez, pero tiene menos características; NFA tiene que voltear y comer caracteres y escupir caracteres, pero la velocidad es lenta, pero Rico en funciones, por lo que es ampliamente utilizado. Los principales motores de expresiones regulares de la actualidad, como Perl, Ruby, el módulo de re de Python, las bibliotecas de expresiones regulares de Java y .NET, son todos NFA. 2. Solo NFA admite funciones como lazy y backreference; 3. NFA está ansioso por invitar, por lo que el estilo regular infantil más a la izquierda coincide primero, por lo que ocasionalmente se pierde el mejor resultado de coincidencia; DFA es "la expresión regular infantil más larga del lado izquierdo" Prioridad en el éxito del partido y ". 4. La NFA utiliza de manera predeterminada el cuantificador codicioso (ver elemento 4); 5. La NFA puede caer en la trampa de las llamadas recursivas y comportarse de manera muy deficiente. Daré un ejemplo aquí para ilustrar el tercer impacto. Por ejemplo, usando expresiones regulares /perl