Problem (tl;dr)

Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once.

How and how fast can it be done?

Background

I'm working on a compiler whose parser is implemented with a tool similar to Yacc+Antlr. I've written up most of the parser code, and I'd like to generate some code of the object language that invokes every production of the grammar at least once so that I can feed it to the parser and make sure that nothing is wrong.

In the interest of good testing, what I'd really like is one, short test file that has a particular production "under test" -- so, for each production rule, I want to generate a minimal string that takes the parser from the start state, through the production being tested, to a set of terminals.

Possible solutions

I imagine there is an elegant solution using graph theory, but I'm not quite sure what it is. I would like to just use Dijkstra's algorithm to find shortest paths through some appropriate structure, but I think that a string is parsed by a context free grammar in a tree structure rather than a path, so I don't know how to make that work.

I think there might be a clever way to pose it as a network flow problem. Something like this: take a graph that has a vertex for every symbol (terminal and nonterminal) and a vertex for every production. If a nonterminal has a production, add a directed edge from the nonterminal to the production. If a production produces a nonterminal, add a directed edge from the production to the nonterminal. Add a source with some capacity $c$ and attach it to the vertex corresponding to the start symbol. Add a sink with infinite capacity and attach it to each terminal.

If a nonterminal has an in-arc with a capacity $k$, add an arc from the nonterminal to each of its productions with capacity $k$. If a production has an in-arc with capacity $k$ and it has an out-arc to $n$ nonterminals, add an arc with capacity $\frac k n$ from the production to each nonterminal.

Then run some maximum flow algorithm on the network and let the productions "trickle down" from the start symbol to the terminals. You should end up with a flow $c$ coming out of your source, and you can return all of the terminals you hit with a nonzero flow as your result string. Then you end up with something like $O(n^3)$ time complexity for each run, where $n$ is the sum of the number of terminals and nonterminals in your grammar -- not too bad.

However, I'm still not really sure what this graph looks like: I think that it needs to be infinite and I'm not sure if you can find the maximum flow of an infinite flow network. Past that, I'm not sure how to "remove" a production from consideration so that I'm guaranteed to get a new one for each test run.

I Googled and I couldn't find anything. Is there a nice solution to this problem?

Problem (tl;dr)

Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once.

How and how fast can it be done?

Background

I'm working on a compiler whose parser is implemented with a tool similar to Yacc+Antlr. I've written up most of the parser code, and I'd like to generate some code of the object language that invokes every production of the grammar at least once so that I can feed it to the parser and make sure that nothing is wrong.

In the interest of good testing, what I'd really like is one, short test file that has a particular production "under test" -- so, for each production rule, I want to generate a minimal string that takes the parser from the start state, through the production being tested, to a set of terminals.

Possible solutions

I imagine there is an elegant solution using graph theory, but I'm not quite sure what it is. I would like to just use Dijkstra's algorithm to find shortest paths through some appropriate structure, but I think that a string is parsed by a context free grammar in a tree structure rather than a path, so I don't know how to make that work.

I think there might be a clever way to pose it as a network flow problem. Something like this: take a graph that has a vertex for every symbol (terminal and nonterminal) and a vertex for every production. If a nonterminal has a production, add a directed edge from the nonterminal to the production. If a production produces a symbol, add a directed edge from the production to the symbol. Add a source with some capacity $c$ and attach it to the vertex corresponding to the start symbol. Add a sink with infinite capacity and attach it to each terminal.

If a nonterminal has an in-arc with a capacity $k$, add an arc from the nonterminal to each of its productions with capacity $k$. If a production has an in-arc with capacity $k$ and it has an out-arc to $n$ nonterminals, add an arc with capacity $\frac k n$ from the production to each nonterminal.

Then run some maximum flow algorithm on the network and let the productions "trickle down" from the start symbol to the terminals. You should end up with a flow $c$ coming out of your source, and you can return all of the terminals you hit with a nonzero flow as your result string. Then you end up with something like $O(n^3)$ time complexity for each run, where $n$ is the sum of the number of terminals and nonterminals in your grammar -- not too bad.

However, I'm still not really sure what this graph looks like: I think that it needs to be infinite and I'm not sure if you can find the maximum flow of an infinite flow network. Past that, I'm not sure how to "remove" a production from consideration so that I'm guaranteed to get a new one for each test run.

I Googled and I couldn't find anything. Is there a nice solution to this problem?