Premium
LL(k)‐PARSING OF COUPLED‐CONTEXT‐FREE GRAMMARS
Author(s) -
Pitsch Gisela
Publication year - 1994
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1994.tb00017.x
Subject(s) - indexed grammar , tree adjoining grammar , context free grammar , l attributed grammar , parsing , computer science , parsing expression grammar , rule based machine translation , embedded pushdown automaton , context sensitive grammar , programming language , natural language processing , phrase structure grammar , extended affix grammar , artificial intelligence , context free language
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.