Regular Expressions
Tipos de motores de expresiones regulares

NFA

Un motor NFA (automatización finita no determinista) es impulsado por el patrón .

Principio

El patrón regex se analiza en un árbol.

El puntero de posición actual se establece en el inicio de la cadena de entrada y se intenta una coincidencia en esta posición. Si la coincidencia es fais, la posición se incrementa al siguiente carácter en la cadena y se intenta otra coincidencia desde esta posición. Este proceso se repite hasta que se encuentra una coincidencia o se llega al final de la cadena de entrada.

Para cada intento de partido

El algoritmo funciona realizando un recorrido del árbol de patrones para una posición inicial dada. A medida que avanza a través del árbol, actualiza la posición de entrada actual al consumir caracteres coincidentes.

Si el algoritmo encuentra un nodo de árbol que no coincide con la cadena de entrada en la posición actual, tendrá que retroceder . Esto se realiza volviendo al nodo principal en el árbol, restableciendo la posición de entrada actual al valor que tenía al ingresar al nodo principal e intentando la siguiente rama alternativa.

Si el algoritmo logra salir del árbol, informa una coincidencia exitosa. De lo contrario, cuando se han probado todas las posibilidades, la coincidencia falla.

Optimizaciones

Los motores Regex suelen aplicar algunas optimizaciones para un mejor rendimiento. Por ejemplo, si determinan que una coincidencia debe comenzar con un carácter dado, intentarán una coincidencia solo en aquellas posiciones en la cadena de entrada donde aparece ese carácter.

Ejemplo

abeacab coincidir a(b|c)a con la cadena de entrada abeacab :

El árbol de patrones podría ser algo así como:

CONCATENATION
    EXACT: a
    ALTERNATION
        EXACT: b
        EXACT: c
    EXACT: a

El partido se procesa de la siguiente manera:

a(b|c)a      abeacab
^            ^

a se encuentra en la cadena de entrada, consúmala y continúe con el siguiente elemento del árbol de patrones: la alternancia. Prueba la primera posibilidad: una b exacta.

a(b|c)a      abeacab
  ^           ^

Se encuentra b , por lo que la alternancia tiene éxito, consúmala y continúe con el siguiente elemento en la concatenación: una exacta a :

a(b|c)a      abeacab
      ^        ^

a no se encuentra en la posición esperada. Retroceda a la alternancia, restablezca la posición de entrada al valor que tenía al ingresar la alternancia por primera vez y pruebe la segunda alternativa:

a(b|c)a      abeacab
    ^         ^

c no se encuentra en esta posición. Retroceder a la concatenación. No hay otras posibilidades para probar en este punto, por lo que no hay coincidencia al comienzo de la cadena.

Intente un segundo partido en la siguiente posición de entrada:

a(b|c)a      abeacab
^             ^

a no coincide allí. Intenta otro partido en la siguiente posición:

a(b|c)a      abeacab
^              ^

Tampoco hay suerte. Avanzar a la siguiente posición.

a(b|c)a      abeacab
^               ^

a coincide, así que consúmelo y entra en la alternancia:

a(b|c)a      abeacab
  ^              ^

b no coincide. Intenta la segunda alternativa:

a(b|c)a      abeacab
    ^            ^

c coincidencias, así que consuma y avance al siguiente elemento en la concatenación:

a(b|c)a      abeacab
      ^           ^

a coincidencia, y el final del árbol se ha alcanzado. Reportar una coincidencia exitosa:

a(b|c)a      abeacab
                \_/

DFA

Un motor DFA (Deterministic Finite Automaton) es impulsado por la entrada .

Principio

El algoritmo escanea a través de la cadena de entrada una vez , y recuerda todas las rutas posibles en la expresión regular que podrían coincidir. Por ejemplo, cuando se encuentra una alternancia en el patrón, se crean dos nuevas rutas y se intentan de forma independiente. Cuando una ruta dada no coincide, se elimina de las posibilidades establecidas.

Trascendencia

El tiempo coincidente está limitado por el tamaño de la cadena de entrada. No hay retroceso, y el motor puede encontrar varias coincidencias simultáneamente, incluso coincidencias superpuestas.

El principal inconveniente de este método es el reducido conjunto de características que puede soportar el motor, en comparación con el tipo de motor NFA.

Ejemplo

Empareja a(b|c)a contra abadaca :

abadaca      a(b|c)a
^            ^        Attempt 1      ==> CONTINUE

abadaca      a(b|c)a
 ^           ^        Attempt 2      ==> FAIL
               ^      Attempt 1.1    ==> CONTINUE
                 ^    Attempt 1.2    ==> FAIL

abadaca      a(b|c)a
  ^          ^        Attempt 3      ==> CONTINUE
                   ^  Attempt 1.1    ==> MATCH

abadaca      a(b|c)a
   ^         ^        Attempt 4      ==> FAIL
               ^      Attempt 3.1    ==> FAIL
                 ^    Attempt 3.2    ==> FAIL

abadaca      a(b|c)a
    ^        ^        Attempt 5      ==> CONTINUE

abadaca      a(b|c)a
     ^       ^        Attempt 6      ==> FAIL
               ^      Attempt 5.1    ==> FAIL
                 ^    Attempt 5.2    ==> CONTINUE

abadaca      a(b|c)a
      ^      ^        Attempt 7      ==> CONTINUE
                   ^  Attempt 5.2    ==> MATCH

abadaca      a(b|c)a
       ^       ^      Attempt 7.1    ==> FAIL
                 ^    Attempt 7.2    ==> FAIL