Recomendaciones para una implementación de C de un analizador de expresiones regulares

Estoy pensando en implementar un analizador de expresiones regulares en una biblioteca C que estoy desarrollando. Ahora, la pregunta es: ¿hay algún código fuente abierto que pueda usar al pie de la letra o con el menor número de cambios posible? Mis expectativas con respecto al código son:Recomendaciones para una implementación de C de un analizador de expresiones regulares

necesita ser escrito en C (no C++)
necesarias para la elaboración bajo GCC, MinGW, M $ VC
no debe depender de ningún tercero espejos/librerías específicos de OS o del partido (es decir, todo lo necesario para compilarlo debe estar fácilmente disponible con una instalación base de gcc, mingw, M $ VC
sería bueno si utilizara la sintaxis de expresiones regulares compatibles con Perl (como PCRE) en PHP).
idealmente, el código debe ser lo más compacto posible

¿Hay alguna solución lista que pueda recomendar? Estaba mirando PCRE para C y parece que tiene todo lo que está disponible en PHP (que rige), pero el tamaño (1.4MB DL) es un poco intimidante. ¿Crees que es una apuesta sólida? ¿O hay otras opciones que vale la pena considerar?

[EDIT]

La biblioteca que estoy desarrollando es de código abierto, la licencia BSD.

Fuente

2010-12-10 mingos

¿Con qué licencia estará liberando su biblioteca? – Cascabel

PHP está construido en la parte superior de C. No me sorprendería si PHP usa PCRE para C. –

@Jefromi: gracias por preguntar sobre eso, olvidé agregar esa información. He actualizado la pregunta. – mingos

PCRE es prácticamente el estándar de facto de las implementaciones de expresiones regulares (por una buena razón). No se preocupe por el tamaño, es grande porque las implementaciones de expresiones regulares son complicadas. Solo úsalo de todos modos.

Fuente

2010-12-10 14:14:09

código malo porque es "estándar de facto" y porque * * foo es "complicada" (pista: es no) no es un buen consejo. –

No lo recomendé porque era complicado. Dije que PCRE era "prácticamente el estándar de facto". No creo que sea un código malo. –

PCRE es tan grande porque las expresiones regulares son difícil. Y la mayor parte es código de documentación y soporte de todos modos; es mucho más pequeño cuando se compila en código objeto.

Fuente

2010-12-10 14:12:30

Las expresiones regulares no son difíciles; PCRE está hinchado y la última vez que lo revisé fue 'O (2^n)'.Una implementación POSIX completa de expresiones regex debe pesar menos de 10k (código de máquina x86); No estoy seguro acerca de la expresión regular al estilo Perl (que ni siquiera es un lenguaje normal) ya que tiene todo tipo de extensiones extrañas, pero dudo seriamente que haya una razón legítima para que PCRE sea tan grande como lo es. –

La razón por la que PCRE es O (2^n) es porque admite expresiones regulares de estilo perl (que admiten referencias anteriores). ¿Has escrito una implementación de expresión retrospectiva? ¿Quién eres tú para decir que no es difícil o cuán grande debería ser? –

Obviamente, con copias de referencias Es 'O (2^n)', pero yo sepa que también tenía muy mal comportamiento asintótico (tal vez sólo 'O (n^2)' o 'O (nm)' sin embargo) para muchos puramente expresiones regulares que no contienen retro referencias. –

Puede probar TRE si está satisfecho con la sintaxis de expresiones regulares POSIX. Si desea la sintaxis de Perl, Google tiene una nueva implementación que vale la pena consultar.

Fuente

2010-12-10 14:52:08

RE2, la aplicación Google expresión regular hace una coincidencia en el tiempo lineal (O(n) si n es la longitud de la cadena), PCRE y la mayoría de los otros motores de expresiones regulares se ejecutan en tiempo exponencial en el peor caso. Otro marcador de regexp O(n) digno de mención es flex, pero necesita todas las expresiones regulares posibles en tiempo de compilación. Si está buscando algo más pequeño que PCRE, mire la comparación de expresiones regulares en busybox, o la coincidencia de patrones en lua.

Fuente

2010-12-10 15:04:37 pts

Pero es C++ :(. Lástima ... – mingos

@mingos, puede que lo envuelva para el consumo de código C a pesar de que las agallas están escritas en C++? Todos los compiladores que conocidas hacen C++ disponibles, después de todo. – RBerteig

No . realmente la biblioteca en cuestión no es de mi propiedad, sólo soy un co-mantenedor La política es bastante estricta:.. todo el código está escrito en C y luego se añade un envoltorio de C++ en la parte superior de la que no estoy realmente en el poder de influenciar eso. – mingos

Recomendaciones para una implementación de C de un analizador de expresiones regulares

Respuesta

Cuestiones relacionadas