As in prediction, the completion step in the Earley algorithm may imply
an infinite summation, and could lead to an infinite loop if computed naively.
However, only unit productions
can give rise to cyclic completions.
The problem is best explained by studying an example. Consider the grammar
where q = 1 - p. Presented with the input a (the only string the grammar generates), after one cycle of prediction, the Earley chart contains the following states.
The 
factors are a result of the left-corner sum
.
After scanning 
,
completion without truncation would enter an infinite loop.
First 
is completed, yielding a complete state
, which allows 
to be completed,
leading to another complete state for S, etc.
The non-probabilistic Earley parser can just stop here, but as in prediction,
this would lead to truncated probabilities.
The sum of probabilities that needs to be computed to arrive at the
correct result contains infinitely many terms, one for each
possible loop through the 
production.
Each such loop adds a factor of q to the forward and inner probabilities.
The summations for all completed states turn out as
The approach taken here to compute exact probabilities in cyclic completions is mostly analogous to that for left-recursive predictions. The main difference is that unit productions, rather than left-corners, form the underlying transitive relation. Before proceeding we can convince ourselves that this is indeed the only case we have to worry about.
We now formally define the relation between nonterminals mediated by unit productions, analogous to the left-corner relation.
As before, a matrix inversion can compute the relation 
in
closed form:
The existence of is shown in Appendix A.
The modified completion loop in the probabilistic Earley parser can now use
the matrix to collapse all unit completions into a single step.
Note that we still have to do iterative completion on non-unit productions.