Emergent Parsing and Generation with Generalized Chart

Emergent Parsing and Generation with Generalized HASIDA KSiti Electrotechnical Laboratory 1-1-4 Umezono, Tukuba, Ibaraki 305, J~,pan E-mail: hasida@etl.go.jp Chart Abstract A new, flexible inference method for Horn logic pro- gram is proposed. It is also a drastic gencndization of chart I)aming, partial instaatiation of clauses in a pro- gram ronghly corresponding to arcs in a chart. Chart- like i)al~ing and semantic-head-driven generation emerge from this method. With a parsimonious instantiation scheme for ambiguity packing, the parsing eoml)lexity reduces to that of standard chart-based algorithms. 1 Introduction Language use involves very complex interactions anmng very divm.'se types of information, not only syntactic one but also semantic, pragmatic, and so forth. It is hence inappropriate to assmne any specific algorithm for syntactic parsing or generation, which prescril)es particular processing directions (such as left-to-right, top-down anti bottom-uI) ) and is I)iascd fl)r specific types of domain knowledge (such ,'~s a eontext-fl'ee grammar). To accmmt for the whole language use, we will lmve to put many such algorithms together, ending up with an intractably complicated model. A better strategy is to i)ostulate no specific algo- rithms for parsing or generation or any particular t~k, but instead a single uniform computational method from which emerge various types of computation in- eluding parsing and generation dei)ending ui)on vari- ous computational contexts. For example, Earley deductiml (Pereir:t & Warren, 1983) is a general procedure for dealing with Horn clauses which gives rise to Earlcy-like parsing when given a context-free grammar and a word string as the inlmt. Shieber (1988) has generalized this method so as to adapt to sentence generation as well. Those nmthods fail to give rise to cllicieut conq)utation for a wide variety of contexts, however, because they pre- scribe processing directions such ,~ left-to-right f(Jr parsing and bottom-up for generation. They also hu:k a general way of efficient anfl)iguity l)acking unlimited to context-free grammars. Hasida (1994a) i)rol)oses a more general inference method for clausal form logic l)rograms wtfich accounts for efficient parsing and gen- eration ~m emergent l)hmmmena. This mctho(l pre- scribes no fixed processing directions, and the way it packs ambiguity is not specific to context-free gnun- mare. However, it is rather complicated an(l has greater computational complexity than standard algorithms do. In this i)ai)er we propose another inference method for tlorn logic programs based on Iiasida (1994a), and show that efficient parsing and generation mnerge from it. Like that of Ilasida (1994a), this metlmd is to- tally eonstraint-1):med in the sense that it prcsupl)oSCS no taxed directions of information llow, but it is more ellicicnt owing to a p:trsimonious nmthod of instanti- ation. In Section 2 we deline this inference method, which is a generalization of chart parsing, and may be also thought of :m a connection method or a sort of l)rogram transformation. Section 3 illustrates how etfi- cient parsing and gencratiml emerge from this method witlmut any procedural stipulation specific to the t:mk and the domain knowledge (syntactic constraints). Sec- tion ,1 introduces a parsimmfious instantiation nmthod for ambiguity packing. …

Content truncated to 500 words