Structure preserving elimination of null productions from context-free grammars

AbstractA method is presented for the elimination of null productions from a context-free grammar in such a way that the resulting grammar covers the original one, that is, the languages generated are the same and parses in the original grammar are homomorphic images of equivalent parses in the covering grammar. We show that in a natural subclass of covers, called the class of compatible covers, the method is best possible in the sense that a compatible cover with no null productions can be produced by the method if and only if such a cover exists. The use of the method in transformations for obtaining a cover in Greibach normal form is finally analyzed