Producing all possible matches of a regular expression

Question

Given a regular expression, I want to produce the set of strings that that regular expression would match. It is important to note that this set would not be infinite because there would be maximum length for each string. Are there any well known algorithms in place to do this? Are there any research papers I could read to gain insight into this problem?

Thanks.

p.s. Would this sort of question be more appropriate in the theoretical cs stack exchange?

Answer 1

Are there any well known algorithms in place to do this?

In the Perl eco-system the Regexp::Genex CPAN module does this.

In Python the sre_yield generates the matching words. Regex inverter also does this.

A recursive algorithm is described here link1 link2 and several libraries that do this in Java are mentioned here.

Generation of random words/strings that match a given regex: xeger (Python)

Are there any research papers I could read to gain insight into this problem?

Yes, the following papers are available for counting the strings that would match a regex (or obtaining generating functions for them):

1. Counting occurrences for a finite set of words: an inclusion-exclusion approach by F. Bassino, J. Clement2, J. Fayolle, and P. Nicodeme (2007) paper slides
2. Regexpcount, a symbolic package for counting problems on regular expressions and words by Pierre Nicodeme (2003) paper link link code