- Start
- Product
Analysis of Two-Level Grammars
Lutz Wegner(Author)
Verlag Günter Mainz
Published in 1978
Book
Paperback/Softback
128 pages
978-3-8107-2014-6 (ISBN)
Description
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.
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.
More details
Series
Language
German
Dimensions
Height: 14.8 cm
Width: 21 cm
Weight
180 gr
ISBN-13
978-3-8107-2014-6 (9783810720146)