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.

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.

Deriving the solution from the useless symbols elimination algorithm.

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

Thus we have $U\Longrightarrow\beta\overset{*}{\Longrightarrow}\mu V\nu$. We know that $\mu$ and $\nu$ derive at least on a string of size 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$

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.

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

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$

There are several aspects to this algorithm. For better intuition I chose to present it in three successive version that introduce progressively more features. The first version does not answer the question, but is a standard algorithms that suggests a solution.

Building a set of string that invoke all rules

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 rules with U as LHS.

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$.

Note that the fact that a string "invokes" a rule does not necessarily means that the rule will be considered by a parser that work with ambiguous grammars and resolves ambiguities arbitrarily.

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 avoid 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.

Building a set of string that invoke every rule

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.

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 at least on a string of size 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$