Algorithm for finding strings that a specific Regex will match

Question

Given a regex pattern, I'm trying to find a string that matches it. Similar to how Django reverses them, but in C#. Are there any pre-made C# libraries that do this?

Edit: Moving this project to Google code pretty soon.

Current Test Results

^abc$                     > abc                  : pass
\Aa                       > a                    : pass
z\Z                       > z                    : pass
z\z                       > z                    : pass
z\z                       > z                    : pass
\G\(a\)                   > \(a\)                : pass
ab\b                      > ab                   : pass
a\Bb                      > ab                   : pass
\a                        >                     : pass
[\b]                      >                    : pass
\t                        > \t                   : pass
\r                        > \r                   : pass
\v                        > ♂                    : pass
\f                        > \f                   : pass
\n                        > \n                   : pass
\e                        > ←                    : pass
\141                      > a                    : pass
\x61                      > a                    : pass
\cC                       > ♥                    : pass
\u0061                    > a                    : pass
\\                        > \\                   : pass
[abc]                     > a                    : pass
[^abc]                    > î                    : pass
[a-z]                     > a                    : pass
.                         > p                    : pass
\w                        > W                    : pass
\W                        > ☻                    : pass
\s                        > \n                   : pass
\S                        > b                    : pass
\d                        > 4                    : pass
\D                        > G                    : pass
(a)\1                     > aa                   : pass
(?<n>a)\k<n>              > aa                   : pass
(?<n>a)\1                 > aa                   : pass
(a)(?<n>b)\1\2            > abab                 : pass
(?<n>a)(b)\1\2            > abba                 : pass
(a(b))\1\2                > ababb                : pass
(a(b)(c(d)))\1\2\3\4      > abcdabcdbcdd         : pass
a\0                       > a                    : pass
ab*                       > a                    : pass
ab+                       > abbb                 : pass
ab?                       > a                    : pass
ab{2}                     > abb                  : pass
ab{2,}                    > abbbbbbbbb           : pass
ab{2,3}                   > abb                  : pass
ab*?                      > abb                  : pass
ab+?                      > abbbbb               : pass
ab??                      > a                    : pass
ab{2}?                    > abb                  : pass
ab{2,}?                   > abbbbbbbbb           : pass
ab{2,3}?                  > abbb                 : pass
/users(?:/(?<id>\d+))?    > /users/77            : pass
Passed 52/52 tests.

I'm confused, are you trying to literally reverse the Regex itself, trying to find a Regex that matches your Regex, or trying to create a string that your Regex matches? — Chris Laplante
– Chris Laplante, Commented Nov 28, 2010 at 19:23
@SimpleCoder: I thought the very first sentence said it all: I'm trying to find a string that my regex matches. — mpen
– mpen, Commented Nov 28, 2010 at 19:27
You might do better by converting the regex to a finite state model. You then generate a string by doing a walk through the state model. — user180247
– user180247, Commented Nov 28, 2010 at 19:39
@Ralph - to handle those quantifiers, since your current approach doesn't have a memory, build the memory into the way you derive your tail-regex strings / state descriptions. If a regex specifies n-to-m repeats of x, when you accept an x, the new state will normally accept (n-1)-to-(m-1) repeats of x - but watch for counts reaching zero. — user180247
– user180247, Commented Nov 28, 2010 at 20:00

Community · Accepted Answer · 2017-05-23 12:04:14Z

4

see for example Using Regex to generate Strings rather than match them

also you can take a look at http://en.wikipedia.org/wiki/Deterministic_finite-state_machine especially at "Accept and Generate modes" section.

as others noted you will need to create a DFA from your regular expression and then generate your strings using this DFA.

to convert your regular expression to DFA, generate NFA first (see for example http://lambda.uta.edu/cse5317/spring01/notes/node9.html) and then convert NFA to DFA.

the easiest way i see is to use a parser generator program for that. i do not think django does this.

hope this helps.

edited May 23, 2017 at 12:04

CommunityBot

11 silver badge

answered Nov 28, 2010 at 19:50

akonsu

29.7k39 gold badges126 silver badges205 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

abelenky · Accepted Answer · 2010-11-30 20:13:17Z

2

"Are there any pre-made C# libraries that do this?"

NO

(I expect this will be accepted as the answer momentarily)

answered Nov 30, 2010 at 20:13

abelenky

65k24 gold badges115 silver badges163 bronze badges

1 Comment

mpen Over a year ago

Lol...that's a bit of a cocky response, and not entirely true :P My library will be released in about 30 minutes. =)

Collectives™ on Stack Overflow

Algorithm for finding strings that a specific Regex will match

Current Test Results

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Current Test Results

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related