An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities
<|reference_start|>An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities: We describe an extension of Earley's parser for stochastic context-free grammars that computes the following quantities given a stochastic context-free grammar and an input string: a) probabilities of successive prefixes being generated by the grammar; b) probabilities of substrings being generated by the nonterminals, including the entire string being generated by the grammar; c) most likely (Viterbi) parse of the string; d) posterior expected number of applications of each grammar production, as required for reestimating rule probabilities. (a) and (b) are computed incrementally in a single left-to-right pass over the input. Our algorithm compares favorably to standard bottom-up parsing methods for SCFGs in that it works efficiently on sparse grammars by making use of Earley's top-down control structure. It can process any context-free rule format without conversion to some normal form, and combines computations for (a) through (d) in a single algorithm. Finally, the algorithm has simple extensions for processing partially bracketed inputs, and for finding partial parses and their likelihoods on ungrammatical inputs.<|reference_end|>
@article{stolcke1994an,
    title={An Efficient Probabilistic Context-Free Parsing Algorithm that Computes
  Prefix Probabilities},
    author={Andreas Stolcke (SRI International, Menlo Park, CA 94025)},
    journal={arXiv preprint arXiv:cmp-lg/9411029},
    year={1994},
    number={ICSI TR-93-065 (Revised 11/94)},
    archivePrefix={arXiv},
    eprint={cmp-lg/9411029},
    primaryClass={cmp-lg cs.CL}
}