#505 Nope, el parser de string a "nodos" lo hice bastante a mano, me quedó parecido al código que autogenera ANTLR. Montar el autómata una vez has representado bien la frase no es del todo complicado, por ejemplo (aab)*|(bc)+ se consigue:
- Construyendo un DFA para aab, que es bastante fácil, vacío -> a -> aa -> aab (aceptar) y rechazar cualquier otra transicion, lo llamas A
- A* se consigue haciendo que el estado inicial de A acepte y añadiendo transiciones extra, las transiciones extras las puedes sacar con una prefix table, en este caso se consigue añadiendo una transición del estado final a la primera a
- Construyendo un DFA para bc, lo llamas B
- B+ se construye como B* pero sin aceptar el estado vacío
- A|B se consigue creando un nuevo estado inicial y poniendo dos transiciones vacías, una hacia A y otra hacia B
En este punto tienes un autómata no determinista, hay un algoritmo para determinizarlo. Algunos motores no determinizan los ors y corren ambas ramas en paralelo, otros no... aquí ya es ponerse con lo que te apetezca.
Otras operaciones como negar un DFA A se conseguían cambiando los estados de aceptador a no aceptador y viceversa, etc
O sea, los pasos eran representar la regex en forma arbórea por decirlo de alguna forma, montar autómatas para las hojas e ir uniéndolas de abajo a arriba.
Lo hice cuando hice teoría de la computación en la carrera, el profe que teníamos era muy bueno y te enganchaba a hacer estas mierdas si te dejabas.