The remainder of the article proceeds as follows. Section 3 briefly reviews the workings of an Earley parser without regard to probabilities. Section 4 describes how the parser needs to be extended to compute sentence and prefix probabilities. Section 5 deals with further modifications for solving the Viterbi and training tasks, for processing partially bracketed inputs, and for finding partial parses. Section 6 discusses miscellaneous issues and relates our work to the literature on the subject. In Section 7 we summarize and draw some conclusions.
To get an overall idea of probabilistic Earley parsing it should be sufficient to read Sections 3, 4.2 and 4.4. Section 4.5 deals with a crucial technicality, and later sections mostly fill in details and add optional features.
We assume the reader is familiar with the basics of context-free grammar theory, such as given in [chapter 2]Aho:72. Some prior familiarity with probabilistic context-free grammars will also be helpful. Jelinek:92 provide a tutorial introduction covering the standard algorithms for the four tasks mentioned in the introduction.