Re: Generate text, given a regex

Midhat wrote:


> Hi. I want to generate text based on a given regex. just any text that
> satisifies the regex. Are there any existing tools/libraries to do
> that.


I don't know any tools/libraries, but it seems like this problem isn't so
difficult.


* Create a syntax tree of the regex.


* Generate text (T(r)) for the leafs of the tree (r). The atomic regexes:
    - If r = a character, T(r) = that character
    - If r = a character class, T(r) = any character satisfying that class
    - If r = . , T(r) = any character (except perhaps \n)


* Recursively generate text (T(R)) for the non-atomic sub-regexes (R) of the
tree, assuming text has already been generated for all the immediate
sub-regexes of R:
    - If R = x*, T(R) = a concatenation of any number of T(x).
    - If R = x+, T(R) = a concatenation of 1 or more of T(x).
    - If R = x?, T(R) = the empty string or T(x).
    - If R = xy, T(R) = the concatenation of T(x) and T(y).
    - If R = x|y, T(R) = T(x) or T(y)
    - If R = (x), T(R) = T(x)


Any choices you make here will lead to T(regex), the text you want. Of
course, if any text will do, you can immediately return empty strings for
x* and x?, without processing x.


And I am assuming here that we are talking about regular expressions in the
classical sense. So without recalling previously captured sub-expressions
and such. However, if you want to have those anyway, there are still
relatively easy adaptations you can make to this algorithm to make it work.


Good luck!


--
Michiel Helvensteijn

Return to the comp.compilers page.
Search the comp.compilers archives again.