On the Covering and Reduction Problems for Context-Free Grammars
James N. Gray, Michael A. Harrison · Journal of the ACM · 1972
A formal definition of one grammar "covering" another grammar is presented.It is argued that this definition has the property that G' covers G when and only when the ability to parse G' suffices for parsing G.It is shown that every grammar may be covered by a grammar in canonical two form.Every A-free grammar is covered by an operator normal form grammar while there exist grammars which cannot be covered by any grammar in Greibach form.Any grammar may be covered by an invertible grammar.Each A-free and chain reduced LR(k) (bounded right context) grammar is covered by a precedence detectable, LR(k) (bounded right context) reducible grammar.