The Acquisition and Application of Context Sensitive Grammar for English

The Acquisition and Application of Context Sensitive Grammar for English Robert F. Simmons and Yeong-Ho Yu @cs.texas.edu Abstract Department of Computer Sciences, AI Lab University of Texas, Austin Tx 78712 A system is described for acquiring a context- sensitive, phrase structure grammar which is applied by a best-path, bottom-up, deterministic parser. The gram- mar was based on English news stories and a high degree of success in parsing is reported. Overall, this research concludes that CSG is a computationally and concep- tually tractable approach to the construction of phrase structure grammar for news story text. 1 1 Introduction Although many papers report natural language process- ing systems based in part on syntactic analysis, their au- thors typically do not emphasize the complexity of the parsing and grammar acquisition processes that were in- volved. The casual reader might suppose that parsing is a well understood, minor aspect in such research. In fact, parsers for natural language are generally very compli- cated programs with complexity at best of O(n 3) where n is the number of words in a sentence. The gram- mars they usually use are technically, "augmented con- text free" where the simplicity of the context-free form is augmented by feature tests, transformations, and occa- sionally arbitrary programs. The combination of even an efficient parser with such intricate grammars may greatly increase the computational complexity of the sys- tem [Tomita 1985]. It is extremely difficult to write such grammars and they must frequently be revised to maintain internal consistency when applied to new texts. In this paper we present an alternative approach using context-sensitive grammar to enable preference parsing and rapid acquisition of CSG from example parsings of newspaper stories. Chomsky[1957] defined a hierarchy of grammars in- cluding context-free and context-sensitive ones. For nat- ural language a grammar distinguishes terminal, single element constituents such as parts of speech from non- terminals which are phrase-names such as NP, VP, AD- VPH, or SNT 2 signifying multiple constituents. 1 This work was partially supported by the Army Research Office under contract DAAG29-84-K-0060. ~NounPhrase, VerbPhrase, AdverbialPhrase, Sentence A context-free grammar production is characterized as a rewrite rule where a non-terminal element as a left- side is rewritten as multiple symbols on the right. Snt -* NP + VP Such rules may be augmented by constraints to limit their application to relevant contexts. Snt --* NP + VP / anim(np), agree(nbr(np),nbr(vp)) To the right of the slash mark, the constraints are applied by an interpretive program and even arbitrary code may be included; in this case the interpreter would recognize that the NP must be animate and there must be agree- ment in number between the NP and the VP. Since this is such a flexible and expressive approach, its many vari- ations have found much use in application to natural lan- guage applications and there is a broad literature on Aug- mented Phrase Structure Grammar [Gazdar et. al. 1985], Unification Grammars of various types [Shieber 1986], and Augmented Transition Networks [Allen, J. 1987, …

Content truncated to 500 words