Both the definition of Viterbi parse, and its computation are straightforward generalizations of the corresponding notion for Hidden Markov Models [Rabiner and Juang1986], where one computes the Viterbi path (state sequence) through an HMM. Precisely the same approach can be used in the Earley parser, using the fact that each derivation corresponds to a path.
The standard computational technique for Viterbi parses is applicable here. Wherever the original parsing procedure sums probabilities that correspond to alternative derivations of a grammatical entity, the summation is replaced by a maximization. Thus, during the forward pass each state must keep track of the maximal path probability leading to it, as well as the predecessor states associated with that maximum probability path. Once the final state is reached, the maximum probability parse can be recovered by tracing back the path of ``best'' predecessor states.
The following modifications to the probabilistic Earley parser implement the forward phase of the Viterbi computation.
Once the final state is reached, a recursive procedure can recover the parse tree associated with the Viterbi parse. This procedure takes an Earley state as input and produces the Viterbi parse for the substring between k and i as output. (If the input state is not complete ( ), the result will be a partial parse tree with children missing from the root node.)
Viterbi-parse( ):
Adjoin a leaf node labeled a as the right-most child to the root of T and return T.
as well as
Adjoin T' to T as the right-most child at the root, and return T.