1. Inicio
  2. Pregunta y respuesta
  3. Cómo funciona un motor RegEx

Cómo funciona un motor RegEx

2010-09-01 14 views
27

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 blackbox para mí, y realmente me encantaría descifrarlo.Cómo funciona un motor RegEx

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

* Nota: No estoy interesado en construir un motor, solo aprendiendo el funcionamiento interno del mismo.

Fuente

2010-09-01 Robb

+1

Mastering Regular Expressions es un gran libro aunque no se centra en ese tema, tiene varios capítulos que tratan sobre cómo se comporta cada motor regex. (Aunque es más práctico que analizar los detalles del motor en sí) – NorthGuard

+0

Estuve hurgando en ese libro pero no sabía nada de esos capítulos. ¡Gracias! – Robb

+1

Un artile excelente es: [Cómo funciona RegEx] (http://perl.plover.com/Regex/article.html) – PHPst

Respuesta

32

Hay dos clases principales de motores de expresiones regulares.

  1. Los basados ​​en Autómatas de estados finitos. Estos son generalmente los más rápidos. Funcionan construyendo un state machine y alimentándolo caracteres de la cadena de entrada. Es difícil, si no imposible, implementar algunas características más avanzadas en motores como este.

    Ejemplos de motores basados ​​FSA:

    • Posix/GNU ERE/BRE — usados ​​en la mayoría de utilidades de Unix, tales como grep, sed y awk.
    • Re2 — Un proyecto relativamente nuevo para tratar de dar más potencia al método basado en Automata.
       

  2. los basados ​​en posterior de seguimiento de. A menudo compilan el patrón en código de bytes, asemejándose a las instrucciones de la máquina. El motor luego ejecuta el código, saltando de instrucción a instrucción. Cuando una instrucción falla, luego retrocede para encontrar otra forma de hacer coincidir la entrada.

    Ejemplos de motores basados ​​en la espalda de seguimiento:

    • 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 No tengo intención de describir más.

Para más información:

Si desea que amplíe algo, publique un comentario.

Fuente

2010-09-02 11:17:15

+0

Parece que tengo algo de trabajo cortado para mí con los enlaces publicados, pero creo que esto es más de lo que estaba buscando. Incluso si sabes de un libro real que podría comprarse, sería fantástico. – Robb

+0

No he leído muchos libros sobre el tema, pero uno que me gustó es "Introducción a la teoría de la computación" de Michael Sipser. No se trata solo de expresiones regulares, sino que llega hasta Máquinas Turing y completitud de NP, etc. –

Cuestiones relacionadas

 Cuestiones relacionadas