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| \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 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.

这篇论文通过退化系统的形式提供了 Earley (1970) 上下文无关解析算法的参考描述，其中包括了多种加速的方法。我们的展示包括从 Earley 的 $O (N^3|G||R|)$ 到 $O (N^3|G|)$ 的已知最坏情况运行时间改进，这在自然语言处理中出现的大型语法中是不可行的，它与语法 G 的二元化版本上的 CKY 算法的运行时间相匹配。在这里，N 是句子长度，|R | 是 G 中的产生式数目，|G | 是这些产生式的总长度。我们还提供了一个版本，在将语法简洁地表示为单个有限状态自动机 M 时实现了 O (N^3|M|) 的运行时间（这部分是新颖的）。我们细致地处理了到半环权重退化的概括，像 Stolcke (1995) 那样预处理语法以消除退化循环，并进一步推广 Stolcke 的方法以计算句子前缀的权重。我们还提供了高效执行的实现细节，在预处理语法上，我们方法的半环权重版本具有与无权重方法相同的渐近运行时间和空间要求，包括在某些语法上在次立方时间内的运行时间。