On parsing two-level grammars |
| |
Authors: | Lutz Michael Wegner |
| |
Affiliation: | (1) Institut für Angewandte Informatik und Formale Beschreibungsverfahren der Universität Karlsruhe, Postfach 6380, 7500 Karlsruhe 1, Germany (Fed. Rep.) |
| |
Abstract: | Summary 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|