[Overview] [Previous] [Next]

Grammars for Exhaustive Parsing II

We have shown that exhaustive search parsing is a finite process, provided that there are no productions of the form Agoes toempty string or Agoes toB in the grammar. Chapter 6 of your textbook (which we will not cover in this course) describes methods for removing such productions from a grammar without altering the language recognized by the grammar. There is, however, one special case we need to consider.

If empty string belongs to the language, we need to keep the production Sgoes toempty string. This creates a problem if S occurs on the right hand side of some production, because then we have a way of decreasing the length of a sentential form. All we need to do in this case is to add a new start symbol, say S0, and to replace the production Sgoes toempty string with the pair of productions

S0goes toempty string
S0goes toS

Copyright 1996 by David Matuszek
Last modified Mar 2, 1996