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

Abstract

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.

45 pages. Slightly shortened version to appear in Computational Linguistics 21

References in corpus (1)

• Precise n-gram Probabilities from Stochastic Context-free Grammars

Cited by in corpus (14)

• Parameter Learning of Logic Programs for Symbolic-Statistical Modeling
• Training a Multilingual Sportscaster: Using Perceptual Context to Learn Language
• Unsupervised Language Acquisition: Theory and Practice
• Precise n-gram Probabilities from Stochastic Context-free Grammars
• Robust Probabilistic Predictive Syntactic Processing
• Neural Language Models as Psycholinguistic Subjects: Representations of Syntactic State
• Superregular grammars do not provide additional explanatory power but allow for a compact analysis of animal song
• Framework and Resources for Natural Language Parser Evaluation
• Infinite probability computation by cyclic explanation graphs
• Statistical Machine Translation by Generalized Parsing
• Utilisation de la linguistique en reconnaissance de la parole : un état de l'art
• Factor Graph Grammars
• Sequence-to-Sequence Learning with Latent Neural Grammars
• Parsing and Generation with Tabulation and Compilation