An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities
| dc.creator | Stolcke, Andreas | |
| dc.date | 1994-11-28 | |
| dc.date.accessioned | 2026-07-07T09:09:40Z | |
| dc.date.available | 2026-07-07T09:09:40Z | |
| dc.description | 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. | |
| dc.description | 45 pages. Slightly shortened version to appear in Computational Linguistics 21 | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9411029 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9411029 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151118 | |
| dc.subject | Computation and Language | |
| dc.title | An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities | |
| dc.type | text |