On strict interpretations of grammar forms

Strict interpretations of grammar forms are studied with respect to parsing, ambiguity, and decidability for intersection and containment. In particular, a parsing procedure for an arbitrary strict interpretation grammar is given which is based on a given parsing method for the master grammar. Time and space bounds on the new procedure are then obtained. Each ambiguous interpretation grammar of an unambiguous grammar form can be converted to an equivalent unambiguous interpretation of the same grammar form. Unambiguity is always decidable for strict interpretation grammars of unambiguous grammar forms. Also, for languages obtained from compatible strict interpretations of an unambiguous grammar form, the following problems are solvable: empty intersection, finite intersection, containment, and equality.Portions of this paper were presented at (i) the 3rd ACM Symposium on Principles of Programming Languages, Jan. 1976, under the title, The Influence of Productions on Derivations and Parsing, and (ii) the 5th Symposium on Mathematical Foundations of Computer Science, Sept. 1976.This author was supported in part by a Guggenheim Fellowship and by NSF Grant No. 42306 and MCS 73-03380.This author was supported in part by NSF Grant No. MCS76-10076.