Combinar varias expresiones regulares en una sola

Question

Tengo varias expresiones regulares (en realidad varios miles), y debo comprobar si una cadena coincide con cualquiera de estas expresiones regulares. No es muy eficiente, por lo que me gustaría fusionar todas estas expresiones regulares como una sola expresión regular.

Por ejemplo, si una tiene estas expresiones regulares:

• 'fu * bar'
• 'fu * zip'
• zap * bar '

me gustaría obtener algo como 'foo * (bar | zip) | zap * bar'.

¿Hay algún algoritmo, biblioteca o herramienta para hacer esto?

Answer 1

Puede concatenar las expresiones regulares usando o (|) (y anclas para el comienzo/final de la cadena).

La mayoría de las buenas bibliotecas de expresiones regulares optimizan sus autómatas de estado finito después de construirlo a partir de su expresión regular. PCRE hace eso, por ejemplo.

Este paso generalmente se ocupa de su problema de optimización, es decir. ellos aplican la mayoría de las transformaciones que tendrían que hacer "a mano".

Answer 2

No me puedo imaginar, incluso si es posible, que la expresión regular resultante sería más eficiente.

Answer 3

Lo dudo mucho, con el argumento de que cualquier herramienta de este tipo tendría que ser muy compleja para tratar todas las formas diferentes en que se podría combinar una expresión regular.

Si las expresiones regulares que tiene son relativamente simples, como en los ejemplos, puede que tenga un poco de suerte escribiendo las suyas propias.

Answer 4

En teoría, una expresión regular es un autómata de estado finito (no determinista); por lo tanto, pueden fusionarse y minimizarse. Puede echar un vistazo al this como punto de partida.

Tenga en cuenta, sin embargo, que esta podría no ser la respuesta más correcta. ¿Por qué tienes que tratar con varias miles de expresiones regulares? Solo puedo comprender el infierno de esa cosa. Tal vez deberías considerar escribir un analizador sintáctico y una gramática, algo muy fácil de hacer (y las gramáticas son más poderosas que las expresiones regulares de todos modos).