tailieunhanh - Báo cáo khoa học: "The Acquisition and Application of Context Sensitive Grammar for English"

A system is described for acquiring a contextsensitive, phrase structure g r a m m a r which is applied by a best-path, bottom-up, deterministic parser. The grammar 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 conceptually tractable approach to the construction of phrase structure g r a m m a r for news story text. 1 A context-free g r a m m a r production is characterized as a rewrite rule where a non-terminal element as a leftside. | The Acquisition and Application of Context Sensitive Grammar for English Robert F. Simmons and Yeong-Ho Yu @cs. Department of Computer Sciences Al Lab University of Texas Austin Tx 78712 Abstract A system is described for acquiring a contextsensitive phrase structure grammar which is applied by a best-path bottom-up deterministic parser. The grammar 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 conceptually tractable approach to the construction of phrase structure grammar for news story 1 Introduction Although many papers report natural language processing systems based in part on syntactic analysis their authors typically do not emphasize the complexity of the parsing and grammar acquisition processes that were involved. 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 complicated programs with complexity at best of O n3 where n is the number of words in a sentence. The grammars they usually use are technically augmented context free where the simplicity of the context-free form is augmented by feature tests transformations and occar-sionally arbitrary programs. The combination of even an efficient parser with such intricate grammars may greatly increase the computational complexity of the system 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 including context-free and context-sensitive ones. For natural language a grammar distinguishes terminal single element constituents such as parts of speech from .