English and context -free languages

Includes bibliographical references (pages 41-43)This thesis represents an investigation of\ud generalized phrase structure grammar (GPSG) . The main\ud goal of this investigation was to empirically evaluate the\ud potential of the GPSG formalism in the creation of an\ud efficient, wide coverage parser. To this end, I have\ud created an experimental parser based on the concepts of\ud generalized phrase structure grammar. The target language\ud was English. Generalized phrase structure grammar is a description\ud formalism for the syntax of natural languages that is\ud still under active development, and rooted in theoretical\ud linguistics. A major attraction of this formalism for the\ud computer scientist is the promise of computational\ud tractability. The weak generative capacity of generalized\ud phrase structure grammars is the set of context-free\ud languages, for which efficient parsing algorithms are well\ud known. The approach I took was to construct a pre-processor\ud to convert generalized phrase structure grammar into\ud context-free phrase structure grammar (CF-PSG), and use\ud this as input to a context-free parser. This approach\ud produces a large number of context-free phrase structure\ud grammar rules. This means that the context-free parser,\ud while still of cubic time complexity, is in practice slow\ud and requires considerable memory space on the host system.\ud In order to make a faster and smaller parsing system the\ud conversion to CF-PSG must be avoided. The parser I developed did allow considerable\ud experimentation with generalized phrase structure grammar.\ud The formalism does seem capable of handling a wide variety\ud of constructs. However, problems with the formalism still\ud exist. "Exhaustive constant partial ordering", is shown\ud to be a weak claim. The handling of conjunctions seems\ud problematic. Solutions to these problems still await\ud developmen