Re: How to print all expressions that match a regular expression

[Gabriel Genellina]

En Mon, 08 Feb 2010 02:17:59 -0300, hzh...@gmail.com <hzh...@gmail.com>
escribió:

Please check out this example on the pyparsing wiki, invRegex.py:http://pyparsing.wikispaces.com/file/view/invRegex.py. This code

implements a generator that returns successive matching strings for
the given regex.  [...]
Of course, as other posters have pointed out, this inverter does not
accept regexen with unbounded multiple characters '+' or '*', but '?'
and "{min,max}" notation will work.  Even '.' is supported, although
this can generate a large number of return values.

Thanks very much. This is exactly what I need now. I will check this
function.

Here you have another approach based on [1]. This is a generator-based
approach, yielding all strings in increasing length order. In principle it
can handle unbounded repetitions, except as written the maximum recursion
limit is shortly reached (the original code is in Haskell, I almost
blindly translated it into Python; certainly it can be rewritten more
efficiently)

You have to parse the R.E. and generate the corresponding function calls
to the merge/prod/closure functions -- pyparsing certainly can help with
that. "ab" becomes prod(a,b), "a|b" becomes merge(a,b), and "a*" becomes
closure(a)

By example, to find the language defined by this expression "(a|bc)*d",
one has to evaluate:

prod(
    closure(
      merge(['a'],
            prod(['b'],['c']))),
    ['d']
)

wich yields these strings:

d
ad
aad
bcd
aaad
abcd
bcad
...

bcbcbcbcaad
bcbcbcbcbcd
aaaaaaaaaaad

and after 234 results aborts with a recursion error :(

[1] http://www.cs.utexas.edu/users/misra/Notes.dir/RegExp.pdf

--
Gabriel Genellina

enumerate_regular_language.py
Description: Binary data

-- 
http://mail.python.org/mailman/listinfo/python-list