---
title: "An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix — Stolcke 1995"
description: "Stolcke proposes a probabilistic extension of the top-down Earley parser that solves all four problems within a… 34 references, cited by 70 papers here."
authors: ["Andreas Stolcke"]
year: 1995
source: "https://aclanthology.org/J95-2002/"
arxiv: "cmp-lg/9411029"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/stolcke-1995-efficient-probabilistic-context-free-parsing/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/stolcke-1995-efficient-probabilistic-context-free-parsing/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1995](https://md.research.elamur.ai/free/en/papers/1995/) / An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities

# An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities

**Authors:** [Andreas Stolcke](https://md.research.elamur.ai/free/en/authors/andreas-stolcke/) · **Year:** 1995 · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J95-2002/) · [PDF](https://aclanthology.org/J95-2002.pdf) · [arXiv cmp-lg/9411029](https://arxiv.org/abs/cmp-lg/9411029)

**Citations:** [70](https://md.research.elamur.ai/free/en/papers/stolcke-1995-efficient-probabilistic-context-free-parsing/cited-by/) in our library, of the 140,884 papers whose bibliographies we read

## Summary
The paper deals with stochastic context-free grammars (SCFG) and four classical problems associated with them: the probability of a string, the most probable parse, the probability of a prefix, and the training of rule probabilities. Previously these problems were solved by separate algorithms, mostly bottom-up ones based on CYK. Stolcke proposes a probabilistic extension of the top-down Earley parser that solves all four problems within a single algorithm. Prefix and substring probabilities are built up step by step during one pass that moves from left to right, so the estimate for a prefix is available as soon as its last word has been read. Viterbi parsing and rule re-estimation require one more, backward, pass over the chart. The algorithm accepts rules of any form without conversion to CNF. On sparse grammars it is more efficient, because top-down prediction immediately prunes impossible branches. The main practical significance of the work is that incremental prefix probabilities make it possible to predict the next word. As a result, SCFGs can be used as language models in place of finite-state ones, for example in speech recognition decoders.

## Key points
- The algorithm computes four quantities: (a) probabilities of successive prefixes, (b) inside probabilities of substrings, including the whole sentence, (c) the Viterbi parse, (d) the expected number of uses of each rule, needed for EM training.
- Quantities (a) and (b) are computed in a single left-to-right pass. Quantities (c) and (d) require an additional backward pass over the Earley chart.
- The conditional probability of the next word is obtained by dividing the probability of the longer prefix by the probability of the shorter one. It can be used in Viterbi and stack decoders, as well as for deriving n-gram probabilities from an SCFG (Stolcke and Segal, 1994).
- In the worst case, the complexity is no worse than that of known specialized algorithms, and on certain classes of grammars it is considerably better. Chomsky Normal Form (CNF) is not required.
- There are extensions for partially bracketed input and for finding partial parses with their probabilities for ungrammatical sentences. The paper appeared in Computational Linguistics (ACL, 1995) and derives from the ICSI technical report TR-93-065.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Computing & GPUs](https://md.research.elamur.ai/free/en/shelves/computing/)

## Cite

Cite as: Andreas Stolcke. 1995. An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{stolcke1995efficient,
  title = {{An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities}},
  author = {Andreas Stolcke},
  year = {1995},
  eprint = {cmp-lg/9411029},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cmp-lg/9411029}
}
```

- [← previous Utilizing Statistical Dialogue Act Processing in Verbmobil](https://md.research.elamur.ai/free/en/papers/reithinger-1995-utilizing-statistical-dialogue-act-processing/)
- [next → Learning Morpho-Lexical Probabilities from an Untagged Corpus with an Application to Hebrew](https://md.research.elamur.ai/free/en/papers/levinger-1995-learning-morpho-lexical-probabilities-untagged/)
- [↑ back to papers of 1995](https://md.research.elamur.ai/free/en/papers/1995/)

## References

34 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Aho, Alfred V., and Ullman, Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing. Prentice-Hall. [find](https://scholar.google.com/scholar?q=Aho%2C+Alfred+V%2E%2C+and+Ullman%2C+Jeffrey+D%2E+%281972%29%2E+The+Theory+of+Parsing%2C+Translation%2C+and+Compiling%2C+Volume+1%3A+Parsing%2E+Prentice%2DHall%2E)
2. Bahl, Lalit R.; Jelinek, Frederick; and Mercer, Robert L. (1983). "A maximum likelihood approach to continuous speech recognition." IEEE Transactions on Pattern Analysis and Machine Intelligence, 5(2), 179-190. [find](https://scholar.google.com/scholar?q=Bahl%2C+Lalit+R%2E%3B+Jelinek%2C+Frederick%3B+and+Mercer%2C+Robert+L%2E+%281983%29%2E+%22A+maximum+likelihood+approach+to+continuous+speech+recognition%2E%22+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C+5%282%29)
3. Baker, James K. (1979). "Trainable grammars for speech recognition." In Speech Communication Papers for the 97th Meeting of the Acoustical Society of America, edited by Jared J. Wolf and Dennis H. Klatt, 547-550. [find](https://scholar.google.com/scholar?q=Baker%2C+James+K%2E+%281979%29%2E+%22Trainable+grammars+for+speech+recognition%2E%22+In+Speech+Communication+Papers+for+the+97th+Meeting+of+the+Acoustical+Society+of+America%2C+edited+by+Jared+J%2E+Wolf+and+Dennis+H%2E+Kla)
4. Baum, Leonard E.; Petrie, Ted; Soules, George; and Weiss, Norman (1970). "A maximization technique occuring in the statistical analysis of probabilistic functions in Markov chains." The Annals of Mathematical Statistics, 41(1), 164-171. [find](https://scholar.google.com/scholar?q=Baum%2C+Leonard+E%2E%3B+Petrie%2C+Ted%3B+Soules%2C+George%3B+and+Weiss%2C+Norman+%281970%29%2E+%22A+maximization+technique+occuring+in+the+statistical+analysis+of+probabilistic+functions+in+Markov+chains%2E%22+The+Annals+of+Math)
5. Booth, Taylor L., and Thompson, Richard A. (1973). "Applying probability measures to abstract languages." IEEE Transactions on Computers, C-22(5), 442-450. [find](https://scholar.google.com/scholar?q=Booth%2C+Taylor+L%2E%2C+and+Thompson%2C+Richard+A%2E+%281973%29%2E+%22Applying+probability+measures+to+abstract+languages%2E%22+IEEE+Transactions+on+Computers%2C+C%2D22%285%29%2C+442%2D450%2E)
6. Briscoe, Ted, and Carroll, John (1993). "Generalized probabilistic LR parsing of natural language (corpora) with unification-based grammars." Computational Linguistics, 19(1), 25-59. [find](https://scholar.google.com/scholar?q=Briscoe%2C+Ted%2C+and+Carroll%2C+John+%281993%29%2E+%22Generalized+probabilistic+LR+parsing+of+natural+language+%28corpora%29+with+unification%2Dbased+grammars%2E%22+Computational+Linguistics%2C+19%281%29%2C+25%2D59%2E)
7. Casacuberta, E, and Vidal, E. (1988). "A parsing algorithm for weighted grammars and substring recognition." In Syntactic and Structural Pattern Recognition, Volume F45, NATO ASI Series, edited by Gabriel Ferrat6, Theo Pavlidis, Alberto Sanfeliu, and Horst Bunke, 51-67. Springer Verlag. [find](https://scholar.google.com/scholar?q=Casacuberta%2C+E%2C+and+Vidal%2C+E%2E+%281988%29%2E+%22A+parsing+algorithm+for+weighted+grammars+and+substring+recognition%2E%22+In+Syntactic+and+Structural+Pattern+Recognition%2C+Volume+F45%2C+NATO+ASI+Series%2C+edited+by+Gab)
8. Corazza, Anna; De Mori, Renato; Gretter, Roberto; and Satta, Giorgio (1991). "Computation of probabilities for an island-driven parser." IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(9), 936-950. [find](https://scholar.google.com/scholar?q=Corazza%2C+Anna%3B+De+Mori%2C+Renato%3B+Gretter%2C+Roberto%3B+and+Satta%2C+Giorgio+%281991%29%2E+%22Computation+of+probabilities+for+an+island%2Ddriven+parser%2E%22+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C)
9. Dempster, A. P.; Laird, N. M.; and Rubin, D. B. (1977). "Maximum likelihood from incomplete data via the EM algorithm." Journal of the Royal Statistical Society, Series B, 34, 1-38. [find](https://scholar.google.com/scholar?q=Dempster%2C+A%2E+P%2E%3B+Laird%2C+N%2E+M%2E%3B+and+Rubin%2C+D%2E+B%2E+%281977%29%2E+%22Maximum+likelihood+from+incomplete+data+via+the+EM+algorithm%2E%22+Journal+of+the+Royal+Statistical+Society%2C+Series+B%2C+34%2C+1%2D38%2E)
10. Earley, Jay (1970). "An efficient context-free parsing algorithm." Communications of the ACM, 6(8), 451-455. [find](https://scholar.google.com/scholar?q=Earley%2C+Jay+%281970%29%2E+%22An+efficient+context%2Dfree+parsing+algorithm%2E%22+Communications+of+the+ACM%2C+6%288%29%2C+451%2D455%2E)
11. Fujisaki, T.; Jelinek, F.; Cocke, J.; Black, E.; and Nishino, T. (1991). "A probabilistic parsing method for sentence disambiguation." In Current Issues in Parsing Technology, edited by Masaru Tomita, 139-152. Kluwer Academic Publishers. [find](https://scholar.google.com/scholar?q=Fujisaki%2C+T%2E%3B+Jelinek%2C+F%2E%3B+Cocke%2C+J%2E%3B+Black%2C+E%2E%3B+and+Nishino%2C+T%2E+%281991%29%2E+%22A+probabilistic+parsing+method+for+sentence+disambiguation%2E%22+In+Current+Issues+in+Parsing+Technology%2C+edited+by+Masaru+Tomita%2C)
12. Graham, Susan L.; Harrison, Michael A.; and Ruzzo, Walter L. (1980). "An improved context-free recognizer." ACM Transactions on Programming Languages and Systems, 2(3), 415-462. [find](https://scholar.google.com/scholar?q=Graham%2C+Susan+L%2E%3B+Harrison%2C+Michael+A%2E%3B+and+Ruzzo%2C+Walter+L%2E+%281980%29%2E+%22An+improved+context%2Dfree+recognizer%2E%22+ACM+Transactions+on+Programming+Languages+and+Systems%2C+2%283%29%2C+415%2D462%2E)
13. Jelinek, Frederick (1985). "Markov source modeling of text generation." In The Impact of Processing Techniques on Communications, Volume E91, NATO ASI Series, edited by J. K. Skwirzynski, 569-598. Nijhoff. [find](https://scholar.google.com/scholar?q=Jelinek%2C+Frederick+%281985%29%2E+%22Markov+source+modeling+of+text+generation%2E%22+In+The+Impact+of+Processing+Techniques+on+Communications%2C+Volume+E91%2C+NATO+ASI+Series%2C+edited+by+J%2E+K%2E+Skwirzynski%2C+569%2D598%2E+Nij)
14. Jelinek, Frederick, and Lafferty, John D. (1991). "Computation of the probability of initial substring generation by stochastic context-free grammars." Computational Linguistics, 17(3), 315-323. [our card](https://md.research.elamur.ai/free/en/papers/jelinek-1991-computation-probability-initial-substring-generation/)
15. Jelinek, Frederick; Lafferty, John D.; and Mercer, Robert L. (1992). "Basic methods of probabilistic context free grammars." In Speech Recognition and Understanding. Recent Advances, Trends, and Applications, Volume F75, NATO ASI Series, edited by Pietro Laface and Renato De Mori, 345-360. Springer… [find](https://scholar.google.com/scholar?q=Jelinek%2C+Frederick%3B+Lafferty%2C+John+D%2E%3B+and+Mercer%2C+Robert+L%2E+%281992%29%2E+%22Basic+methods+of+probabilistic+context+free+grammars%2E%22+In+Speech+Recognition+and+Understanding%2E+Recent+Advances%2C+Trends%2C+and+Appli)
16. Jones, Mark A., and Eisner, Jason M. (1992). "A probabilistic parser and its applications." In AAAI Workshop on Statistically~Based NLP Techniques, 20-27. [find](https://scholar.google.com/scholar?q=Jones%2C+Mark+A%2E%2C+and+Eisner%2C+Jason+M%2E+%281992%29%2E+%22A+probabilistic+parser+and+its+applications%2E%22+In+AAAI+Workshop+on+Statistically%7EBased+NLP+Techniques%2C+20%2D27%2E)
17. Jurafsky, Daniel; Wooters, Chuck; Segal, Jonathan; Stolcke, Andreas; Fosler, Eric; Tajchman, Gary; and Morgan, Nelson (1995). "Using a stochastic context-free grammar as a language model for speech recognition." In Proceedings, IEEE Conference on Acoustics, Speech and Signal Processing, 189-192. Det… [find](https://scholar.google.com/scholar?q=Jurafsky%2C+Daniel%3B+Wooters%2C+Chuck%3B+Segal%2C+Jonathan%3B+Stolcke%2C+Andreas%3B+Fosler%2C+Eric%3B+Tajchman%2C+Gary%3B+and+Morgan%2C+Nelson+%281995%29%2E+%22Using+a+stochastic+context%2Dfree+grammar+as+a+language+model+for+speech+re)
18. Jurafsky, Daniel; Wooters, Chuck; Tajchman, Gary; Segal, Jonathan; Stolcke, Andreas; Fosler, Eric; and Morgan, Nelson (1994). "The Berkeley restaurant project." In Proceedings, International Conference on Spoken Language Processing, 4, 2139-2142. Yokohama, Japan. [find](https://scholar.google.com/scholar?q=Jurafsky%2C+Daniel%3B+Wooters%2C+Chuck%3B+Tajchman%2C+Gary%3B+Segal%2C+Jonathan%3B+Stolcke%2C+Andreas%3B+Fosler%2C+Eric%3B+and+Morgan%2C+Nelson+%281994%29%2E+%22The+Berkeley+restaurant+project%2E%22+In+Proceedings%2C+International+Conferenc)
19. Kupiec, Julian (1992). "Hidden Markov estimation for unrestricted stochastic context-free grammars." In Proceedings, IEEE Conference on Acoustics, Speech and Signal Processing, 1, 177-180, San Francisco, California. [find](https://scholar.google.com/scholar?q=Kupiec%2C+Julian+%281992%29%2E+%22Hidden+Markov+estimation+for+unrestricted+stochastic+context%2Dfree+grammars%2E%22+In+Proceedings%2C+IEEE+Conference+on+Acoustics%2C+Speech+and+Signal+Processing%2C+1%2C+177%2D180%2C+San+Francis)
20. Lari, K., and Young, S. J. (1990). "The estimation of stochastic context-free grammars using the Inside-Outside algorithm." Computer Speech and Language, 4, 35-56. [find](https://scholar.google.com/scholar?q=Lari%2C+K%2E%2C+and+Young%2C+S%2E+J%2E+%281990%29%2E+%22The+estimation+of+stochastic+context%2Dfree+grammars+using+the+Inside%2DOutside+algorithm%2E%22+Computer+Speech+and+Language%2C+4%2C+35%2D56%2E)
21. Lari, K., and Young, S. J. (1991). "Applications of stochastic context-free grammars using the Inside-Outside algorithm." Computer Speech and Language, 5, 237-257. [find](https://scholar.google.com/scholar?q=Lari%2C+K%2E%2C+and+Young%2C+S%2E+J%2E+%281991%29%2E+%22Applications+of+stochastic+context%2Dfree+grammars+using+the+Inside%2DOutside+algorithm%2E%22+Computer+Speech+and+Language%2C+5%2C+237%2D257%2E)
22. Magerman, David M., and Marcus, Mitchell P. (1991). "Pearl: A probabilistic chart parser." In Proceedings, Second International Workshop on Parsing Technologies. Cancun, Mexico, 193-199. [find](https://scholar.google.com/scholar?q=Magerman%2C+David+M%2E%2C+and+Marcus%2C+Mitchell+P%2E+%281991%29%2E+%22Pearl%3A+A+probabilistic+chart+parser%2E%22+In+Proceedings%2C+Second+International+Workshop+on+Parsing+Technologies%2E+Cancun%2C+Mexico%2C+193%2D199%2E)
23. Magerman, David M., and Weir, Carl (1992). "Efficiency, robustness and accuracy in Picky chart parsing." In Proceedings, 30th Annual Meeting of the Association for Computational Linguistics. Newark, Delaware, 40-47. [find](https://scholar.google.com/scholar?q=Magerman%2C+David+M%2E%2C+and+Weir%2C+Carl+%281992%29%2E+%22Efficiency%2C+robustness+and+accuracy+in+Picky+chart+parsing%2E%22+In+Proceedings%2C+30th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2E+Newark%2C+D)
24. Nakagawa, Sei-ichi (1987). "Spoken sentence recognition by time-synchronous parsing algorithm of context-free grammar." In Proceedings, IEEE Conference on Acoustics, Speech and Signal Processing, 2, 829-832. Dallas, Texas. [find](https://scholar.google.com/scholar?q=Nakagawa%2C+Sei%2Dichi+%281987%29%2E+%22Spoken+sentence+recognition+by+time%2Dsynchronous+parsing+algorithm+of+context%2Dfree+grammar%2E%22+In+Proceedings%2C+IEEE+Conference+on+Acoustics%2C+Speech+and+Signal+Processing%2C+2%2C+8)
25. Ney, Hermann (1992). "Stochastic grammars and pattern recognition." In Speech Recognition and Understanding. Recent Advances, Trends, and Applications, volume F75 of NATO ASI Series, edited by Pietro Laface and Renato De Mori, 319-344. Springer Verlag. [find](https://scholar.google.com/scholar?q=Ney%2C+Hermann+%281992%29%2E+%22Stochastic+grammars+and+pattern+recognition%2E%22+In+Speech+Recognition+and+Understanding%2E+Recent+Advances%2C+Trends%2C+and+Applications%2C+volume+F75+of+NATO+ASI+Series%2C+edited+by+Pietro+)
26. P~iseler, Annedore (1988). "Modification of Earley's algorithm for speech recognition/' In Recent Advances in Speech Understanding and Dialog Systems, volume F46 of NATO ASI Series, edited by H. Niemann, M. Lang, and G. Sagerer, 466-472. Springer Verlag. [find](https://scholar.google.com/scholar?q=P%7Eiseler%2C+Annedore+%281988%29%2E+%22Modification+of+Earley%27s+algorithm+for+speech+recognition%2F%27+In+Recent+Advances+in+Speech+Understanding+and+Dialog+Systems%2C+volume+F46+of+NATO+ASI+Series%2C+edited+by+H%2E+Niema)
27. Pereira, Fernando C. N., and Schabes, Yves (1992). "Inside-outside reestimation from partially bracketed corpora." In Proceedings, 30th Annual Meeting of the Association for Computational Linguistics. Newark, Delaware, 128-135. [our card](https://md.research.elamur.ai/free/en/papers/pereira-1992-inside-outside-reestimation-partially-bracketed/)
28. Pereira, Fernando C. N., and Shieber, Stuart M. (1987). Prolog and Natural-Language Analysis. CLSI Lecture Notes Series, Number 10. Center for the Study of Language and Information, Stanford, California. [find](https://scholar.google.com/scholar?q=Pereira%2C+Fernando+C%2E+N%2E%2C+and+Shieber%2C+Stuart+M%2E+%281987%29%2E+Prolog+and+Natural%2DLanguage+Analysis%2E+CLSI+Lecture+Notes+Series%2C+Number+10%2E+Center+for+the+Study+of+Language+and+Information%2C+Stanford%2C+Californ)
29. Rabiner, L. R., and Juang, B. H. (1986). "An introduction to hidden Markov models." IEEE ASSP Magazine, 3(1), 4-16. [find](https://scholar.google.com/scholar?q=Rabiner%2C+L%2E+R%2E%2C+and+Juang%2C+B%2E+H%2E+%281986%29%2E+%22An+introduction+to+hidden+Markov+models%2E%22+IEEE+ASSP+Magazine%2C+3%281%29%2C+4%2D16%2E)
30. Schabes, Yves (1991). "An inside-outside algorithm for estimating the parameters of a hidden stochastic context-free grammar based on Earley's algorithm." Paper presented at the Second Workshop on Mathematics of Language, Tarrytown, New York. [find](https://scholar.google.com/scholar?q=Schabes%2C+Yves+%281991%29%2E+%22An+inside%2Doutside+algorithm+for+estimating+the+parameters+of+a+hidden+stochastic+context%2Dfree+grammar+based+on+Earley%27s+algorithm%2E%22+Paper+presented+at+the+Second+Workshop+on+Mat)
31. Stolcke, Andreas, and Segal, Jonathan (1994). "Precise n-gram probabilities from stochastic context-free grammars." In Proceedings, 3 lth Annual Meeting of the Association for Computational Linguistics. Las Cruces, New Mexico, 74-79. [find](https://scholar.google.com/scholar?q=Stolcke%2C+Andreas%2C+and+Segal%2C+Jonathan+%281994%29%2E+%22Precise+n%2Dgram+probabilities+from+stochastic+context%2Dfree+grammars%2E%22+In+Proceedings%2C+3+lth+Annual+Meeting+of+the+Association+for+Computational+Linguistic)
32. Stolcke, Andreas (1993). "An efficient probabilistic context-free parsing algorithm that computes prefix probabilities." Technical Report TR-93-065, International Computer Science Institute, Berkeley, CA. [find](https://scholar.google.com/scholar?q=Stolcke%2C+Andreas+%281993%29%2E+%22An+efficient+probabilistic+context%2Dfree+parsing+algorithm+that+computes+prefix+probabilities%2E%22+Technical+Report+TR%2D93%2D065%2C+International+Computer+Science+Institute%2C+Berkeley%2C)
33. Tomita, Masaru (1986). Efficient Parsing for Natural Language. Kluwer Academic Publishers. [find](https://scholar.google.com/scholar?q=Tomita%2C+Masaru+%281986%29%2E+Efficient+Parsing+for+Natural+Language%2E+Kluwer+Academic+Publishers%2E)
34. Wright, J. H. (1990). "LR parsing of probabilistic grammars with input uncertainty for speech recognition." Computer Speech and Language, 4, 297-323. [find](https://scholar.google.com/scholar?q=Wright%2C+J%2E+H%2E+%281990%29%2E+%22LR+parsing+of+probabilistic+grammars+with+input+uncertainty+for+speech+recognition%2E%22+Computer+Speech+and+Language%2C+4%2C+297%2D323%2E)