An efficient context-free parsing algorithm

By Jay Earley. 1970

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

Citations in the corpus

Recurrent Neural Network Grammars (2016, methodology): “Furthermore, standard parsing evaluation scores do not depend on preterminal prediction accuracy. operation and later COMPLETEs them after consuming terminal symbols one at a time using SCAN (Earley, 1970).”
Joint Video and Text Parsing for Understanding Events and Answering Queries (2013, methodology): “The Earley parsing algorithm [54], [58] is used to parse the dependencies using the attribute grammar, which employs topdown dynamic programming to search for a valid set of production rules that generate the dependencies.”
Automatically Solving Number Word Problems by Semantic Parsing and Reasoning (2015, methodology): “1, following the Earley algorithm (Earley, 1970).”
Adversarial Generation of Natural Language (2017, methodology): “We do this by generating 1,280 samples from noise and computing the fraction of those that are valid under our grammar using the Earley parsing algorithm (Earley, 1970).”
Category-theoretic quantitative compositional distributional models of natural language semantics (2013, background): “CYK [15, 50, 89], Earley [25]), and a large number of corpora and other resources have been created to assist the learning of such generative grammars (e.”
Interpreting multimodal referring expressions in real time (2016, methodology): “We also plan to extend our language model so that it supports models of compositional semantics by embedding a parsing chart into the state [11, 7].”
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, methodology): “As examples, the weighted version of Earley’s (1970) algorithm (Stolcke, 1995) handles arbitrary WCFGs (not restricted to CNF).”
Distinguishing effects of structure and decay on attachment and repair: A cue-based parsing account of recovery from misanalyzed ambiguities (2003, background): “…interpretation and the length of the NP (i.e., the duration of the processorÕs commitment to the incorrect interpretation) affect the probability of preserving the incorrect interpretation. as dynamic programming parsers that store and reuse parses of well-formed substrings (e.g., Earley, 1970).”
The Gap of Semantic Parsing: A Survey on Automatic Math Word Problem Solvers (2018, methodology): “algorithm is based on context-free grammar (CFG) [52], [53],”
Survey of the State of the Art in Human Language Technology (2010, methodology): “3 Such tabular algorithms are widely used in parsing and language modeling with appropriate kinds of grammars (Younger, 1967; Kay, 1986; Earley, 1970; Lang, 1974; Graham, Harrison, et al., 1980; Tomita, 1987), because they support exhaustive search algorithms with polynomial space and time with resp”
Speech and language processing: an introduction to natural language processing, computational linguistics, and speech recognition, 2nd Edition (2000, unknown): “However, it is most common to use a different kind of context for the dimensions of a word’s vector representation.”
A Probabilistic Earley Parser as a Psycholinguistic Model (2001, background): “The computation of prefix probabilities takes advantage of the design of the Earley parser (Earley, 1970) which by itself is not probabilistic.”
LL(*): the foundation of the ANTLR parser generator (2011, methodology): “LL(*) is an optimization of packrat parsing just as GLR is an optimization of Earley’s algorithm [5].”
Unsupervised learning of event AND-OR grammar and semantics from video (2011, methodology): “We use an online parsing algorithm (details are referred to a companion paper [7]) similar to Earleys parser [1, 11] to generate parse graphs based on the input data.”
Syntax Augmented Machine Translation via Chart Parsing (2006, methodology): “Each cell of the parsing process in (J.Earley, 1970) contains a set of hypergraph nodes (Huang and Chiang, 2005).”