creating an (inefficent) alternating regular expression from a listof options

[metaperl.com]

Pyparsing has a really nice feature that I want in PLY. I want to
specify a list of strings and have them converted to a regular
expression.

A Perl module which does an aggressively optimizing job of this is
Regexp::List -
http://search.cpan.org/~dankogai/Regexp-Optimizer-0.15/lib/Regexp/List.pm

I really dont care if the expression is optimal. So the goal is
something like:

vowel_regexp = oneOf("a aa i ii u uu".split()) # yielding r'(aa|a|uu|
u|ii|i)'

Is there a public module available for this purpose?

 

[Larry Bates]

Pyparsing has a really nice feature that I want in PLY. I want to
specify a list of strings and have them converted to a regular
expression.

A Perl module which does an aggressively optimizing job of this is
Regexp::List -
http://search.cpan.org/~dankogai/Regexp-Optimizer-0.15/lib/Regexp/List.pm

I really dont care if the expression is optimal. So the goal is
something like:

vowel_regexp = oneOf("a aa i ii u uu".split()) # yielding r'(aa|a|uu|
u|ii|i)'

Is there a public module available for this purpose?

Perhaps I'm missing something but your function call oneOf(...) is longer than
than actually specifying the result.

You can certainly write quite easily:

def oneOf(s):
return "|".join(s.split())

-Larry

 

[skip]

Check Ka-Ping Yee's rxb module:

http://lfw.org/python/

Needs translating from the old regex module to the current re module, but it
shouldn't take a lot of effort. You can find regex docs in old
distributions (probably through 2.1 or 2.2?). Also, check PyPI to see if
someone has already updated rxb for use with re.

Skip

 

[Marc 'BlackJack' Rintsch]

Perhaps I'm missing something but your function call oneOf(...) is
longer than than actually specifying the result.

You can certainly write quite easily:

def oneOf(s):
return "|".join(s.split())

I'd throw `re.escape()` into that function just in case `s` contains
something with special meaning in regular expressions.

Ciao,
Marc 'BlackJack' Rintsch

 

[George Sakkis]

Pyparsing has a really nice feature that I want in PLY. I want to
specify a list of strings and have them converted to a regular
expression.

A Perl module which does an aggressively optimizing job of this is
Regexp::List -http://search.cpan.org/~dankogai/Regexp-Optimizer-0.15/lib/Regexp/Lis...

I really dont care if the expression is optimal. So the goal is
something like:

vowel_regexp = oneOf("a aa i ii u uu".split()) # yielding r'(aa|a|uu|
u|ii|i)'

Is there a public module available for this purpose?

I was about to start a thread about a very similar problem; hope I'm
not hijacking this thread. However I am interested in a solution that
(1) scales to a potentially large number of alternate strings
(hundreds or thousands), which will hit, sooner or later, some max
limit in the builtin regexps and (2) is not limited to strings but can
be used for arbitrary objects. Therefore I am looking for a different
approach, perhaps a specialization of the general regexp search
algorithm.

More formally, given (a) an input sequence I and (b) a set of
'censored' sequences S, find and remove all the sequences in S that
appear in I. For instance, if
S = set([(a,), (a,b), (a,c), (c,), (d,a)])
and
I = (x, a, b, c, y, d, a, b), the filtered sequence would be:
O = (x, y, b)
i.e. the censored subsequences are (a,b), (c,), and (d,a).

As with regexps, if sequence `x` is a prefix of `y`, the longer
sequence `y` wins when both match (e.g. if (a,b) matches, it
supersedes (a,)).

For extra bonus, the algorithm should remove overlapping subsequences
too, i.e. for the input I above, the output would be (x, y) since both
(d,a) and (a,b) would match for (d,a,b).

With respect to complexity, I am mainly interested in len(S); len(I)
is small for my application, typically no more than 10. Of course, an
algorithm that scales decently in both len(S) and len(I) would be even
better. Any ideas or relevant links ?

George

PS: This is not a homework

 

[Fredrik Lundh]

Perhaps I'm missing something but your function call oneOf(...) is
longer than than actually specifying the result.

You can certainly write quite easily:

def oneOf(s):
return "|".join(s.split())

"|" works strictly from left to right, so that doesn't quite work since
it doesn't place "aa" before "a". a simple reverse sort will take care
of that:

return "|".join(sorted(s.split(), reverse=True))

you may also want to do re.escape on all the words, to avoid surprises
when the choices contain special characters.

</F>

 

[metaperl.com]

    >> I really dont care if theexpressionis optimal. So the goal is
    >> something like:

    >> vowel_regexp = oneOf("a aa i ii u uu".split())  # yielding r'(aa|a|uu|
    >> u|ii|i)'

    >> Is there a public module available for this purpose?

Check Ka-Ping Yee's rxb module:

   http://lfw.org/python/

Ok <http://lfw.org/python/rxb.py>
suffers from the possibility of putting shorter match before longer
one:

def either(*alternatives):
options = []
for option in alternatives:
options.append(makepat(option).regex)
return Pattern('\(' + string.join(options, '|') + '\)')

 Also, check PyPI to see if
someone has already updated rxb for use with re.

No one has - http://pypi.python.org/pypi?:action=search&term=rxb&submit=search

no results returned

 

[metaperl.com]

you may also want to do re.escape on all the words, to avoid surprises
when the choices contain special characters.

yes, thank you very much:

import re

def oneOf(s):
alts = sorted(s.split(), reverse=True)
alts = [re.escape(s) for s in alts]
return "|".join(alts)