Analysis of Two-Level Grammars

Making use of the fact that two-level grammars (tlgs) may be thought of as finite specification of context-free grammars (cfgs) with „infinite“ sets of productions, known techniques for parsing cfgs are applied to tlgs by first specifying a canonical cfg G' - called skeleton grammar - obtained from the „cross-reference“ of the tlg G. Under very natural restrictions it can be shown that for these grammar pairs (G, G') there exists a 1-1 correspondence between leftmost derivations in G and leftmost derivations in G'. With these results a straightforward parsing algorithm for restricted tlgs is given. In connection with the cross-reference, a detailed study of the sets of strict notions which a hypernotion yields is made. The class of languages - called hypernotion languages - has extremely poor closure properties. A number of interesting problems arise, some of which are shown to be undecidable, respectively open, respectively dicidable with unexpected high cost.