A Polynomial Parser for Contextual Grammars with Linear, Regular and Context-Free Selectors

Contextual Grammars were introduced by Solomon Marcus in 1969 as "intrinsic grammars" without auxiliary symbols, based only on the fundamental linguistic operation of inserting words into given phrases according to certain contextual dependencies. The formal properties of the formalism have been extensively studied. Furthermore, it can be shown that this formalism provides an appropriate description of natural languages. But unfortunately, up to now no parser which runs in polynomial time was known for some linguistically relevant classes of Contextual Grammar. In the following, an intertwined two--level Earley-- based parser is presented for Contextual Grammars with finite, regular or context--free selectors on the basis of the three derivation definitions in, Mg and M l, i.e. the unrestricted replacement of contexts according to a selector, only allowing the replacement of maximal selectors according to all selectors or according to the same selector. The individual two passes can b..