In finite-state parsing (especially speech decoding) one often makes use of
the forward probabilities for pruning partial parses before having seen
the entire input.
Pruning is formally straightforward in
Earley parsers: in each state set, rank states according to their
values, then remove those states with small probabilities compared to
the current best candidate, or simply those whose rank exceed a given limit.
Notice this will not only omit
certain parses, but will also underestimate the forward and
inner probabilities of the derivations that remain.
Pruning procedures have to be evaluated empirically since they
invariably sacrifice completeness and, in the case of the Viterbi
algorithm, optimality of the result.
While Earley-based on-line pruning awaits further study, there is reason to believe the Earley framework has inherent advantages over strategies based only on bottom-up information (including so-called ``over-the-top'' parsers). Context-free forward probabilities include all available probabilistic information (subject to assumptions implicit in the SCFG formalism) available from an input prefix, whereas the usual inside probabilities do not take into account the nonterminal prior probabilities that result from the top-down relation to the start state. Using top-down constraints does not necessarily mean sacrificing robustness, as discussed in Section 5.4. On the contrary, by using Earley-style parsing with a set of carefully designed and estimated ``fault tolerant'' top-level productions, it should be possible to use probabilities to better advantage in robust parsing. This approach is a subject of ongoing work, in the context of tight-coupling SCFGs with speech decoders [Jurafsky et al. 1995].