LL(k)‐PARSING OF COUPLED‐CONTEXT‐FREE GRAMMARS
Gisela Pitsch · Computational Intelligence · 1994
Coupled‐context‐free grammars are a natural generalization of context‐free grammars obtained by combining nonterminals to corresponding parentheses which can only be substituted simultaneously. Refering to the generative capacity of the grammars we obtain an infinite hierarchy of languages that comprises the context‐free languages as the first and all the languages generated by TAGs as the second element. Here, we present a generalization of the context‐free LL(k)‐notion onto coupled‐context‐free grammars, which leads to a characterization of subclasses of coupled‐context‐free grammars–and in this way of TAGs as well–which can be parsed in linear time. The parsing procedure described works incrementally so that it can be used for on‐line parsing of natural language. Examples show that important elements of the tree‐adjoining languages can be generated by LL(k)‐coupled‐context‐free grammars.