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][1] to conc-or graphs (also known as CF
grammars) and and-or graphs of [Dijkstra's shortest path algorithm][2].
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][3], 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][4].
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][5].
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][6].
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$
[1]: http://www.sciencedirect.com/science/article/pii/0020019077900023
[2]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
[3]: http://en.wikipedia.org/wiki/Fibonacci_heap
[4]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
[5]: http://cstheory.stackexchange.com/questions/7374#18006
[6]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm