Efficient Semiring-Weighted Earley Parsing

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 3687–3713 July 9-14, 2023 ©2023 Association for Computational Linguistics Efficient Semiring-Weighted Earley Parsing Andreas Opedal1,2 Ran Zmigrod3 Tim Vieira4 Ryan Cotterell1 Jason Eisner4 1ETH Zürich 2Max Planck ETH Center for Learning Systems 3University of Cambridge 4Johns Hopkins University andreas.opedal@inf.ethz.ch rz279@cam.ac.uk tim.f.vieira@gmail.com ryan.cotterell@inf.ethz.ch jason@cs.jhu.edu Abstract This paper provides a reference description, in the form of a deduction system, of Earley’s (1970) context-free parsing algorithm with various speed-ups. Our presentation includes a known worst-case runtime improvement from Earley’s O � N 3|G||R| � , which is unworkable for the large grammars that arise in natural language processing, to O � N 3|G| � , which matches the runtime of CKY on a binarized version of the grammar G. Here N is the length of the sentence, |R| is the number of productions in G, and |G| is the total length of those productions. We also provide a version that achieves runtime of O � N 3|M| � with |M| ≤ |G| when the grammar is represented compactly as a single finite-state automaton M (this is partly novel). We carefully treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate deduction cycles, and further generalize Stolcke’s method to compute the weights of sentence prefixes. We also provide implementation details for efficient execution, ensuring that on a preprocessed grammar, the semiring-weighted versions of our methods have the same asymptotic runtime and space requirements as the unweighted methods, including sub-cubic runtime on some grammars. https://github.com/rycolab/ earleys-algo 1 Introduction Earley (1970) was a landmark paper in computer science.1 Its algorithm was the first to directly parse under an unrestricted context-free grammar in time O � N3� , with N being the length of the input string. Furthermore, it is faster for certain grammars because it uses left context to filter its search at each position. It parses unambiguous grammars in O � N2� time and a class of “bounded- state” grammars, which includes all deterministic 1Based on the author’s dissertation (Earley, 1968). grammars, in O(N) time. Its artful combination of top-down (goal-driven) and bottom-up (data- driven) inference later inspired a general method for executing logic programs, “Earley deduction” (Pereira and Warren, 1983). Earley’s algorithm parses a sentence incremen- tally from left to right, optionally maintaining a packed parse forest over the sentence prefix that has been observed so far. This supports online sen- tence processing—incremental computation of syn- tactic features and semantic interpretations—and also reveals for each prefix the set of grammatical choices for the next word.2 It can be attractively extended to compute the probabilities of the possible next words (Jelinek and Lafferty, 1991; Stolcke, 1995). This is a standard way to compute autoregressive language model probabilities under a PCFG to support cogni- tive modeling (Hale, 2001) and speech recognition (Roark, 2001). Such probabilities could further be combined with those of a large autoregressive lan- guage model to form a product-of-experts model. Recent papers …

Content truncated to 500 words