Generating all strings that a regular expressions describe

Question

I'm having trouble generating the set of strings, which a regular expressions describe. A typical regular expression can look like this:

[atom_0] atom_1 (atom_2 | atorm_3 | ... | atom_n-1) <var> [atom_n]

Or any other combination of the following:

[], means, that the atom inside of it can be omitted
(), one of the atoms (seperated by | (stands for OR)) inside the braces can be chosen 
<>, variable.
atom, it can be thought as a constant, which is hard coded.

For example:

The [yellow] (dog | cat) named <animalName>

This expression describes the following set of strings:

The yellow dog named <animalName>;
The yellow cat named <animalName>;
The dog named <animalName>;
The cat named <animal Name>;

The strings can vary, depending on the variable <animalName>, but say, we have two names for <variableName> : Petsy and Rony, then w'll have:

The yellow dog named Petsy;
The yellow cat named Petsy;
The dog named Petsy;
The cat named Petsy;
The yellow dog named Rony;
The yellow cat named Rony;
The dog named Rony;
The cat named Rony;

Right now, I'm thinking that I could build a tree (or graph) from the expression and then a DFS or BFS can do the job.

Any comments or document/article references would be helpful to me.

Answer 1

There is a standard construction for converting regular expressions into finite automata (check here or any textbook on formal languages). Once you have such an automaton in hand (either NFA or DFA) you can enumerate all accepted strings with a breadth-first search from the initial state looking for finite states (ordered by length).

Be careful, though: in general, regular expressions specify infinite languages. You can easily specify a length limit, though.

Answer 2

For regular expressions specified the way you describe, you can use a backtracking algorithm to enumerate all acceptable strings. Following is a Python implementation.

The input is a list of items. An item being one of the ones you describe.

gen_candidates generates candidates for the k'th position.

def gen_candidates(item):
    c = []
    if type(item) is list:
        for e in item: c.append(e)
        if(len(item) == 1):
            c.append('')
    elif type(item) is str:
        c.append(item)
    return c

The next function prints a solution when one is found.

def process_solution(solution):
    s = ''
    for e in solution:
        if len(e) > 0:
            s += e + ' '
    print(s)

backtrack tries all possibilities recursively.

def backtrack(regex, solution, k):
    if len(regex) > 0:
        candidates = gen_candidates(regex[0])
        for c in candidates:
            solution[k] = c
            backtrack(regex[1:], solution, k + 1)
    else:
        process_solution(solution)

You invoke the algorithm as follows:

input = ['The', ['yellow'], ['dog', 'cat'], 'named', '<animalName>']
solution = ['', '', '', '', '']
backtrack(input, solution, 0)