next up previous
Next: Eliminating null productions Up: Null productions Previous: Prediction with null productions

Completion with null productions

Modification of the completion step follows a similar pattern. First, the unit-production relation has to be extended to allow for unit-production chains due to null productions. A rule tex2html_wrap_inline8563 can effectively act as a unit production that links X and tex2html_wrap_inline8525 if all other nonterminals on the RHS can expand to tex2html_wrap_inline7691 . Its contribution to the unit production relation tex2html_wrap_inline8571 will then be

displaymath8561

From the resulting revised tex2html_wrap_inline8573 matrix we compute the closure tex2html_wrap_inline7703 as usual.

The second modification is another instance of spontaneous dot shifting. When completing a state tex2html_wrap_inline8577 and moving the dot to get tex2html_wrap_inline8579 , additional states have to be added, obtained by moving the dot further over any nonterminals in tex2html_wrap_inline7759 that have non-zero tex2html_wrap_inline7691 -expansion probability. As in prediction, forward and inner probabilities are multiplied by the corresponding tex2html_wrap_inline7691 -expansion probabilities.



Andreas Stolcke
Sat Jun 29 21:49:02 PDT 1996