# Generating a set of minimal-length strings that, together, invoke every production of a context free language

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?

• Can the input grammar be ambiguous? If so, does a string count for all productions in all derivations? Can we assume that the grammar is reduced, i.e. contains not "dead end" rules (every rules is reachable from the start symbol and has a right side that can derive to a word)?
– Raphael
Jul 8 '14 at 0:59
• @Raphael The particular grammar that I'm working with is ambiguous in a few minor places but that can be ignored for simplicity if necessary. I'd rather an ambiguous string not count for all of its possible derivations, because my aim is to force the parser to hit every code branch, but as I say that I realize it might not be possible. The grammar is reduced. Jul 8 '14 at 1:30
• Try it backward. Build a set of rule where the right-hand-side (RHS) is a terminal strings (that includes the empty word, which is an empty string of terminals). Then look at all remaining rules successively, to see if one has a RHS that can be derived into a terminal string with the rules in your set ... and try to finish this yourself. Two remarks though: I am very surprised you programmed a parser "similar to Yacc+Antlr" with such a limited knowledge of context-free grammars. Second point is that I doubt your test is enough: rules may interact in the parsing process. Jul 8 '14 at 7:53
• Definitely, code-coverage is known to be a very rough testing strategy. What's more, you have a programming language with ambiguous syntax? Oh dear.
– Raphael
Jul 8 '14 at 8:51
• @Raphael Ambiguous grammar for a programming language does not bother me. I have been advocating them for many years. The USA Defence has been using one for some 30 years. But, the technology depends on how ambiguous, and on how ambiguity is to be dealt with. If the technology is to be Yacc+Antlr like, then the parser behaves as if the language was unambiguous: if forces a choice. Other technologies may keep the ambiguity. But I am still bothered by the fact it all requires a level of understanding that does not seem to be present in the question. Jul 8 '14 at 9:16

# In a nutshell

Not knowing enough the literature, I worked out a solution which is presented in the next section, together with a proof for the hardest part. Once I knew what was needed, I could search the literature for the right ideas. Here is a quick presentation of the algorithm, based on the literature, which is essentially the same I developed.

The first thing to do is to find a size-minimal terminal string $\sigma(U)$ for every non-terminal $U$ of the grammar. This can be done by using Knuth's extension to conc-or graphs (also known as CF grammars) and and-or graphs of Dijkstra's shortest path algorithm. Example B in Knuth's paper does what is needed, almost.

Actually, Knuth computes only the length of these terminal strings, but it is quite easy to modify his algorithm to actually compute one such terminal string $\sigma(U)$ for each non-terminal $U$ (as I do it in my own version below). We also define $\sigma(a)=a$ for every terminal $a$, and we extend $\sigma$ as usual into a string homomorphism.

Then we consider a directed graph where non-terminals are the nodes, and there is an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha V\beta$. If several such rules can produce the same arc $(U,V)$, we keep one such that the length $|\sigma(\alpha\beta)|$ is minimal. The arc is labeled with that rule, and that minimal length $|\sigma(\alpha\beta)|$ becomes the weight of the arc.

Finally, using Dijkstra's shortest path algorithm, we compute the shortest path from the initial non-terminal $S$ to each non-terminal of the grammar. Given the shortest path for a non-terminal $U$, the rule labels on the arcs may be used to get a derivation $S\overset{*}{\Longrightarrow}\alpha U \beta$. Then, to every rule of the form $U\rightarrow\gamma$ in the grammar, we associate the size-minimal terminal string $\sigma(\alpha\gamma\beta)$ which can be derived using that rule.

To achieve low complexity, both Dijkstra's algorithm and Knuth's extension are implemented with heaps, AKA priority queues. This gives for Dijkstra's algorithm a complexity of $O(n\log n +t)$, and for Knuth's algorithm a complexity $O(m \log n +t)$, where there are $m$ grammar rules and $n$ non-terminals, and $t$ is the total length of all rules. The whole is dominated by the complexity of Knuth's algorithm since $m\geq n$.

What follows is my own work, before I produced the short answer above.

# Deriving the solution from the useless symbols elimination algorithm.

There are several aspects to this algorithm. For better intuition I chose to present it in three successive versions that introduce progressively more features. The first version does not answer the question, but is a standard algorithm for useless symbols elimination that suggests a solution. The second version answers the question without the minimality constraint, The third version gives an answer to the question, satisfying thye minimality constraint. This third solution is then improved by using an adaptation to and-or graphs of Dijkstra's shortest path algorithm.

The end result is a very simple algorithm, that avoids reconsidering computations already done. But it is less intuitive and does require a proof.

This answer only tries to answer the question as made precise by the OP's comment: "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." Hence I only try to get a set of strings such that for each rule, there is a string in the set that is one of the size-minimal strings of the language having a derivation using the rule.

It must be however noted that the fact that a string "invokes" a rule, that is has a derivation using that rule, does not necessarily means that the rule will be considered by a parser that work with ambiguous grammars and resolves ambiguities arbitrarily. Handling such a situation would probably require more precise knowledge of the parser, and might well be a more complex question.

## The basic algorithm

To solve this question, one can start with the classical algorithm for useless symbols removal in context-free grammars. It is in section 4.4, pp 88-89, of Hopcroft & Ullman, 1979 edition. But the presentation here may be a bit different.

The algorithm aims precisely at proving the existence of such a covering as requested by the OP, and consists in two parts:

• lemma 4.1 of H&U, page 88: removal of all unproductive non-terminals. This is done by trying find for each terminal a terminal string it can derive on. A simple way to explain it is as follow: You create a set $Prod$ od productive symbols, which you initialize with all terminals. Then for each rule, not yet processed, that has all its right-hand-side (RHS) symbols in $Prod$, you add the left-hand-side (LHS) non-terminal to the set $Prod$, and you remove all rules with the same LHS non-terminal from the set of rules to be processed. You iterate the process until there is no rule left with all its RHS symbols in $Prod$. The remaining non-terminals, not in $Prod$ at the end of this process, are non-productive: they cannot be derived into a terminal string, and can thus be removed from the grammar.

• lemma 4.2 of H&U, page 89: removal of all unreachable symbols. This is done by the classical node reachability in directed graphs, by considering non-terminals as nodes and having an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha$ such that $V$ occurs in $\alpha$. You create a set $Reach$ of reachable symbols which is initialized with only the initial symbol $S$. Then, for every non-terminal symbol $U$ in $Reach$ or later added to it, and for every rule $U\rightarrow \alpha$, you add to $Reach$ all the symbols in $\alpha$. When all non-terminals in $Reach$ have been thus processed, all symbols (terminal or non-terminals) that are not included in $Reach$ cannot appear in a string derived from the initial symbol, and are therefore useless. Thus they can be removed from the grammar.

These two basic algorithms are useful to simplify the raw results of some grammar construction techniques, such as used for the intersection of a context-free language and a regular set. In particular, this is useful in cleaning up the results of general CF parsers.

Useless non-terminal symbols removal is necessary in the context of solving the question asked, as the rules using them cannot be "invoked" (i.e. used in its derivation) by any string of the language.

## Building a set of string that invoke every rule

(We are not looking yet for minimal strings.)

Now answering specifically the question, one must indeed remove all useless symbols, whether unreachable symbols or unproductive non-terminal symbols, a well as useless rules having such useless non-terminals as LHS. They have no chance of being ever invoked usefully while parsing a terminal string (though some may well waste the processing time of a parser when they are not removed; which ones may waste time depends on the parser technology).

We now consider, for each (useful) rule, the production of a terminal string that invokes it, i.e. that may be generated by using this rule. This is essentially what is done by these two algorithms above, though they do not keep the information, as they are satisfied with proving the existence of these strings to ensure that non-terminals are both reachable and productive.

We modify the first algorithm (lemma 4.1) by keeping with each non-terminal $U$ in the set $Prod$ a terminal string $\sigma(U)$ it derives on: $U\overset{*}{\Longrightarrow}\sigma(U)$. For every terminal we define the $\sigma$ as the identity mapping. When $U$ is added to the set $Prod$ because a rule $U\rightarrow\gamma$ has all its RHS symbols in $Prod$, then we define $\sigma(U)=\sigma(\gamma)$, extending $\sigma$ as a homomorphism on strings, and we remove all $U$-rules, that is all rules with $U$ as LHS.

We modify the second algorithm (lemma 4.2) by keeping with each non-terminal symbol $U$ added to $Reach$ the path used to reach it from the intial symbol $S$, which gives the successive rules to get a derivation $S\overset{*}{\Longrightarrow}\alpha U \beta$.

Then, for each rule $U\rightarrow\gamma$ in the grammar, we produce a terminal string that "invokes" this rule as follows. We take from the result of the second algorithm the derivation $S\overset{*}{\Longrightarrow}\alpha U \beta$. Then we apply the rule to get the string $\alpha \gamma \beta$. A terminal string "invoking" the rule $U\rightarrow\gamma$ is $\sigma(\alpha \gamma \beta)$

## Building a set of minimal strings that "invoke" every rule

We ignore the issue of eliminating useless symbols, which can be a by-product of these modified algorithms.

Building a set of minimal strings relies on first getting a minimal derived string for each non-terminal. This is done by further modifying the first algorithm (lemma 4.1). First we remove from the set of rules to be processed all recursive rules (i.e. with a LHS symbol occurring in the RHS string). It is obvious that none of these rules can derive to a shorter terminal string than the non-recursive rules with the same LHS. And there must be at least one non-recursive rule if the LHS is not a useless non-terminal (because non-productive).

Then we procede as before to build the set $Prod$ of productive symbols, associating with each synbol $U$ a terminal string, which we note $\sigma(U)$. The string $\sigma(U)$ is produced as before by application of the rule $U\rightarrow\gamma$, substituting each non-terminal $V$ occurring in $\gamma$ with $\sigma(V)$. So far, it was necessary to apply this to only one rule with a given non-terminal $U$ as its LHS, the first that would have all its RHS non-terminals in $Prod$, and then ignore the others, because any such derived string would do. But we are now looking for a minimal derived string. Hence, for a non-terminal $U$, this has to be done for all rules with $U$ as LHS. But we keep only one terminal string $\sigma(U)$, replacing the current one by the newly found one, whenever the new one is smaller.

Furthermore, whenever the string $\sigma(U)$ is replaced by a smaller one, all rules with an occurrence of $U$ in the RHS that had been already processed have to be put back in the set of rules to be processed, since change allows deriving their RHS on a shorter string. So doing this will call for more iterations, but will eventually end since none of these strings ever gets much shorter than the empty string.

At the end of this first algorithm, the string $\sigma(U)$ is one of the smallest strings that can be derived from $U$. There may be others.

Now we also have to modify the second algorithm to get, for every non-terminal $U$, (one of) the shortest string containing U as the only non-terminal. To do this, we keep the same directed graph with non-terminals as nodes, and having an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha V \beta$. But now we put weights on the arcs, to compute the minimum length of the terminal context that has to be associated with reachable non-terminals. The weight associated with the arc $(U,V)$ above is the length $|\sigma(\alpha\beta)|$, where the mapping $\sigma$ is extended to terminals as the identity, and then extended again as a string homomorphism. It is the length of (one of) the shortest terminal strings that can be derived from the string $\alpha\beta$. Note that $V$ is removed in this calculation. HOwever, when there are several occurences of $V$ in the RHS, only one must be removed. There may be several possible $(U,V)$ arcs, with different weights, if there are several rules with $U$ as LHS and $V$ in the RHS. In such a case, only (one of) the lighter such arc is kept.

In this graph, we no longer look just for reachability of nodes from $S$, but for the shortest weighted path that reaches every node from the initial symbol $S$. This can be done with Dijkstra's algorithm.

Given the shortest path for a non-terminal $U$, we read it as before as a sequence of rules, from which we get a dérivation $S\overset{*}{\Longrightarrow}\alpha U \beta$. Then to every rule of the form $U\rightarrow\gamma$ in the grammar, we produce a minimal terminal string that "invokes" this rule as $\sigma(\alpha\gamma\beta)$

Remark: The same minimal string may probably be used for several rules. But the fact that one of the strings uses a rule $\rho$ in its derivation does not necessarily mean it is a minimal string for that rule $\rho$, as it may have been found for another rule, while a shorter one can be found for $\rho$. It may be possible to increase the likelyhood that the same minimal string will be found for several rules by using some priority policy whenever there is flexibility. But is it worth the trouble?

## A faster algorithm for minimal terminal string deriving from a non-terminal

Building the function $\sigma$ such that $\sigma(U)$ is a minimal terminal string deriving from $U$ is done above with a rather naive technique that requires iteratively reconsidering work already done when a new smaller derived string is found for some non-terminal. This is wasteful, even if the process will clearly terminate.

We propose here a more efficient algorithm, that is, in essence, an adaptation to the CF grammar graph of an extension of Dijkstra's shortest path algorithm to and-or graphs, with a proper definition of the path-concept for an and-or graph. This variant of the algorithm probably exists in the literature (assuming it is correct), but I have been unable to find it in the resources I can access. Hence I am describing it in more details, together with a proof.

As previously, we first remove from the set of rules to be processed all recursive rules (i.e. rules with a LHS symbol occurring in the RHS string). It is obvious that none of these recursive rules can derive to a shorter terminal string than the non-recursive rules with the same LHS. And, for a LHS $U$ there must be at least one non-recursive $U$-rule if the symbol $U$ is not a useless non-terminal (because non-productive). This is not strictly necessary, but reduces the number of rules to be considered later.

Then we procede as before to build the set $Prod$ of productive symbols, associating with each synbol $X$ a terminal string, which we note $\sigma(X)$, which is a size-minimal terminal string derivable from $X$ (in the previous algorithm, that was true only after termination).The set $Prod$ is initialized with all terminal symbols, and for each terminal symbol $a$, we define $\sigma(a)=a$.

Then we consider every rule $U\rightarrow\gamma$ such that all RHS symbols are in $Prod$, and we choose one such that $\sigma(\gamma)$ is size-minimal. Then we add $U$ to $Prod$, with $\sigma(U)=\sigma(\gamma)$, and remove all $U$-rules. We iterate until all productives terminals have been entered in $Prod$. Any non-terminal $U$, once entered in $Prod$, never has to be considered again to change $\sigma(U)$ for a smaller string.

Proof:

The previous algorithms were more or less intuitively obvious. This one is a bit trickier, because of the and-or character of the graph, and a proof seems more necessary. All we need is actually the following lemma, which establishes the correctness of the algorithm when applied to the last iteration.

Lemma: After each iteration of the algorithm, $\sigma(X)$ is a size-minimal terminal string derivable from $X$, for all $X$ in $Prod$.

The base step is obvious, since this is true by definition for all terminals in $Prod$ when it is initialized.

Then, assuming it is true after some non-terminals have been added to $Prod$, let $U\rightarrow\gamma$ be the rule chosen to add a new non-terminal to $Prod$. We know that this rule is chosen because $\gamma\in{Prod}^*$ and $\sigma(\gamma)$ is size-minimal over all RHS of all rules with a RHS in ${Prod}^*$. Then $U$ is added to $Prod$, and we have only to prove that $\sigma(\gamma)$ is a size-minimal terminal string derivable from $U$.

This is obviously the case for all derivations beginning with the rule $U\rightarrow\gamma$, since by induction hypothesis, application of mapping $\sigma$ is such that all non-terminals in $\sigma$ are substituted with size-minimal terminal strings deriving from them. Hence no other derivation can produce a shorter terminal string.

We thus consider only derivations starting with another $U$-rule $U\rightarrow\beta$, such that $\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$, where $\Sigma$ is the set of terminal symbols.

If $\beta\in{Prod}^*$, then a minimal string it can derive on is $\sigma(\beta)$. But, since we chose the rule $U\rightarrow\gamma$, it must be that $|\sigma(\beta)|\geq|\sigma(\gamma)|$. So the rule $U\rightarrow\beta$ does not derive on a smaller terminal substring.

The last case to consider is when $\beta\notin{Prod}^*$, and we then consider a derivation $\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$. If that derivation involves only non-trminals in $Prod$, then $\beta\in{Prod}^*$, which is a case we have already seen. Hence we consider only derivations that have steps using a rule with its LHS not in $Prod$. Let $V\rightarrow\alpha$ be such a rule, such that $\alpha\in{Prod}^*$.There must be at least one such rule since they are partially ordered by derivation order, and $w\in{Prod}^*$.

Thus we have $U\Longrightarrow\beta\overset{*}{\Longrightarrow}\mu V\nu$. We know that $\mu$ and $\nu$ derive on a string of size at least 0, and since no $V$-rule with a RHS in ${Prod}^*$ was chosen, they derive on terminal strings of length at least equal to $|\sigma(\gamma)|$. Hence, with the rule $U\rightarrow\beta$, $U$ derives on a terminal string of length at least equal to $|\sigma(\gamma)|$. $\blacksquare$

• looks plausible but suggest it needs to be converted at least to pseudocode. also it seems plausible the problem or near variants has been studied in the literature somewhere...
– vzn
Jul 16 '14 at 2:19
• @vzn I doubt this problem has been published, because I do not see an application that does require this minimality. The useless symbols elimination algorithm is a classical technique, found probably in all textbooks on CF languages. And, as I said, it has some applications in general CF parsing. I never heard of pushing it further for producing test sentences. I chose to try explain its derivation, rather than give pseudo code. As it is the answer is already very long. Maybe in a second answer, if that is acceptable on the site ... as the text is becoming too long to handle. Jul 16 '14 at 21:47
• @vzn What could be in the literature is the extension of Dijkstra's shortest path algorithm to and-or graphs. Unfortunately, I do not have access to resources for finding out. I could write it up in a simplified form, without the CF grammar stuff. But then, I do not think it is a big deal. But it does gives the right hints to implement with low complexity. Jul 16 '14 at 21:58
• minimization & "coverings" are common considerations in the theoretical literature. further thought, maybe a normal form either Greibach or Chomsky could be key to understanding it better (there is some connection there also with removing unproductive terminals/nonreachable symbols). think this is worthwhile question for tcs.se, may ask it at some pt there & cite this one (afaik migrations tend to lose comments.)
– vzn
Jul 16 '14 at 22:37
• @vzn I doubt Greibach or Chomsky normal form will bring any light. This is grammar dependent more than language dependent. Changing the grammar changes the problem. Actually, I first thought it was a homework dump. The minimality requirement does give it some interest, as finding a good algorithm was less obvious, especially my last version. I wrote the proof because I could not convinced myself any other way that it actually works. It is somehow less intuitive that the straight Dijkstra's algorithm from which I derived it. Jul 16 '14 at 23:12

## A simple solution

If you don't care too much about the number of strings, there is an easy solution. Basically, for each production, we will generate a string that covers that production.

How do we do that? It's a straightforward worklist algorithm. Suppose we want to cover the production $A ::= BCx$. Basically, we do breadth-first search starting from the start non-terminal $S$ to find a derivation that includes the non-terminal $A$ on the right hand side: initially, all non-terminals are unmarked, and the set of reachable non-terminals is $\{S\}$; in each iteration, we pick one unmarked reachable non-terminal, say $X$, and for each production with $X$ on the left-hand side, we add all the non-terminals on the right to the set of reachable terminals, then we mark $X$. Repeat until this process finds that $A$ is reachable. When it does, by backtracing, you obtain a derivation of the form $S \to \cdots A \cdots$. You can extend this to a derivation of the form $S \to \cdots A \cdots \to \cdots BCx \cdots$.

Next, we need to complete the derivation, by picking some way to complete it to be all non-terminals. This is also easy. For each non-terminal, we find the shortest string that is in the language generated by that non-terminals. This can be obtained by a worklist iteration. Let $\ell(A)$ denote the length of the shortest string we've found so far in the language generated by $A$. Initially, we set $\ell(A)=\infty$ for all non-terminals $A$, unless there is a production $A ::= xyz$ where all the symbols on the right-hand side are terminals; in that case, we set $\ell(A)$ accordingly (e.g., $\ell(A)=3$ if the production tells us that $xyz$ is in $L(A)$). Now we iteratively look for a way to find a shorter string. If you have a production like $A ::= xBCy$, you know that $\ell(A) \le 2 + \ell(B) + \ell(C)$; so any time you find a new shorter string in $L(B)$ or $L(C)$ (i.e., any time you update $\ell(B)$ or $\ell(C)$ to be smaller), you can check whether this gives you a new shorter string in $L(A)$, and if so, reduce the value of $\ell(A)$... which may in turn cause other cascading changes. Keep applying all cascading changes until no further changes are triggered. At that point, you have reached a fixed point, and by backtracing, for each non-terminal you know the shortest string (of terminals) that can be derived from that non-terminal.

Now, given your derivation of the form $S \to \cdots BCx \cdots$, find a way to complete the derivation: replace each non-terminal in $\cdots BCx \cdots$ with the shortest string (of terminals) that can be derived from it.

This gives you a string (of terminals) that covers the production $A ::= BCx$. Do this once for each production, until all of them are covered.

The number of strings is equal to the number of productions. The running time is quadratic: the process is linear-time for each production. (You could probably reduce it to be a linear-time algorithm in total, but I suspect this will be good enough in practice.)

## Optimizations

If you want to reduce the number of strings, you might notice that each string will typically cover many productions, so a subset of these strings will probably suffice.

There are many ways you could reduce the number of strings. One simple one is to use the standard greedy approximation algorithm for set cover. Start by generating all of the strings as above, one for each production, and count how many productions each string covers. Keep the string that covers the most productions; that one you definitely want, so add it to your set of keepers. Now some of the productions are covered by this keeper, so we don't need any new strings that cover them again. Thus, you should update your set of counts for each strings: for string $s$, count the number of productions that are covered by $s$ but aren't covered by any keeper. Pick the string that has the largest number, add it to your set of keepers, and update the counts again. Repeat until all productions have been covered. This will likely give you a significantly smaller set of strings that cover all productions in your grammar.