Efficient Semiring-Weighted E arley Parsing (2023)

Abstract: We present Earley’s (1970) context-free parsing algorithm as a deduction system, incorporating various known and new speed-ups. In particular, our presentation supports a known worst-case runtime improvement from Earley’s (1970) 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 complexity 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| \leq |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 the possibility of 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.

## weighted context-free grammars a context-free grammar (cfg) g is a tuple ⟨n , σ, r, s⟩ where σ is a finite set of terminal symbols, n is a finite set of nonterminal symbols with σ ∩ @xmath0, r is a set of productions from a nonterminal to a sequence of terminals and nonterminals (i.e., r ⊆ n × (σ ∪ n ) * ), and @xmath1. we use lowercase variable names (a, b, . . . ) and uppercase ones (a, b, . . . ) for elements of σ and n , respectively. we use a greek letter (ρ, µ, or ν) to denote a sequence of terminals and nonterminals, i.e., an element of (σ ∪ n ) * . therefore, a production has the form @xmath2. note that ρ may be the empty sequence ε. we refer to |ρ| ≥ 0 as the arity of the production, |@xmath3, and |g| @xmath4. therefore, if k is the maximum arity of a production, |g| ≤ |r|(1 + k). productions of arity 0, 1, and 2 are referred to as nullary, unary, and binary productions respectively. for a given g, we write µ ⇒ ν to mean that µ ∈ (σ ∪ n ) * can be rewritten into ν ∈ (σ ∪ n ) * by a single production of g. for example, a b ⇒ ρ b expands a into ρ using the production @xmath5. the reflexive and transitive closure of this relation, * ⇒, then denotes rewriting by any sequence of zero or more productions: for example, a b * ⇒ ρ µ ν. we may additionally write a * ⇒ l ρ iff a * ⇒ ρ µ, and refer to ρ as a prefix of ρ µ. a derivation subtree of g is a finite rooted ordered tree t such that each node is labeled either with a terminal @xmath6, in which case it must be a leaf, or with a nonterminal @xmath7, in which case r must contain the production @xmath8. for any @xmath9, we write t a for the set of derivation subtrees whose roots have label a, and refer to the elements of t s as derivation trees. given a string @xmath10, we write t a x for the set of derivation subtrees with leaf sequence x. for an input sentence x, its set of derivation trees t x @xmath11 an ordinary unweighted recognizer is the special case where w is the boolean semiring, so a parser returns at least one derivation tree from t x iff t x ̸ = ∅. as an extension to the weighted recognition problem (2), one may wish to find the prefix weight of a string @xmath12, which is the total weight of all sentences @xmath13: ## parsing as deduction we will describe earley's algorithm using a deduction system, a formalism that is often employed in the presentation of parsing algorithms @xcite , as well as in mathematical logic and programming language theory @xcite . much is known about how to execute @xcite , transform @xcite , and neuralize @xcite ) deduction systems. a deduction system proves items v using deduction rules. items represent propositions; the rules are used to prove all propositions that are true. a deduction rule is of the form v where example is the name of the rule, the 0 or more items above the bar are called antecedents, and the single item below the bar is called a consequent. antecedents may also be written to the side of the bar; these are called side conditions and will be handled differently for weighted deduction in §6. axioms (listed separately) are merely rules that have no antecedents; as a shorthand, we omit the bar in this case and simply write the consequent. a proof tree is a finite rooted ordered tree whose nodes are labeled with items, and where every node is licensed by the existence of a deduction rule whose consequent v matches the label of the node and whose antecedents u 1 , u 2 , . . . match the labels of the node's children. it follows that the leaves are labeled with axioms. a proof of item v is a proof tree d v whose root is labeled with v : this shows how v can be deduced from its children, which can be deduced from their children, and so on until axioms are encountered at the leaves. we say v is provable if d v , which denotes the set of all its proofs, is nonempty. our unweighted recognizer determines whether a certain goal item is provable by a certain set of deduction rules from axioms that encode g and x. the deduction system is set up so that this is the case iff s * ⇒ x. the recognizer can employ a forward chaining method (see e.g. @xcite that iteratively deduces items by applying deduction rules whenever possible to antecedent items that have already been proved; this will eventually deduce all provable items. an unweighted parser extends the recognizer with some extra bookkeeping that lets it return one or more actual proofs of the goal item if it is provable. foot_5 ## earley's algorithm earley's algorithm can be presented as the specific deduction system earley shown in the input sentence x is encoded by axioms of the form [k -1, k, a] where @xmath14; this axiom is true iff x k-1:@xmath15. 7 the remaining items have the form [i, j, @xmath16, where 0 ≤ @xmath17, so that the span (i, j) refers to a substring x i:j the item [i, j, @xmath18:j . therefore, • indicates the progress we have made through the production. an item with nothing to the right of • , e.g., [i, j, @xmath19, is called complete. the set of all items with a shared right index j is called the item set of j, denoted t j . while µ * ⇒ x i:j is a necessary condition for [i, j, @xmath20, it is not sufficient. for efficiency, the earley deduction system is cleverly constructed so that this item is provable iff 8 it can appear in a proof of the goal item for some input string beginning with x 0:j , and thus possibly for x itself. 9 including [0, 0, s ′ → • s] as an axiom in the system effectively causes forward chaining to start looking for a derivation at position 0. forward chaining will prove the goal item [0, n, s ′ → s • ] iff s * ⇒ x. these two items conveniently pretend that the grammar has been augmented with a new start symbol s ′ / ∈ n that only rewrites according to the single production s ′ → s. the earley system employs three deduction rules: predict, scan, and complete. we refer the reader to app. b for a presentation and analysis of these rules, which reveals a total runtime of o n 3 |g||r| . app. c outlines how past work improved this runtime. in particular, @xcite presented an unweighted recognizer that is a variant of earley's, along with implementation details that enable it to run in time o n 3 |g| . however, those details were lost in retelling their algorithm as a deduction system @xcite . our improved deduction system in the next section does enable the o n 3 |g| runtime, with execution details of forward chaining spelled out in app. h. ## an improved deduction system our earleyfast deduction system, shown in the right column of we now describe our new deduction rules for comp and pred. (scan is unchanged.) we also analyze their runtime, using the same techniques as in app. b. ## semiring-weighted parsing we have so far presented earley's algorithm and our improved deduction system in the unweighted case. however, we are often interested in determining not just whether a parse exists, but the total weight of all parses as in equation ( 2 ), or the total weight of all parses consistent with a given prefix as in equation ( 3 ). we first observe that by design, the derivation trees of the cfg are in 1-1 correspondence with the proof trees of our deduction system that are rooted at the goal item. furthermore, the weight of a derivation subtree can be found as the weight of the corresponding proof tree, if the weight w(d v ) of any proof tree d v is defined recursively as follows. base case: d v may be a single node, i.e., v is an axiom. if v has the form @xmath23, then w(d v ) is the weight of the corresponding grammar production, i.e., w(@xmath24. all other axiomatic proof trees of earley and earleyfast have weight 1 . 10 recursive case: if the root node of however, the factors in this product include only the antecedents written above the bar, not the side conditions (see §3). following @xcite , we may also associate a weight with each item v , denoted β(v ), which is the total weight of all its proofs d @xmath25. by the distributive property, we can obtain that weight as an ⊕-sum over all one-step proofs of v from antecedents. specifically, each deduction rule that deduces v contributes an ⊕-summand, given 10 however, this will not be true in earleyfsa ( §7 below). there the grammar is given by a wfsa, and each axiom corresponding to an arc or final state of this grammar will inherit its weight from that arc or final state. similarly, if we generalize to lattice parsing-where the input is given by an acyclic wfsa and each proof tree corresponds to a parse of some weighted path from this so-called lattice-then an axiom providing a terminal token should use the weight of the corresponding lattice edge. then the weight of the proof tree will include the total weight of the lattice path along with the weight of the cfg productions used in the parse. by the product β(u 1 ) ⊗ β(u 2 ) ⊗ • • • of the weights of its antecedent items (other than side conditions). now our weighted recognizer can obtain z x (the total weight of all derivations of x) as β of the goal item (the total weight of all proofs of that item). for an item v of the form [i, j, @xmath26, the weight β(v ) will consider derivations of nonterminals in µ but not those in ν. we therefore refer to β(v ) as an incomplete inside weight. however, ν will come into play in the extension of §6.1. the deduction systems work for any semiringweighted cfg. unfortunately, the forwardchaining algorithm for weighted deduction @xcite , fig. 3 ) may not terminate if the system permits cyclic proofs, where an item can participate in one of its own proofs. in this case, the algorithm will merely approach the correct value of z x as it discovers deeper and deeper proofs of the goal item. cyclicity in our system can arise from sets of unary productions such as we take the approach of eliminating problematic unary and nullary productions from the weighted grammar without changing z x for any x. we provide methods to do this in app. e and app. f respectively. it is important to eliminate nullary productions before eliminating unary cycles, since nullary removal may create new unary productions. the elimination of some productions can increase |g|, but we explain how to limit this effect. ## earley's algorithm using an fsa in this section, we present a generalization of earleyfast that can parse with any weighted finite-state automaton (wfsa) grammar m in o n 3 |m| . here m is a wfsa @xcite that encodes the cfg productions as follows. for any ρ ∈ (σ∪n ) * and any @xmath27, for m to accept the string ρ a with weight @xmath28. the grammar size |m| is the number of wfsa arcs. see fig. 2 for an example. this presentation has three advantages over a cfg. first, m can be compiled from an extended cfg @xcite ), which allows user-friendly specifications like @xmath29. second, productions with similar right-hand-sides can be partially merged to achieve a smaller grammar and a faster runtime. they may share partial paths in m, which means that a single item can efficiently represent many dotted productions. third, when ⊗ is non-commutative, only the wfsa grammar formalism allows elimination of nullary rules in all cases (see app. f). our wfsa grammar is similar to a recursive transition network or rtn grammar @xcite . adapting earley's algorithm to rtns was discussed by @xcite , @xcite , and @xcite . @xcite used a weighted version for ptb parsing. none of them spelled out a deduction system, however. also, an rtn is a collection of productions of the form @xmath30, where for m a to accept ρ corresponds to having @xmath31. thus an rtn uses one fsa per nonterminal. our innovation is to use one wfsa for the entire grammar, specifying the left-hand-side nonterminal as a final symbol. thus, to allow productions @xmath32, our single wfsa can have paths µ ν a and µ ν ′ b that share the µ prefix-as in fig. 2 . this allows our earleyfsa to match the µ prefix only once, in a way that could eventually result in completing either an a or a b (or both). 13 a traditional weighted cfg g can be easily encoded as an acyclic wfsa m with |m| = |g|, by creating a weighted path of length k and weight w 14 for each cfg production of size k and weight w, terminating in a final state, and then merging the initial states of these paths into a single state that becomes the initial state of the resulting wfsa. the paths are otherwise disjoint. importantly, this wfsa can then be determinized and minimized 13 @xcite also shares prefixes between a and b; but there, once paths split to yield separate items, they cannot remerge to share a suffix. we can merge by deriving [j, k, q?] in multiple ways. our [j, k, q?] does not specify its set of target left-hand sides; filter recomputes that set dynamically. 14 for example, the production @xmath33. the production's weight may arbitrarily be placed on the first arc of the path, the other arcs having weight 1 (see app. a). in general, however, the grammar can be specified by any wfsa m-not necessarily deterministic. this could be compiled from weighted regular expressions, or be an encoded markov model trained on observed productions @xcite , or be obtained by merging states of another wfsa grammar @xcite in order to smooth its weights and speed it up. the wfsa has states q and weighted arcs (or edges) e, over an alphabet a consisting of σ ∪ n together with hatted nonterminals like a. its initial and final states are denoted by i ⊆ q and f ⊆ q, respectively. 15 we denote an arc of the wfsa by (q a ⇝ q ′ ) ∈ e where q, q ′ ∈ q and @xmath34. this corresponds to an axiom with the same weight as the edge. @xmath35. the item @xmath36; the item's weight is the total weight of all such ε-paths, where a path's weight includes its final-state weight. for a state @xmath37, the precomputed side condition q a ⇝ ⋆ is true iff there exad-15 note that if the wfsa is obtained as described above, it will only have one initial state. the earleyfsa deduction system is given in one important practical advantage of this scheme for natural language parsing is that it prevents a large-vocabulary slowdown. 16 in earley, applying predict to (say) [3, 4, @xmath38, 4, @xmath39. but earleyfsa in the corresponding situation will predict only [4, 4, q] where q is the initial state, without yet predicting the next word. if the next input word is [4, 5, happy], then earleyfsa follows just the happy arcs from q, yielding items of the form [4, 5, q ′ ?] (which will then be filtered away since happy is not a noun). note that scan, comp1 and comp2 are ternary, rather than binary as in earleyfast. for further speed-ups we can apply the fold transform on these rules in a similar manner as before, resulting in binary deduction rules. we present this binarized version in app. i. as before, we must eliminate unary and nullary rules before parsing; app. j explains how to do this with a wfsa grammar. in addition, although as noted above, we can speed up earleyfsa by reducing the size of the wfsa. unfortunately, minimization of general fsas is np-hard. however, we can at least seek the minimal deterministic wfsa m ′ such that |m ′ | ≤ |m|, at least in most semirings @xcite . the determinization @xcite and minimization @xcite algorithms for the boolean semiring are particularly well-known. minimization merges states, which results in merging items, much as when earleyfast merged items that had different predot symbols @xcite @xcite . another advantage of the wfsa presentation of earley's is that it makes it simple to express a tighter bound on the runtime. much of the grammar size |g| or |m| is due to terminal symbols that are not used at most positions of the input. suppose the input is an ordinary sentence (one word at each position, unlike the lattice case in footnote 7), and suppose c is a constant such that no state q has more than c outgoing arcs labeled with the same terminal @xmath40. then when scan tries to extend ## practical runtime of earley's we empirically measure the runtimes of earley, earleyfast, and earleyfsa. we use the tropical semiring to find the highest-weighted derivation trees. we use two grammars that were ex-tracted from the ptb: markov-order-2 (m2) and parent-annotated markov-order-2 (pm2). 17 for each grammar, we ran our parsers (using the tropical semiring; pin, 1998) on 100 randomly selected sentences of 5 to 40 words from the ptb test-set (mean 21.4, stdev 10.7), although we omitted sentences of @xmath41. the full results are displayed in app. l. the graph shows that earleyfast is roughly 20× faster at all sentence lengths. we obtain a further speed-up of 2.5× by switching to earleyfsa. ## conclusion in this reference work, we have shown how the runtime of earley's algorithm is reduced to o n 3 |g| from the naive o n 3 |g||r| . we presented this dynamic programming algorithm as a deduction system, which splits prediction and completion into two steps each, in order to share work among related items. to further share work, we generalized earley's algorithm to work with a grammar specified by a weighted fsa. we demonstrated that these speed-ups are effective in practice. we also provided details for efficient implementation of our deduction system. we showed how to generalize these methods to semiring-weighted grammars by correctly transforming the grammars to eliminate cyclic derivations. we further provided a method to compute the total weight of all sentences with a given prefix under a semiring-weighted cfg. we intend this work to serve as a clean reference for those who wish to efficiently implement an earley-style parser or develop related incremental parsing methods. for example, our deduction systems could be used as the starting point for