regular - regex perl online

Cómo funciona un motor RegEx

Question

Al aprender Expresiones regulares, me preguntaba cómo funciona el motor subyacente. Probablemente más específicamente, me gustaría saber más sobre cómo evalúa, prioriza y analiza la expresión. Siento que el motor RegEx es una caja negra para mí, y realmente me encantaría descifrarlo.

Así que me gustaría preguntar si hay algunos recursos excelentes que podría leer sobre la teoría del motor RegEx.

* Nota: No me interesa construir un motor, solo aprender su funcionamiento interno.

Answer 1

Hay dos clases principales de motores regex.

1. Los basados ​​en la automatización del estado finito . Estos son generalmente los más rápidos. Trabajan construyendo una máquina de estado y alimentándola con caracteres de la cadena de entrada. Es difícil, si no imposible, implementar algunas funciones más avanzadas en motores como este.

   Ejemplos de motores basados ​​en FSA:

   • Posix / GNU ERE / BRE: se utiliza en la mayoría de las utilidades de Unix, como grep, sed y awk.
   • Re2 : un proyecto relativamente nuevo para tratar de dar más poder al método basado en autómatas.
     

2. Los que se basan en el seguimiento . Estos a menudo compilan el patrón en un código de bytes, pareciéndose a las instrucciones de la máquina. El motor ejecuta el código, saltando de una instrucción a otra. Cuando una instrucción falla, luego retrocede para encontrar otra manera de hacer coincidir la entrada.

   Ejemplos de motores basados ​​en back-tracking:

   • Perl - El original. La mayoría de los otros motores de este tipo intentan replicar la funcionalidad de las expresiones regulares en el lenguaje Perl.
   • PCRE - La implementación más exitosa. Esta biblioteca es la implementación más utilizada. Tiene un amplio conjunto de características, algunas de las cuales ya no se pueden considerar como "Regular" .
   • Python , Ruby , Java , .NET - Otras implementaciones que no pretendo describir más adelante.

Para más información:

• regular-expressions.info - Tutorial
• regular-expressions.info - Comparación de sabores
• swtch.com/~rsc/regexp - Un buen conjunto de artículos sobre expresiones regulares efectivas, basadas en autómatas.

Si quieres que amplíe algo, publica un comentario.