LATE Ain'T Earley: A Faster Parallel Earley Parser
We present the LATE algorithm, an asynchronous variant of the Earley algorithm for parsing context-free grammars. The Earley algorithm is naturally task-based, but is difficult to parallelize because of dependencies between the tasks. We present the LATE algorithm, which uses additional data structures to maintain information about the state of the parse so that work items may be processed in any order. This property allows the LATE algorithm to be sped up using task parallelism. We show that the LATE algorithm can achieve a 120x speedup over the Earley algorithm on a natural language task.
Code (1)
Similar Papers 제목 키워드 기반
Generalized Earley Parser: Bridging Symbolic Grammars and Sequence Data for Future Prediction
Future predictions on sequence data (e.g., videos or audios) require the algorithms to capture non-Markovian and compositional properties of high-level semantics. Context-free grammars are natural choices to capture such…
Activity PredictionFuture predictionMarpa and nullable symbols
The Marpa parser was intended to make the best results in the academic literature on Earley's algorithm available as a practical general parser. Earley-based parsers have had issues handling nullable symbols. Initially, …
Exploring a Probabilistic Earley Parser for Event Composition in Biomedical Texts
Marpa, A practical general parser: the recognizer
The Marpa recognizer is described. Marpa is a practical and fully implemented algorithm for the recognition, parsing and evaluation of context-free grammars. The Marpa recognizer is the first to unite the improvements to…
Efficient Weighted Deduction Systems for Earley’s Algorithm
The parsing algorithm of Earley (1970), as presented, has a runtime complexity of $\mathcal{O}(N^3\lvert\mathcal{G}\rvert \lvert\mathcal{R}\rvert)$ where $N$ is the length of the sentence, $\lvert\mathcal{G}\rvert $ is t…
Sentence