¿Cómo simular referencias traseras, lookaheads y lookbehinds en autómatas de estado finito?

Creé un simple lexer y analizador de expresiones regulares para tomar una expresión regular y generar su árbol de análisis. Crear un autómata de estado finito no determinista a partir de este árbol de análisis es relativamente simple para las expresiones regulares básicas. Sin embargo, parece que no puedo entender cómo simular referencias traseras, mirar hacia atrás y mirar hacia atrás.

Por lo que leí en el libro del dragón púrpura, entendí que para simular una anticipada donde la expresión regular coincide si y solo si la coincidencia es seguida por una coincidencia de la expresión regular , se crea un finito no determinista autómata de estado en el que es reemplazado por . ¿Es posible crear un autómata determinista de estado finito que haga lo mismo?$r/s$$r$$s$$/$$\varepsilon$

¿Qué pasa con la simulación de lookaheads negativos y lookbehinds? Realmente agradecería que me vincule a un recurso que describe cómo hacer esto en detalle.

En primer lugar, las autoreferencias no pueden simularse mediante autómatas finitos, ya que le permiten describir lenguajes no regulares. Por ejemplo, ([ab]^*)\1coincide con , que ni siquiera está libre de contexto.$\{ww \mid w \in \{a,b\}^*\}$

Mirar hacia adelante y mirar hacia atrás no son nada especial en el mundo de los autómatas finitos, ya que aquí solo combinamos entradas enteras . Por lo tanto, la semántica especial de "solo verificar pero no consumir" no tiene sentido; simplemente concatena y / o interseca las expresiones de comprobación y consumo y usa los autómatas resultantes. La idea es verificar las expresiones de mirar hacia adelante o atrás mientras "consume" la entrada y almacena el resultado en un estado.

Al implementar expresiones regulares, desea ejecutar la entrada a través de un autómata y recuperar los índices de inicio y finalización de las coincidencias. Esa es una tarea muy diferente, por lo que no hay realmente una construcción para autómatas finitos. Usted construye su autómata como si la expresión de mirar hacia adelante o hacia atrás consumiera, y cambia su índice almacenando resp. informar en consecuencia.

Tomemos, por ejemplo, miradas atrás. Podemos imitar la semántica regexp ejecutando la verificación regexp simultáneamente con la expresión regular "match-all" implícitamente consumidora. solo desde los estados donde el autómata de la expresión de mirar hacia atrás está en un estado final, se puede ingresar el autómata de la expresión protegida. Por ejemplo, la expresión regular /(?=c)[ab]+/(suponiendo que es el alfabeto completo) - tenga en cuenta que se traduce en la expresión regular { a , b , c } ∗ c { a , b } + { a , b , c $\{a,b,c\}$ - podría coincidir con$\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$

^{[ fuente ]}

y tendrías que

• almacenar el índice actual como cada vez que ingrese q 2 (inicialmente o desde q 2 ) y$i$$q_2$$q_2$
• informe una coincidencia (máxima) de al índice actual ( - 1 ) cada vez que presione (salga) q 2 .$i$$-1$$q_2$

Observe cómo la parte izquierda del autómata es el autómata paralelo del autómata canónico para [abc]*y c(iterado), respectivamente.

$i$$j$$i$$j$

Tenga en cuenta que el no determinismo es inherente a esto: el autómata main y look-ahead /-behind puede superponerse, por lo que debe almacenar todas las transiciones entre ellas para informar las coincidencias más adelante, o retroceder.

La referencia autorizada sobre los problemas pragmáticos detrás de la implementación de motores regex es una serie de tres publicaciones de blog de Russ Cox . Como se describe allí, ya que hacen referencias hacia atrás su idioma no regular, que se implementan utilizando vuelta hacia atrás .

Lookaheads y lookbehinds, como muchas características de los motores de coincidencia de patrones regex, no encajan en el paradigma de decidir si una cadena es miembro de un lenguaje o no. En lugar de expresiones regulares, generalmente estamos buscando subcadenas dentro de una cadena más grande. Las "coincidencias" son subcadenas que son miembros del lenguaje, y el valor de retorno son los puntos inicial y final de la subcadena dentro de la cadena más grande.

El punto de mira hacia atrás y hacia atrás no es tanto para introducir la capacidad de hacer coincidir idiomas no regulares, sino más bien para ajustar dónde el motor informa los puntos de inicio y finalización de la subcadena coincidente.

Confío en la descripción en http://www.regular-expressions.info/lookaround.html . Los motores regex que admiten esta función (Perl, TCL, Python, Ruby, ...) parecen estar basados ​​en el retroceso (es decir, admiten un conjunto de idiomas mucho más grande que solo los idiomas normales). Parecen estar implementando esta característica como una extensión relativamente "simple" de retroceso, en lugar de tratar de construir autómatas finitos reales para realizar la tarea.

Lookahead positivo

La sintaxis para la búsqueda anticipada positiva es (?=regex) . Entonces, por ejemplo q(?=u), qsolo coincide si es seguido por u, pero no coincide con u. Me imagino que implementan esto con una variación en el retroceso. Cree un FSM para la expresión antes de la búsqueda anticipada positiva. Cuando eso coincida, recuerde dónde terminó y comience un nuevo FSM que represente la expresión dentro de la búsqueda anticipada positiva. Si eso coincide, entonces tiene una "coincidencia", pero la coincidencia "termina" justo antes de la posición donde comenzó la coincidencia positiva anticipada.

La única parte de esto que sería difícil sin retroceder es que debe recordar el punto en la entrada donde comienza la búsqueda anticipada y mover la cinta de entrada a esta posición después de que haya terminado con la coincidencia.

Lookahead negativo

La sintaxis para el lookahead negativo es (?!regex) . Entonces, por ejemplo, q(?!u)coincide qsolo si no es seguido por u. Esto podría ser qseguido por algún otro personaje o qal final de la cadena. Me imagino que esto se implementa creando un NFA para la expresión de búsqueda anticipada, y luego tiene éxito solo si el NFA no coincide con la cadena posterior.

Si desea hacerlo sin depender de retroceder, podría negar el NFA de la expresión anticipada, luego trátelo de la misma manera que trata la anticipación positiva.

Mirada hacia atrás positiva

(?<=)(?=q)uuqq$n$$n$$n$

Es posible que pueda implementar esto sin retroceder tomando la intersección de "cadena que termina con regex " con cualquier parte de la expresión regular que viene antes del operador retrospectivo. Sin embargo, esto va a ser complicado, porque la expresión regex de retrospectiva puede necesitar mirar más atrás que el comienzo actual de la entrada.

Mirada hacia atrás negativa

La sintaxis para la mirada hacia atrás negativa es (?<!regex) . Entonces, por ejemplo, (?<!q)ucoincide u, pero solo si no está precedido por q. Por lo tanto, coincidiría con el uin umbrellay el uin doubt, pero no con el uin quick. Nuevamente, esto parece hacerse calculando la longitud de la expresión regular , haciendo una copia de seguridad de esa cantidad de caracteres, probando la coincidencia con la expresión regular , pero ahora fallando toda la coincidencia si el aspecto posterior coincide.

Es posible que pueda implementar esto sin retroceder tomando la negación de la expresión regular y luego haciendo lo mismo que haría para una mirada positiva hacia atrás.

Al menos para referencias posteriores, esto no es posible. Por ejemplo, la expresión regular (.*)\1representa un lenguaje que no es regular. Lo que eso significa es que es imposible crear un autómata finito (determinista o no) que reconozca este lenguaje. Si quiere probar esto formalmente, puede usar el lema de bombeo .

He estado investigando esto yo mismo, y deberías poder implementar con anticipación usando un Autómata finito alterno . Cuando se encuentra con anticipación, ejecuta de forma no determinista tanto la anticipación como el resto de la expresión, aceptando solo si ambas rutas aceptan. Puede convertir un AFA en un NFA con una ampliación razonable (y, por lo tanto, en un DFA), aunque no he verificado que la construcción obvia funcione bien con los grupos de captura.

La mirada atrás de ancho fijo debería ser perfectamente posible sin retroceder. Deje n ser el ancho. Comenzando desde el punto en su NFA donde comenzó la retrospectiva, dividiría los estados mirando hacia atrás para que cada camino hacia la retrospectiva terminara con n caracteres de estados que solo entraban en la retrospectiva. Luego, agregue anticipación al comienzo de esos estados (e inmediatamente compile el subgráfico de AFA a NFA si lo desea).

Las referencias posteriores, como otros han mencionado, no son regulares, por lo que no pueden ser implementadas por un autómata finito. De hecho, son NP completos. En la implementación en la que estoy trabajando, la coincidencia rápida de sí / no es primordial, por lo que decidí no implementar referencias posteriores.