2009-12-11 17 views
7

Ho diverse regex (in realtà diverse migliaia) e devo verificare se una stringa corrisponde a una qualsiasi di queste regex. Non è molto efficiente, quindi mi piacerebbe unire tutte queste regex come una singola regex.Unisci più espressioni regolari a una singola

Ad esempio, se un avere queste espressioni regolari:

  • 'foo * bar'
  • 'foo * zip'
  • 'zap * bar'

Vorrei ottieni qualcosa come "foo * (bar | zip) | zap * bar".

C'è qualche algoritmo, libreria o strumento per fare questo?

risposta

7

È possibile concatenare le espressioni regolari utilizzando o (|) (e le ancore per l'inizio/fine della stringa).

La maggior parte delle librerie di espressioni regolari ottimizza gli automi a stati finiti dopo averli creati dalla regex. PCRE lo fa, per esempio.

Questo passaggio di solito si occupa del problema di ottimizzazione, ad es. applicano la maggior parte delle trasformazioni che dovresti fare "a mano".

+0

Buon primo passo, ma non è necessario ottimizzare a mano: http://www.rexegg.com/regex-optimizations.html –

0

Non riesco a immaginare, anche se possibile, che la regex risultante sarebbe più efficiente.

+2

Non sono d'accordo; una ricerca regolare per "foo (?: bar | baz)" sarà più veloce di una ricerca per "foo bar" e una ricerca per "foo baz", poiché la ricerca separata richiederebbe l'abbinamento (o meno) del "foo" parte due volte. –

+1

-1 Il modo in cui è costruito l'automa ottimizzerà automaticamente molti casi. Inoltre, è possibile ottimizzare ulteriormente la macchina a stati risultante (vedere la risposta di Vlad). –

+0

me ~ = corretto. Grazie! – hometoast

0

Ne dubito fortemente, sulla base del fatto che qualsiasi strumento di questo tipo dovrebbe essere molto complesso per gestire tutti i diversi modi in cui una regex potrebbe essere combinata.

Se le regex che hai sono relativamente semplici, ad esempio nei tuoi esempi, potresti avere un po 'di fortuna a scrivere la tua, comunque.

2

In teoria una regex è un automa allo stato finito (non deterministico); così possono essere uniti e ridotti al minimo. Puoi dare un'occhiata a this come punto di partenza.

Attenzione, tuttavia, questa potrebbe non essere la risposta più corretta. Perché devi gestire diverse migliaia di espressioni regolari? Posso solo capire l'inferno della maintentance di una cosa del genere. Forse dovresti considerare di scrivere un parser e una grammatica - molto facilmente (e le grammatiche sono più potenti delle regex comunque).

+0

Alcuni motori regex includono funzionalità non implementabili in un DFA come la corrispondenza parentesi annidata arbitraria. Prima di adottare questo approccio, assicurati che le espressioni regex di partenza possano effettivamente convertirsi in DFA in modo da poterli unire con un NFA che poi convertirai in un DFA e riduci a icona. – Techrocket9