Table:
Earley chart as constructed during the parse of aaa with the grammar
in (a).
The two columns to the right in (b) list the forward and inner probabilities,
respectively, for each state.
In both and columns, the separates old
factors from new ones (as per equations 1,
2 and 3).
Addition indicates multiple derivations of the same state.
Consider the grammar
where q = 1 - p. This highly ambiguous grammar generates strings of any number of a's, using all possible binary parse trees over the given number of terminals. The states involved in parsing the string aaa are listed in Table 2, along with their forward and inner probabilities. The example illustrates how the parser deals with left-recursion and the merging of alternative sub-parses during completion.
Since the grammar has only a single nonterminal, the left-corner matrix has rank 1:
Its transitive closure is
Consequently, the example trace shows the factor being introduced into the forward probability terms in the prediction steps.
The sample string can be parsed as either (a (aa)) or ((a a) a), each parse having a probability of . The total string probability is thus , the computed and values for the final state. The values for the scanned states in sets 1, 2 and 3 are the prefix probabilities for a, aa, and aaa, respectively: , , .